Условия двойственности

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

(21)

(22)

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

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

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

а) ; (23)

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

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

x^*T(A^Ty^* – c) = 0, (24)

y^*T(- Ax^* + b) = 0. (25)

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

y_i^*(аⁱx^* - b_i) = 0,, i = 1, …, m. (26)

Аналогично, если имеет место a^jy^* > c_j, то соответствующая двойственная переменная x_j^* равна нулю, и должно выполняться условие

x_j^*(a^jy^* - c_j) = 0. j = 1, …, n, (27)

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

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

(28)

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

Например, в таблице T₂ первой части работы имеем

,

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

После решения двойственной задачи симплекс-методом, аналогичные соотношения находим и для двойственных переменных x_j^*, 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.

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