Основы симплексного метода. Приведенная целевая функция. Вывод формулы = – a0pXp.
Ключевая теорема симплексного метода.
Если все оценки нулевой строки а0k ? 0 и задача решается на максимум, то достигнуто лучшее решение. Если имеется хотя бы одна отрицательная оценка и в соответствующем столбце есть хотя бы один положительный элемент, решение может быть улучшено. Если есть хотя бы одна отрицательная оценка, но соответствующем столбце нет ни одного положительного элемента, то Z cтремится к бесконечности и ЗЛП не имеет решения.
Алгоритм симплексного метода.
Привести ЗЛП к канонической форме. Систему ограничений к исходному опорному решению. Заполнить симплексную таблицу и оценочную строку.
Каждая операция теперь начинается с нулевой строки.
Могут возникнуть три случая согласно ключевой теореме. Первый и третий случай означают конец решения. Делается вывод.
Второй случай состоит из следующих этапов:
Выбирается столбец с отрицательной оценкой (если их несколько, то выбирается большая по модулю). Выбирается разрешающая строка по меньшему из отношений аio/aip. Выполняются преобразования однократного замещения по известным формулам, в том числе нулевой строки.
Вывод формулы:
После выполнения 1 итерации придем к новой системе уравнений, приведенной к новому единичному базису. Найдем изменение функции, достигнутое в результате этой итерации.
Обозначим новое значение Z1.
Z1=AooAqp-AqoAop/Aqp=Aoo-AqoAop/Aqp
Xp=Aqo/Aqp - новое значение базисной переменной, >0.
Z1=Aoo-XpAop
т.к. мы выбирали Аор отрицательным, то ХрАор будет также отрицательным, а Z1>Z
Z=Z1-Zo=Aoo-XpAop-Aoo=-XpAop.