Двойственная задача.

Задача 1. Задача 2.

 

 

 

Для того, чтобы X*=(2,0) был оптимальным планом задачи 1, необходимо и достаточно, чтобы существовал план Y*=(y₁*,y₂*,y₃*) двойственной ей задачи 2. Y* вычисляется по следующей формуле Y*=C*D^-1, значение которых находим из таблица 2: C*=(0,0,4), D*=

 

Получаем, что Y*=(0,0,4/3)-оптимальный план, а g(Y*)=18*0+14*0+6*4/3=8. Поэтому f(X*)=g(Y*)=8. Получили тот же результат.

 

21-40.Решить транспортную задачу. Заданы мощности поставщиков a_i, емкости потребителей b_jи матрица c_jстоимости перевозок единицы продукции от каждого поставщика каждому потребителю. Найти план перевозок, при котором суммарные транспортные затраты будут наименьшими.

ai bj

Посчитаем суммарную мощность поставщиков и суммарную емкость потребителей: a₁+a₂+a₃=42 < b₁+b₂+b₃=60, поэтому задача является открытой моделью транспортной задачи и для сведения ее к закрытой введем фиктивного поставщика с емкостью 60-42=18. Стоимости перевозки продукции от фиктивного поставщика к каждому потребителю положим равными нулю. В результате получим закрытую модель транспортной задачи:

ai bj

Решим транспортную задачу с помощью метода потенциалов.

Составим исходный план перевозок X₁методом «северо-западного угла».

 

				u1=0
X1=				u2=-4
				u3=-2
				u4=-8
	v1=5	v2=8	v3=8

 

Для плана X₁число занятых клеток k=m+n-1=6, значит, план является невырожденным.

Суммарная стоимость перевозок по плану X_1:

f(X₁)=19*5+1*8+10*4+12*6=215.

Проверим план на оптимальность: найдем потенциалы u_iи v_jтак, чтобы выполнялись условия 1⁰ и 2⁰ критериев оптимальности плана перевозок.

По условию 2⁰ для занятых клеток:

u₁+v₁=5 u₂+v₂=4 u₄+v₂=0

u₁+v₂=8 u₃+v₂=6 u₄+v₃=0

Зададим u₁=0, отсюда получим, что u₂=-4, u₃=-2, u₄=-8, v₁=5, v₂=8, v₃=8.

По условию 1⁰ для свободных клеток:

Подставив потенциалы, получим:

0+8=8 > 3 -2+8=6 > 3 -2+5=3 < 7

-4+8=4 >2 -4+5=1 < 2 -8+5=-3 < 0

Мы видим, что не выполнено 3 неравенства из 6, причем,

.

Следовательно, план перевозок можно улучшить, введя перевозку

x₁₃= . С этой целью составим цикл, имеющий начало в клетке (1,3). В результате получим план

X2(0)=

 

Выберем , при включении в план X₁перевозки

суммарная стоимость перевозок изменится на

, то есть уменьшится на 5, поэтому

Пересчитав все перевозки, вошедшие в цикл плана при

Получим новый план перевозок X₂.

				u1=0
X2=				u2=1
				u3=3
				u4=-3
	v1=5	v2=3	v3=3

 

План X₂ лучше X_1,так как стоимость перевозок f(X₂)=210. Проверим план X₂ на оптимальность. Для занятых клеток составим систему:

u₁+v₁=5 u₂+v₂=4 u₄+v₂=0

u₁+v₃=3 u₃+v₂=6 u₄+v₃=0

Снова зададим u₁=0, отсюда получим, что u₂=1, u₃=3, u₄=-3, v₁=5, v₂=3, v₃=3.

По условию 1⁰ для свободных клеток:

Подставив потенциалы, получим:

0+3=3 < 8 3+3=6 > 3 3+5=8 > 7

1+3=4 >2 1+5=6 > 2 -3+5=2 > 0

Мы видим, что не выполнено 5 неравенства из 6, причем,

.

Следовательно, план перевозок можно улучшить, введя перевозку

x₂₁= . С этой целью составим цикл, имеющий начало в клетке (2,1). В результате получим план

 

X3(0)=

 

Выберем , при включении в план X₂перевозки

суммарная стоимость перевозок изменится на

, то есть уменьшится на 36, поэтому

Пересчитав все перевозки, вошедшие в цикл плана при

Получим новый план перевозок X₃.

 

				u1=0
