Cостоялось внеочередное заседание общемосковского научного семинара "МАТЕМАТИЧЕСКИЕ МЕТОДЫ АНАЛИЗА РЕШЕНИЙ В ЭКОНОМИКЕ, БИЗНЕСЕ И ПОЛИТИКЕ"

Борис Гольденгорин (Нижегородский Филиал ВШЭ, Россия, Университет Гронингена, Нидерланды)

Аннотация доклада:

 

После нахождения оптимального решения Задачи Комбинаторной Оптимизации (ЗКО) следующим естественным шагом является анализ его чувствительности, часто называемым пост-оптимальным анализом post-optimality analysis) или что будет если анализом (what-if analysis) . Целью анализа чувствительности заданного оптимального решения ЗКО является выяснение зависимости этого решения от изменения исходных данных ЗКО.

Экстремальные значения верхних и нижних допусков являются основой переборных алгоритмов решения различных классов ЗКО. В докторской диссертации Ягера (Gerold Jager, 2010) приведен достаточные условия равенства максимальных значений верхних и нижних допусков для широко используемого класса задач комбинаторной оптимизации с аддитивной целевой функцией и множеством невложенных друг в друга допустимых решений.

Среди таких задач укажем на задачи о максимальном (минимальном) взвешенном независимом множестве (МВНМ), взвешенной раскраске графа, задачи составления оптимального расписания на одной машине для n работ одинаковой длительности с разными моментами их появления и с разными весами приоритетности на одной машине, а также классическими задачами о минимальном (максимальном) взвешенном остовном дереве (1-дереве) и ее труднорешаемых вариаций, например, с дополнительными ограничениями на степени вершин (напомним, что 1-деревья со всеми степенями вершин равными 2 являются гамильтоновскими циклами), на количество листьев в остовном дереве, на максимальную длину простого пути и т.д. К этому же классу задач относится классическая задача о максимальном (минимальном) взвешенном паросочетании и ее частный случай задача о покрытии графа непересекающимися циклами минимального (максимального) суммарного веса, известная калинейная задача о назначении, а также многие ее вариации и обобщения. Пользуясь минимальными значениями допусков, мы формулируем необходимые и достаточные условия единственности (решение единственно тогда и только тогда, когда минимальный его допуск строго положителен) и неединственности (решение неединственно тогда и только тогда, когда минимальный его допуск равен нулю) множества оптимальных решений, а максимальные значения допусков дают оценки сверху для наилучших границ в методе ветвей и границ относительно заданной релаксации исходной задачи. Отметим, что в недавно опубликованной монографии (R.Burkard et al. Assignment Problems.

SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA, USA, 2009) вопрос об упомянутой единственности остался открытым даже для линейной задачи о назначении. Приведенный нами критерий единственности оптимального решения легко проверяется в процессе вычисления оптимального решения. Более того, допуски являются инвариантами относительно множества оптимальных решений в том смысле, что их значения не зависят от выбранного оптимального решения.

В этом докладе мы приводим необходимые и достаточные условия равенства минимальных и максимальных значений верхних и нижних допусков для широко используемого класса задач комбинаторной оптимизации с аддитивной целевой функцией и множеством невложенных друг в друга допустимых решений. В заключении мы мотивируем полезность обобщения допусков на многие элементы оптимального решения и намечаем пути создания их исчисления.

 

FUAD_Seminar.ppt

Рабочий язык: русский 

------------------------------------------------------------------------------------------------------------------------- 

Руководители семинара: д.т.н., проф. Алескеров Фуад Тагиевич, д.т.н., проф. Подиновский Владислав Владимирович. 
Соруководитель семинара - д.т.н., проф. Миркин Борис Григорьевич,

-------------------------------------------------------------------------------------------------------------------------