Алгоритм графического метода.

1.      Строится область допустимых решений системы ограничений. Для этого на плоскости решается графически система ограничений.

ничений. При этом возможны случаи:

1)     область допустимых решений - пустое множество;

2)     область допустимых решений - единственная точка;

3)     область допустимых решений - выпуклый многоугольник;

4)     область допустимых решений - выпуклая неограниченная область.

В первом случае ЗЛП не имеет оптимального решения из-за несовместности системы ограничений.

Во втором случае - это единственное решение и будет оптимальным решением.

2.      Строится вектор-градиент целевой функции, выходящий из начала координат.

3.      Строится линяя уровня целевой функции, перпендикулярная вектору-градиенту и проходящая через область.

4.      Линия уровня смещается параллельно в направлении вектора-градиента (в противоположном направлении) в задаче максимизации (минимизации) до выхода из области. Точки, в которых произошел выход из области, являются точками экстремума.

Если экстремум достигается в двух угловых точках, то, по теореме об альтернативном оптимуме, оптимальным решением будет любая точка отрезка, соединяющего эти точки:

, .

В четвертом случае, когда область допустимых решений системы ограничений задачи неограниченная выпуклая область, оптимальное решение находится аналогично описанному выше. В данном случае оптимальное решение может совпадать с одной угловой точкой, с двумя угловыми точками и оптимальное решение может и не существовать из-за неограниченности целевой функции сверху в задаче на максимум или снизу в задаче на минимум.

5.      Находятся координаты точек экстремума и вычисляется экстремальное значение целевой функции.