Линейное программирование. Геометрическая интерпретация и графический метод решения задачи линейного программирования, страница 13

Введя m-мерный вектор-строку Y, построим стандартную задачу вида

                                min w = b₁y₁+ b₂y₂ +…+ b_my_{m  ,}

                                a₁₁y₁+a₂₁y₂+…+a_m1y_m  ³ c_{1 ,}

                                a₁₂y₁+a₂₂y₂+…+a_m2y_m  ³ c_{2  ,}

.   .   .   .   .   .   .   .   .   .   .                                     (2.27)

                                a_1ny₁+a_2ny₂+…+a_mny_m  ³ c_{n  ,}

                                y₁ ³0, y₂ ³0, …, y_m ³0 .

или в матричной записи:

min YB ; YA ³C ; Y ³0.                                      (2.28)

Задача (2.27) называется двойственной задаче (2.25). Соответственно задача (2.25) называется прямой по отношению к задаче (2.27).

Из сопоставления задач (2.25) и (2.27) определяются правила, в соответствии с которыми одна стандартная задача (прямая) преобразуется в другую (двойственную).

1) Задача максимизации переходит в задачу минимизации.

2) Вектор C коэффициентов целевой функции прямой задачи становится вектором ограничений двойственной задачи.

3) Вектор B ограничений прямой задачи становится вектором коэффициентов целевой функции двойственной задачи.

4) Матрица ограничений (условий) двойственной задачи получается в результате транспонирования матрицы ограничений (условий) прямой задачи.

5) Знаки неравенств в ограничениях меняются на обратные.

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

Обратим внимание на то, что если одна из двойственных задач стандартная, то и другая стандартная. Система ограничений в обоих случаях задана неравенствами. Поэтому задачи (2.25) и (2.27) называются симметричными. Связь между ограничениями симметричных задач удобно отразить с помощью следующей схемы:

a_ijx_j£b_i , i=1, …, m   «   y_i ³ 0, i=1, …, m;

x_j ³ 0, j = 1, …, n   «   a_ijy_i ³ c_j, j=1, …, n, откуда видно, что каждому ограничению одной задачи сопоставлена переменная с тем же номером другой задачи; каждой переменной одной задачи сопоставлено ограничение с тем же номером другой задачи.

Рассмотрим теперь каноническую задачу

max z  = CX ; AX=B ; X³0.                                       (2.29)

Описанные правила построения двойственной задачи можно применить к задаче (2.29), если предварительно записать ее в виде стандартной задачи. В итоге задача, двойственная канонической, принимает вид

min w  = YB ; YA³C,                                               (2.30)

причем на вектор Y не накладывается  условие неотрицательности.

Можно также проверить, что задача, двойственная (2.30), совпадает с (2.31), а двойственная (2.27), совпадает с (2.25). Поэтому прямую и двойственную задачи называют также взаимодвойственными. Взаимодвойственные задачи (2.29) и (2.30) называются несимметричными, так как в прямой задаче система ограничений задана равенствами, а в двойственной – неравенствами. В прямой задаче все переменные - неотрицательные, в двойственной же задаче они могут быть отрицательными.

Полный набор постановок взаимодвойственных задач, учитывающий все возможные варианты экстремумов, приведен в [4]. Отметим также, что взаимодвойственным задачам может быть дана экономическая интерпретация [4,5].

Рассмотрим далее взаимосвязи между прямой и двойственной задачами. Для их описания используется теорема двойственности, доказательства которой приведены в [4, 6]. Она может быть сформулирована следующим образом: если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет оптимальное решение, причем значения их целевых функций равны.

Рассмотренная теорема позволяет при решении одной из двойственных задач находить оптимальный план другой.

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