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

Рассмотрим задачу об использовании ресурсов. Пусть предпри­ятие № 1 производит п видов продукции и использует т видов сы­рья. Известна прибыль, получаемая с единицы продукции . Известны технологические коэффициенты . Требуется организовать производство так, чтобы предпри­ятию была обеспечена максимальная прибыль. Сведем все исход­ные данные в следующую таблицу:

Цены на ресурсы	Запасы сырья	Продукция
		П1	П2	…	Пn
u1	a1	a11	a12	…	a1n
u2	a2	a21	a22	…	a2n
…	…	…	…	…	…
um	am	am1	am2	…	amn
	Прибыль с единицы продукции	c1	c2	…	cn

Запишем в общем виде экономико-математическую модель за­дачи об использовании ресурсов. Для этого введем переменные — количество продукции j-го вида. Тогда ограничения на сырье запишутся в виде

(8.55)

Целевая функция, определяющая максимум прибыли, имеет вид

По этим же исходным данным сформулируем задачу по пред­приятию № 2.

Допустим, предприятие № 2 решило закупить все ресурсы, ко­торыми располагает предприятие № 1. В этом случае предприятию № 2 необходимо установить оптимальные цены на эти ресурсы, исходя из следующих условий:

17. общая стоимость ресурсов для предприятия № 2 должна быть минимальной;

18. за каждый вид ресурса предприятию № 1 надо уплатить не менее той суммы, которую это предприятие может получать при переработке данного вида ресурса в готовую продукцию.

Обозначим цены, по которым предприятие № 2 покупает ре­сурсы у предприятия № 1, через . Запишем экономико-математическую модель для предприятия № 2 с учетом вышеука­занных условий 1) и 2).

Целевая функция, определяющая минимальную суммарную стоимость ресурсов, имеет вид

(8.57)

В соответствии с условием 2) запишем систему ограничений:

(8.58)

Сравним математические модели задач (8.55), (8.56) и (8.57), (8.58):

1) число неизвестных одной задачи равно числу ограничений другой задачи;

• матрица коэффициентов системы ограничений получается одна из другой путем транспонирования;

• неравенства в системах ограничений имеют противополож­ный смысл;

• свободные члены системы ограничений одной из задач ста­новятся коэффициентами целевой функции другой задачи, коэф­фициенты целевой функции превращаются в свободные члены ог­раничений;

• целевые функции в задачах имеют противоположный смысл: в первой — max, во второй — min.

Задачи линейного программирования, обладающие пятью ука­занными формальными признаками, называются симметричными. Одна из них называется основной, а другая — двойственной.

В линейном программировании кроме симметричных двойст­венных пар существуют несимметричные двойственные пары, ко­торые имеют следующий вид:

основная задача:

(8.59)

(8.60)

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

(8.61)

(8.62)

Эти задачи отличаются от симметричной пары двумя особенно­стями;

1. ограничения задачи (8.59)—(8.60) выражены уравнениями вместо неравенств;

2. в задаче (8.61)—(8.62) отсутствуют условия неотрицательнос­ти переменных .

Общее правило построения двойственной пары

К пяти признакам, сформулированным ранее, необходимо до­бавить следующие:

а) в исходной задаче ограничения неравенства следует записывать со знаком г, если целевая функция стремится к min, и со знаком , если целевая функция стремится к max;

б) каждому ограничению неравенства исходной задачи соответ­ствует в двойственной задаче условие неотрицательности перемен­ных ;

в) каждому условию равенства соответствует переменная y_i- без ограничения на знак, и наоборот: неотрицательным переменным x_kиз основной задачи в двойственной задаче соответствуют ограниче­ния неравенства, а неограниченным по знаку переменным соответ­ствуют равенства.

Пример 8.15.

Дана следующая система:

Проверяем условие: целевая функция стремится к min, а знак неравенства должен быть . Исходная задача соответствует данно­му условию, и можно сразу приступить к построению симметрич­ной двойственной пары.

Так как в прямой задаче в системе ограничений два неравенст­ва, то в двойственной будет две переменных u₁ и и₂, причем .

Целевая функция:

.

Учитывая, что целевая функция на max и в прямой задаче , то система ограничений запишется в следу­ющем виде:

Пример 8.16.

Имеем систему

и не имеют ограничения знака;

Так как целевая функция на min, то в исходной задаче ограни­чения неравенства должны иметь знак . Умножим второе нера­венство системы на -1:

В прямой задаче число ограничений равно 3, значит, в двойст­венной будет три переменных: . Так как и₂ и и₃ соответст­вуют неравенствам, то . Параметр и₁ соответствует ра­венству, поэтому и₁ — переменная без ограничения знака.

Число ограничений в двойственной задаче равно 5, так как в прямой задаче пять переменных, в том числе первое, третье и пя­тое ограничения будут неравенствами, потому что они соответству­ют неотрицательным переменным, а второе и четвертое ограниче­ния будут уравнениями, так как соответствуют переменным без ог­раничения знака. Запишем двойственную задачу с учетом вышеиз­ложенного:

