Параметр для верхней и нижней границы в решателях линейного программирования

Question

Многие вычислительные платформы scientifi c предоставляют решение для линейного программирования. Например, есть функция linprog в MATLAB, Scipy и DolphinDB. И linprog во всех этих трех платформах предоставляет параметр для ограничений неравенства, а именно A, и два параметра для ограниченных переменных, а именно lb и ub.

Если задача линейного программирования ограничена переменных, я мог бы поместить их в ограничения неравенства A, добавив строку, содержащую только одну 1 или -1 с остальными элементами 0, или, альтернативно, я мог бы просто поместить их в lb и / или ub.

Есть ли разница между этими двумя способами? Или есть причина, по которой я должен отдать предпочтение A над lb / ub или наоборот?

Answer 1

Границы немного более эффективны, чем явные ограничения. По сути, в решателе Simplex граница не увеличивает размер базовой матрицы. Эта базовая матрица должна быть решена и инвертирована (разложена на множители).

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