Методы оптимизации
Контрольная работа, 16 Декабря 2012, автор: пользователь скрыл имя
Краткое описание
Бомбить аэродром отправляются 3 самолета, 2 из них – бомбардировщики. Противник может выстрелить по двум самолетам. При выстреле по самолету он поражает летящий первым с вероятностью 0,4, летящий вторым или третьим – с вероятностью 0,5. Аэродром разбомблен, если хотя бы один бомбардировщик уцелел. Сформулировать задачу как задачу теории игр. Найдите решение или укажите алгоритм нахождения решения.
Вложенные файлы: 1 файл
Мет.опт.реш.Вариант 1.doc
— 601.50 Кб (Скачать файл)Вариант 1
- Бомбить аэродром отправляются 3 самолета, 2 из них – бомбардировщики. Противник может выстрелить по двум самолетам. При выстреле по самолету он поражает летящий первым с вероятностью 0,4, летящий вторым или третьим – с вероятностью 0,5. Аэродром разбомблен, если хотя бы один бомбардировщик уцелел. Сформулировать задачу как задачу теории игр. Найдите решение или укажите алгоритм нахождения решения.
Данную задачу можно рассматривать как игру, в которой у 1 игрока (аэродром) есть три стратегии:
I: d1={выстрелить по 1 самолету, затем по 2}
d2={выстрелить по 1 самолету, затем по 3}
d3={выстрелить по 2 самолету, затем по 3}
У второго игрока (самолеты) есть 3 стратегии:
II: q1={бомбардировщик, бомбардировщик, небомбардировщик}
q2={бомбардировщик, небомбардировщик, бомбардировщик}
q3={небомбардировщик, бомбардировщик, бомбардировщик}
Определим потери 1 игрока в каждом случае. Будем считать, что если аэродром разбомблен, то потери 1 игрока равны 1, в противном случае -1.
II I |
q1 |
q2 |
q3 |
d1 |
0,6 |
1 |
1 |
d2 |
1 |
0,6 |
1 |
d3 |
1 |
1 |
0,6 |
Получили следующую матрицу потерь I игрока:
Для нахождения решения игры определим, имеет ли матрица потерь седловую точку:
II I |
q1 |
q2 |
q3 |
v* max |
d1 |
0,6 |
1 |
1 |
1 |
d2 |
1 |
0,6 |
1 |
1 |
d3 |
1 |
1 |
0,6 |
1 |
v* min |
0,6 |
0,6 |
0,6 |
v* min=1
v* max=0,6
Т.к. a* min ≠ a* max, то игра не имеет седловой точки и неразрешима в чистых стратегиях.
В нашем случае : 0,6 v 1.
Укажем дальнейший алгоритм решения. Для нахождения решения составляем системы уравнений для прямой и двойственной задачи и находим их решение.
Если P* = ( p*1 , p*2 , p*3 ) и Q* = ( q*1 , q*2 , q*3 ) являются оптимальным решением, то должны выполняться две следующие системы неравенств : |
|
0,6 p*1 |
+ p*2 |
+ p*3 |
v | |
p*1 |
+ 0,6 p*2 |
+ p*3 |
v | ||
p*1 |
+ p*2 |
+ 0,6 p*3 |
v |
|
0,6 q*1 |
+ q*2 |
+ q*3 |
v | |
q*1 |
+ 0,6 q*2 |
+ q*3 |
v | ||
q*1 |
+ q*2 |
+ 0,6 q*3 |
v |
Рассмотрим первую систему. |
Разделим почленно первую систему на v (цену игры). |
Т.к. цена игры положительная, то знаки в неравенствах системы не изменятся. |
Введем новые обозначения: |
y1 = p*1 / v , y2 = p*2 / v , y3 = p*3 / v |
Рассмотрим сумму: |
y1 + y2 + y3 = p*1 / v + p*2 / v + p*3 / v = 1/v * ( p*1 + p*2 + p*3 ) = 1/v |
Т.к игрок A старается увеличить свой выигрыш, т.е. цену игры v, то выражение 1/v будет стремиться к минимуму. |
Мы получили задачу линейного программирования. |
Требуется найти минимум линейной функции F = y1 + y2 + y3 при следующей системе ограничений : |
|
0,6 y1 |
+ y2 |
+ y3 |
1 | |
y1 |
+ 0,6 y2 |
+ y3 |
1 | ||
y1 |
+ y2 |
+ 0,6 y3 |
1 |
Рассмотрим вторую систему. |
Разделим почленно вторую систему на v (цену игры). |
Т.к. цена игры положительная, то знаки в неравенствах системы не изменятся. |
Введем новые обозначения: |
x1 = q*1 / v , x2 = q*2 / v , x3 = q*3 / v |
Рассмотрим сумму: |
x1 + x2 + x3 = q*1 / v + q*2 / v + q*3 / v = 1/v * ( q*1 + q*2 + q*3 ) = 1/v |
Т.к игрок B старается уменьшить свой проигрыш, т.е. цену игры v, то выражение 1/v будет стремиться к максимуму. |
Мы получили задачу линейного программирования. |
Требуется найти максимум линейной функции L = x1 + x2 + x3 при следующей системе ограничений : |
|
0,6 x1 |
+ x2 |
+ x3 |
1 | |
x1 |
+ 0,6 x2 |
+ x3 |
1 | ||
x1 |
+ x2 |
+ 0,6 x3 |
1 |
Полученные задачи являются парой симметричных взаимно двойственных задач. |
Решив одну из них, мы автоматически получим решение второй. |
Удобнее решить вторую задачу. Решим ее симплекс методом. |
|
Система ограничений должна быть приведена к каноническому виду. |
К левой части неравенства 1 системы ограничений прибавляем неотрицательную переменную x4 , тем самым мы преобразуем неравенство 1 в равенство. |
К левой части неравенства 2 системы ограничений прибавляем неотрицательную переменную x5 , тем самым мы преобразуем неравенство 2 в равенство. |
К левой части неравенства 3 системы ограничений прибавляем неотрицательную переменную x6 , тем самым мы преобразуем неравенство 3 в равенство. |
|
0,6 x1 |
+ x2 |
+ x3 |
+ x4 |
= |
1 | ||
x1 |
+ 0,6 x2 |
+ x3 |
+ x5 |
= |
1 | |||
x1 |
+ x2 |
+ 0,6 x3 |
+ x6 |
= |
1 |
Система ограничений
приведена к каноническому |
|
Определимся с начальным опорным решением. |
Наличие единичного базиса в системе ограничений позволяет легко найти начальное опорное решение. Рассмотрим подробнее: |
Переменная x4 входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x4 - базисная переменная. |
Переменная x5 входит в уравнение 2 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x5 - базисная переменная. |
Переменная x6 входит в уравнение 3 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x6 - базисная переменная. |
Переменные , которые не являются базисными, называются свободными переменными. Приравняв свободные переменные нулю, в получившийся системе ограничений, мы получим начальное опорное решение. |
X нач = ( 0 , 0 , 0 , 1 , 1 , 1 )
Значение функции для начального решения: L (X нач) = 0 |
1) |
За ведущий выберем столбец 1 , так как -1 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу свободных членов не рассматриваем. |
За ведущую выберем строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для 2 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 1. |
базисные переменные |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
свободные члены |
отношение | |||||
x4 |
0,6 |
1 |
1 |
1 |
0 |
0 |
1 |
| |||||
x5 |
1 |
0,6 |
1 |
0 |
1 |
0 |
1 |
1 | |||||
x6 |
1 |
1 |
0,6 |
0 |
0 |
1 |
1 |
1 | |||||
L |
- 1 |
- 1 |
- 1 |
0 |
0 |
0 |
0 |
- |