 |
ПРИМЕР ГРАФИЧЕСКОГО РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Обратимся к целевой функции. Ее градиент есть вектор (32; 27). Для решения задачи следует изобразить этот вектор в виде стрелки с началом в точке (0; 0) и концом в точке (32; 27).
Такая стрелка является короткой и поэтому плохо различимой на чертеже. Однако длина этой стрелки не играет никакой роли при решении задачи. Важно лишь ее направление. Если обе координаты точки (32; 27) умножить или разделить на одно и то же положительное число, то изменится лишь длина стрелки, но не ее направление. Поэтому на результате решения задачи это не скажется.
Удлиним стрелку до границы нашего рисунка (Рис. 2.5 ).
Все линии уровня целевой функции параллельны друг другу и перпендикулярны градиенту. На Рис. 2.5 пунктиром изображены линии, соответствующие различным значениям целевой функции, начиная от 10000 и с шагом 16000. Разумеется, такие линии могут быть построены для любых значений целевой функции, они параллельны и все вместе покрывают координатную плоскость.
Градиент показывает направление роста целевой функции. Мы решаем задачу на максимум. Чем больше значение целевой функции, тем лучше. Однако при слишком больших значениях пунктирная линия уровня окажется за пределами области допустимых планов.
Рис. 2.6. Построение оптимального плана
В своем крайнем положении линия уровня проходит через точку L. Таким образом, точка L является оптимальным планом задачи. Это единственная точка, принадлежащая одновременно области допустимых планов и линии уровня в ее крайнем положении. Следовательно, наша задача обладает единственным оптимальным планом.
Найдем координаты оптимального плана. Приближенно их можно определить по чертежу. Для точного расчета необходимо решить соответствующую систему уравнений. Точка L лежит на границе первого и четвертого ограничений. Составляем систему уравнений:
Решив эту систему, получаем компоненты оптимального плана: x1 = 1250 и x2 = 667. Таким образом, оптимальный план X*max равен:
.
Он предписывает выпустить 1250 кг Печенья и 667 (точнее, 666,667) кг Бисквитов.
Для определения оптимума следует подставить компоненты оптимального плана в целевую функцию задачи. Оптимум Z*max определяется равенством:
.
Таким образом, реализация выпущенной продукции даст выручку в размере 58000 руб. Задача решена. Теперь следует обратиться к экономическому содержанию задачи и проанализировать полученный результат.
Рассмотрим, для полноты картины, задачу, когда при той же системе ограничений и той же целевой функции требуется найти не максимальное, а минимальное ее значение. В этой ситуации все рассуждения, связанные с построением области допустимых планов и градиента полностью сохраняются. Однако для нахождения оптимального плана следует теперь смещать линию уровня до крайнего положения в направлении, противоположном градиенту. Оптимальным планам для задачи на минимум окажется точка О - начало координат. Оптимум будет равен 0.
