Теорема 2 (вторая теорема двойственности).
Планы х* и у* оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задач I и II соответственно хотя бы одно из любой пары сопряженных неравенств обращается в равенство.
Доказательства теорем опускаем, а на конкретном примере посмотрим связь в паре двойственных задач.
Итак, имеем исходную задачу I, которую мы решили в п. 3.8, и ее оптимальное решение х* = (0, 40, 0, 100) и F(х*) = 700.
Найдем решение двойственной задачи II у* = (у1, у2, у3) из п. 3.9.1, не прибегая к симплекс-методу, а воспользовавшись второй теоремой двойственности и известным оптимальным планом х*.
Рассмотрим выполнение неравенств задачи I при подстановке х* в систему ограничений.
Поскольку 1, 5, 7 неравенства строгие (имеют знак "<" или ">"), то соответствующие им неравенства в задаче II из пары сопряженных обязаны обратиться в равенства. имеем:
или
т. е. у* = (0, 1, 4) - оптимальное решение.
Заметим, что действительно G(y*) = 400y1 + 300y2 + 100y3 = 400 · 0 + 300 · 1 + 100 · 4 = 700 = F(x*).
Итак, в силу второй теоремы двойственности мы очень быстро нашли оптимальное решение задачи II, пользуясь условием обращения в равенство хотя бы одного из пары сопряженных неравенств в системах ограничений двойственных задач.
Между переменными исходной задачи и переменными двойственной существует глубокая связь. А именно: после приведения обеих задач I и II к каноническому виду основные и дополнительные переменные задач соответствуют друг другу следующим образом:
Установив такую связь, внимательный читатель заметит, что, решив задачу I симплекс-методом и получив последнюю симплекс-таблицу (табл. 3.15), мы фактически решим и задачу II.
Запишем таблицу 3.15, учитывая соответствие между переменными хi и yj (табл. 3.16).
Таблица 3.16
у4 | у2 | у6 | у3 | |||
базисные | -х1 | -х6 | -х3 | -х7 | свободные | |
у1 | х5 | 334 | ||||
у5 | х2 | 40 | ||||
у7 | х4 | 100 | ||||
-F | 1 | 1 | 1 | 4 | 700 |
В силу соответствия и II теоремы двойственности переменные у1, у5, у7 обязаны равняться 0, т. к. х5, х2, х4>0 строго. А переменные у4, у2, у6, у3 принимают значения из индексной строки 1, 1, 1, 4 соответственно, т. к. им соответствующие переменные х1, х6, х3, х7 = 0, как свободные. Итак, из последней таблицы задачи II, не проводя даже никаких вычислений и пользуясь лишь соответствием переменных:
у* = (у1*, у2*, у3*, у4*, у5*, у6*, у7*) = (0, 1, 4, 1, 0, 1, 0).