Решение. Обозначим через хij - количество станков, доставляемых с завода i на фабрику j

Обозначим через х_ij - количество станков, доставляемых с завода i на фабрику j. Тогда, с учетом того, что общая стоимость станко будет складываться из стоимости изготовления и доставки станка, будем иметь:

		Ответ: х 11 = 3; х 12 Î{0; 1; 2; 3}; x 21 = 0; x 22 = 7 - x 12.

Рис. 4.11

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

Задача 4 (см. рис. 4.12)

Как видно из рис. 4.12, оптимальная точка М (2;3) находится на пересечении трех граничных линий. Оптимальное значение целевой функции равно 26. Выпишем двойственную задачу и найдем ее решение.

.

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

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

Найдем для проверки правильности вычислений значение целевой функции:

, что подтверждает правильность вычислений.

Задача 4 (см. рис. 4.13)

Из рис. 4.13 видно, что оптимальные значения целевой функции будут достигаться всюду на ребре АВ допустимого множества, где А (1;3) – точка пересечения границ 2 и 3, а В (3;1) – точка пересечения границ 1 и 2. Это ребро задается уравнением . Значение целевой функции на нем равно

Посмотрим, каково оптимальное решение двойственной задачи.

Рассмотрим какую-нибудь внутреннюю точку С отрезка АВ. В ней активным является только одно ограничение – второе, ограничения 1 и 3 – не активны. Поэтому в двойственной задаче (в оптимальной точке) , Далее, поскольку обе координаты точки С не равны нулю, оба функциональных ограничения в двойственной задаче (в оптимальной точке) выполняются как равенства. Итак, имеем: Значение целевой функции, очевидно, равно 8.

Проверим, что получится, если вместо внутренней точки С взять конец отрезка, например, точку А. В этой точке неактивным является только одно ограничение – первое, координаты точки А, по-прежнему не равны нулю. Поэтому имеем:

т.е. получили тот же результат. Тот же результат, очевидно, получим, если вместо А возьмем точку В.

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

4.5. Анализ чувствительности оптимального решения к параметрам задачи линейного программирования

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

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

Рассмотрим эти вопросы подробнее и проиллюстрируем на примере задач с двумя переменными.

Пусть имеем задачу линейного программирования вида (4.1):

и пусть - функция, задающая оптимальные значения задачи (4.1) в зависимости от значений констант ограничений . Можно доказать, что эта функция в определенных пределах существует и является кусочно-линейной, а кроме того, , где - соответствующий множитель Лагранжа (двойственная переменная).

Из последнего равенства можно вывести приближенное равенство: . Это равенство можно трактовать так: увеличение константы на мелкую единицу влечет увеличение значения целевой функции на единиц. Таким образом, чем больше значение множителя Лагранжа (двойственной переменной), тем выгоднее увеличивать запас ресурса .

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

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

Назовем состав активных ограничений в оптимальной точке базисом разложения градиента целевой функции, или просто базисом (градиенты активных ограничений и в самом деле будут представлять базис, если их количество равно размерности задачи и сами они линейно независимы). Тогда приведенные рассуждения можно сформулировать следующим образом: изменение констант ограничений не вызывает изменения двойственных переменных (множителей Лагранжа), пока не происходит смены базиса.

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

Поиск по сайту: