вырожденные планы в симплекс-методе

[Andrey_Kireew]

Здравствуйте уважаемые участники форума, никак не могу разобраться в тонкостях предотвращения зацикливания симплекс-алгоритма при наличии вырожденных планах. Такая тема уже поднималась (много лет назад), но после изучения имеющихся комментариев вопрос для меня остался не вполне понятным.

Насколько я понял [Юдин Д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования, 1961г.] , гарантированное предотвращение зацикливания достигается с помощью решения т.н. е - задачи, в которой, за счёт введения небольшого смещения вектора неизвестных переменных достигается невырожденность при сохранении того же самого плана исходной задачи.
Практически, метод сводится к тому, что после обнаружения нескольких одинаковых минимальных отношений элементов столбца свободных членов и разрешающего столбца, для этих, альтернативных, строк вычисляются отношения первого по порядку таблицы столбца к соответствующим элементам разрешающего столбца. Если среди этих отношений минимальное значение единственно, то оно указывает на номер разрешающей строки. Если же минимальных отношений опять несколько, то для оставшихся альтернативных строк вычисляются отношения второго столбца к разрешающему столбцу и т.д., до тех пор, пока разрешающая строка не будет всё же найдена.

Вопрос мой вот в чём: Среди элементов разрешающей строки рассматриваются только положительные элементы, а элементы столбца свободных членов положительны по определению. Так что первые отношения получаются положительными. Относительно элементов первого и последующих столбцов не совсем понятно, при вычислении отношений нужно брать только положительные, или отрицательные тоже? И если отрицательные элементы рассматриваются, то минимальное отношение выбирается по абсолютной величине, или с учётом знака?

В сети есть разные примеры с вырожденными планами, но из них я так и не понял как правильно, к тому же достоверность этих источников вызывает у меня сомнения. Вообще этот метод напоминает мне известный в сети метод Креко, хотя может я просто не замечаю различий. На счёт метода Бленда я разобрался - он не гарантирует отсутствия циклов, а просто значительно снижает вероятность их возникновения.

Если не сложно, разъясните мне этот вопрос по подробнее.

[Someone]

Andrey_Kireew в сообщении #1214252 писал(а):

На счёт метода Бленда я разобрался - он не гарантирует отсутствия циклов, а просто значительно снижает вероятность их возникновения.

Странно. Я видел теорему, в которой прямо утверждается, что правило Бленда исключает зацикливание. Доказательство я не разбирал.

А. И. Беников. Линейное программирование. Учебное пособие. Иркутск, 2005. Глава 2, § 4.

Robert G. Bland. New finite pivoting rules for the simplex method. Mathematics of operations research. Vol. 2, No. 2, May 1977, p. 103—107.

В доказательствах есть ошибки? Или Вы можете предъявить контрпример?

[Andrey_Kireew]

Доказательства не разбирал, так же как и Вы, но об этом сказано в [Юдин Д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования, 1961г.] на стр. 213. Теперь разобрался, что речь там идёт не о правиле Бленда, которое действительно предотвращает зацикливание. Спасибо за ссылку! там написано всё понятно, по крайней мере должно работать.

Но, всё же, правило Бленда предполагает выбор ведущего столбца не с минимальной, а с первой по порядку отрицательной оценкой, сходимость процедуры при этом очевидно будет более медленной.

В связи с этим всё же хотелось бы услышать ответ и на свой вопрос

[Someone]

Andrey_Kireew в сообщении #1214401 писал(а):

Но, всё же, правило Бленда предполагает выбор ведущего столбца не с минимальной, а с первой по порядку отрицательной оценкой, сходимость процедуры при этом очевидно будет более медленной.

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

[Andrey_Kireew]

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

Что касается целесообразности предотвращения зацикливания, которое, как пишут в литературе, возникает крайне редко, то в моём конкретном случае она присутствует (появляются вырожденные планы). По этому в моей программе есть соотв. фрагмент, который в принципе зацикливание всегда предотвращает. Работает всё так:
1. ведущий столбец выбирается по минимуму в строке функционала.
2. В первом столбце, среди альтернативных строк находится строка с максимальным отношением к соотв. элементу ведущего столбца и отбрасывается.
3. Если осталось несколько альтернативных трок, то во втором столбце ищется элемент с максимальным отношением и соотв. строка отбрасывается.
4. Так до тех пор, пока не останется единственная строка.

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