проблеммы с улучшенным симплекс-методом

[Andrey_Kireew]

Добрый день,
не так давно реализовал программу для решения своей задачи с помощью простого симплекс-метода.
В принципе программа работает хорошо, однако из интереса, попробовал использовать для решения той же задачи улучшенный симплекс-метод (метод обратной матрицы, модифицированный симплекс-метод). Долгое время алгоритм отказывался работать, хотя много раз перепроверял и всё было правильно. Чтобы найти ошибку - стал просматривать последовательность матриц обращения, симплекс-множителей и симплекс-разностей (те что в строке целевой функции). Обнаружилось, что решение сначала идёт как и положено, функционал монотонно увеличивается и стремится к нулю (у меня задача ни минимум). В конце концов оптимальное решение достигается (судя по значениям столбца свободных членов), но среди оценок остаются очень маленькие отрицательные величины порядка -1Е-10, указывающие на то что план ещё не оптимален. Разумеется алгоритм продолжает работать. Пересчитывает столбец, вводимый в базис. В этом столбце один элемент получается равным единице, а остальные близки к нулю (то же порядка -1Е-10). После этого всё и "сыпется". После пересчёта матрицы обращения она меняется до неузнаваемости, а функционал "уходит" в плюс.
Пока я нашел только один выход - делать останов ни когда все оценки будут >=0, а когда они будут >=k, где k - маленькая отрицательная константа. В этом случае, если правильно подобрать k, всё работает нормально. Правда точность получается меньше, и алгоритм работает примерно в 10 раз медленнее простого симплекс-метода, хотя заявляется о его вычислительных преимуществах. Число итераций в обоих случаях одинаковое, получается модифицированный метод на каждом цикле требует выполнения большего числа вычислений. Посмотрев на задачу - я понял, что это действительно так. Пока вижу одни только недостатки. Допускаю что, это не общая тенденция, а лишь частный случай, свойственный моей конкретной задаче.

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

[Grabovskiy]

(Оффтоп)

Знаю только, что на методе обратной матрицы основан метод Данцига-Вульфа, который позволяет разбить "большую" задачу на серию "маленьких". А в программировании при работе с чем-нибудь вроде double всегда рекомендуется вместо неравенств типа $a > b$ писать $a > b-\varepsilon$. То же самое с равенствами: если нужно $a=b$, то следует писать $|a-b| < \varepsilon$. В частности, отношения $\leq$ и $\geq$ при работе с double не имеют смысла (а Вам нужно проверять неотрицательность).

[Andrey_Kireew]

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

[Grabovskiy]

Andrey_Kireew, а не пробовали ли Вы запускать этот метод в каком-нибудь онлайн приложении и там сравнить?

[Andrey_Kireew]

нет не пробовал, думаю в этом нет никакого смысла

[Andrey_Kireew]

у Банди в Основах линейного программирования этот метод описан довольно подробно и доходчиво, собственно я так и делал.
Но преимущество этого улучшенного метода мне представляются сомнительными и вот почему:
1. Заявляется что от устойчивее простого симплекс-метода к накоплению ошибок округления, потому что оценки (элементы нуль строки) равно как и разрешающий столбец текущего плана, всё время вычисляются по столбцам исходной таблицы. Так то оно так, но в этих вычислениях участвует матрица обращения и симплекс-множители, а они вычисляются рекуррентно, и при этих вычислениях накопление ошибок может быть даже больше. Конечно, может быть, если вместо Жордановых исключений использовать другой метод нахождения матрицы обращения (а в сети я встречал, что именно так и нужно делать), то о снижении вычислительной трудоёмкости алгоритма, на мой взгляд, говорить не приходится.
2. Заявляется, что алгоритм эффективнее в вычислительном отношении, так как всё время вычисляется только ведущий столбец таблицы среди всех остальных. Но при этом необходимо пересчитывать матрицу обращения. В простом методе она всегда единичная и её пересчёт почти не влияет на вычислительную сложность, основная сложность возникает при пересчёте столбцов не входящих в план. В улучшенном методе матрица обращения единичная только на первой итерации, потом она быстро "забивается" ненулевыми числами и основная сложность заключается именно в её пересчёте. Конечно, если число ограничений очень большое, а матрица обращения маленькая - преимущества неоспоримы, но если это не так, как в моём случае, то оказывается намного проще пересчитать все столбцы, не входящие в базис.

[Karan]

Andrey_Kireew, поправьте формулы в первом сообщении

[Karan]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.