Помогите с зацикливанием симплекс-метода

[slimsaw]

Здравствуйте, товарищи! Поздравляю всех с великим праздником победы!

Помогите, пожалуйста! Уже замучился...
Проблема такая: написал программу симплекс-метода, а он зацикливается. Точнее я решаю задачу не симплекс-методом, а М-методом (метод искусственного базиса). Но не суть. При каждом новом запуске программы генерируется новая исходная матрица. Так вот при большой размерности матрицы, порядка 20 строк на 100 столбцов, симплекс начинает зацикливаться.
В одной книге прочитал, что можно бороться с зацикливанием с помощью модификации симплекс-метода: лексикографический симплекс-метод. Немного переписал программу как было написано в книге. Стало меньше зацикливаться, но полностью не прекратилось.

Подскажите, пожалуйста, есть ли какие-нибудь другие способы борьбы с зацикливанием? В интернете не нашёл.

[Alexey1]

Для симплекс-метода (применительно к реализации в симплекс-таблицах) можете использовать Bland's Rule:
1. При определении переменной $x_j$ которую будете включать в базис (переменная с отрицательной симплексной разностью), выбирается переменная с наименьшим индексом.
2. Из всех переменных $x_i$ которые можно исключить из базиса выбирается та, которая имеет наименьший индекс.

[slimsaw]

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

[Alexey1]

Данное правило гарантировано избегает зацикливания (доказано). Может Вы что-то не так делаете? Посмотрите ещё раз это правило.

[Vadim Shlovikov]

slimsaw в сообщении #317437 писал(а):

Здравствуйте, товарищи! Поздравляю всех с великим праздником победы!

Помогите, пожалуйста! Уже замучился...
Проблема такая: написал программу симплекс-метода, а он зацикливается. Точнее я решаю задачу не симплекс-методом, а М-методом (метод искусственного базиса). Но не суть. При каждом новом запуске программы генерируется новая исходная матрица. Так вот при большой размерности матрицы, порядка 20 строк на 100 столбцов, симплекс начинает зацикливаться.
В одной книге прочитал, что можно бороться с зацикливанием с помощью модификации симплекс-метода: лексикографический симплекс-метод. Немного переписал программу как было написано в книге. Стало меньше зацикливаться, но полностью не прекратилось.

Подскажите, пожалуйста, есть ли какие-нибудь другие способы борьбы с зацикливанием? В интернете не нашёл.

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

[Alexey1]

Vadim Shlovikov в сообщении #317721 писал(а):

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

Ну наверное любая последовательность выбора переменных всё же не подойдёт.

[Vadim Shlovikov]

Alexey1 в сообщении #317732 писал(а):

Vadim Shlovikov в сообщении #317721 писал(а):

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

Ну наверное любая последовательность выбора переменных всё же не подойдёт.

А Вы предлагайте последовательности выбора переменных в качестве базисных. Одобренную большинством голосов последовательность выбора переменных в качестве базисных будем внедрять вместо нынешних правил выбора переменных в качестве базисных.

[slimsaw]

Alexey1 в сообщении #317623 писал(а):

Данное правило гарантировано избегает зацикливания (доказано). Может Вы что-то не так делаете? Посмотрите ещё раз это правило.

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

Вот я в одной книге ещё нашёл: "Разработаны различные модификации симплекс-метода, позволяющие избежать зацикливания. Одна из подобных модификаций основана на том соображении, что вырожденность задачи обусловлена неудачным расположением вектора b правой части ограничений. Чтобы ликвидировать это неудачное расположение, нужно несколько сместить вектор b, заменив его на специально подобранный вектор b(E)."

В этой книге подробно этот метод на рассматривался, а в интернете что-то нет про это ничего.
Кто знает этот метод, расскажите пожалуйста.

[Alexey1]

Метод о котором Вы говорите заключается в следующем. Ограничения записываются в виде $Ax=b+\vec\epsilon, \ \vec\epsilon=(\epsilon \ \epsilon^2 \ ...\ \epsilon^m)^T$, где $\epsilon$ некоторая достаточно маленькая константа. Для данной задачи существует такое $\epsilon^*$, что все базисные решения для $0<\epsilon<\epsilon^*$ данной задачи невырожденные (отсюда и требование, чтобы $\epsilon$ была достаточно маленькой величиной). После того как найдено оптимальное решение для данной задачи, решение для первоначальной задачи получается при $\epsilon=0$.

[slimsaw]

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

P.S. Мои матрицы состоят из 0 и 1

[Yu_K]

slimsaw в сообщении #318017 писал(а):

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

Что это за три способа - в смысле разные способы для случая одинаковых симплексных отношений (чтобы избежать зацикливания)?

Не могли бы привести матрицы свои здесь и ЦФ.

[Alexey1]

slimsaw в сообщении #318017 писал(а):

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

P.S. Мои матрицы состоят из 0 и 1

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

[slimsaw]

Yu_K в сообщении #318025 писал(а):

Что это за три способа - в смысле разные способы для случая одинаковых симплексных отношений (чтобы избежать зацикливания)?

Не могли бы привести матрицы свои здесь и ЦФ.

Ну да, два способа - чтобы избежать зацикливания (правило Бленда и лексикографический симпплекс) и один простой способ (без избежания зацикливания).
К сожалению, здесь привести свою матрицу я не могу, т.к. она большая. Вот ссылка на скачивание файла, в который я записал матрицу.
http://narod.ru/disk/20621849000/file.txt.html
Первые два числа - число строк и столбцов ограничений матрицы. Далее сама матрица, записанная по строкам (без правых частей ограничений).
Ещё должны быть ограничения вида Xj <= 1 (все переменные не больше единицы). В файле нет этих условий, но они дописываются в программе.
Целевая функция - все единицы. Правые части ограничений тоже все единицы. Ограничения в виде >=.
Это задача о рёберном покрытии графа. А матрица в файле - это матрица инциденций графа.

-- Вт май 11, 2010 18:32:54 --

Alexey1 в сообщении #318028 писал(а):

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

Именно так! Я сам удивляюсь! Я понимаю, что значение ЦФ должно быть одинаковым, но вот получаются разные значения.
А запрограммировано всё правильно. Я не раз проверял программу на тестовых примерах, всё работает.
Уж не знаю, что делать...

[Alexey1]

slimsaw в сообщении #318040 писал(а):

Именно так! Я сам удивляюсь! Я понимаю, что значение ЦФ должно быть одинаковым, но вот получаются разные значения.
А запрограммировано всё правильно. Я не раз проверял программу на тестовых примерах, всё работает.
Уж не знаю, что делать...

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

[Yu_K]

ПОИСК РЕШЕНИЯ в Excel находит минимум равный 10 и там действительно альтернативный оптимум (много вариантов решений) и находит максимум 88, когда все $x_i=1$ (ограничения неотрицательности переменных еще добавил). Если я так понял условие.