Методы от зацицкливания:Анализ

[damir_777]

Здравствуйте.
Я провел небольшой анализ двух методов от зацикливания в симплекс методе на примере нескольких примеров, которые дают зацикливание, если не принять специальных мер : Правило Бленда и лексикографический метод, и хочу с вами поделиться. Сами примеры в принципе могу не писать,
Вот результаты: (буду писать Индекс примера - Кол-во итераций, потребовавшееся для получения результата):
Правило Бленда: (в данных примерах все время выбирал переменные с наименьшим индексом среди тех, которые могут войти в базис, и соответственно при одинаковых минимальных симплекс-отношениях выбирал переменную, которая выйдет из базиса, с наименьшим индексом)
Пример 1 (так называемый пример Билла)-6 итераций
Пример 2 - 7 итераций
Пример 3 - 1 итерация

Те же примеры, но решенные с помощью лексикографического метода
Пример 1 (так называемый пример Билла)-2 итераций
Пример 2 - 2 итераций
Пример 3 - 1 итерация

Т.е получается что лексикографический метод дает меньшее количество итераций. А если, например, разработана программа, которая решает задачу ЛП автоматически, то, например, если применять правило Бленда, то программа должна при выборе ведущих и исключаемых переменных всегда применять правило Бленда, ведь неизвестно, даст ли данная задача зацикливание или нет. К примеру, я взял простой пример, который не дает зацикливания, и решил его сначала , применяя на каждом шаге Правило Бленда, а потом простым симплекс методом. При правиле Бленда мне потребовалось 6 итераций, при простом же методе решение было найдено на следующей итерации. А если применять лексикографический метод, то он будет применяться только тогда когда нужно, что не повлияет на количество итераций. Видимо сказывается эмпирическое правило, что нужно в качестве нового базиса выбирать элемент с наибольшим коэффициентом, ну я так думаю),
Правда вот у меня есть вопрос. При лексикографическом симплекс методе (модифицированном) если получаются два одинаковых минимальных отношения, последовательно просматриваются столбцы обращенного базиса и элементы, которые находятся на пересечении этих столбцов и строк, на которых получилось минимальное отношения делятся на соответствующие элементы ведущего столбца. Скажите, а если попался ноль в ведущем столбце, то на него делить же нельзя, тогда что делать?

[Someone]

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

damir_777 в сообщении #1229954 писал(а):

Скажите, а если попался ноль в ведущем столбце, то на него делить же нельзя, тогда что делать?

Ничего. Просто пропустить строку с нулём.

[damir_777]

К примеру если имеется большое множество переменных, которые являются кандидатами на базисные переменные. предположим выбирается переменная имеющая наибольший коэффициент. После выбора переменной, которая исключается из базиса, выясняется что значение функции не изменилось. Это что же получается, нужно сделать откат назад, и выбирать переменную по правилу Бленда, если применяется это правило. Это же лишняя итерация. Если такие ситуации будут происходить чаcто, то каждый раз нужно будет откатываться назад? Не лучше ли сразу тогда применять это правило?
Вы снизу пишите что нужно пропустить эту строку. Т.е если у меня имеется всего две строки с одинаковым мин. значением, и одно из значений в этой строке в ведущем столбце равно нулю. Это получается автоматически исключается переменная из базиса, в которой не ноль?
А может ли быть 2 нуля в той и той строке? тогда что выбирать. Я конечно знаю что при применение лексикографического правила итерации выполнятся за конечное число шагов, просто непонятно когда такие вот ситуации могут попасться

[Someone]

damir_777 в сообщении #1230020 писал(а):

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

Зачем же делать целую итерацию? Для этого нужно проверить два числа: оценку в ведущем столбце и свободный член в ведущей строке. Поскольку оценку Вы всё равно проверяете, чтобы она была отрицательной, остаётся посмотреть только свободный член. Если он нулевой — включаете правило Бленда. Если не нулевой — правило Бленда игнорируете.

damir_777 в сообщении #1230020 писал(а):

Т.е если у меня имеется всего две строки с одинаковым мин. значением, и одно из значений в этой строке в ведущем столбце равно нулю.

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

damir_777 в сообщении #1230020 писал(а):

предположим выбирается переменная имеющая наибольший коэффициент

Имеется в виду коэффициент в целевой функции (я привык называть его оценкой)? Выбор наибольшей по модулю отрицательной оценки не гарантирует, что приращение целевой функции будет наибольшим. Большие приращения целевой функции на начальных шагах легко могут привести к очень маленьким приращениям на последующих шагах.

[damir_777]

Цитата:

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

Я вот здесь понял в чем дело, задачу я решаю модифицированным симплекс методом, и у меня действительно был ноль в ведущем столбце, однако для этой строки, где был ноль все равно находилось симплекс отношение. Дело в том , что происходит так называемая генерация столбца (обратную матрицу умножаем на ведущий столбец) и свободный член делим уже на коэффициенты сгенерированного столбца. Поэтому, мне кажется , нужно при лексикографическом методе для модифицированного симплекс метода когда есть несколько одинаковых минимальных симплекс отношений находить мин. отношения для определения какая переменная выйдет из базиса между столбцами обращенного базиса и этого сгенерированного столбца. Скажите. правильна ли моя догадка? Но, кстати все равно правило Бленда дает больше итераций

[Someone]

Извините, я в модифицированном симплекс-методе не разбирался. Пусть кто-нибудь другой объяснит.