Двойственный симплексный метод

Воспользуемся (без дока­зательства) теоремой для решения двойственных задач. Теорема устанавливает связь между оптимальными планами пары двойственных задач.

Теорема (теорема двойственности): если одна из двойственных задач имеет оптимальное ре­шение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций равны Z(x*) = f(у*). При этом свободным переменным одной задачи сопоставляются базисные переменные другой и наоборот.

Пример 15. По условиям примера 1 найти:

1) ассортимент выпускаемой продукции, обеспечивающей предпри­ятию max выручки;

2) оценки ресурсов, используемых при производстве продукции.

Решение:

1) Симплексным методом решаем задачу, модель которой уже составлена.

Таблица 23

N	БП	Сб	В	Х1	Х2	Х3	Х4	Х5	Х6	Х7	q
0	х5 х6 х7	0 0 0	488 2400 1500	4 2 1	2 10 0	2 6 2	[8] 0 1	1 0 0	0 1 0	0 0 1	4800/8 = 600   1500/1 = 1500
	z(j) – c(j)		0	– 65	– 70	– 60	– 120	0	0	0
1	x4   x6   х7	120   0   0	600   2400   900	1/2   2   1/2	1/4   0   – 1/4	1/4   [6]   7/4	1   0   0	1/8   0   – 1/8	0   1   0	0   0   1	= 2400  = 400
	z(j) – c(j)		72000	– 5	– 40	– 30	0	15	0	0
2	x4 х3 х7	120 60 0	500 400 200	5/12 1/3 – 1/12	– 1/6 0 – 19,6	0 1 0	1 0 0	1/8 0 – 1/8	– 1/24 1/6 – 7/24	0 0 1
	z(j) – c(j)		84000	5	10	0	0	15	5	0

 

После второй итерации получим все оценки значит найденный опорный план:

оптимален и – max.

Основные переменные  показывают, что продукцию П₁ и П₂ выпускать не целесообразно ( = 0, = 0), а продукции П₃ произвести 400 ед., продукции П₄ – 500 ед.

Дополнительные переменные показывают, что ресурсы Р₁ и Р₂ используются полностью (  =  = 0), а вот ресурса Р₃ осталось 200 ед. неиспользованными.

2) Определимся с переменными оптимального плана двойственной задачи: двойственной оценки  В прямой задаче х₁, х₂, х₃, х₄ являются свободными переменными, а х₅, х₆, х₇ – базисными.

В двойственной задаче свободными переменными будут у₁, у₂, у₃, а у₄, y₅, у₆, y₇ – базисными переменными.

Соответствие между переменными будет:

 

 

x₁ х₂  х₃ х₄ х₅ х₆ х₇

 

                                    СП                      БП      

y₄ y₅ у₆ y₇ y₁ y₂ y₃

 

                                    БП                       СП      

 

Учитывая это соответствие, из индексной строки последней итерации выписываем оптимальный план у^*:

– двойственные оценки.

В соответствии с основной теоремой двойственности имеем max z (х^*) = min f (у^*) = 84000.

Замечание. Если при решении задачи у нас имеются  < 0, то переменную, соответствующую этому свободному члену, следует исключить из базиса. Для выбора переменной, включаемой в ба- зис, просматриваем i-строку: если в ней не содержится , то исходная задача не имеет решения. Если же есть , то для столбцов, содержащих эти , находим q₁ = min

Затем находим  q = max  при решении задачи на m i n и   q = m in  при решении задачи на max. Эту переменную и вводим в базис. В процессе вычисления по алгоритму двойственного симплексного метода ус­ловие оптимальности (D _j ³ 0 или D _j £ 0) можно не учитывать, пока не бу­дут исключены все b_i < 0, затем оптимальный план находим обычным симплексным методом.

Пример 16. Найти а) m i n Z= -2х₁+х₂ +5х₃ при ограничениях

б) решение двойственной ей задачи.

Решение:

а)

Þ – система имеет пред- почтительный вид.

Составим симплексную табл. 24, выбрав за базисные переменные х₄ и х₅. Так как х₅= – 5<0, то просматриваем коэффициенты второй строки. Среди них два отрицательных коэффициента, стоящие в столбцах х₁ и х₃. Имеем:

Таблица 24

№ итерации	БП	Сб	В	x1	x2	x3	x4	x5	q
				– 2	1	5	0	0
Исходное состояние 0	x4   x5	0   0	4   – 5	[1]   – 1	1   5	– 1   – 1	1   0	0   1	q1 = min = = 4  q1×D1 = 4 × 2 = 8  q3 = min  = 5  q3×D3 = – 25 max(8; – 25) = 8
	zj – cj		D0 =  0	D1 = [ 2]	D2 =  – 1	D3 = – 5	D4 = 0	D4 = 0
1	x1   x5	– 2   0	4   – 1	1   0	1   6	– 1   [2]	1   1	0   1	q1 = min = 0,5
	zj – cj		D0 = – 8	D1 =  0	D2 =  – 3	D3 = – 3	D4 = – 2	D4 = 0
2	x1   х3	– 2   5	9/2   1/2	1   0	– 2   – 3	0   1	1/2   – 1/2	– 1/2   – 1/2
	zj – cj		D0 = = – 13/2	0	– 12	0	– 7/2	– 3/2

 

Исходная задача решается на отыскание минимального значения линейной функции, поэтому в базис исходной задачи надо включить вектор, которому соответствует  т. е. вектор x₁ с разрешающим элементом 1, а x₄ исключаем из базиса и т. д. В итоге получаем: план = (9/2; 0; 1/2; 0; 0) оптимальный, т. к. все ∆ _j = z_j – c_j £ 0, Z min = = –

б) решение двойственной задачи:

x₁ х₂ х₃ х₄ х₅

 

                                           СП       БП

                                    y₃ y₄ y₅ y₁ y₂,

                                           БП        СП

тогда оптимальный план = (– 7/2; – 3/2; 0; – 12; 0), F max = F = = – 13/2. Так как все y _j ≥ 0, то умножив  на (– 1), получим

= (7/2; 3/2; 0; 12; 0).

 

Задания для самостоятельной работы

Задание 1. Составить двойственную задачу для исходной задачи из задания (тема 1, стр. 11). Дать экономическую интерпретацию полученной двойственной задачи.

Задание 2. Составить двойственную задачу для исходной задачи из заданий 1 и 2 (тема 2, стр. 26 – 29) и решить ее. Сравнить полученные результаты в двойственной и исходной задаче.