2014 dxdy logo

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

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


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


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

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

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

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

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



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


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

Действительно, похоже на верное решение. У меня задача на минимум.
Я вот думаю отказаться от симплекса. Не подскажите метод решения задачи линейного программирования? Какой попроще?

-- Вт май 11, 2010 21:50:34 --

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

Ну не знаю. Всё таки надо, чтобы один метод сразу решал задачу. Может взять другой метод решения задачи линейного программирования?

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


07/10/07
21
Я сейчас повнимательнее изучил, что происходит в программе. Стал записывать все промежуточные результаты в файл и смотреть.
Вот что я заметил. Во всех случаях, когда симплекс начинал зацикливаться или неправильно считать происходило вот что.
На определённом шаге алгоритма разрешающим (главным) элементом оказывалось число, очень близкое к нулю. Чуть больше нуля.
И после преобразования матрицы, в матрице появлялись очень большие числа, на порядок больше всех остальных. И дальше на всех последующих шагах симплекса, в матрице были большие числа.
Мне кажется, с зацикливанием связан выбор очень маленького числа в качестве разрешающего элемента.
Что скажете, мои догадки верны? И что можно сделать?

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


08/09/07
841
В принципе да, дело может быть и в чисто вычислительных процедурах. То что должно быть нулём после точных вычислений, может быть отличным от нуля если вычисления проводить на компьютере, и наоборот. Кстати, может кто из форума "Computer Sciences" знает как разрешать такие проблемы.

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


02/11/08
1187
Ваша матрица 88*20 + добавляете еще 20 переменных, чтоб получить каноническую форму, и неравенства $x_i\leq 1$ тоже превращаете в равенства - это еще добавит 88 переменных. Итого 2*88+20 переменных - суровая получается задача. Может можно доказать, что дополнительных переменных вводить не надо - тогда достаточно правильно найти начальное приближение (решение в Excel дает точное выполнение равенства в 20-ти исходных неравенствах). Или к двойственной перейти - число переменных уменьшится.

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

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


07/10/07
21
Ошибку я не нашёл, но проблему решил.
Просто поставил в программе условие, что если искусственные переменные выведены из базиса и целевая функция не увеличивается определённое количество итераций, то прекратить выполнение программы и вывести текущий результат. И ведь выводит правильный ответ!
Всем спасибо за помощь! :-)

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


20/03/11
1
Есть очень удобная программа для решения задач симплекс-методом.

Скачать можно тут: http://alexeyspace.ru/programs/2/

Скриншот:

Изображение

Там же можно купить курсовую по симплекс-методу, а также исходники этой программы.

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


07/10/15

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

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

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



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

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


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

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