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

[slimsaw]

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

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

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

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

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

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

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

[slimsaw]

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

[Alexey1]

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

[Yu_K]

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

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

[slimsaw]

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

[alex_ey]

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

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

Скриншот:



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

[Andrey_Kireew]

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