Графический метод решения задачи линейного программирования
Если задача линейного программирования имеет две переменные x1 и x2, то ее можно решить графически.
Решение задачи происходит в два этапа.
На первом этапе необходимо на плоскости изобразить допустимое множество, а на втором найти оптимальную точку, если она существует, в противном случае убедиться в неразрешимости задачи.
Этап 1. Построение допустимого множества.
Каждое неравенство в рассматриваемой задаче представляет собой полуплоскость, а допустимое множество – пресечение этих полуплоскостей. Если неравенства в задаче заменить уравнениями, то получим уравнения прямой. Каждую прямую можно построить по двум точкам. Для того чтобы выделить необходимую полуплоскость, надо взять точку, не лежащую на прямой, и подставить ее координаты в левую часть неравенства, если неравенство выполнено, то выбираем полуплоскость, содержащую данную точку, в противном случае другую полуплоскость.
Так как в ограничениях присутствуют ограничения неотрицательности переменных, то рассматриваем только первый координатный угол.
Если правая часть не равна нулю, то в качестве пробной точки удобнее всего выбрать начало координат (0,0).
Алгоритм
Шаг 1: Выделение первого координатного угла.
Шаг 2: 
.
Шаг 3: i-е неравенство записывается как уравнение
Шаг 4: Полагаем 
находим из уравнения
Шаг 5: Полагаем 
находим из уравнения
Шаг 6: Через точку 
и 
проводится прямая.
Шаг 7: В левую часть неравенства подставляется точка с координатами 
. Если неравенство выполнено, то выбирается полуплоскость содержащая начало координат, в противном случае противоположная полуплоскость.
Шаг 8: Если 
, то 
, переходим к шагу 3, иначе шаг 9.
Шаг 9: Допустимое множество получено. Если оно непустое ( 
), то выписывается ответ: Задача несовместна, иначе переход к этапу 2.
Этап 2: Поиск оптимальной точки
Рассмотрим градиент функции 
. Т.к. функция линейна, то ее градиент есть постоянный вектор с координатами 
.
Известно, что движение в направлении градиента увеличивает значение функции.
Прямая перпендикулярная вектору – градиенту называется линией уровня, т.к. значения функции в любой точке этой прямой одинаковы.
Алгоритм
Шаг 1: Строится вектор градиент 
.
Шаг 2: Кладется линейка перпендикулярно вектору – градиенту.
Шаг 3: Линейка сдвигается параллельно самой себе по направлению вектора градиента, пока хотя бы одна точка соответствующей прямой принадлежит допустимому множеству.
Шаг 4: Если при любом положении линейки перпендикулярно вектору градиенту имеются точки допустимого множества, то выписывается ответ: Задача неразрешима из-за неограниченности целевой функции переход к шагу 10. Иначе шаг 5.
Шаг 5: Находится последняя точка допустимого множества, лежащая на соответствующей линии уровня.
Шаг 6: Если эта точка неединственная, то выбирается точка, которая является пересечением двух прямых, ограничивающих допустимое множество.
Шаг 7: Выписывается система двух уравнений с двумя неизвестными.
Шаг 8: Из системы уравнений находится оптимальная точка 
.
Шаг 9: Находится оптимальное значение целевой функции 
.
Шаг 10. Конец.
Пример 1.4.1.Решить задачу линейного программирования графически.
, (1.4.1)
, (1.4.2)
, (1.4.3)
Решение. Строим допустимое множество в соответствии с первым этапом алгоритма. В результате получаем ограниченную многогранную область.
Рис. 1.4.1
В таблице 1.4.1 заданы точки, по которым строятся прямые (1.4.1)-(1.4.3).
Таблица 1.4.1
| (1.4.1) | (1.4.2) | (1.4.3) | ||||
| -9 | |||||
| -10 |
В качестве пробной кочки выбираем начало координат (0, 0).
Для (1.4.1) 
(Верно: выбирается полуплоскость содержащая начало координат.)
Для (1.4.2) 
(Верно: выбирается полуплоскость содержащая начало координат.)
Для (1.4.3) 
(Верно: выбирается полуплоскость содержащая начало координат.)
На этапе 2 находим 
.
Сдвигаясь по линии уровня в направлении вектора-градиента, получаем оптимальную точку А, находим ее координаты. Так как она является точкой пересечения прямых (1.4.1) и (1.4.3), то решаем систему уравнений
Таким образом, оптимальной точкой 
является точка 
.
Находим оптимальное значение целевой функции, подставляя значение в функцию:
.
Пример 1.4.2. Решить графически следующую задачу:
,
,
,
,
.
Решение. Построение допустимого множества выполняется также как и в предыдущей задаче. В результате получаем неограниченную многогранную область.
Рис. 1.4.2.
На втором этапе решения - параллельном перемещении по линиям уровня в направлении вектора-градиента устанавливаем, что такое перемещение можно производить неограниченно. Следовательно, целевая функция неограниченна сверху, т.е. 
, а сама задача линейного программирования неразрешима из-за неограниченности целевой функции. Заметим, что если при тех же исходных данных требовалось бы целевую функцию минимизировать, то получили бы оптимальное решение в точке 
с 
.
Пример 1.4.3. Решить задачу
(1.4.4)
(1.4.5)
.
.
Решение. Допустимое множество в данной задаче имеет вид
Рис. 1.4.3.
Из рисунка видно, что допустимое множество неограниченно, однако оптимальное решение существует, им является луч, выходящий из точки 
. Линии уровня целевой функции параллельны прямой 
, соответствующей первому ограничению. Перемещая линии уровня в направлении вектора-градиента, получаем, что линия уровня с максимально возможным значением целевой функции совпадает с прямой . Таким образом, целевая функция достигает своего максимального значения 
во всех точках луча, выходящего из точки 
. Задача имеет бесчисленное множество решений. Для того чтобы выписать решение в общем виде, возьмем на луче еще одну точку 
. Уравнение луча записывается следующим образом: 
. Таким образом, любое решение данной задачи записывается в виде 
.
Пример 1.4.4. Решить графически задачу
.
Решение. Допустимое множество данной задачи пусто. Это видно из следующего рисунка.
Рис. 1.4.4.
Поэтому данная задача несовместна.