Методы оптимальных решений

  В нашей задаче минимальную  стоимость 1 мы имеем сразу в трех клетках. Начнем с клетки ( ).За счет запаса По =3 можно удовлетворить всю заявку Пн =2. Поэтому записываем 2 в клетку ( ). При этом  заявка Пн -  теперь полностью удовлетворена. Но надо запомнить, что запас По- уменьшился на 2 единицы и теперь составляет 1 единицу. Такую же по величине стоимость равную =1 мы имеем в клетке ( ). Но поскольку запас По- =1, что меньше заявки Пн- =5, в эту клетку мы можем записать только 1 единицу товара. При этом запас По- =1 полностью исчерпан, но помним, в Пн -   необходимо доставить еще 4 единицы товара, используя возможности оставшихся По. Так как в клетке ( ) имеющей такую же по величине стоимость =1, уже стоит прочерк, то далее будет заполнена клетка ( )  с наименьшей из оставшихся стоимостью =2, куда мы запишем 4 единицы товара, полностью удовлетворяющих заявку . Рассуждая аналогично заполняем остальные клетки. В результате получим следующую транспортную таблицу 2 соответствующую первому опорному плану:

 

Таблица 2

По\Пн	=2	=5	=4
=6	-	4	2
=3	2	1	-
=2	-	-	2

 

 

 

 Нетрудно убедиться, что сумма перевозок в каждой строке равна запасу соответствующего По, а в каждом столбце – заявке соответствующего Пн. 

 

 

 

Сам первый опорный имеет вид- =(0,4,2,2,1,0,0,0,2).

А целевая функция задачи на этом плане равна 

=2х4+3х2+1х2+1х1+2х2=21.

 

2. Проверим, является ли найденный опорный план оптимальным.

 

Сопоставим каждому По – число и каждому Пн – число так, чтобы для любой базисной клетки выполнялось условие: . Числа и называются потенциалами. Оценки - , вычисляются для пустых клеток по формуле . Так как в нашем опорном плане m+n-1=3+3-1=5 базисных переменных, то для нахождения потенциалов нужно решить систему из 5 уравнений с 6-ю неизвестными. Поскольку число неизвестных на 1 больше числа уравнений значение одного потенциала можно выбрать произвольно. В нашей задаче система уравнений для нахождения потенциалов имеет вид:

 

 

Полагаем  =0 и сразу получаем значения остальных потенциалов: =-1, =3, =-1, =2, =2.

Теперь можно вычислить оценки:

, , аналогично =1, =1. Данные оценки занесены в таблицу в свободные клетки слева от стоимостей перевозок и выделены серым цветом.

 

 

 

 

 

 

Таблица 3

.По\Пн	=2	=5	=4
=6	1      3 -	2 4	3 2	0
=3	1 2	1 1	-1      1 -	-1
=2	1      2 -	1      2 -	2 2	-1
	2	2	3

 

Среди оценок есть отрицательные, значит выбранный нами опорный план не является оптимальным.

 

3. Найдем оптимальный  опорный план.

 

Для перехода к новому опорному плану  свободная переменная с отрицательной  оценкой вводится в базис, а одна из базисных переменных переводится  в свободные. Для этого построим цикл с началом (и концом) в клетке (2,3) с отрицательной оценкой =-1 и вершинами в занятых клетках. Ребра цикла могут проходить и через свободные, и через занятые клетки, но повороты на 90 градусов должны происходить только в занятых клетках. В нашем примере получается следующий цикл:

 

Таблица 4

.По\Пн	=2	=5	=4
=6	1      3 -	+w   2 4	-w     3 2	0
=3	1 2	-w    1 1	-1      1 +w	-1
=2	1      2 -	1      2 -	2 2	-1
	2	2	3

 

 

Для вывода из базиса выбирается клетка, помеченная знаком “ ” и имеющая наименьшее значение. Это условие гарантирует неотрицательность нового опорного плана. Если наименьшее значение находится в нескольких клетках, то выбирается любая из них. В любом случае значение целевой функции уменьшается на величину .

В нашей задаче w=min{х₁₃ =2, х₂₂ =1}=1. Тогда новые значения переменных будут следующими: х₂₃ =1 (и пустая клетка становится занятой), х₂₂ =0 (занятая клетка становится пустой), х₁₂ =5, х₁₃ =1. Значение целевой функции на новом опорном плане будет равно =21 - 1х1=20. Далее переходим к следующей таблице и вычисляем новые значения потенциалов и новые оценки, которые таким же образом заносим в таблицу.

Новые потенциалы:

u1=0; u2=-2; u3=-1; v1=3; v2=2; v3=3.

 

Таблица 5

.По\Пн	=2	=5	=4
=6	0      3 -	2 5	3 1	0
=3	1 2	1      1 -	1 1	-2
=2	0      2 -	1      2 -	2 2	-1
	3	2	3

 

Отрицательных оценок больше нет, следовательно  план х² является оптимальным. Вот он:

х² = (0,  5, 1, 2, 0, 1, 0, 0, 2). Наличие нулевых оценок в клетках с11 и с31 как бы намекает нам, что возможны варианты логистических решений с той же стоимостью перевозки.

 

Ответ:  из пункта a₁ следует перевезти 5 единиц груза в пункт b₂ и 1 единицу груза в пункт b₃ . Из пункта а₂ следует перевезти 2 единицы груза в пункт b₁ и 1 единицу груза в пункт b₃. Из пункта а₃ следует перевезти 2 единицы груза в пункт b₃ .

Стоимость перевозки составит 20 условных единиц.

 

Задача 4. Игроки А и В имеют по 4 стратегии игры каждый, причем во время игры один не знает, какую стратегию выбрал другой. При выборе игроком А  i-й стратегии, а игроком В – j-й,  игрок В выплачивает игроку А сумму, равную значению элемента а_ij платежной матрицы

 

 (1)

 

Найти цену игры и оптимальную стратегию.

 

Решение.

 

Стратегии игрока А – строки платежной  матрицы, стратегии игрока В –  ее столбцы. Какой бы стратегии ни придерживался игрок В, выигрыш игрока А при выборе им стратегии 1 не будет меньше выигрыша при выборе им стратегии 4, т.е. первая стратегия доминирует четвертую, так что игрок А никогда не выберет последнюю. Аналогично для игрока В стратегия 1 при любом раскладе предпочтительнее стратегий 3 и 4. Следовательно, мы можем упростить платежную матрицу, вычеркнув из нее четвертую строку и третий и четвертый столбец.

 

 

  (2)

 

Договоримся считать, что теперь у игрока А имеется первая, вторая и третья стратегии, а у игрока В – первая и вторая (в оговоренном ранее порядке).

 

Справа в каждой строке выпишем гарантированный выигрыш игрока А, а внизу под каждым столбцом – максимальный проигрыш игрока В для каждой из стратегий:

 

5 3 | 3

6 -2 | -2

-1 4 | -1

________

6 4

 

Для игрока А наилучшей является первая стратегия, по которой он гарантированно выигрывает 3 ед. a₀ =3 – нижняя цена игры. А для игрока В наилучшей является вторая стратегия, так как он в худшем случае платит 4 ед.  b₀ = 4 - верхняя цена игры. Так как нижняя и верхняя цены игры не совпадают, то в чистых стратегиях задача не имеет решения.

 

Найдём решение задачи в смешанных  стратегиях. Для этого будем считать, что игрок В с вероятностью р использует первую стратегию и с вероятностью 1 – р – вторую.

 

р 1-р

5 3

6 -2

-1 4

 

Найдём средний выигрыш игрока А.

Если игрок А выбирает первую стратегию, то он получает математическое ожидание выигрыша, равное

u₁=5p+3(1 – p)=2p+3

Если игрок А выбирает вторую стратегию, то он получает математическое ожидание выигрыша, равное

u₂= 6p - 2(1 – p)=  8p -2

Если игрок А выбирает третью стратегию, то он получает математическое ожидание выигрыша, равное

u₃= -p+4(1 – p)=-5p+4

Так как неизвестной величиной  является только одна – вероятность р, то выигрыш игрока А удобно изобразить на графике в переменных (u,p).

 

 

 

 

 

Если бы игрок А знал значение р, он выбрал бы ту стратегию, для которой значение u(р) было бы наибольшим, т. е. выигрыш игрока А всегда является ординатой верхней огибающей всех u(p) (выделена на рисунке).

Игроку В выгодно зафиксировать такое р, при котором выигрыш игрока А, а значит и проигрыш игрока В, минимален. Из графика видно, что минимум верхней огибающей всех  u(p) достигается в точке М. Найдем ее координаты.

 

 Так как

 

,

то

2р+3=-5р+4

7р=1

р=1/7

Найдём цену игры.

μ=2р+3=23/7

Найдём стратегии игрока А.

Точка М – точка оптимальной стратегии определяется как первая и третья стратегии игрока А, поэтому вторая и четвёртая стратегии игрока А не используются.

Пусть игрок А с вероятностью q использует стратегию 1 и с вероятностью (1 – q) – стратегию 3. Но цена игры известна, поэтому можно написать уравнение на q в виде:

5q+3(1-q)=23/7

2q=2/7

q=1/7

Ответ: Оптимальная стратегия матричной  игры – смешанная. Игрок А не применяет вторую и четвёртую стратегии, первая стратегия им используется с вероятностью 1/7, третья стратегия используется с вероятностью 6/7. Игрок В не применяет третью и четвёртую стратегии, первую применяет с вероятностью 1/7, вторую – с вероятностью 6/7. Цена игры равна 23/7.