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

3.1. Понятие двойственности. Построение пары
взаимно двойственных задач

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

Первоначальная задача называется прямой или исходной. Многие задачи линейного программирования первоначально ставятся в виде исходных или двойственных задач, поэтому говорят о паре взаимно двойственных задач линейного программирования.

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

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

Таблица 10

Прямая задача	Двойственная задача

 

Для построения двойственной задачи необходимо пользоваться следующими правилами:

1. если прямая задача решается на максимум, то двойственная – на минимум, и наоборот.

2. в задаче на максимум ограничения-неравенства имеют смысл £, а в задаче минимизации – смысл ³.

3. коэффициенты c_j целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.

4. свободные члены b_i ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи.

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

6. если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение-неравенство, если же нет, то как ограничение-равенство.

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

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

Пример 6. Построить двойственную задачу к каждой из исходных:

1.

2.

Решение

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

f = 15 y ₁ + 9 y ₂ ® max;

2. данная задача записана в произвольной несимметричной форме. Прежде всего, ограничения типа ³ умножением на –1 сведем к ограничениям типа £. Получим

z = –4 x ₁ + 2 x ₂ – 7 x ₃ + 5 x ₄ ® max;

В результате применения указанных правил получим следующую модель двойственной задачи:

f = –3 y ₁ + 7 y ₂ + 4 y ₃ – 5 y ₄ – 2 y ₅ ® min;

 

 

3.2. Теоремы двойственности. Критерий оптимальности
Канторовича (достаточный признак оптимальности)

 

Если для некоторых допустимых планов х ^* и у ^* пары двойственных задач выполняется равенство z (x ^*) = f (y ^*), то х ^* и у ^* являются оптимальными планами соответствующих задач.

Теорема 7 (о существовании оптимальных планов пары двойственных задач). Для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существования допустимого плана для каждой из них.

Согласно теории линейного программирования каждой задаче линейного программирования соответствует двойственная ей. Основные утверждения о взаимно двойственных задачах содержатся в нижеприведенных теоремах.

Первая теорема двойственности. Для взаимно двойственных задач линейного программирования имеет место один из взаимоисключающих случаев:

1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций в оптимальных решениях совпадают:

.

 

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

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

4. Обе из рассматриваемых задач имеют пустые допустимые множества.

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

 

	(13)
	(14)

 

Условия (13), (14) называются условиями дополняющей нежесткости. Из них следует, что если какое-либо неравенство системы ограничений одной из задач не обращается в строгое равенство оптимальным планом этой задачи, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в строгое равенство.

Таким образом, если , то

если , то

Точно так же, если , то

если , то

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

Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач и оценок в последней симплексной таблице:

 

х 1	х 2	…	хj	…	хn	xn +1	хn +2	…	хn + i	…	хn + m
		…		…				…		…
ym +1	ym +2	…	ym + j	…	ym + n	y 1	y 2	…	yi	…	ym
		…		…				…		…

 

Отсюда имеем оптимальный план двойственной задачи. Если прямая задача решается на максимум, то , .

Если прямая задача решается на минимум, тогда .

 

Пример 7. Для исходной задачи

 

 

построить двойственную и решить ее симплексным методом. Записать решение исходной и двойственной задач.

 

Решение

Двойственная задача будет иметь две переменные y ₁ и y ₂, так как исходная задача содержит два ограничения. Используя общее правило записи двойственной задачи, получим

 

 

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

Рассмотрим второй случай построения начального опорного плана. Сведем задачу к каноническому виду. Для этого добавим к левым частям неравенств дополнительные переменные y ₃, y ₄, y ₅, которые в целевую функцию вводятся с коэффициентами, равными нулю.

Итак, задача примет следующий вид:

Система имеет предпочтительный вид. Предпочтительные переменные y ₃, y ₄, y ₅ – базисные, а y ₁, y ₂ – свободные. Свободные переменные приравниваются к нулю, а базисные – к свободным членам.

Следовательно, начальный опорный план примет следующий вид:

При этом f (x ₀) = 0.

Составим симплексную табл. 11.

Таблица 11

БП	сБ	А 0	y 1	y 2	y3	y 4	y 5
y 3				(3)
y 4
y 5
fi – ci		–2	–5

