Введение в проблему двойственности

Прямая задача линейного программирования ставится следующим образом. Находят значения переменных (х₁, х₂,..., x_n), удовлетворяющие условиям:

a₁₁x₁ +... + a_{1 l} x _l + a₁, _{l +1}x _{l +1} +... + a_1nx_n = b₁

.....................................

a_k1x₁ +... + a_{k l} x _l + a_{k, l +1}x _{l +1} +...+ a_knx_n = b_k

(2.11)

a_k+1,₁x₁ +... + a_k+1, _l x _l + a_k+1, _{l +1}x _{l +1} +... + a_k+1,_nx_n ≤ b_k+1

.....................................

a_m1x₁ +... + a_{m l} x _l + a_{m, l +1}x _{l +1} +... + a_mnx_n ≤ b_m,

обращающим в максимум линейную форму

L = c₁x₁ +... + c_nx_n → max.

При этом допускается, что часть переменных x₁,..., x_{1 l} имеет любые знаки, а переменные x _{l +1},...,x_n ³ 0.

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

a₁₁y₁ +... + a_k1y_k + a_k+1,₁y_k+1 +... + a_m1xy_m = c₁

.....................................

a_{1 l} y₁ +... + a_{k l} y_k + a_{k+1, l} y_k+1 +... + a_{m l} y_m = c _l

(2.12)

a₁, _{l +1}y₁ +... + a_{k, l +1}y_k + a_{k+1, l +1}y_k+1 +... + a_{m, l +1}y_m ³ c _{l +1}

.....................................

a_1ny₁ +... + a_kny_k + a_k+1,ny_k+1 +... + a_mnxy_m ³ c_n,

обращающим в минимум линейную форму

L′ = b₁y₁ +... + b_my_m → min.

Здесь переменные y₁,..., y_k также могут иметь произвольные знаки, а y_k+1,..., y_m ³ 0. Заметим, что l равенствам (2.12) соответствуют свободные переменные x₁,..., x _l, а n – l неравенствам – неотрицательные переменные прямой задачи x _{l +1},..., x_n. И наоборот, k равенствам прямой задачи (2.11) соответствуют свободные (неограниченные по знаку) переменные y₁,..., y_k, а n – k неравенствам – неотрицательные переменные y_k+1,..., y_m двойственной задачи.

Коэффициенты b_j, стоящие в правой части ограничений прямой задачи, фигурируют как коэффициенты линейной формы в двойственной задаче, а коэффициенты линейной формы прямой задачи становятся коэффициентами правых частей ограничений двойственной задачи. Матрица А^T коэффициентов левых частей ограничений двойственной задачи является транспонированной матрицей А коэффициентов левых частей прямой задачи. Запишем эти матрицы в виде

(2.13)

А = ||a_ij||;

А^T = ||a_jI||.

Если нет специальных оговорок, далее используется матрица прямой задачи с m строками и n столбцами и i меняется от 1 до m, а j – от 1 до n. Поэтому переменные и коэффициенты имеют, соответственно, индексы x_j, a_ij, y_i, b_i, c_j. Соответственно число ограничений двойственной задачи равно числу неизвестных n прямой, а число неизвестных двойственной задачи равно числу ограничений m прямой задачи.

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

minL′ = maxL,

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

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