2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Помогите с зацикливанием симплекс-метода
Сообщение09.05.2010, 22:44 


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

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

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

 Профиль  
                  
 
 Re: Помогите с зацикливанием симплекс-метода
Сообщение09.05.2010, 23:01 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Помогите с зацикливанием симплекс-метода
Сообщение10.05.2010, 14:03 


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

 Профиль  
                  
 
 Re: Помогите с зацикливанием симплекс-метода
Сообщение10.05.2010, 14:55 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Помогите с зацикливанием симплекс-метода
Сообщение10.05.2010, 18:51 
Заблокирован


05/09/09

144
г.Вологда.
slimsaw в сообщении #317437 писал(а):
Здравствуйте, товарищи! Поздравляю всех с великим праздником победы! :D

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

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

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

 Профиль  
                  
 
 Re: Помогите с зацикливанием симплекс-метода
Сообщение10.05.2010, 19:25 
Заслуженный участник


08/09/07
841
Vadim Shlovikov в сообщении #317721 писал(а):
Предлагаем радикальный метод: сначала решения задачи симплекс-методом установить последовательность выбора переменных в качестве базисных, вместо нынешнего необоснованного выбора переменных в качестве базисных по величине коэффициентов переменных линейной функции и системы условий, что не является критерием. Это позволит избежать не только зацикливания , но и избежать гаданий при выборе переменных в качестве базисных.
Ну наверное любая последовательность выбора переменных всё же не подойдёт.

 Профиль  
                  
 
 Re: Помогите с зацикливанием симплекс-метода
Сообщение10.05.2010, 19:48 
Заблокирован


05/09/09

144
г.Вологда.
Alexey1 в сообщении #317732 писал(а):
Vadim Shlovikov в сообщении #317721 писал(а):
Предлагаем радикальный метод: сначала решения задачи симплекс-методом установить последовательность выбора переменных в качестве базисных, вместо нынешнего необоснованного выбора переменных в качестве базисных по величине коэффициентов переменных линейной функции и системы условий, что не является критерием. Это позволит избежать не только зацикливания , но и избежать гаданий при выборе переменных в качестве базисных.
Ну наверное любая последовательность выбора переменных всё же не подойдёт.

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

 Профиль  
                  
 
 Re: Помогите с зацикливанием симплекс-метода
Сообщение11.05.2010, 12:00 


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

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

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

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

 Профиль  
                  
 
 Re: Помогите с зацикливанием симплекс-метода
Сообщение11.05.2010, 16:01 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Помогите с зацикливанием симплекс-метода
Сообщение11.05.2010, 16:30 


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

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

 Профиль  
                  
 
 Re: Помогите с зацикливанием симплекс-метода
Сообщение11.05.2010, 16:51 


02/11/08
1187
slimsaw в сообщении #318017 писал(а):
Я сейчас попытался решить симплексом задачу с одной и той же матрицей, тремя разными способами выбора ведущего элемента.

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

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

 Профиль  
                  
 
 Re: Помогите с зацикливанием симплекс-метода
Сообщение11.05.2010, 16:54 
Заслуженный участник


08/09/07
841
slimsaw в сообщении #318017 писал(а):
Я сейчас попытался решить симплексом задачу с одной и той же матрицей, тремя разными способами выбора ведущего элемента.
Все три раза были получены разные результаты, с разным значением целевой функции.
Такое вообще возможно?

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

 Профиль  
                  
 
 Re: Помогите с зацикливанием симплекс-метода
Сообщение11.05.2010, 17:28 


07/10/07
21
Yu_K в сообщении #318025 писал(а):
Что это за три способа - в смысле разные способы для случая одинаковых симплексных отношений (чтобы избежать зацикливания)?

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

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

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

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

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

 Профиль  
                  
 
 Re: Помогите с зацикливанием симплекс-метода
Сообщение11.05.2010, 17:45 
Заслуженный участник


08/09/07
841
slimsaw в сообщении #318040 писал(а):
Именно так! Я сам удивляюсь! Я понимаю, что значение ЦФ должно быть одинаковым, но вот получаются разные значения.
А запрограммировано всё правильно. Я не раз проверял программу на тестовых примерах, всё работает.
Уж не знаю, что делать...
Ну Вы же понимаете, что это неправильно. Что ещё может быть кроме как ни ошибка в программе? Вы посмотрите на ту часть программы, которая говорит, что найденное решение оптимальное. Действительно ли все симплекс-разности неотрицательные?
Что касается тестовых примеров, то они наверное были учебные, простые.
Попробуйте так, как только нашли оптимальное решение одним методом, начните поиск оптимального решения другим методом с этого найденного решения.

 Профиль  
                  
 
 Re: Помогите с зацикливанием симплекс-метода
Сообщение11.05.2010, 18:28 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group