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

Графический метод основан на 2-х утверждениях из аналитической геометрии.

Утв.1. Прямая, заданная уравнением а_х+в_у=с делит числовую плоскость Оху на две полуплоскости, в одной из которых выполняется неравенство

I: а_х+в_х>с

II: а_х+в_х<с

Утв.2. Отыскание оптимальной точки.

Пусть прямая на плоскости задана уравнением а_х+в_х=с, вектор = а,в состоит из коэфф. перпендикулярной прямой и называется его нормальным вектором.

L₁: а_х+в_х=с₁ параллельно прямой

Прямая L₁ получена перемещением прямой L в направлении вектора , если С₁>С и противоположен , если С₁<С

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

I этап: Построение множества допустимых планов.

Составляем уравнение граничных прямых, заменяя в каждом ограничении знак неравенства на точное равенство, строим прямые на плоскости и отмечаем стрелками те полуплоскости, в которых выполняется неравенство нужного направления.

Пересечение всех построенных линий на плоскостях дает множество допустимых планов.

Если множество допустимых планов не пусто, то переходим ко второму этапу.

II Этап: Строим вектор =(С1,С2) координаты, которого соотв. при переменной в целевой функции через произв.точку множество допустимых планов проводим прямую L перпендикулярную вектору

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

При решении задачи на min прямая перемещается в направлении против вектора , до разрешающего положения.