double arrow

Возврат к пройденной угловой точке множества допустимых решений при преобразовании «симплекс-таблицы». Пути выхода из зацикливания в случае вырожденности задачи ЛП

Если задача ЛП вырождена, то bi0=0 => D0k+1=D0k, Т.е. ы переходим к нехудшему допустимому базисному решению, но значение целевой ф-ции не изменится. Если такая ситуация будет систематически повторяться, при переходе к новому базисному решению, то в силу конечности доп-х базисных решений ы придем к решению, которое ранее встречалось, т.е будем иметь повторяющееся симплекс таблицу. Т.о. получили зацикливание. Зацикливание можно избежать изменением правила выбора завершающего столбца и строки.

К строке Qi симпл таблицы будем присваивать номер базисной переменной xi, соответствующий этой таблице. Qm+1=(D0, D1, …, Dn).

Допустимое базисное решение xi нзв обобщенно-положительным, если Qiý0 "iÎI={i1, …, im}.

Если x0 – допустимое баз решение, то сделать его обобщен-положительным можно перенумеровав столбцы матрицы А. В невырожденной задаче все допустимые базисн решения обобщ-положительны.

Пусть имеется задача на минимум, x0 – допуст баз решение.

Теорема: Если Dj0 >0, а индекс разрешающей строки i0 выбрать из множ-ва I’={iÎI: aij0>0} Так, чтобы 1/ai0j0Qi0í1/aij0Qi, i¹i0, то новое допустимое базисное решение будет обобщ-положит, при этом Q’m+1íQm+1

Вывод из теоремы: если перед решением задачи произвести нумерацию базисных переменных xi так, что исходное допуст баз решение будет обобщ-положит, а разрешающую строку при каждой последующей итерации выбирать по правилу (1), то зацикливания не произойдет. Это следует из того, что если сущ Dj0 >0, aij0>0 для некотор i, то при переходе к нов допустим базису строка Qm+1 будет лексикографически уменьшаться. Поэтому ни одно из допуст баз решений не повторится с исх допус баз решениями. А в силу конечности допуст баз решений получим, что найдется либо оптим решение, либо ф-ция F неограниченна снизу.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: