Двойственность в линейном программировании, страница 8

Если рассмотреть критериальную строку таблицы 19, можно заметить, что÷D₃ç = 29,889 = у₈. В самом деле, переменной х₃ соответствует третье ограничение двойственной задачи, в котором дополнительной переменной является как раз переменная у₈. Коэффициент ÷D₆ç = 0,122 = у₃. В самом деле, дополнительная переменная х₆ прямой задачи стоит как раз в ее третьем ограничении, которому соответствует двойственная переменная у₃.

Коэффициенты при основных переменных х₁ и х₂ D₁ = D₂ = 0, так как дополнительные переменные двойственной задачи в ее первых двух ограничениях соответственно у₆ = у₇ = 0. Коэффициенты при дополнительных переменных х₄, х₅ и х₇ D₄ = D₅ = D₇ = 0, так как основные переменные двойственной задачи, которые соответствуют первому, второму и четвертому ограничениям у₁ = у₂ = у₄ = 0.

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

Теперь сравним столбец В таблицы 19 (из которого следовало, что Х^* = (0,011; 0,489; 0; 0,711; 1,289; 0; 15,222), с последней строкой в таблице 20 (критериальной строкой оптимальной симплексной таблицы для двойственной задачи). Здесь D₁ = 0,711 = х₄ (поскольку переменной у₁ соответствует первое ограничение прямой задачи, в котором дополнительной была переменная х₄). Аналогично можно объяснить, почему D₂ = 1,289 = х₅, D₃ = 0 = х₆, а D₄ = 15,222 = х₇. Поскольку пятое ограничение прямой задачи – уравнение, и разность между его частями всегда равна нулю, D₅`= D₅``= 0.

Рассмотрим коэффициенты при дополнительных переменных двойственной задачи. Поскольку эти переменные у₆, у₇ и у₈ стоят в трех ограничениях двойственной задачи, которым соответствуют три основные переменные прямой задачи х₁, х₂ и х₃, оказывается, что D₆ = 0,0111 = х₁, D₇ = 0,489 = х₂, а D₈ = 0 = х₃.

Мы убедились в том, что оптимальный план прямой задачи находится в критериальной строке оптимальной симплексной таблицы для двойственной задачи (так и должно было оказаться, поскольку двойственность взаимна).

5.6.3 Выполнение теоремы о равновесии

Теперь убедимся в том, что выполняется вторая теорема двойственности. Для этого установим соответствие между переменными сопряженных задач в виде таблицы 21. В каждой строке этой таблицы записаны соответствующие друг другу переменные и ограничения сопряженных задач (и оптимальные значения переменных). В пятом ограничении прямой задачи дополнительной переменной нет, но в графе «значение» все равно указан ноль, так как разность между частями уравнения равна нулю. При перемножении двух значений во всех восьми строках получается ноль (х₁*y₆ = 0,011*0 = 0; х₂*y₇ = 0,489*0 = 0; …; х₇*y₄ = 15,222*0 = 0; 0*y₅ = 0*4 = 0).

Таблица 21 – Соответствие между переменными сопряженных задач

5.6.4 Выполнение теоремы об оценке

В условиях задачи сказано, что недельный рацион должен содержать не менее 4, но не более 6 г кальция; не менее 110 г белка; не более 25 г клетчатки; и этой смеси должно быть ровно 500 г. Предположим, что эти величины могут меняться. Чтобы узнать, на сколько при этом изменится оптимальная стоимость рациона, в соответствии с третьей теоремой двойственности надо воспользоваться теневыми ценами y_1-5, которые соответствуют ограничениям прямой задачи. Но для этого вначале следует провести анализ устойчивости теневых цен.