線形計画問題
線形計画問題 は、ある条件下での 領域の最大・最小 を求める問題です。
数理最適化ライブラリのPuLP を使うと、線形計画問題 を解くことができます。
[問題]
ある工場では製品 p と製品 q を製造しています。 製品 p と製品 q を製造するには原料 m と原料 n が必要で、次のような条件となっています。 ・製品 p を1kg製造するには原料 m が1kg、原料 n が2kg必要。 ・製品 q を1kg製造するには原料 m が3kg、原料 n が1kg必要。 ・原料 m の在庫は30kg、原料 n の在庫は40kgあります。 ・単位量当たりの利益は、製品 p が1万円、製品 q が2万円です。 この条件で利益を最大にするためには、製品 p と製品 q をそれぞれ何kg製造すればよいでしょうか。
製品 p の製造量を x kg、と製品 q の製造量を y kgとすると以下のように不等号をつかった式にまとめることができます。
x + 3y ≦ 30
2x + y ≦ 40
x ≧ 0、y ≧ 0
連立方程式との違いは、等号(==) が 不等号(≧、≦) になっている点です。ソースコード
上記の条件式をもとにソースコードを作成すると下記のようになります。 [Google Colaboratory][実行結果]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 import pulp
# 第1引数は任意の名前、第2引数は最大化問題を解く指定
problem = pulp.LpProblem('Test', pulp.LpMaximize)
x = pulp.LpVariable('x') # 製品pを製造する量。変数xをpulp.LpVariable関数を定義。
y = pulp.LpVariable('y') # 製品qを製造する量。変数yをpulp.LpVariable関数を定義。
# 線形計画問題の条件式
problem += 1 * x + 3 * y <= 30
problem += 2 * x + 1 * y <= 40
problem += x >= 0
problem += y >= 0
problem += x + 2 * y # 目的関数。最大化する式。
status = problem.solve() # 数理モデルを解く
print('Status:', pulp.LpStatus[status]) # 結果
print('x =', x.value(), 'y =', y.value(), 'obj =', problem.objective.value()) # xとyの解と利益の関数値Status: Optimal x = 18.0 y = 4.0 obj = 26.0製品 p の製造量を 18kg、と製品 q の製造量を 4kgとしたときに利益を最大にできることが導きだされました。
obj = 26.0 は最大化しようとした利益の関数値です。(15行目)
x + 2 * y = 26 となることが確認できます。