Симплекс таблицы
Рисуем симплекс таблицу:
Столбики называются: Сi, хi, a0(-C0), x1(C1), …,xn (Cn), aio/aip.
Оценочная строка: z под xi, a00, a10, …,a0n.
Словами: что? где? и как?
Ключевая теорема симплексного метода.
Если все оценки нулевой строки а0k и 0 и задача решается на максимум, то достигнуто лучшее решение. Если имеется хотя бы одна отрицательная оценка и в соответствующем столбце есть хотя бы один положительный элемент, решение может быть улучшено. Если есть хотя бы одна отрицательная оценка, но соответствующем столбце нет ни одного положительного элемента, то Z cтремится к бесконечности и ЗЛП не имеет решения.
Алгоритм симплексного метода.
Привести ЗЛП к канонической форме. Систему ограничений к исходному опорному решению. Заполнить симплексную таблицу и оценочную строку.
Каждая операция теперь начинается с нулевой строки.
Могут возникнуть три случая согласно ключевой теореме. Первый и третий случай означают конец решения. Делается вывод.
Второй случай состоит из следующих этапов:
Выбирается столбец с отрицательной оценкой (если их несколько, то выбирается большая по модулю). Выбирается разрешающая строка по меньшему из отношений аio/aip. Выполняются преобразования однократного замещения по известным формулам, в том числе нулевой строки.