Симплекс-метод с инструментом ограниченных переменных

Question

Есть ли надежный инструмент или исходный код (предпочтительно C++) для решения LP с ограниченными переменными симплекс-методом? В моей задаче все переменные ограничены 1.

Я действительно нашел некоторые инструменты в сообщениях Stackru: SoPlex, CLP и lpsolve.

Среди них SoPlex более обширный, я полагаю. В документации сказано, что SoPlex учитывает границы переменных. Тогда это говорит:

"Если все первичные переменные находятся в своих границах, то симплекс-базис называется первичным выполнимым. Аналогично, если все двойственные переменные находятся в своих границах, его называют двойственным выполнимым. Если базис является и первичным, и двойственным выполнимым, оптимальный решение найдено."

У меня сложилось впечатление, что он не заставляет базис находиться в пределах переменных, вместо этого он проверяет, находятся ли переменные решения в пределах границ. Если это так, он считает решение оптимальным.

Существуют ли какие-либо инструменты для поиска приемлемого решения с учетом переменных границ?

Answer 1

LP с ограниченными или коробочными переменными являются полностью нормальными и очень распространенными. Точно так же, как проблемы с дальними ограничениями, то есть ограничениями как с левой, так и с правой стороны.

SoPlex способен работать как первичным, так и двойным симплексом. Он начинается с слабого базиса - все переменные находятся на одной границе - и соответственно сдвигает границы, чтобы сделать этот базис первичным или двойственным осуществимым для соответствующего симплексного типа.

Еще одна возможность получить реальную основу - это использовать так называемую фазу 1. Это решает измененный LP и переключается обратно на оригинал.