Алгоритм графического метода решения ЗЛП.

Суть графического метода решения ЗЛП основывается на следующих утверждениях:

1) совокупность опорных планов ЗЛП совпадает с системой вершин многогранника решений;

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

Для практического решения ЗЛП с двумя переменными графическим методом необходимо:

1) построить все полуплоскости, соответствующие ограничениям системы;

2) найти область допустимых решений (ОДР), как множество точек, в котором пересекаются все построенные полуплоскости;

3) построить вектор , выходящий из начала координат, где и – это коэффициенты при неизвестных в целевой функции . Этот вектор указывает направление возрастания целевой функции.

4) Перпендикулярно вектору провести так называемую линию уровня (т.е. прямую , проходящую через начало координат).

5) Переместить линию уровня параллельно самой себе в направлении вектора (если задача на максимум (max)) или в противоположном направлении (если задача на минимум (min)) до тех пор, пока линия уровня имеет хотя бы одну общую точку с ОДР.

6) Найти координаты этой общей крайней точки, решая систему уравнений прямых, на пересечении которых она находится.

7) Подставить эти координаты в целевую функцию и найти ее max (или min).

Пример 6. Решить задачу линейного программирования графическим методом

при ограничениях

► Построим область L допустимых решений. Заменим в каждом неравенстве задачи знак неравенства на знак равенства. Получим уравнения прямых:

x ₁+4 x₂=8, 2x₁-x₂=4, x₁+x₂­=1,x₁=0,x₂=0.

Область L определяется как общая часть полуплоскостей, соответствующих неравенствам ограничений:

В данной задаче она составляет многоугольник ABCD. Для нахождения экстремума функции , строим разрешающую прямую, приравнивая линейную форму нулю: . Строим градиент целевой функции .

Минимальное значение функция принимает в точке , а максимальное в точке B.

Анализ решения задачи линейного программирования.

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

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