Графический метод решения

Рассмотрим случай n=2, то есть задачу на плоскости:

найти , (8.1)

при ограничениях (8.2)

(8.3)

Каждое ограничение в этом случае задаёт полуплоскость (при наличии знака неравенства), либо прямую (при наличии в ограничении знака равенства). Пересечение этих полуплоскостей и прямых может дать пустое множество, точку, луч, многоугольник, неограниченную многоугольную область. Непустая область пересечения называется многоугольником решений или областью допустимых решений ОДР.

Если целевая функция ЗЛП ограничена на многограннике решений, то существует такая угловая точка многогранника решений, в которой ЦФ достигает своего оптимума.

Графический способ решения состоит из следующих этапов:

1. Строится многоугольная область допустимых решений ЗЛП – ОДР.

2. Строится вектор-градиент целевой функции c₁, c₂, где с₁, с₂ – коэффициенты ЦФ.

3. Строится целевая функция – линия уровня.

4. Выбирается оптимальное решение

При нахождении максимума целевой функции F(x₁, x₂) линию уровня L_a надо передвигать параллельно самой себе в направлении вектора-градиента до тех пор, пока она не покинет пределов области допустимых решений D. Предельная точка области при таком движении и является точкой максимума целевой функции.

При нахождении минимума целевой функции линию уровня L_a надо передвигать в направлении противоположном вектору градиенту до достижения предельной точки многоугольника.