X3=				u2=-3
				u3=-1
				u4=-7
	v1=5	v2=7	v3=3

 

План X₃ лучше X_2,так как стоимость перевозок f(X₃)=174. Проверим план X₃ на оптимальность. Для занятых клеток составим систему:

u₁+v₁=5 u₂+v₂=4 u₄+v₂=0

u₁+v₃=3 u₃+v₂=6 u₂+v₁=2

Снова зададим u₁=0, отсюда получим, что u₂=-3, u₃=-1, u₄=-7, v₁=5, v₂=7, v₃=3.

По условию 1⁰ для свободных клеток:

Подставив потенциалы, получим:

0+7=7 < 8 -1+3=2 < 3 -1+5=4 < 7

-3+3=0 < 2 -7+3=-4 < 0 -7+5=-2 < 0

Отсюда следует, что выполняются оба условия 1⁰ и 2⁰ критерия оптимальности плана перевозок. Следовательно, план X₃является оптимальным планом закрытой модели, а f(X₃)=174 представляет собой наименьшую стоимость перевозок.

Отбросив последнюю строку плана X₃, получим оптимальный план X* исходной открытой модели, для которой f(X*)=174 есть наименьшая стоимость перевозок. Отброшенная строка означает, что у второго потребителя останется недопоставлено 18 единиц продукции.

 

 

Ответ:оптимальный план X* исходной открытой модели, для которой f(X*)=174 есть наименьшая стоимость перевозок.

X*=

 

41-60.Найти оптимальные стратегии и цену игры, заданной платежной матрицейА.

А=

Решение:

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

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

A’ =

 

Прибавив ко всем элементам матрицы A’, например, число c=3, получим матрицу A’’, все элементы 1 строки которой строго положительны, а все элементы 2 строки неотрицательны.

A’’=

Составим пару симметричных двойственных задач, так чтобы исходная задача была стандартной задачей максимизации, матрица коэффициентов этой задачи совпадала с платежной матрицей A’’, а коэффициенты при неизвестных в целевой функции и свободные члены неравенств были бы равны единице.

Задача 1. Задача 2.

 

Решим задачу 1 симплекс-методом. Она задана в форме общей задачи. Сведем ее к основной при помощи дополнительных переменных и прибавим их к левым частям неравенств (I), тогда получим основную задачу:

 

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

Из столбца x₀и индексной строки Табл.4 выпишем оптимальные планы пары двойственных задач: X*=(0,0,0.5), Y*=(0.2, 0.3), причем f(X*)=f(Y*)=0.5.

Из решения пары двойственных задач получим цену игры и оптимальные стратегии игроков: v’’=1/f(X*)=1/f(Y*)=2, P’*=v’’Y*=(0.4,0.6), Q’*=v’’X*=(0,0,1).

Игра с матрицей A’ будет иметь те же оптимальные стратегии P’* и Q’*? Что и игра с матрицей A’’, причем цена игры будет v’=v’’-c=2-3=-1.

 

 

							Табл.1
	Базис	x0	x1	x2	x3	x4	x5
	x4
	x5
	f		-1	-1	-1
							Табл.2
	x4
	x1
	f			-1
							Табл.3
	x2
	x1
	f
							Табл.4
	x2		-1,2			0,2	0,2
	x3	0,5	3,5				0,5
	f	0,5	1,3			0,2	0,3
		g	y3	y4	y5	y1	y2

И наконец, исходная игра Aимеет оптимальные стратегии игроков P*=(0, 0.4, 0.6), Q*=(0, 0, 0, 1) (полученные из стратегий P’* и Q’*, приписав нули на месте удаленных строк и столбцов) и цену игры v=v’=-1.

Проверим правильность решения игры с помощью критерия оптимальности стратегий. Для этого подставим компоненты найденных оптимальных стратегий P* и Q*, компоненты чистых стратегий P_i(i=1,2,3) и Q_j(j=1,2,3,4) в неравенство

 

И сравним их с ценой игры v=-1.

 

 

Мы видим, что все неравенства выполнены, значит, решение игры выполнено правильно.

Ответ:Игра Aимеет оптимальные стратегии игроков P*=(0, 0.4, 0.6), Q*=(0, 0, 0, 1) (полученные из стратегий P’* и Q’*, приписав нули на месте удаленных строк и столбцов) и цену игры v=v’=-1.