5 Двойственность в линейном программировании 83

5.1 Понятие двойственности 83

5.2 Экономическая интерпретация двойственной задачи 87

5.3 Первая теорема двойственности 88

5.4 Вторая теорема двойственности 90

5.5 Третья теорема двойственности 92

5.6 Пример решения сопряженных задач 96

5.6.1 Задача, двойственная задаче о диете 96

5.6.2 Выполнение основной теоремы двойственности 97

5.6.3 Выполнение теоремы о равновесии 99

5.6.4 Выполнение теоремы об оценке 99

5.7 Вопросы и упражнения 106

5 Двойственность в линейном программировании

5.1 Понятие двойственности

Рассмотрим задачи линейного программирования в стандартной форме, записанные в матричной форме:

max CX

(20)

,

где С = (с₁. . . с_n), X =, B =, A =

min YB

(21)

,

где Y= (y₁. . .y_m).

Здесь X, Y - переменные^*; A, B, C - константы.

Задача (21) и любая эквивалентная ей задача линейного программирования называется двойственнойзадаче (20) и любой эквивалентной ей задаче.

Подчеркнем, что новых переменных вводится ровно столько, сколько в задаче (20) ограничений, т.е. m.

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

Исходную задачу, по отношению к которой строится двойственная, иногда еще называют прямой задачей.

Теорема (о сопряженных задачах). Задача, двойственная двойственной, эквивалентна исходной.

Доказательство. Построим задачу линейного программирования, двойственную (21). Поскольку определение дает возможность построить двойственную задачу только для задачи в той же форме записи, что и задача (20), вначале преобразуем задачу (21) таким образом, чтобы форма ее записи была такой же.

Приведем задачу (21) к стандартной форме на максимум:

mах Y(-B)

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

mах -B^ТY^Т

Теперь можно построить двойственную задачу в соответствии со сформулированным определением. Введем строку переменных Z.

min Z(-C^T)

Эта задача является двойственной к двойственной. Преобразуем ее.

mах СZ^Т

Эта задача эквивалентна задаче (20) с точностью до обозначения.

Теорема доказана.

Таким образом, двойственность является взаимной. Пара взаимно двойственных задач называется парой сопряженных задач.

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

Построим теперь двойственную задачу. Отметим, что число ограничений задачи возросло в два раза (каждое уравнение преобразовано в два неравенства). Вектор-строку переменных двойственной задачи разобьем на две части, в каждую из которых будет входить равное число переменных, и обозначим его (U,V) = (u₁, …,u_m,v₁, …,v_m).

При этом во всех линейных выражениях компоненты вектора В и матрицы А можно вынести за скобки, а в скобках останется разность векторов U = (u₁, …,u_m) и V = (v₁, …,v_m). Например, при перемножении строки переменных на первый столбец матрицы А будет получено: (a₁₁u₁+a₂₁u₂+ …+ a_m1u_m - a₁₁v₁ - a₂₁v₂ - … - a_m1v_m = a₁₁(u₁ - v₁) + a₂₁(u₂ – v₂) + … + a_m1(u_m – v_m); - и т.д.

Обозначим U - V = Y. При этом переменные Y = (u₁-v₁; …;u_m–v_m) = = (y₁. . .y_m) не ограничены по знаку. Тогда двойственная задача примет вид:

min YB

YA  C

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

На основании проведенных рассуждений можно сделать вывод, что для построения двойственной задачи не обязательно каждый раз приводить задачу линейного программирования к стандартной форме, а именно нет необходимости преобразовывать уравнения к неравенствам, а не ограниченные по знаку переменные - к неотрицательным. Пусть в задаче в смешанной форме первые m` ограничений – уравнения, а остальныеm-m` - неравенства; и первыеn` переменных неотрицательны, а остальныеn-n` переменных по знаку могут быть любыми. Между задачей линейного программирования в смешанной форме и двойственной ей задачей линейного программирования можно установить следующее соответствие:

max cjxj	min biyi
aijxj = bi,	(22) aijyicj,
aijxjbi,	aijyi = cj,
xj0,	yi0,
xj 0,	yi 0,

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

а) Переменные двойственной задачи соответствуют ограничениям исходной задачи, а ограничения - переменным.

б) Если исходная задача линейного программирования задана на максимум, то двойственная строится на минимум, и наоборот.

в) В задаче линейного программирования на максимум в ограничениях-неравенствах должен стоять знак , а на минимум -.

г) Ограничениям-неравенствам исходной задачи соответствуют неотрицательные двойственные переменные, а уравнениям – не ограниченные по знаку переменные.

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

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

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

min 2х₁+ 3х₂ - 4х₃ + х₅

4х₁- 3х₂ - х₃+ х₄ + х₅ 10

х₁+ 4х₂ + х₃ + х₅= 15

2х₁- 4х₂ - х₃+ х₄ 3

х_{1-3, 5} 0

Так как задача на минимум, умножим обе части первого ограничения на -1, чтобы получить знак неравенства : -4х₁+ 3х₂ + х₃- х₄ - х₅  -10.

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

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

Первое ограничение двойственной задачи соответствует переменной х₁прямой задачи, поэтому коэффициенты этого ограничения берут из столбца коэффициентов при х₁, а свободный член – из целевой функции прямой задачи. Так как х₁0, это ограничение – неравенство. Так как двойственная задача на максимум, знак неравенства. Аналогично строятся второе, третье и пятое ограничения. Четвертое ограничение соответствует переменной х₄, знак которой может быть любым. Поэтому оно – уравнение.

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

max -10y₁ + 15y₂ + 3y₃

-4y₁ + y₂ + 2y₃  2

3y₁ + 4y₂ - 4y₃  3

y₁ + y₂ - y₃  -4

-y₁ + y₃ = 0

-y₁+y₂1

y_1,3 0