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

Пример проведения анализа устойчивости будет рассмотрен в разделе 5.6.4. Вопрос о том, изменятся ли теневые цены в задаче о кондитерской фабрике при изменении запасов сахарного песка, патоки и фруктового пюре на 1 т, или на 10 т и т.п., будет решен в разделе 6.6.2.

Задача производственного планирования позволяет также выявить экономический смысл дополнительных переменных двойственной задачи.

Если привести двойственную задачу к канонической форме с помощью дополнительных переменных и затем построить к ней двойственную, то переменные этой новой задачи должны быть не ограничены по знаку (так как соответствуют ограничениям-равенствам). Но поскольку дополнительные переменные входят по одной в каждое ограничение с коэффициентом 1 и все в целевую функцию с коэффициентом 0, им в новой задаче будут соответствовать новые ограничения х₁ ³ 0, . . . х_j ³ 0, . . . х_n ³ 0, которые сами по себе определяют знак переменных; т.е. эта задача будет эквивалентна исходной.

Для исходной задачи, записанной в таком виде, тоже выполняются теоремы двойственности. При этом по теореме о равновесии если дополнительная переменная двойственной задачи отлична от нуля, то соответствующее ей ограничение исходной задачи будет выполняться как равенство, т.е. х_j = 0, переменная небазисная. Если изменить свободный член (0) на единицу, получим х_j ³ 1 (при таком условии эта переменная обязательно должна стать базисной, т.к. нулевой она уже быть не может). По теореме об оценке значение двойственной оценки показывает, на сколько изменится оптимум при изменении свободного члена на единицу. Таким образом, дополнительная переменная двойственной задачи показывает, на сколько изменится оптимум при включении небазисной переменной в базис с единичным значением.

В задаче производственного планирования дополнительная переменная двойственной задачи может быть отлична от нуля только для тех видов продукции, которые выпускать вообще не выгодно. Эта переменная показывает, на сколько уменьшится оптимальная прибыль, если обязательно требуется выпустить хотя бы единицу такого вида продукции. Дополнительные переменные двойственной задачи иногда называют сокращенными затратами (сокращенными за счет отказа от выпуска некоторого вида продукции), или редуцированной стоимостью.

Поскольку в задаче, решенной в разделе 3.3, было выгодно выпускать оба вида карамели – и «Снежинку», и «Яблочную», - обе дополнительные переменные равнялись нулю. Предположим, что при других величинах прибыли на тонну карамели выпускать «Яблочную», стало невыгодно, и х₂^*= 0 (фабрика выпускает только карамель «Снежинка»). Тогда переменная у₅^* могла бы быть отличной от нуля. Предположим, что она оказалась равна, например, 3,75. Это означало бы, что если фабрику обяжут выпустить хотя бы 1 тонну карамели «Яблочная», ее оптимальная прибыль при этом уменьшится на 3,75 руб. (см. раздел 6.8).

Обычно решение задачи линейного программирования дополняется анализом чувствительности (постоптимизационным анализом), который включает в себя:

а) нахождение оптимального плана двойственной задачи;

б) анализ устойчивости двойственных оценок;

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

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

5.6 Пример решения сопряженных задач

5.6.1 Задача, двойственная задаче о диете

Проиллюстрируем выполнение теорем двойственности на примере задачи о диете (см. раздел 1.3.1).

Построим задачу, двойственную к задаче о составлении рациона, решение которой было найдено в разделе 4.2 (в которой минимальное содержание белка в рационе должно составлять 44 г, а не 110 г).

Для этого вначале необходимо добиться, чтобы во всех неравенствах прямой задачи стоял знак ³ (так как задача на минимум), т.е. умножить обе части второго и четвертого ограничения на -1: