Графический метод основан на геометрической интерпретации задачи линейного программирования, которая дает возможность наглядно изобразить структуру задачи линейного программирования, и применяется только для решения задач двумерного пространства и некоторых задач трехмерного.
Каждое ограничение целевой функции определяет в евклидовом n-мерном пространстве полупространство, состоящее из точек x (x1,…,xn), расположенных «по одну сторону» от плоскости и на самой этой плоскости. Точки, принадлежащие всем полупространствам (т.е. множество всех решений системы) как пересечение выпуклых множеств, образуют некоторый выпуклый многогранник D.
Таким образом, геометрический смысл задачи линейного программирования заключается в отыскании в многограннике D точек, которые наиболее (наименее) отдалены от начала координат, причем, нужно учитывать не только абсолютную величину, а и знак расстояния.
Экстремальные значения достигаются на границе множества планов задачи, и определение экстремальных значений целевой функции принципиально сводится к сравнению их в некоторых предельных точках многогранника планов, заданных основными ограничениями задачи линейного программирования.
Могут быть такие случаи.
* Многогранник планов задачи линейного программирования ограничен: в этом случае линейная форма достигает своего экстремума или в отдельных вершинах многогранника, или на его некоторой грани или ребре, если гиперплоскости уровня параллельные этим граням.
* Многогранник планов задачи линейного программирования неограниченный: тогда линейная форма может быть неограниченной на множестве планов снизу или лишь сверху, или снизу и сверху.
* Множество планов задачи линейного программирования пустая, т.е. не существует планов задачи линейного программирования, которые бы не противоречили системе условий задачи.
Алгоритм геометрической интерпретации задачи линейного программирования содержит такие этапы:
1. В каждом ограничении — неровности заменить знаки неровностей на знаки точных уравнений и провести на плоскости соответствующие им гиперплоскости — прямые.
2. Найти полупространство, определенное каждым соответствующим ограничением — неровностью.
3. Проявить многогранник планов задачи.
4. Провести гиперплоскость-прямую уровня целевой функции, которая имеет общие точки с многогранником планов.
5. Найти точку (или точки) многогранника, где прямая достигает наибольшего (наименьшего) значения, или установить ее неограниченность на множестве планов задачи.
6. Найти координаты точки решения задачи линейного программирования, которая и буде оптимальным планом задачи.