SHPORA.net :: PDA

[ Back ]

Рисуем симплекс таблицу:

Столбики называются: Сi, хi, a0(-C0), x1(C1), …,xn (Cn), aio/aip.

Оценочная строка: z под xi, a00, a10, …,a0n.

Словами: что? где? и как?

Ключевая теорема симплексного метода.

Если все оценки нулевой строки а0k и 0 и задача решается на максимум, то достигнуто лучшее решение. Если имеется хотя бы одна отрицательная оценка и в соответствующем столбце есть хотя бы один положительный элемент, решение может быть улучшено. Если есть хотя бы одна отрицательная оценка, но соответствующем столбце нет ни одного положительного элемента, то Z cтремится к бесконечности и ЗЛП не имеет решения.

Алгоритм симплексного метода.

Привести ЗЛП к канонической форме. Систему ограничений к исходному опорному решению. Заполнить симплексную таблицу и оценочную строку.

Каждая операция теперь начинается с нулевой строки.

Могут возникнуть три случая согласно ключевой теореме. Первый и третий случай означают конец решения. Делается вывод.

Второй случай состоит из следующих этапов:

Выбирается столбец с отрицательной оценкой (если их несколько, то выбирается большая по модулю). Выбирается разрешающая строка по меньшему из отношений аio/aip. Выполняются преобразования однократного замещения по известным формулам, в том числе нулевой строки.