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

Запишем алгоритм (последовательность действий) графического метода решения задач линейного программирования.

1. На плоскости построим граничные прямые , соответствующие каждому из неравенств ограничений (14).

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

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

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

5. Построим одну из линий уровня , пересекающую область допустимых решений.

6. Переместим линию уровня в направлении нормали для задачи максимизации или в противоположном направлении для задачи минимизации целевой функции.

Если при перемещении линия уровня уходит в бесконечность, то задача не имеет оптимального решения.

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

7. Запишем уравнения граничных прямых, пересекающихся в данной вершине. Совместное решение этих уравнений будет являться оптимальным решением задачи. В случае существования альтернативного решения, когда целевая функция достигает экстремума на отрезке (рис.2), оптимальным решением будет линейная комбинация экстремальных решений и на концах отрезка:

.

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

,

Решение.

Построим на плоскости область допустимых решений (ОДР).

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

2. Определяем полуплоскости, являющиеся областью решений каждого из неравенств ограничений. Для этого подставим в неравенство координаты какой-либо точки, не лежащей на граничной прямой.

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

Обозначим их стрелкой на соответствующей граничной прямой.

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

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

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

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

.

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

(1)

D

8

6

(2)

С В

А

2 4 6 8 (3)

Рис.4. Графическое решение задачи 2.