ММ экономических систем, методология исследований. Многокритериальные задачи, преодоление неопределенности целей, страница 10

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

Алгоритм решения целочисленных задач.

1.  Включаем в список исходную задачу, устанавливаем первоначальное значение рекорда – ∞.

2.  Выбираем одну из задач текущего списка в качестве ЗК.

3.  Заменяем ЗК ее релаксацией ЗКР. Релаксацией целочисленной задачи будет  является она сама без условия  целочисленности, т. е. задача линейного программирования.

4.  Находим решение ЗКР и переходим к его анализу с использованием критериев.

5.  Если ЗКР не имеет допустимого решения (критерий 1), переходим к шагу 10, где исключаем критерий из списка.

6.  Если максимум целевой функции ЗКР не больше рекорда (критерий 2), переходим к шагу 10, где исключаем ЗК из списка.

7.  Если оптимальное значение ЗКР целочисленно (критерий 3), оно является допустимым для ЗК. Переходим к шагу 9. Если решения ЗКР целочисленны, переходим к шагу 8.

8.  Разветвляем ЗК, заменяем ее в списке задачами-потомками и переходим к шагу 2.

9.  Запоминаем решение ЗК, полученное в результате решения ЗКР, в качестве нового решения-претендента, заменяем рекорд и переходим к шагу 10, где исключаем из списка эту ЗК и все ЗК, для которых верхняя граница не больше нового рекорда.

10.  По результатам зондирования ЗК удаляется из текущего списка.

11.  Проверяем, пуст ли список задач. Если список пуст, то вычисления окончены. Если при этом рекорд равен – ∞, то основная задача не имеет допустимого решения. Если рекорд конечен, то имеющееся решение-претендент и данный рекорд являются оптимальным решением основной задачи.

Лекция  № 9

Игровые задачи исследования операций

Цель работы – исследование игровых моделей операций и рационального поведения в конфликтных ситуациях.

Теоретические сведения

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

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

Формальное математическое описание игры состоит в следующем:

,                                        (9.1)

где  – множество конфликтующих (конкурирующих сторон);  – совокупности стратегий сторон;  – выигрыши сторон.

Математическую модель игры (9.1) удобно представлять в виде таблицы – матрицы игры (m×n). Часто между ПА(u) и ПВ(u) устанавливается соотношение, например ПА(u)= –ПВ(u) = a_ij(антагонистическая игра – выигрыш одного означает проигрыш другого). Если же в качестве a_ij рассматривается какая-либо комбинация ПА(u_ij), ПВ(u_ij) – среднее, сумма и т. д., то  тем  самым предусматривается возможность объединения усилий сторон, ведение переговоров, соглашение и т. д.

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