выход из вырожденного плана ЗЛП

[Andrey_Kireew]

Добрый день.
Вырожденные планы ЗЛП, как следует из литературы, явление редкое. И тем не менее, у меня они появляются постоянно и приходится с этим бороться. Первое время алгоритм банально зависал. Потом я его усовершенствовал, применим пресловутый метод Креко. Казалось, что проблема была решена. Но, на всякий случай, я поставил счётчик вырожденных планов. Иногда они появлялись. Иногда, на их прохождение тратилась большая часть итераций. Но работа всё время завершалась успешно. До сего дня. Алгоритм работал 2-е суток и надежда дождаться решения была потеряна.
Я заинтересовался, в каком порядке следуют вырожденные планы. Оказалось, что друг за другом. Другими словами, получается, что алгоритм встречает один вырожденный план и так долго из него выходит.

У меня такой вопрос - нормально ли, что для выхода из вырожденного плана тратится так много итераций?
Вообще есть подозрение, что предотвращение зацикливания реализовано не правильно, и проблема в этом.

[vpb]

Я не специалист никакой в данном вопросе, но недавно тоже пытался разобраться. По книжке Васильева с соавтором (точно не помню с кем, книжка где-то 180 стр. толщиной, посвящена специально ЛП). Разобраться не разобрался, бросил, поскольку к моим потребностям все это было очень по касательной. Но вынес следующее, весьма смутно. Для выхода из вырожденного плана может потребоваться, грубо говоря, перебрать все подмножества мощности $k$ в данном множестве из $n$ элементов. А такой перебор имеет, вообще говоря, экспоненциальную сложность. Даже при умеренных $n$ и $k$ может потребоваться рассмотреть астрономическое число вариантов. Ну вот Вы на это и напоролись...

Для комплекта замечу, из области общего образования (скорее всего, Вы уже в курсе), что симплекс-метод имеет, вообще говоря, экспоненциальную сложность, однако существуют и полиномиальные по сложности алгоритмы (Хачияна и Кармаркара).

[Andrey_Kireew]

vpb это Вы про алгоритм "внутренней точки"?
(добавлено) да, нашел, это он и есть. Но его преимущества проявятся только на очень больших задачах, у меня таких пока нет.
Для задач 2000х5000 простой симплекс-метод вполне подходит. Обычно, решение готово уже через несколько секунд.

[Andrey_Kireew]

Чтобы посмотреть в чём дело "вытащил" всю симплекс-таблицу, после 1000 попыток выйти из вырожденного плана, и нашел причину!

Оказывается, по ошибке, алгоритм рассматривал не только положительные, но и нулевые отношения. Когда в столбце свободных членов было много нулей, возникали эти псевдонеопределённости. После исправления остался только один вырожденный план (разобравшись понял, что он действительно должен быть). Выход из него происходит за 1 итерацию, и больше ничего такого не появляется

[mustitz]

Ну будущее, зацикливание хорошо рассмотрено в книге Юдина и Гольштейна, Линейное программирование, в частности глава 5, § 9. Там же пример зацикливания для отладки. Вообще есть два метода выхода из зацикливания, приближённый и точный. Минимальная длина цикла в приближённом случае семь шагов.

[Andrey_Kireew]

Спасибо