-Python- SciPy 線形計画問題

数理最適化は,与えられた制約の中で,ある関数の値を最大化(あるいは最小化)する問題です.数理最適化問題の基本として,まずは線形計画問題を考えます.

一般には,n変数の場合に線形計画問題を考えることができます.
n次元ベクトルxを変数とすると,線形計画法の一般型は以下のように表されます.

f:id:HidehikoMURAO:20181105111345p:plain

 

具体例として以下の条件のもと,3 x + 4 y を最大化する問題を考えます.

f:id:HidehikoMURAO:20181105111440p:plain

これらの指揮を一般型に当てはめることを考えます.一般型は最小化を考えているので,例の最大化の問題を当てはめるには目的関数の符号を反転して - ( 3 x + 4 y )の最小化問題と考えます.標準形に当てはめると以下のようになります.

f:id:HidehikoMURAO:20181105111500p:plain

すなわち,

f:id:HidehikoMURAO:20181105111512p:plain

となります.
スクリプトは以下のようになります.

 

# Import Module
import numpy as np
from scipy import optimize
 
c = np.array([-3, -4], dtype = np.float64)
G = np.array([[1, 4], [2, 3], [2, 1]], dtype = np.float64)
h = np.array([1700, 1400, 1000], np.float64)
sol = optimize.linprog(c, A_ub = G, b_ub = h, bounds = (0, None))
 
print(sol.x)

 

print(sol.fun)
 
上記のスクリプトでは,SciPyの関数scipy.optimize,linprog を使って線形計画問題を解いています.この関数では,標準形でc にあたるものは引数c で,GhAbにあたるものはそれぞれA_ub,b_ub,A_eq,b_eqで指定しています.
全ての変数の上限と下限を引数 bounds で設定できるので,制約式のうち最後の2つはこちらの引数を指定することで A_ub は3行の行列にすることができます.この場合下限は0で上限はないので,boundsの指定は(0, None)とします.このように上限または下限がないときはNoneで指定します.
 

実行結果は以下のようになります.

[400. 200.]
-2000.0
 
この結果は,(x, y) = (400, 200)のとき最適値は-2000ということです.標準形に変形するために目的関数の符号を変えているので,元の式の最適値は2000ということになります.