• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
ФКН
Контакты

109028, Москва,
Покровский бульвар, дом 11, каб. Т-614
(проезд: м. Тургеневская/Чистые пруды, Китай-город, Курская/Чкаловская)
тел: (495) 628-83-68

почта: fes@hse.ru 

Руководство
Первый заместитель декана Мерзляков Сергей Анатольевич
Заместитель декана по учебной работе Покатович Елена Викторовна
Заместитель декана по научной работе Веселов Дмитрий Александрович
Заместитель декана по международной деятельности Засимова Людмила Сергеевна
Заместитель декана по работе со студентами Бурмистрова Елена Борисовна
Мероприятия
1 апреля – 6 апреля
проводится онлайн 
2 апреля, 18:00
2 апреля, 18:00
проводится онлайн 
11 апреля, 20:00
проводится онлайн 

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

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

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

 

После нахождения оптимального решения Задачи Комбинаторной Оптимизации (ЗКО) следующим естественным шагом является анализ его чувствительности, часто называемым пост-оптимальным анализом 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

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

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

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

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