線形計画法 : LP(scipy.optimize.linprog)を利用

 線形計画法は線形関数を最適化する方法です。LPは様々なソルバーが揃っていますが、非線形計画をやることを考えてscipy.opimize.linprogを使ってみました。scipy.optimizeで非線形計画としても解けますが、微分などwarningが出てきますので、ここではlinprogを使っていきます。

scipy.opimize.linprog の仕様 : https://docs.scipy.org/doc/scipy/reference/optimize.linprog-interior-point.html

ソースコード

ポイントとしては、線形計画問題を Ax <= b の形で行列表現をして、それをソルバーに渡してあげます。等式制約の場合も同じです。x >= 0の場合もマイナスをかけて、不等式制約に当てはまるように変形します。

一つ例題3であげたもので、変数に制約が無い場合、boundsで制約をつけないとうまく計算ができませんでした。

このようなソルバーを使ったとき大規模化が問題になるので、大規模問題では検証が必要です。