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

Заданным значениям констант задачи линейного программирования соответствуют оптимальный план и оптимум (если они существуют). При изменении констант решение задачи также будет изменяться (т.е. другим исходным данным может соответствовать другое решение). Рассмотрим оптимум задачи, как функцию от свободных членов ограничений Z^*(B) (в самом деле, каждому набору значений свободных членов будет соответствовать одно значение оптимума, если задача разрешима).

Теорема 3 (об оценке). Частные производные Z^*(B) по элементам столбца свободных членов равны оптимальным значениям соответствующих двойственных переменных:

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

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

Например, для задачи, решенной в разделе 3.3, теневые цены сахарного песка, патоки и фруктового пюре равны соответственно у₁^* » 125; у₂^* = 0 и у₃^* » 773. Это означает, что при увеличении запасов сахарного песка на одну тонну оптимальная прибыль фабрики возрастет на 125 руб., при увеличении запасов патоки эта прибыль не изменится, а на каждую тонну увеличения запасов фруктового пюре рост прибыли составит 773 руб.

Если исходные данные задачи изменятся, и будет известно, что запасы сахарного песка составляют, например, 810 т, то для определения оптимальной прибыли нет необходимости решать задачу заново. В самом деле, зная, что запас сахара возрос на 810 – 800 = 10 (т), можно сделать вывод, что прибыль возросла на 125*10 = 1250 (руб.). Т.к. ранее оптимальная прибыль составляла 193067 руб., то можно подсчитать, что при новых запасах сахарного песка она составит 193067 + 1250 = 194317 (руб.).

Однако следует помнить о том, что элементы столбца свободных членов являются коэффициентами целевой функции двойственной задачи. При изменении коэффициентов целевой функции на некотором интервале оптимальный план задачи остается неизменным, но за его пределами происходит переход к другому оптимальному плану, и третья теорема двойственности теряет свой смысл. Это хорошо видно на рисунке 27 (при графическом решении задачи с изменением коэффициентов целевой функции изменяются координаты ее градиента, который при этом как бы «поворачивается»).

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

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