Геометрическая интерпретация задач линейного программирования. Графический метод их решения

Определение 1. Значения неизвестных переменных, удовлетворяющие всем ограничениям задачи линейного программирования, называются допустимыми значениями переменных или планами.

Определение 2. Множество всех планов задачи линейного программирования называется областью допустимых значений переменных (ОДЗ).

Определение 3. План задачи линейного программирования, при котором целевая функция принимает минимальное (или максимальное) значение на ОДЗ называется оптимальным.

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

1) Находятся геометрические решения всех ограничений задачи.

2) Областью допустимых значений будет многоугольник, полученный с помощью пересечения всех полуплоскостей.

Таким образом, геометрически решить задачу линейного программирования означает найти среди всех точек ОДЗ такую точку (точки), при которой (которых) целевая функция принимает своё экстремальное значение.

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

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

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

Графический метод является наглядным и простым методом решения задач линейного программирования. Однако область его применения ограничена размерностью задачи. Если задача представлена в стандартной форме, то количество переменных должно быть не более трёх.