Типовой расчет №1 «Линейное программирование» (стр. 3 )

Г) Прямая задача

Сформулируем двойственную задачу, учитывая необходимые требования. Число переменных в двойственной задаче, равно числу ограничений в прямой задаче. Правыми частями ограничений двойственной задачи являются коэффициенты при неизвестных в целевой функции прямой задачи. Коэффициентами при неизвестных в целевой функции двойственной задачи являются правые части ограничений прямой задачи. Матрица, составленная из коэффициентов при неизвестных в системе ограничений прямой задачи, и аналогичная матрица двойственной задачи, получаются друг из друга транспонированием. Т. к. все четыре переменные исходной задачи принимают лишь неотрицательные значения, то в системе ограничений двойственной задачи должны быть четыре неравенства вида ≥. Получаем двойственную задачу:

Решим двойственную задачу симплексным методом. Приведем задачу к каноническому виду. Для этого перейдем от ограничений типа неравенств к ограничениям типа равенств, введя дополнительные переменные . Двойственная задача линейного программирования будет сформулирована так:

Базисным переменным одной задачи соответствуют свободные переменные другой, и, наоборот

X1	X2	X3	X4	X5	X6
Y3	Y4	Y5	Y6	Y1	Y2

Решим двойственную задачу табличным симплекс-методом.

Составим первую таблицу, содержащую 4 строки.

i	Баз.	С баз.	А0	0	6	0	0	0	0
A1	A2	A3	A4	A5	А6
1			2	3	0	-1	0	0	0
2			0	-1	2	0	-1	0	0
3			1	-2	1	0	0	-1	0
4			2	1	1	0	0	0	-1

Единичных векторов среди ограничений нет, поэтому преобразуем систему ограничений методом Гаусса, чтобы выделить недостающие единичные вектора. При преобразованиях необходимо следить, чтобы задача не перестала быть канонической, т. е. элементы столбца А0 были неотрицательные. Четвертую строку умножим на 2 и прибавим к третьей. Четвертую строку прибавим ко второй. Четвертую строку множим на (-3) и прибавим к первой. Получаем первый базисный вектор А1.

i	Баз.	С баз.	А0	0	6	0	0	0	0
A1	A2	A3	A4	A5	А6
1			-4	0	-3	-1	0	0	3
2			2	0	3	0	-1	0	0
3			5	0	3	0	0	-1	-2
4	А1		2	1	1	0	0	0	-1

Первую строку прибавим ко второй и к третьей. Первую строку умножим на (1/3) и прибавим к четвертой. В таблице запишем первую строку, умноженную на (-1/3). Получаем второй базисный вектор А2.

i	Баз.	С баз.	А0	0	6	0	0	0	0
A1	A2	A3	A4	A5	А6
1	А2		4/3	0	1	1/3	0	0	-1
2			-2	0	0	-1	-1	0	3
3			1	0	0	-1	0	-1	1
4	А1		2/3	1	0	-1/3	0	0	0

Третью строку прибавим к первой. Третью строку умножим на (-3) и прибавим ко второй. Получаем третий базисный вектор А6.

i	Баз.	С баз.	А0	0	6	0	0	0	0
A1	A2	A3	A4	A5	А6
1	А2		7/3	0	1	-2/3	0	-1	0
2			-5	0	0	2	-1	3	0
3	А6		1	0	0	-1	0	-1	1
4	А1		2/3	1	0	-1/3	0	0	0

Вторую строку умножим на (-1) и получим последний четвертый базисный вектор А4.

i	Баз.	С баз.	А0	0	6	0	0	0	0
A1	A2	A3	A4	A5	А6
1	А2		7/3	0	1	-2/3	0	-1	0
2	А4		5	0	0	-2	1	-3	0
3	А6		1	0	0	-1	0	-1	1
4	А1		2/3	1	0	-1/3	0	0	0

Получили базис из векторов А1, А2, А4, А6 запишем эти вектора в базисный столбец, в следующий столбец запишем коэффициенты перед соответствующими переменными целевой функции. Соответственно в системе уравнений y1, y2, y4, y6 - базисные переменные, а y3, y5– свободные переменные. Получаем симплексную таблицу для первой итерации.

i	Баз.	С баз.	А0	0	6	0	0	0	0
A1	A2	A3	A4	A5	А6
1	А2	6	7/3	0	1	-2/3	0	-1	0
2	А4	0	5	0	0	-2	1	-3	0
3	А6	0	1	0	0	-1	0	-1	1
4	А1	0	2/3	1	0	-1/3	0	0	0
5			0=14	∆1=0	∆2=0	∆3=-4	∆4=0	∆5=-6	∆6=0

Получили план Y1=(2/3; 7/3; 0; 5; 0; 1) является неотрицательным, а значит допустимым. Проверим оптимальность. Все оценки ∆I неположительные, а значит, план оптимален в задаче на минимум.

И min(2/3; 7/3)=14.

Теорема двойственности: если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем для экстремальных значений линейных функций выполняется соотношение Lmax =min. Если линейная функция одной из задач неограниченна, то другая не имеет решения.

Итак, решение прямой задачи Lmax(4;0;6;0)=14 и двойственной min(2/3; 7/3)=14 совпадает, что согласуется с теоремой двойственности, значит решено, верно.