Алгоритм графического метода решения ЗЛП.
Суть графического метода решения ЗЛП основывается на следующих утверждениях:
1) совокупность опорных планов ЗЛП совпадает с системой вершин многогранника решений;
2) целевая функция достигает оптимального значения в вершине многогранника решений.
Для практического решения ЗЛП с двумя переменными графическим методом необходимо:
1) построить все полуплоскости, соответствующие ограничениям системы;
2) найти область допустимых решений (ОДР), как множество точек, в котором пересекаются все построенные полуплоскости;
3) построить вектор 
, выходящий из начала координат, где 
и 
– это коэффициенты при неизвестных в целевой функции 
. Этот вектор указывает направление возрастания целевой функции.
4) Перпендикулярно вектору 
провести так называемую линию уровня 
(т.е. прямую 
, проходящую через начало координат).
5) Переместить линию уровня параллельно самой себе в направлении вектора (если задача на максимум (max)) или в противоположном направлении (если задача на минимум (min)) до тех пор, пока линия уровня имеет хотя бы одну общую точку с ОДР.
6) Найти координаты 
этой общей крайней точки, решая систему уравнений прямых, на пересечении которых она находится.
7) Подставить эти координаты в целевую функцию и найти ее max (или min).
Пример 6. Решить задачу линейного программирования графическим методом
при ограничениях
► Построим область L допустимых решений. Заменим в каждом неравенстве задачи знак неравенства на знак равенства. Получим уравнения прямых:
x1+4x2=8, 2x1-x2=4, x1+x2=1,x1=0,x2=0.
Область L определяется как общая часть полуплоскостей, соответствующих неравенствам ограничений:
 |
В данной задаче она составляет многоугольник ABCD. Для нахождения экстремума функции , строим разрешающую прямую, приравнивая линейную форму нулю: . Строим градиент целевой функции 
.
Минимальное значение функция принимает в точке 
, а максимальное в точке B.
Анализ решения задачи линейного программирования.
В результате решения задачи линейного программирования были получены минимум и максимум рассматриваемой функции, вследствие того, что область ограничений представляет собой замкнутый многоугольник, если бы фигура области ограничений была не замкнута, функция могла бы не иметь одного или обоих экстремумов в заданной области. ◄
Замечание 4. Если оптимальное значение целевая функция принимает более чем в одной вершине, то она принимает его во всякой точке, являющейся выпуклой линейной комбинацией этих вершин, то есть на всей прямой.