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

Ответ от Личный Кабинет Удален[гуру]
Да, конечно сложно что то говорить, когда задачи нет. Объясню на своем примере:
Пусть задана система ограничений:
5x1+9x2<=45
3x1+3x2<=19
2x1+x2<=10
f(x1,x2)=2x1+x2=max
Переход к каноническому виду означает переход от системы неравенств к системе равенств. При этом строку с равенством не меняем. Знак <= заменяем добавлением к выражению нек. слагаемого, а >= - вычитанием. Поскольку придется менять все неравенства, то возникнет три новых переменных: x3,x4,x5. Но они будут носить чисто формальный характер!! ! и фактически будут нулями. Получим
5x1+9x2+x3=45
3x1+3x2+x4=19
2x1+x2+x5=10
В матричной форме:
5 9 1 0 0 45
3 3 0 1 0 19
2 2 0 0 1 10
Это есть канонический вид. Стоит также иметь в виду, что все переменные >=0!
Теперь необходимо выразить базисные векторы в матрице (по количеству строк) . Это уже математика, преобразования Гаусса.
Благо в нашем случае этого делать не надо: в матрице сразу видна единичная.
Справедливо, очевидно:
x3=45-5x1-9x2
x4=19-3x1-3x2 (**)
x5=10-2x1-x2
Вспоминая, что x3,x4,x5 - фактически нули, то получаем уравнения прямых на плоскости Ox1x2 (либо x2 выражаем через x1, либо наоборот) . Проводим все эти три прямые прямые. Теперь ищем общую область. Для этого проверим для каждой прямой, какую область та ограничивает (сверху или снизу) . Для этого выберем точку (x1,x2)=(0,0) и подставим в (**). Если x3 (аналогично с x4, x5) положительно, то область лежит ниже прямой, отрицательна - выше.
Находите общую область пересечения (опять же учитываем, что x1,x2>=0!).
Осталось рассмотреть целевую функцию/ Допускают f(x1,x2)=0, т. е x2=-2x1.
Теперь делаем параллельный перенос этой прямой на нашу область (пусть она треугольник, в общем случае это многоугольник) . Очевидно, что входить она будет через одну из вершин треугольника - это будет минимум целевой функции. Со-но выходить из области прямая будет в точке максимума. Конечно может возникнуть ситуация, когда целевая функция параллельна одной их (**) или несколько прямых из (**) параллельны между собой. Это ситуации, когда число решений бесконечно, либо нет вообще. Но не буду о грустном, сам точно не помню.
Осталось только найти координату этой точки и подставить полученные x1,x2 в исходную целевую функцию.
Фух, надеюсь частично смог объяснить : )
23.11.11