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

Графический метод решения ЗЛП используется только тогда, когда поставленная ЗЛП зависит от двух переменных. Такая задача будет иметь вид:

Целевая функция:

                                                        (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 шаг. Строится вектор, указывающий направление возрастания целевой функции, называемый градиентом функции (). Компонентами градиента являются значения частных производных целевой функции по переменным x_j, то есть

Так как в ЗЛП целевая функция линейна, то фактически компонентами вектора  будут являться коэффициенты целевой функции c_j.

Для рассматриваемой задачи (4.6-4.10) вектор = (3;2) (см. Рис. 4.5).

3 шаг. Строится линия уровня целевой функции. Линией уровня функции называется множество всех точек, в которых функция принимает постоянное значение, то есть . Для задачи (4.6)-(4.10) построим линию уровня -  (см. Рис. 4.5).

4 шаг. Линия уровня сдвигается параллельно самой себе в направлении вектора  до тех пор, пока не останется последняя общая точка пересечения линии уровня с ОДР. Эта точка и определяет максимум целевой функции (4.6), на рис. 4.5 – это вершина D, координаты которой (x₁ = 9, x₂ = 2) и  есть оптимальное решение задачи (4.6-4.10), соответственно максимальное значение функции в этой точке равно - .

Исходя из рассмотренного алгоритма, можно сделать следующие выводы:

1. Каждой вершине выпуклого многоугольника (в случае n переменных – выпуклого многогранника) соответствует одно из возможных (допустимых) решений ЗЛП.

2. Оптимальное решение ЗЛП, если оно существует, соответствует одной из угловых точек выпуклого многоугольника (в случае n переменных – выпуклого многогранника).

3. Точке максимума целевой функции будет соответствовать последняя точка пересечения линии уровня с ОДР, точке минимума – первая точка пересечения.

4. ЗЛП будет иметь бесконечное множество решений, если линия уровня будет параллельна одной из сторон ОДР, то есть экстремум будет достигаться не в угловой точке, а во всех точках соответствующей стороны.