はじめに

何らかの事情で線形計画問題を解くためのシンプレックス法(単体法)の既存実装を探しているが、
C/C++でバシっとかかれたOSSのソルバ(COIN-OR CLP, GLPKなど)は読みたくないという軟弱な人向けに、
比較的信用できそうなPython実装はこれですよというメモを書きます。
Nelder-Meadの単体法ではありません。

scipy.optimize.linprog

https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linprog.html
scipyはPythonの数値計算のための有名なライブラリで、
割と最近になってPythonによる単体法の実装が追加されています。

LL言語の数値計算パッケージにはたいてい最適化問題を解くためのメソッドが用意されていますが、中身は単なる既存ソルバのバインディングである場合が多いように思います。
ピュアPython実装があるのはうれしいですね。
利用者の多いライブラリで、テストコードもあって、LL言語によるピュア実装となると、多分これくらいだと思います。

cylp

https://github.com/coin-or/CyLP
こっちはシンプレックス法のPython実装というわけではないんですが、
CLPやCBCというC++で書かれたソルバをPythonでカスタマイズできるようにするライブラリです。
詳細な設計はこの論文に書かれています。

オレオレピボットルールを実装したいだけなんだという人はこれを使うと計算速度と簡単さを両立出来るかと思います。
ピボット規則はなんでもいいんだけど単体法の反復ごとに呼び出したいコールバック関数があるんだという場合でもcylpで実現できます。

Dantzigの規則の実装あたりを読んだらきっとわかるかと思いますが、PivotPythonBaseのインターフェースをいくつか実装すればオレオレピボット規則の単体法を動かすことが出来ます。

あと https://github.com/coin-or/CyLP/blob/master/cylp/py/pivots/ をみるといろいろなピボット規則の実装が載ってるので勉強になります。

自分が確認した時点ではPython3系への移行はまだなのですが、プルリクエストには来ているので、そっちのブランチを使えばPython3でもcylpを使えるかも知れません。