Научный семинар «Математические методы анализа решений в экономике, бизнесе и политике»

20 апреля 2011 года в НИУ ВШЭ-Пермь состоялась трансляция очередного заседания общемосковского научного семинара «Математические методы анализа решений в экономике, бизнесе и политике». С докладом «Экстремальные значения допусков в некоторых задачах комбинаторной оптимизации» выступил Борис Гольденгорин (Университет Гронингена, Нидерланды).

Аннотация:

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

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

Пользуясь минимальными значениями допусков, мы формулируем необходимые и достаточные условия единственности (решение единственно тогда и только тогда, когда минимальный его допуск строго положителен) и неединственности (решение неединственно тогда и только тогда, когда минимальный его допуск равен нулю) множества оптимальных решений, а максимальные значения допусков дают оценки сверху для наилучших границ в методе ветвей и границ относительно заданной релаксации исходной задачи. Приведенный нами критерий единственности оптимального решения легко проверяется в процессе вычисления оптимального решения. Более того, допуски являются инвариантами относительно множества оптимальных решений в том смысле, что их значения не зависят от выбранного оптимального решения.

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