Так как в индексной строке (f -строке) существуют отрицательные оценки, то план x ₀ неоптимален.

От табл. 11 нужно перейти к следующей. Переход осуществляем следующим образом: разрешающий столбец находим по max{|–2|; |–5|} = 5, разрешающая строка определяется по

На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент 3.

Теперь составим табл. 12. Вместо y ₃ в базис вводим y ₂. На месте разрешающего элемента пишем 1, все остальные элементы разрешающего столбца равны нулю. Элементы разрешающей строки делятся на разрешающий элемент. Все остальные элементы табл. 12 вычисляются по правилу прямоугольника.

Таблица 12

БП	сБ	А 0	y 1	y 2	y 3	y 4	y 5
y 2
y 4					–1
y 5
fi – ci

 

В индексной строке нет отрицательных оценок. Следовательно, получен оптимальный план

y ^* = y_отп = (0; 5; 0; 15; 5), f _max(y ^*) = 25.

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

 

y 1	y 2	y 3	y 4	y 5
x 4	x 5	x 1	x 2	x 3

Имеем ,

Итак, решение исходной задачи найдено.

Ответ: , ,

 

Вопросы для самоконтроля

 

1. Определение двойственной задачи в линейном программировании.

2. Модели двойственных задач.

3. Правила для построения двойственной задачи.

4. Основные теоремы теории двойственности и достаточный признак оптимальности.

5. Экономический смысл теорем двойственности, экономическая интерпретация свойств двойственных оценок.

 

 

Транспортная задача

 

4.1. Постановка транспортной задачи по критерию
стоимости в матричной форме

 

В m пунктах отправления A ₁, A ₂, …, A_m, которые в дальнейшем будем называть поставщиками, сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим a ₁, a ₂,…, a_m. Данный продукт потребляется в n пунктах B ₁, B ₂,…, B_n, которые будем называть потребителями; объем потребления обозначим b ₁, b ₂, …, b_n. Известны расходы (транспортные издержки) на перевозку единицы продукта из пункта A_i (i = 1, 2, …, m) в пункт B_j (j = 1, 2, …, n), которые равны c_ij и приведены в матрице транспортных расходов (издержек) C = (c_ij).

Требуется составить план перевозок, при котором весь продукт вывозится из пунктов A_i в пункты B_j в соответствии с потребностью и общая величина транспортных расходов (издержек) будет минимальной.

Обозначим количество продукта, перевозимого из пункта A_i в пункт B_j, через x_ij. Предполагается, что все x_ij ³ 0. Совокупность всех переменных x_ij для краткости обозначим X.

В математической форме задача линейного программирования имеет следующий вид:

 

	(15)
	(16)
	(17)

 

при этом (15) – целевая функция, (16) – ограничения по потребностям и запасам, (17) – условие неотрицательности.

Стоимость всех перевозок выражается линейной функцией (15). Условия (16) означают полное удовлетворение спроса во всех пунктах потребления и определяют полный вывоз продукции от всех поставщиков.

Для наглядности условие транспортной задачи (ТЗ) можно представить таблицей, которую будем называть распределительной. Распределительную таблицу называют иногда табличной или матричной моделью ТЗ (матрицей планирования).

Матрицу X = (x_ij) _{m ´ n} будем называть матрицей перевозок,матрицу C = (c_ij) _m´n – матрицей тарифов, а число c_ij – тарифом клетки (i; j).

Будем называть план перевозок X = (x_ij) _{m ´ n} допустимым, если он удовлетворяет ограничениям (16).

Допустимый план перевозок, доставляющий минимум целевой функции (15), называется оптимальным.

 

Таблица 13

Потребители, Вj	В 1	В 2	…	Вп	Запасы, аi
Поставщики, Аi
	c 11	c 12		c 1 n
A 1	x 11	x 12	…	x 1 n	a 1
	c 21	c 22		c 2 n
A 2	x 21	x 22	…	x 2 n	a 2
	cm 1	cm 2		cmn
Am	xm 1	xm 2	…	xmn	am
Потребности, bj	b 1	b 2	…	bn

 

Теорема 8 (о существовании допустимого плана). Для того, чтобы ТЗ имела допустимые планы, необходимо и достаточно выполнение равенства

(18)

 

(сумма запасов продукта равна сумме спроса на него).

Условие (18) является условием баланса.