Введение к работе
Актуальность теш». Проблематика, связанная с исследованием трудоемкости и точности градиентных алгоритмов решения екстремальних комбинаторных задач, является актуальной ввиду невозможности построения точных и в то же время эффективных алгоритмов решения таких задач. В ряде работ (см., например, [1-4]) показано, что класс задач дискретной оптимизации, у которых градиентный (локальный) экстремум совпадает с глобальным, не слитком велик. По существу все эффективные алгоритмы для широких классов задач дискретной оптимизации являются приблихенными. Поэтому поиск оценок точности алгоритмов градиентного типа, как наиболее эффективных, остается актуальным.
В то же время одним из перспективных подходов к решению дискретных оптимизационных задач является так называемый статистический подход, позволяющий получать оценки сложности задач и эффективности алгоритмов в типичном случае ("почти всегда"). Многие задачи, являясь задачами большой размерности (в частности -задачи на графах), диктуют необходимость построения приближенных статистически. эффективных алгоритмов для их решения. Большая размерность этих задач исключает возмокнооть разработки точных методов, которые гарантировали бы нахоадение искомого решения за реальное время. Таким образом,актуальной является проблема создания быстрых (малотрудоемких) алгоритмов, которые применительно к выделенным классам дискретных задач оптимизации оказываются эффективными в типичном случае как по точности, так и по трудоемкости.
Проблема выбора наиболее рациональных решений в реальных-задачах автоматизированного проектирования, планирования, экономики я других важных областей неизбежно приводит к необходимости учета многих противоречивых требований. В результате адекватные математические постановки задач оказываются многокритериальными задачами (МКЗ) оптимизации. Особенность таких задач состоит в оценке качества решений по многим критериям. В этих условиях выбор наиболее целесообразного решения осуществляется из множества яесравнимых альтернатив. При этом необходимо учитывать такие ректоры, как неточность построения математических моделей реальных процессов, погрешность вычисления на ЭВМ, появление .лго-ритмов, состоящих из решения последовательности "близких" задач. Зсе это требует исследования устойчивости к таким возмущениям іараметров ШСЗ, которые сохраняют искомое множество яльторнптип.
Подобные исследования проводятся, например, в ВЦ РАН, ИК АН Украины, Запорожском государственном университете.
Связь работы с крупньши научными програшами, темами. Работі выполнена в соответствии с темой "Изучение проблем дискретной ма тематики и математической кибернетики" N 451/28, включенной к І99І-І995 г.г. в план НИР, выполняемой на кафедре УМФ механико математического факультета Белгосуниверситета.
Цель и задачи работы. Целью диссертационной работы являете разработка аффективных методов решения задач оптимизации на дис кратных структурах и нахождение условий, при выполнении которы многокритериальная (векторная) траєкторная задача является устой чивой к возмущениям некоторых ее параметров. Для достижения ука занной цели в диссертации были поставлены следующие задачи:
получить оценки близости глобального и градиентного экстрему мов в задачах максимизации строго выпуклых функций дискретног аргумента на основе использования параметров допустимой области границ изменения элементов матрицы, представлящей собой дискрет ный аналог гессиана функции.
построить и обосновать статистически эффективные алгоритмы ре шбния задач оптимального размещения медиан и центров в графе орграфе.
разработать методику оценки эффективности градиентных алгориї мов решения указанных задач в типичном случае.
исследовать разрешимость МКЗ о k-медиане графа в классе алге ритмов линейной свертки критериев.
изучить поведение множеств сильно, слабо и собственно эффекта! них траекторий МКЗ при малых возмущениях коэффициентов целеві функций, составляющих векторный критерий.
найти радиус и ядро устойчивости траєкторних МКЗ.
Научная новизна. Найдены более точные (по сравнению с ран« известными) оценки качества градиентных экстремумов в задачі максимизации строго выпуклых функций на координатных решетка: Построен и обоснован ряд статистически аффективных алгоритмі решения задач размещения медиан и центров нв взвешенном графо, доквзаиы теоремы об асимптотической оптимальности и оптимальное в типичном случае получаемых решений. Доказана неразрешимое векторной задачи о k-медиане графа в классе алгоритмов лтогайн* свертки критериев. RnepBuo исследована устойчивость мнохесті сильно аффективных и множества слабо аффективных траекторий п
малых возмущениях целевых функций в многокритериальной траекторией задаче с частными критериями вида minsum, ЫШШС и MTNMIN. Выделено ядро устойчивости такой задачи, и найдены нижние достижимые оценки для радиуса устойчивости и радиуса ядра устойчивости.
Практическая значимость. Результаты диссертации могут быть применены там, где требуется решать задачи размещения центров на сетях. Подобные задачи взнккают при размещении станций скорой медицинской помощи, постов пожарной охраны, торговых центров, фабрик, складов и т.д. Идеи доказательства статистической эффективности разработашшх алгоритмов могут быть применены в дальнейших исследованиях при построении и обосновании новых методов дискретной опл—лизации. В этом ке направлении могут быть использованы полученные в диссертации оценки точности градиентных алгоритмов решения задач максимизации строго выпуклых функций на дискретных струтурах. Возможности для приложения результатов диссертации, касающихся устойчивости МКЗ, обуславливаются тем, что на практике параметры задач, как правило, заданы с некоторой степенью точности. Естественно возникав вопрос,насколько велика может быть указанная погрешность при условии,что она не повлияет на искомое множество альтернатив МКЗ. Поэтому любая задача, возникающая на практике, не монет быть корректно поставлена и решена без хотя бы неявного использования результатов теории устойчивости.
Экономическая значимость. В настоящее время оценить экономическую значимость результатов диссертации не представляется возможным.
Основные поло: ?ния диссертации, выносимые на защиту. В настоящей диссертационной работе получены и выносятся на защиту следующие результаты :
-
На основе информации о мере строгой выпуклости целевой функции найдены более точные по сравнении с ранее известными оценки близости глобального и градиентного экстремумов в задачах максимизации строго выпуклых функций на координатных решетках.
-
Построен и обоснован ряд статистически эффективных алгоритмов решения задач оптимального размещения медиан и центров в графе и орграфе.Доказана асимптотическая оптимальность и оптимальность в типичном случае найденных решений.При этом результаты, полученные для однокритеривлышх задач, обобщены на случай многих критериев вида uinsum, нішах и юшш в произвольной комбинации.
-
Доказана неразрешимость МКЗ о к-медийне графа в классе
алгоритмов линейной свертки критериев.
-
Исследовано поведение множеств сильно, слабо и собственно эффективных траекторий МКЗ при малых возмущениях целевых функций в векторной траекторной задаче с критериями вида mihsum, ЫШМАХ и Ы1ШШ. Найдены необходимые и достаточные условия, при выполнении которых малые изменения коэффициентов целевых функций, составляющих векторный критерий, не приводят к появлению новых аффективных траекторий.
-
Выделено ядро устойчивости векторной траекторной задачи. Получены нижние достижиые оценки для радара устойчивости и радиуса ядра устойчивости.
Публикации! апробация работы, личный вклад. По теме диссертационной работы опубликовано 11 печатных работ. Основные результаты диссертации докладывались на VI конференции математиков Беларуси (Гродно, 1992), на мевдународном семинаре "Discrete Optimization" (Веймар, 1994), на Пятом Межгосударственном семинаре "Дискретная математика и ее приложения" (Москва, 1995), на Conference of the European Chapter on Combinatorial Optimization (Познань 1995), на научных семинарах в ИТК АН Беларуси, Белорусском государственном университете.
Все основные результаты, приведенные в выносимой на защиту диссергационной работе, получены автором лично. Часть результатов получена в соавторстве, что отмечено в тексте работы.
Структура и объем работы. Диссертация состоит из введения, трех гл"в и списка использованных источников, включающего 98 наименований. Общий объем работы 80 страниц машинописного текста.