Графический метод решения ЗЛП используется только тогда, когда поставленная ЗЛП зависит от двух переменных. Такая задача будет иметь вид:
Целевая функция:
(4.3)
Ограничения:
(4.4)
Дополнительные ограничения:
(4.5)
Пусть сформулирована следующая задача о планировании производства:
(4.6)
(4.7)
(4.8)
(4.9)
(4.10)
Для того, чтобы получить решение этой задачи графическим методом необходимо реализовать следующий алгоритм.
1 шаг. Строится область допустимых решений системы неравенств (4.7-4.9) и условий неотрицательности (4.10) (см. Рис. 4.5)
Рис. 4.5
Например, чтобы получить множество решений неравенства (4.7), необходимо отобразить на графике линию равенства , а затем выбрать одну из двух полуплоскостей, на которые вся плоскость делится этой прямой. В данном случае, множеством решения данного неравенства будет являться полуплоскость, которая содержит начало координат, так как точка (0;0) удовлетворяет неравенству (4.7). Аналогично можно получить множество решений неравенств (4.7-4.9). В результате полученное пересечение полуплоскостей дает область решения системы неравенств (4.7 – 4.9). Как видно на Рис. 4.5, эта область является незамкнутой. Поэтому необходимо учесть условия неотрицательности переменных (4.10). Окончательно, ОДР будет представлять собой выпуклый многоугольник АВСDE.
2 шаг. Строится вектор, указывающий направление возрастания целевой функции, называемый градиентом функции (). Компонентами градиента являются значения частных производных целевой функции по переменным xj, то есть
Так как в ЗЛП целевая функция линейна, то фактически компонентами вектора будут являться коэффициенты целевой функции cj.
Для рассматриваемой задачи (4.6-4.10) вектор = (3;2) (см. Рис. 4.5).
3 шаг. Строится линия уровня целевой функции. Линией уровня функции называется множество всех точек, в которых функция принимает постоянное значение, то есть . Для задачи (4.6)-(4.10) построим линию уровня - (см. Рис. 4.5).
4 шаг. Линия уровня сдвигается параллельно самой себе в направлении вектора до тех пор, пока не останется последняя общая точка пересечения линии уровня с ОДР. Эта точка и определяет максимум целевой функции (4.6), на рис. 4.5 – это вершина D, координаты которой (x1 = 9, x2 = 2) и есть оптимальное решение задачи (4.6-4.10), соответственно максимальное значение функции в этой точке равно - .
Исходя из рассмотренного алгоритма, можно сделать следующие выводы:
1. Каждой вершине выпуклого многоугольника (в случае n переменных – выпуклого многогранника) соответствует одно из возможных (допустимых) решений ЗЛП.
2. Оптимальное решение ЗЛП, если оно существует, соответствует одной из угловых точек выпуклого многоугольника (в случае n переменных – выпуклого многогранника).
3. Точке максимума целевой функции будет соответствовать последняя точка пересечения линии уровня с ОДР, точке минимума – первая точка пересечения.
4. ЗЛП будет иметь бесконечное множество решений, если линия уровня будет параллельна одной из сторон ОДР, то есть экстремум будет достигаться не в угловой точке, а во всех точках соответствующей стороны.