Построение градиента и определение оптимального плана

Обратимся к целевой функции. Ее градиент есть вектор (32; 27). Для решения задачи следует изобразить этот вектор в виде стрелки с началом в точке (0; 0) и концом в точке (32; 27).

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

Удлиним стрелку до границы нашего рисунка (Рис. 2.5).

Все линии уровня целевой функции параллельны друг другу и перпендикулярны градиенту. На Рис. 2.5 пунктиром изображены линии, соответствующие различным значениям целевой функции, начиная от 10000 и с шагом 16000. Разумеется, такие линии могут быть построены для любых значений целевой функции, они параллельны и все вместе покрывают координатную плоскость.

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

Рис. 2.6. Построение оптимального плана

В своем крайнем положении линия уровня проходит через точку L. Таким образом, точка L является оптимальным планом задачи. Это единственная точка, принадлежащая одновременно области допустимых планов и линии уровня в ее крайнем положении. Следовательно, наша задача обладает единственным оптимальным планом.

Найдем координаты оптимального плана. Приближенно их можно определить по чертежу. Для точного расчета необходимо решить соответствующую систему уравнений. Точка L лежит на границе первого и четвертого ограничений. Составляем систему уравнений:

Решив эту систему, получаем компоненты оптимального плана: x₁ = 1250 и x₂ = 667. Таким образом, оптимальный план X*_max равен:

.

Он предписывает выпустить 1250 кг Печенья и 667 (точнее, 666,667) кг Бисквитов.

Для определения оптимума следует подставить компоненты оптимального плана в целевую функцию задачи. Оптимум Z*_max определяется равенством:

.

Таким образом, реализация выпущенной продукции даст выручку в размере 58000 руб. Задача решена. Теперь следует обратиться к экономическому содержанию задачи и проанализировать полученный результат.

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

24. Основные теоремы линейного программирования.

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

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

На рис. 2.1 изображено выпуклое множество (выпуклый многоугольник), а на рис. 2.2 - невыпуклое.

Рис.2.1 Рис. 2.2

Определение 2. Пересечение конечного числа выпуклых множеств также выпуклое множество.

Определение 3. Точка выпуклого множества называется угловой (или крайней), если через неё нельзя провести ни одного отрезка, состоящего только из точек данного множества и для которого она была бы внутренней.

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

Утверждение 1. Множеством решений системы m линейных неравенств с n переменными является выпуклый многогранник в n-мерном пространстве (исключая случай, когда система несовместна).

Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

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

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

Справедливость этого утверждения иллюстрируется в примере 3.

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

Дата добавления: 2015-04-24