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

Задачи 1 и 2 дают пример пары симметричных двойственных задач. В общем виде такие задачи могут быть записаны так:

З а д а ч а 1.

Задача 2.

Таким образом, две задачи линейного программирования называются симметричными взаимно-двойственными, если:

а) в каждой задаче все неравенства в системе ограничений одного смысла, причем если эти неравенства смысла «≤», то функция цели стремится к максимуму, в другой задаче – все наоборот;

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

в) если одна задача содержит n неизвестных и m ограничений, то в другой из них наоборот, m неизвестных и n ограничений;

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

д) все неизвестные в обеих задачах неотрицательны.

Пример. Построим задачу, двойственную данной, если исходная задача имеет вид:

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

Функция цели f стремится к максимуму, поэтому смысл обоих неравенств должен быть «≤». Умножив обе части первого неравенства на -1, придем к задаче, для которой может быть построена симметричная двойственная задача.

Задача 1.

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

Задача 2. записывается следующим образом:

Основные теоремы теории двойственности

Вернёмся к задачам 1 и 2. При их решении мы, в частности, получили . Оптимальные значения функций цели совпали. Случайно ли это? Ответ на этот вопрос даёт первая теорема двойственности, которую приведём без доказательства.

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

Познакомимся ещё с одной интересной и полезной теоремой. Она позволяет найти оптимальное решение двойственной задачи, не решая её! Называется эта теорема второй основной теоремой двойственности. Прежде чем её сформулировать, проделаем следующие преобразования: ограничения взаимно-двойственных задач запишем в форме уравнений. К левой части каждого неравенства в задаче 1 прибавим вспомогательную неотрицательную переменную, что поможет восстановить нарушенный баланс:

(1)

Неотрицательные «довески» позволили уравнять левые и правые части ограничений.

Точно также поступим и в отношении системы ограничений задачи 2. Только здесь неотрицательные вспомогательные переменные придётся вычитать из левых частей неравенств:

(2)

Системы линейных уравнений (1) и (2) содержат по m + n неизвестных. В первой из них n основных и m вспомогательных, а во второй – наоборот: m основных и n вспомогательных. Запишем все ив таблицу:

1	Основные переменные	Вспомогательные переменные
(А)
2
(В)	Вспомогательные переменные	Основные переменные

Переменные, находящиеся в одном и том же столбце таблицы, будем называть соответствующими.

Теорема 2. Если в оптимальном плане одной из взаимно-двойственных задач значение основной переменной положительно, то соответствующая ей вспомогательная переменная другой задачи равна нулю. И наоборот, из положительности вспомогательной переменной следует равенство нулю соответствующей ей основной переменной в оптимальном плане двойственной задачи.

Покажем теперь, как, используя вторую теорему двойственности можно найти оптимальный план двойственной задачи. Мы нашли графическим способом оптимальный план в задаче В₂. Найдём оптимальный план для задачи А₂. Перейдём от неравенств к уравнениям так же, как это делается при переходе к задаче канонической формы.

Уравнения для задачи А₂ имеют вид:

а)

а для задачи В₂:

б)

Составим таблицу соответствия переменных:

Основные			Вспомогательные
x1	x2	x3	x4	x5
?	?	0	0	0
0	0	5	1	2
y3	y4	y5	y1	y2
Вспомогательные			Основные

Заполним строку y_i.

Значения y₁ = 1 и y₂ = 2 мы нашли графическим способом.

Из уравнений системы (б) находим:

По второй теореме двойственности:

x₃ = 0, так как y₅ = 5 > 0,

x₄ = 0, так как y₁ = 1 > 0,

x₅ = 0, так как y₂ = 2 > 0.

Осталось найти x₁ и x₂. Найденные нулевые x_i подставим в систему (а). Получим систему:

Её решение находится без труда.

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

для задачи А₂ найден. Далее можно вычислить .

Пример. Решим задачу линейного программирования:

(3)

(4)

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

Двойственная задача, очевидно, записывается в виде

(5)

(6)

Множество её допустимых значений ограничено. Это треугольник АВС. Функция цели достигает максимума в точке В.

(l₁)

(l₂)

(l₂)

Для отыскания её координат решим систему линейных уравнений (7):

(7)

Решение системы имеет вид:

Итак,

По первой основной теореме двойственности

(8)

.

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

(9)

и

(10)

В системе (10) вместо y₁ и y₂ подставим найденные выше их оптимальные значения y₁ = y₂ = 2,4. Это позволит найти значения вспомогательных переменных:

Подумайте: случайно ли y₃ и y₅ оказались равными нулю?

Заполним таблицу, используя полученные данные и вторую основную теорему двойственности:

	Основные переменные			Вспомогательные переменные
(3)	x1	x2	x3	x4	x5
(4)	?	0	?	0	0
(5)	0	0,8	0	2,4	2,4
(6)	y3	y4	y5	y1	y2
	Вспомогательные переменные			Основные переменные

Подставим в (9) вместо x₂, x₄ и x₅ нули. Получим систему двух линейных уравнений с двумя неизвестными:

Отсюда

Теперь можно записать оптимальный план исходной задачи:

Выводы:

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

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

3. Если в задаче 1 все неравенства смысла «≥» и функция цели стремится к min, то в двойственной задаче – наоборот: все неравенства смысла «≤», а функция цели стремится к max.

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

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

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

7. Оптимальные значения функций цели задач 1 и 2 совпадают.

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