37

線形計画法モデルを作成する必要があります。私が使用している不等式は次のとおりです（たとえば）：

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

これらの不等式で表される領域を見つけ、グラフで影を付け、この領域の境界線の頂点を追跡し、境界線を別の色で描画する必要があります。私が探しているものの例については、下のグラフを参照してください。

交点のイメージ.

Python 3.2、numpy、matplotlib を使用しています。Python での線形計画法のより良いモジュールはありますか?

4

7 に答える 7

69

更新:過去 4 年間で回答がやや古くなっています。ここに更新があります。多くのオプションがあります:

  • Pythonでそれを行う必要がない場合は、モデリング言語でこれを行う方がはるかに簡単です。Linuxで整数プログラムを解決するための良いツールはありますか?を参照してください。

  • 私は最近、Python API を通じてGurobiを個人的に使用しています。これは商用のクローズドソース製品ですが、学術研究には無料です。

  • PuLPを使用すると、 MPSおよびLP ファイルを作成し、コマンドライン インターフェイスを介して GLPK、COIN CLP/CBC、CPLEX、または XPRESS でそれらを解決できます。このアプローチには、長所と短所があります。

  • GoogleのOR-Toolsは、最適化のためのオープン ソース ソフトウェア スイートであり、配車ルート、フロー、整数および線形計画法、制約プログラミングにおける世界で最も困難な問題に取り組むように調整されています。

  • Pyomoは、さまざまな最適化機能を備えた Python ベースのオープンソースの最適化モデリング言語です。

  • SciPy は線形プログラミングを提供します: scipy.optimize.linprog。（私はこれを試したことはありません。）

  • どうやらCVXOPTは GLPK へのPython インターフェイスを提供しているようですが、私はそれを知りませんでした。私はGLPKを 8 年間使用しており、GLPK を強くお勧めします。CVXOPTの例とチュートリアルは本当にいいですね!

  • ウィキブックのGLPK/Pythonで他の可能性を見つけることができます 。これらの多くは、必ずしも GLPK に制限されているわけではないことに注意してください。

于 2012-05-22T16:06:12.507 に答える
20

Python で凸最適化問題を解決するには、パッケージcvxoptをお勧めします。線形プログラムの Python コードを使用した短い例は、cvxopt のドキュメントhere にあります。

于 2012-05-22T09:42:35.493 に答える
6

線形計画法を解くためにグラフが使用されるのは、宿題の問題だけです。それ以外の場合、線形計画問題は行列線形代数によって解決されます。

Python に関しては、純粋な Python ライブラリがいくつかありますが、ほとんどの人は Python バインディングを備えたネイティブ ライブラリを使用します。線形計画法には、さまざまな無料および商用のライブラリがあります。詳細なリストについては、Wikipedia の Linear Programming または OR/MS Today のLinear Programming Software Surveyを参照してください。

免責事項: 私は現在 Gurobi Optimization で働いており、以前は CPLEX を提供する ILOG で働いていました。

于 2012-05-23T02:11:55.947 に答える
4

線形計画法の問題を解決するには、シンプレックス アルゴリズムを使用する SciPyのscipy.optimize.linprogモジュールを使用できます。

于 2015-10-02T06:48:40.223 に答える
0

lpsolve は私にとって最も簡単です。別のソルバーをインストールする必要はありません。パッケージに同梱されています。

于 2014-11-02T18:04:39.857 に答える