1.2 Исследование двойственной задачи линейного рограммирования

Рассмотрим соотношение прямой и двойственной задач:

(2.2)

Число переменных двойственной задачи совпадает с числом ограничений прямой задачи.

Исходная задача:

F(x)=2x₁-4x₂-4x₃ (max)при следующих ограничениях:

Так как требуется найти максимум целевой функции, то неравенства в системе ограничений должны быть вида <. Второе неравенство ограничений прямой задачи умножим на (-1):

тогда

, ,

Двойственная задача будет иметь 4 переменные, так как прямая содержит 4 ограничения. В соответствии с (2.2) запишем двойственную задачу в виде:

,

Тогда условие пример следующий вид:

,

следовательно:

.

Введем дополнительные переменные и умножим на (-1):

Составим симплекс-таблицу, учитывая, что коэффициенты при небазисных переменных в F-строке не меняют знаки на противоположные, т.к. осуществляется минимизация функции.

Т аблица 1.5

БП	Своб. члены	НП
		y1	y2	y3	y4
y5	-2	-2	-3	2	-2
y6	4	3	5	-3	-2
y7	4	2	5	4	-5
F	0	-9	-21	-9	30

Таблица 1.6

БП	Своб. члены	НП
		y1	y5	y3	y4
y2	0,6667	0,6667	-0,333	-0,667	0,6667
y6	0,6667	-0,333	1,6667	0,3333	-5,333
y7	0,6667	-1,333	1,6667	7,3333	-8,333
F	14	5	-7	-23	44

Таблица 1.7

БП	Своб. члены	НП
		y1	y5	y7	y4
y2	0,7273	0,5455	-0,182	0,0909	-0,091
y6	0,6364	-0,273	1,5909	-0,045	-4,955
y3	0,0909	-0,182	0,2273	0,1364	-1,136
F	16,091	0,8182	-1,773	3,1364	17,864

Таблица 1.8

БП	Своб. члены	НП
		y1	y6	y7	y4
y2	0,8	0,5143	0,1143	0,0857	-0,657
y5	0,4	-0,171	0,6286	-0,029	-3,114
y3	0	-0,143	0,1429	0,1429	-0,429
F	16,8	0,5143	1,1143	3,0857	12,343

Оптимальное решение прямой задачи определяется коэффициентами F-строки. Переменные прямой задачи приравниваются к коэффициентам при соответствующим им небазисных переменных в F-строке оптимальной симплекс-таблицы двойственной задачи. Оптимальное решение найдено:

F_min =16,8.

Оптимальный план:

y1 =0; y2 =0,8; y3 =0; y4 =0; y5 =0,4; y6 =0

y7 =0.

Запишем соответствие между переменными прямой и двойственной задач:

Исходные переменные Дополнительные переменные

прямой задачи прямой задачи

x₁ x₂ x₃ R x₄ x₅ x₆

(2.3)

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

Дополнительные переменные Исходные переменные

двойственной задачи двойственной задачи

Решения прямой и двойственной задачи совпадают Fmin(у)= Fmax(x).