Билет №25

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

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

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

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

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

…	B1	…	Bl	…	Bk	…	Br	…	As	…	B
…	1	…	0	…	0	…	0	…	a’1s	…
…	…	…	…	…	…	…	…	…	…	…	…
…	0	…	1	…	0	…	0	…	a’ls	…
…	…	…	…	…	…	…	…	…	…	…	…
…	0	…	0	…	1	…	0	…	a’ks	…
…	…	…	…	…	…	…	…	…	…	…	…
…	0	…	0	…	0	…	1	…	a’rs	…
…	0	…	0	…	0	…	0	…		…

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