целевая функция:

ограничения:

Решение симметричных двойственных задач

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

Теорема (первая теорема двойственности). Если одна из двойст­венных задач имеет оптимальное решение, то и другая его имеет.

Причем экстремальные значения целевых функций совпадают. Если же в одной задаче целевая функция не ограничена, то двойственная ей задача противоречива.

Запишем в обшем виде прямую и двойственную задачи линейного программирования:

а) прямая задача:

(8.63)

б) двойственная задача:

(8.64)

Преобразуем задачи (8.63) и (8.64) к виду, допускающему при­менение симплекс-алгоритма. Для этого введем выравнивающие переменные в прямую задачу и — в двойствен­ную задачу:

а) прямая:

(8.63’)

б) двойственная:

(8.64’)

Построим для задач (8.63') и (8.64') общую симплекс-таблицу, причем эта таблица имеет дополнительные столбец и строку для двойственной задачи:

Двойственная задача		v1	v2	…	vn	Lmin
	С Б	x1	x2	…	xn	свободные члены
-u1	y1	a11	a12	…	a1n	a1
-u2	y2	a21	a22	…	a2n	a2
…	…	…	…	…	…	…
-um	ym	am1	am2	…	amn	am
	Zmax	-c1	-c2	…	-cn	0

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

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

• планы Х= (х₁ ,х₂, .., х_п) и U = (u₁, u₂, ..., и_т) оптимальны, если Z_max(X) = I_min(U);

• решения Х= (х₁ ,х₂, .., х_п) и U = (u₁, u₂, ..., и_т) оптимальны, ес­ли все произведения сопряженных условий для этих решений равны 0.

Запишем следующие сопряженные условия:

1 группа:

II группа получается, если умножить на х₁, х₂, .... х_п выражения для базисных переменных двойственной задачи:

Пример 8.17. По исходной задаче построить двойственную и най­ти оптимальное решение обеих задач.

Согласно общему правилу составления двойственных задач запишем:

Решим задачи в единой симплекс-таблице. Для этого представим их в виде, позволяющем применить симплекс-метод: прямая задача: вводим выравнивающие переменные х₅, x₆:

х₅ = 50 - (3 х₁ + 8 х₂ + х₃ + х₄);

х₆ = 14 — (5х₁ - 4 х₂ — х₃. + х₄);

Z_max = 0 - (З х₁ - 5х₂ - х₃ – х₄);

двойственная задача: вводим в левую часть ограничений выравнивающие переменные v₁,v₂, v₃, v₄ со знаком «—»:

Итак, составим таблицу, внешний контур которой образует двойственную задачу, внутренний – прямую задачу:

С**	Б*	v1	v2	v3	v4	Lmin
	С Б	x1	x2	x3	x4	Свободные члены
-u1	x5	3		1	1	50
-u2	x6	5	-4	-1	1	14
Свободные члены	Zmax	3	-5	-1	-1	0
*Б – базисные переменные.
**С – свободные переменные.

Будем работать по симплекс – методу, но так как записанная в последней строчке функция стремится к максимуму, то в этой строчке мы будем искать наименьший отрицательный элемент:

Построим итоговую таблицу:

С*	Б*	v1	u2	v3	v4	Lmin
	С Б	x1	x5	x3	x4	Свободные члены
-v2	x2	3/8	1/8		1/8	50/8
-u2	x6	52/8	4/8	-4/8	12/8	39
Свободные члены	Zmax	39/8	5/8	-3/8	-3/8	250/8

С*	Б*	v1	u1	v2	v4	Lmin
	С Б	x1	x5	x2	x4	Свободные члены
-v3	x3	3	1	8	1	50
-u2	x6	8	1	4		64
Свободные члены	Zmax	6	1	3		50

С*	Б*	v1	u1	v2	u2	Lmin
	С Б	x1	x5	x2	x6	Свободные члены
-v3	x3	-1	1/2	6	-1/2	18
-v4	x4	4	1/2	2	1/2	32
Свободные члены	Zmax	6	1	3	0	50

Итак, мы получили итоговую таблицу, в последней строчке которой нет отрицательных элементов, следовательно, задачи решены:

прямая задача X = (0; 0; 18; 32), Z_mm = 50;

двойственная задача U = (1; 0), L_min = 50.

Проверим полученное решение на оптимальность;

условие I) выполнено; Z(X) = L (U) = 50.

Для выполнения условия 2) составим произведения сопряженных условий:

Итак, оба условия выполняются, значит, полученный план — оптимальный.

Рассмотренную задачу примера 8.17 можно решить иначе. Для этого необходимо:

• Решить прямую задачу обычным симплекс-методом. Реше­ние получим следующее: Z_max = 50; X = (0; 0; 18; 32).

• Составить произведение сопряженных условий и приравнять их к 0:

Подставим вектор X в записанные условия, тогда будем иметь

После преобразований получим

Откуда ,так как , значит, задача решена верно.