Математика \ Теория игр и исследование операций

Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 14

Z1,1 = Z1 È {x1 £ 2} Z1,2=Z1 È {x1 ³ 3}

(2,2), fоптлп=14 <R             (3,3/2), fоптлп=13,5 <R

=> улучшения или повторения рекорда не может быть.


В России всякая полезная деятельность вредна.        

Сергей Юрский

2. Принятие решений и элементы теории игр.

2.1. Задачи многокритериальной оптимизации.

Пусть xÎX, и f1(x),…,fn(x)- различные критерии.

Пример. При проектировании самолета (x) возникают критерии: надежность f1, скорость f2, стоимость f3, комфортабельность f4, и т.п. Какой проект выбрать?

Принципы принятия решения:

Выбор главного критерия

Свертка критериев

Принцип Парето

®extr

все критерии желательно максимизировать

 " i¹i0

(вводим ограничения на другие критерии)

Для оценки весовых коэффициентов ai привлекают экспертов, но конкретную величину назвать невозможно

"i fi(x)>fi(y) &

$ i0: fi0(x)>fi0(y)

Û xy

т.е. x лучше y (предпочтительнее).

№10. Построение свертки критериев. Пусть эксперт указал, что х "лучше" y, причем zxy={fi(x)-fi(y)} -известные вектора, а в качестве вектора a={ai} возьмем точку выпуклой оболочки множества Z, ближайшую к началу координат. Если aÎG (некоторой грани оболочки), то a^G. Задача не имеет решения, если a=0.

Пример. Есть 4 факультета, оцененные по двум показателям f1 и f2, и по мнению эксперта Х1Х2, X1X3, X3X2. На какое место поместить Х4?

Факультеты

Критерии

Свертка критериев F(X)=a1 f1(X)+a2 f2(X)

Место

f1

f2

Х1

X2

X3

X4

25

30

10

45

25

20

30

15

F(X1)=3*25+7*25=250

F(X2)=3*30+7*20=230

F(X3)=3*10+7*30=240

F(X4)=3*45+7*15=240

1

4

2-3

2-3

Решение:

Построим свертку критериев ;

X1X2Þz12=(f1(Х1)-f1(Х2), f2(Х1)-f2(Х2))=(-5,5),

X1X3Þz13=(f1(Х1)-f1(Х3), f2(Х1)-f2(Х3))=(15,-5),

X3X2Þz32=(f1(Х3)-f1(Х2), f2(Х3)-f2(Х2))(-20,10).

Ближайшая к началу координат точка выпуклой оболочки множества Z лежит на отрезке [z32 z13]. Þ a ^ (z32-z13)=(-35,15) Þ a=(15,35) или (3,7)

Значения свертки критериев см. в таблице.

Ответ: По свертке критериев факультет Х4 делит 2-3 место.

Связь задачи с ЛП. Ограничения - строгие линейные неравенства. Функционал – квадратичная функция.

Линейный алгоритм построения свертки в Â2.

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

  1. Разобьем множество исходных точек на пары, соединенные отрезками.
  2. Найдем медиану m из направлений нормалей к отрезкам, направленных в сторону начала координат.
  3. Найдем множество крайних точек Z для направления m.
  4. Проведем из начала координат луч L в направлении, противоположном m. Если луч L пересекает отрезок conv(Z), то точка пересечения есть решение. Иначе луч L и противоположную ему нормаль m  надо повернуть в сторону conv(Z).
  5. В половине пар с «плохим» направлением нормали оставляем только точку, вокруг которой поворачивается отрезок при вращении нормали.

Общее число отброшенных точек равно n/4. Повторяя в цикле шаги 1-5, мы получим линейную трудоемкость, т.к.

Пример. На рисунках отметим медиану красной двойной стрелкой, а луч – оранжевой, «плохие» нормали – сиреневым, «хорошие» – зеленым, а крайние точки – жирным синим цветом. Результаты выполнения шагов 1-5 запишем в таблицу.

Скачать файл