Линейное программирование в python?

Мне нужно создать модель линейного программирования. Вот те неравенства, которые я использую (например):

6x + 4y <= 24
x + 2y <= 6
-x + y <= 1
y <= 2

Мне нужно найти область, описываемую этими неравенствами, и затушевать ее на графике, а также отслеживать вершины ограничивающих линий этой области и нарисовать границу линии другого цвета. См. График ниже для примера того, что я ищу.

image of the points of intersection.

Я использую Python 3.2, numpy и matplotlib. Существуют ли лучшие модули для линейного программирования в Python?

Ответы

Ответ 1

ОБНОВЛЕНИЕ: Ответ стал несколько устаревшим за последние 4 года, вот обновление. У вас есть много вариантов:

  • Если вам не нужно делать это на Python, тогда гораздо проще сделать это в языке моделирования, см. Какие-нибудь хорошие инструменты для решения целочисленных программ на Linux?

  • Я лично использую Gurobi в эти дни через его Python API. Это коммерческий продукт с закрытым исходным кодом, но бесплатный для академических исследований.

  • SciPy предлагает линейное программирование: scipy.optimize.linprog. (Я никогда не пробовал это.)

  • С помощью PuLP вы можете создавать файлы MPS и LP, а затем решать их с помощью GLPK, COIN CLP/CBC, CPLEX или XPRESS через интерфейс командной строки. Этот подход имеет свои преимущества и недостатки.

  • Очевидно, CVXOPT предлагает интерфейс Python для GLPK, я этого не знал. Я использую GLPK уже 8 лет, и я настоятельно рекомендую GLPK. Примеры и учебник по CVXOPT кажутся действительно хорошими!

  • Вы можете найти другие возможности в Wikibook под GLPK/Python. Обратите внимание, что многие из них не обязательно ограничены GLPK.

Ответ 2

Я бы порекомендовал пакет cvxopt для решения задач выпуклой оптимизации в Python. Короткий пример с кодом Python для линейной программы приведен в документации по cvxopt здесь.

Ответ 3

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

Что касается Python, то, хотя есть некоторые чистые библиотеки Python, большинство людей используют нативную библиотеку с привязками Python. Существует большое количество бесплатных и коммерческих библиотек для линейного программирования. Для получения подробного списка см. Линейное программирование в Википедии или Обзор программного обеспечения для линейного программирования в OR/MS Today.

Отказ от ответственности: в настоящее время я работаю в Gurobi Optimization и ранее работал в ILOG, которая предоставила CPLEX.

Ответ 4

Другие ответы сделали хорошую работу, предоставив список решателей. Тем не менее, только PuLP был упомянут в качестве библиотеки Python для разработки моделей LP.

Еще один отличный вариант - Pyomo. Как и PuLP, вы можете отправить задачу любому решателю и прочитать решение обратно в Python. Вы также можете управлять параметрами решателя. Мы с одноклассником сравнили производительность PuLP и Pyomo еще в 2015 году и обнаружили, что Pyomo может создавать файлы .LP для одной и той же проблемы в несколько раз быстрее, чем PuLP.

Ответ 5

Для решения проблемы линейного программирования вы можете использовать модуль scipy.optimize.linprog в SciPy, который использует алгоритм Simplex.

Ответ 6

Я бы рекомендовал использовать PuLP пакет python. Он имеет приятный интерфейс, и вы можете использовать различные типы алгоритмов для решения LP.

Ответ 7

lpsolve - самый легкий для меня. Не нужно устанавливать отдельный решатель. Он поставляется в пакете.