SHPORA.net :: PDA | |
Main FAQ гуманитарные науки естественные науки математические науки технические науки Основы симплексного метода. Приведенная целевая функция. Вывод формулы = – 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. |