Графический метод решения
Задача с двумя переменными
Графический метод решения задач линейного программирования
Пусть требуется найти максимальное значение функции
F(X) = с1 х1 + с2 х2 (2.1)
при ограничениях
(2.2)
Допустим, что система ограничений (2.2) совместна, т.е. имеет решение, а многоугольник ее решений (ОДР) ограничен. Каждое из неравенств (2.2) определяет полуплоскость с границей 
, i = 1, 2, ..., т или х1 = 0, х2 = 0. Представим этот многоугольник на плоскости Ох1х2 (рис. 2.1).
Рис.2.1
Линейная функция (2.1) при фиксированных значениях F(X) является уравнением прямой линии c1x1+ c2x2=const.
Изобразим прямую, соответствующую линейной функции, при F(X) = 0. Эта прямая пройдет через начало координат. Другим значениям F(X) будут соответствовать прямые, параллельные друг другу.
Прямая, уравнение которой получено из целевой функции задачи при равенстве ее постоянной величине, называется линией уровня.
Известно, что коэффициенты при переменных в линейном уравнении являются координатами нормального вектора к соответствующей прямой или плоскости. Следовательно, нормальный вектор линий уровня и имеет координаты с1 и с2, т.е. 
= (с1, с2).
Если перемещать линию уровня параллельно ее начальному положению в направлении вектора , то для данного случая (см. рис. 2.1) последней точкой, в которой линия уровня коснется ОДР, окажется точка С. Линия уровня, имеющая общие точки с ОДР и расположенная так, что ОДР целиком находится в одной из полуплоскостей, называется опорной прямой.
Алгоритм решения ЗЛП с двумя переменными графическим методом таков:
1. Строится область допустимых решений.
2. Строится вектор = (с1, с2) с точкой приложения в начале координат.
3. Перпендикулярно вектору проводится одна из линий уровня, например линия уровня, соответствующая уравнению с1х1 + с2х2 = 0.
4. Линия уровня перемещается до положения опорной прямой. На этой прямой и будет находиться максимум или минимум функции.
В зависимости от вида ОДР и целевой функции F(X) задача может иметь единственное решение (рис. 2.3, а), бесконечное множество решений (рис. 2.3, б) или не иметь ни одного оптимального решения (рис. 2.3, в).
a) б) в)
Рис. 2.3
Пример 1.Решить задачу линейного программирования графическим методом: F(X)=2x1+4x2→ max,
 |
Решение. Изобразим на плоскости систему координат Ох1х2 и построим
|
|
построим одну из линий уровня (на рис. 2.4 она проходит через начало координат). Так как задача на максимум, то перемещаем линию уровня в направлении вектора до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L1 и L2, т.е. через точку В = L1∩L2. Для определения координат точки В решаем систему уравнений 
Получаем х1 = 3, х2 = 6. Это и будет оптимальное решение данной задачи, которому соответствует максимальное значение целевой функции
max F(X) = 2 · 3 + 4 · 6 = 30.
Пример 2.Найти минимум функции F(X)=2x1+x2→ min при ограничениях
Отличие этого примера от предыдущего состоит в том, что здесь ищется не максимум, а минимум функции F. Областью решений данной системы ограничений является треугольник АВС (рис.2.5). На рисунке изображены также исходная линия уровня и вектор q = (2; 1), показывающий направление движения этой линии для достижения максимума функции F. Так как требуется найти минимум этой функции, то будем передвигать исходную линию уровня в сторону, противоположную вектору q. Как видно из рис. 2.5, минимум функции F достигается в угловой точке А, координаты которой служат решением системы уравнений
|
 |
Отсюда А (6/7; 25/7) и Fmin = 37/7.