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

В линейном программировании существует 2 метода:

• · графоаналитический;
• · симплекс-метод

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

Пусть задана система ограничений:

• 5x1+9×2<=45
• 3x1+3×2<=19
• 2x1+x2<=10

f (x1,x2)=2×1+x2=max.

Переход к каноническому виду означает переход от системы неравенств к системе равенств. При этом строку с равенством не меняем. Знак = - вычитанием. Поскольку придется менять все неравенства, то возникнет три новых переменных: x3, x4,x5. Но они будут носить чисто формальный характер! ! и фактически будут нулями. Получим.

• 5x1+9×2+x3=45
• 3x1+3×2+x4=19
• 2x1+x2+x5=10

Это есть канонический вид. Стоит также иметь в виду, что все переменные >=0!

Теперь необходимо выразить базисные векторы в матрице (по количеству строк). Это уже математика, преобразования Гаусса.

Благо в нашем случае этого делать не надо: в матрице сразу видна единичная.

Справедливо, очевидно:

x3=45−5×1−9×2.

x4=19−3×1−3×2 (**).

x5=10−2×1-x2.

Вспоминая, что x3, x4,x5 — фактически нули, то получаем уравнения прямых на плоскости Ox1x2 (либо x2 выражаем через x1, либо наоборот). Проводим все эти три прямые. Теперь ищем общую область. Для этого проверим для каждой прямой, какую область та ограничивает (сверху или снизу). Для этого выберем точку (x1,x2)=(0,0) и подставим в (**). Если x3 (аналогично с x4, x5) положительно, то область лежит ниже прямой, отрицательна — выше.

Находите общую область пересечения (опять же учитываем, что x1, x2>=0!).

Осталось рассмотреть целевую функцию/ Допускают f (x1,x2)=0, т. е x2=-2×1.

Теперь делаем параллельный перенос этой прямой на нашу область (пусть она треугольник, в общем случае это многоугольник). Очевидно, что входить она будет через одну из вершин треугольника — это будет минимум целевой функции. Со-но выходить из области прямая будет в точке максимума. Конечно может возникнуть ситуация, когда целевая функция параллельна одной их (**) или несколько прямых из (**) параллельны между собой. Это ситуации, когда число решений бесконечно, либо нет вообще. Но не буду о грустном, сам точно не помню.

Осталось только найти координату этой точки и подставить полученные x1, x2 в исходную целевую функцию.