Методы оптимизации

Вариант 1

  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
 

5

  
 

3


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

-


 

От элементов строки 1 отнимает соответствующие элементы строки 2 умноженные на 0,6.


От элементов строки 3 отнимает соответствующие элементы строки 2 .


От элементов строки L отнимает соответствующие элементы строки 2 умноженные на -1.


 

базисные

переменные

x1

x2

x3

x4

x5

x6

свободные

члены

отношение

x4

0
 

16

  
 

25
 

2

  
 

5

1

-

3

  
 

5

0
 

2

  
 

5

-

x1

1

0,6

1

0

1

0

1

-

x6

0
 

2

  
 

5

-

2

  
 

5

0

- 1

1

0

-

L

0

-

2

  
 

5

0

0

1

0

1

-


X 1 = ( 1 , 0 , 0 , 2/5 , 0 , 0 )

Значение функции L для  данного решения: L (X 1) = 1


2)


За ведущий выберем  столбец 2 , так как -2/5 наименьший элемент  в L строке. Элемент L строки, принадлежащий столбцу свободных членов не рассматриваем.


За ведущую выберем  строку 3, так как отношение свободного члена к соответствующему элементу выбранного столбца для 3 строки является наименьшим. Обратите внимание, что  отношение мы вычисляем только для  положительных элементов столбца 2.


 

Базисные

переменные

x1

x2

x3

x4

x5

x6

Свободные

члены

отношение

x4

0
 

16

  
 

25
 

2

  
 

5

1

-

3

  
 

5

0
 

2

  
 

5
 

5

  
 

8


x1

1

0,6

1

0

1

0

1
 

5

  
 

3


x6

0
 

2

  
 

5

-

2

  
 

5

0

- 1

1

0

0

L

0

-

2

  
 

5

0

0

1

0

1

-


 

Разделим элементы строки 3 на 2/5.


 

Базисные

переменные

x1

x2

x3

x4

x5

x6

Свободные

члены

отношение

x4

0
 

16

  
 

25
 

2

  
 

5

1

-

3

  
 

5

0
 

2

  
 

5
 

5

  
 

8


x1

1

0,6

1

0

1

0

1
 

5

  
 

3


x6

0

1

- 1

0

-

5

  
 

2
 

5

  
 

2

0

0

L

0

-

2

  
 

5

0

0

1

0

1

-


 

От элементов строки 1 отнимает соответствующие элементы строки 3 умноженные на 16/25.


От элементов строки 2 отнимает соответствующие элементы строки 3 умноженные на 0,6.


От элементов строки L отнимает соответствующие элементы строки 3 умноженные на -2/5.


 

базисные

переменные

x1

x2

x3

x4

x5

x6

свободные

члены

отношение

x4

0

0
 

26

  
 

25

1

1

-

8

  
 

5
 

2

  
 

5

-

x1

1

0
 

8

  
 

5

0
 

5

  
 

2

-

3

  
 

2

1

-

x2

0

1

- 1

0

-

5

  
 

2
 

5

  
 

2

0

-

L

0

0

-

2

  
 

5

0

0

1

1

-


 

X 2 = ( 1 , 0 , 0 , 2/5 , 0 , 0 )

Значение функции L для  данного решения: L (X 2) = 1


 

 

3)


За ведущий выберем  столбец 3 , так как -2/5 наименьший элемент  в L строке. Элемент L строки, принадлежащий  столбцу свободных членов не рассматриваем.


За ведущую выберем строку 1, так как отношение свободного члена к соответствующему элементу выбранного столбца для 1 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 3.


 

базисные

переменные

x1

x2

x3

x4

x5

x6

свободные

члены

отношение

x4

0

0
 

26

  
 

25

1

1

-

8

  
 

5
 

2

  
 

5
 

5

  
 

13


x1

1

0
 

8

  
 

5

0
 

5

  
 

2

-

3

  
 

2

1
 

5

  
 

8


x2

0

1

- 1

0

-

5

  
 

2
 

5

  
 

2

0

-

L

0

0

-

2

  
 

5

0

0

1

1

-

Методы оптимизации