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

Говорят, что две задачи линейного программирования находятся в отношении двойственности, если они имеют структуру

(6.1)

(6.2)

В них с, х Î Е^п; y, b Î Е^m; A – (mxn) – матрица, x, y ³ 0; D, D^\ -области допустимых решений.

Как видно, в первой задаче, назовем ее прямой, целевая функция максимизируется, а во второй задаче, соответственно назовем ее двойственной, она минимизируется; размерность первой задачи – (nxm), т. е. п переменных и m ограничений, а размерность второй задачи – (mxn), т. е. m переменных и п ограничений.

Наиболее важными свойствами двойственных задач являются:

а) ; (6.3)

б) если существуют векторы x⁰ и y⁰, такие, что , то x⁰ является оптимальным решением прямой, а y⁰ – оптимальным решением двойственной задач;

в) для оптимальных решений справедливы условия дополняюшей нежесткости Слейтера

x^0T(A^Ty⁰ – c) = 0, (6.4)

y^0T(- Ax⁰ + b) = 0. (6.5)

Эти условия выражают «экономическую» сущность переменных: переменные х_j, j = 1, …, n, являются «теневыми» ценами для второй задачи. А переменные y_i, i = 1, …, m, - «теневыми» ценами для первой задачи. «Теневая» цена означает, что если какой либо ресурс b_i использован не полностью, т.е. аⁱx^* < b_i, то соответствующая двойственная переменная y_i0 равна нулю, т.е.

y_i0(аⁱx^* - b_i) = 0,, i = 1, …, m, (6.6)

аналогично, если имеет место a^jy > c_j, то нулю равна переменная x_j0 и выполняется условие

x_j0(a^jy - c_j) = 0. j = 1, …, n, (6.7)

В этих выражениях через a^j обозначены строки матрицы А, а через a^j – строки матрицы А^Т.

г) оптимальные решения x⁰ и y⁰ связаны с соответствующими элементами индексной строки симплексных таблиц соотношениями

(6.8)

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

Например, в таблице T₂ предыдущей задачи мы имеем

,

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

После решения двойственной задачи симплекс-методом, аналогичные соотношения находим и для двойственных переменных x_j0, j = 1, …, n.

Иллюстрируем соотношения двойственности на уже рассмотренном выше примере.

Прямая задача:

4x₁ + 3x₂ ≤ 12

x₁ ≤ 2, x₂ ≤ 3

x₁, x₂ ≥ 0

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

.

4y₁ + 1y₂ ≥ 2

3y₁ + 1y₃ ≥ 3

y₁, y₂, y₃ ≥ 0

Оптимальные решения прямой и двойственной задачи имеют вид (смотри выше)

x⁰ = x^* = (3/4, 3)^T; y⁰ = y^* = (1/2, 0, 3/2)^T,

f (x⁰) = 21/2 = (y⁰) = 21/2.

Эти решения удовлетворяют условиям дополняющей нежесткости Слейтера: