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

Решая каноническую задачу линейного программирования на минимум, мы выполняем ряд шагов. При этом на каждом шаге осуществляется либо переход от базиса исходного опорного решения к базису нового опорного решения, на котором значение целевой функции меньше, чем на исходном опорном решении, либо переход к очередному базису исходного опорного решения, если это опорное решения является вырожденным.

Так как опорных решений у канонической задачи линейного программирования конечное число, то через конечное число шагов задача будет решена, т.е. либо будет найдено оптимальное решение, либо будет установлена неограниченность целевой функции на множестве допустимых решений этой задачи.

Если задача имеет вырожденное опорное решение, то, переходя от одного его базиса к другому, можно вернуться к базису, который уже встречался ранее, и продолжать движение уже по пройденной последовательности базисов этого опорного решения. Такую ситуацию называют зацикливанием алгоритма симплекс метода.

Чтобы избежать зацикливания, необходимо при переходе от одного базиса к другому ввести дополнительные условия. Рассмотрим симплекс таблицу, приведенную к базису В₁,…,B_l,…,B_k,…,B_r, опорного решения α.

…	B1	…	Bl	…	Bk	…	Br	…	As	…	B
…		…		…		…		…	a’1s	…	s w:ascii="Cambria Math" w:h-ansi="Cambria Math"/><wx:font wx:val="Cambria Math"/><w:i/><w:sz w:val="18"/></w:rPr><m:t>О±</m:t></m:r></m:e><m:sub><m:r><w:rPr><w:rFonts w:ascii="Cambria Math" w:h-ansi="Cambria Math"/><wx:font wx:val="Cambria Math"/><w:i/><w:sz w:val="18"/></w:rPr><m:t>1</m:t></m:r></m:sub></m:sSub></m:oMath></m:oMathPara></w:p><w:sectPr wsp:rsidR="00000000" wsp:rsidRPr="00B356AB"><w:pgSz w:w="12240" w:h="15840"/><w:pgMar w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></wx:sect></w:body></w:wordDocument>">
…	…	…	…	…	…	…	…	…	…	…	…
…		…		…		…		…	a’ls	…
…	…	…	…	…	…	…	…	…	…	…	…
…		…		…		…		…	a’ks	…
…	…	…	…	…	…	…	…	…	…	…	…
…		…		…		…		…	a’rs	…
…		…		…		…		…		…	s w:ascii="Cambria Math" w:h-ansi="Cambria Math"/><wx:font wx:val="Cambria Math"/><w:i/><w:sz w:val="18"/></w:rPr><m:t>Оґ</m:t></m:r></m:e><m:sub><m:r><w:rPr><w:rFonts w:ascii="Cambria Math" w:h-ansi="Cambria Math"/><wx:font wx:val="Cambria Math"/><w:i/><w:sz w:val="18"/></w:rPr><m:t>0</m:t></m:r></m:sub></m:sSub></m:oMath></m:oMathPara></w:p><w:sectPr wsp:rsidR="00000000" wsp:rsidRPr="00A20D68"><w:pgSz w:w="12240" w:h="15840"/><w:pgMar w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></wx:sect></w:body></w:wordDocument>">

 

Среди положительных одинаковых оценок симплекс таблице выбираем оценку с наименьшим номером. Затем среди отношений вида } для всех a’_is 0 выбираем наименьшее. Если указанное отношение не является единственным, то выбираем то, которое имеет наименьший номер i. применяя это правило на каждом шаге симплекс метода, будем получать базис системы условий задачи, который не встречался ранее. Поэтому через конечное число шагов задача будет решена.

Билет №25

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

Если каноническая задача линейного программирования н минимум имеет допустимое решение, а целевая функция на множестве допустимых решений ограничена снизу, то эта задача имеет оптимальное решение.

Доказательство: в теореме о существовании опорного решения было доказано, что если каноническая задача линейного программирования имеет допустимое решение, то эта задача имеет и опорное решение. Принимаем это опорное решение за начальное опорное решение и решаем задачу симплекс методом. Так как целевая функция ограничена снизу на множестве допустимых решений, то через конечное число шагов симплекс метода будет найдено оптимальное решение данной задачи.

 

Билет №26