線形計画法 + pulp のハンズオン
線形計画法の概要
線型計画法（せんけいけいかくほう LP; linear programming ）は、数理計画法において、いくつかの1次不等式および1次等式を満たす変数の値の中で、ある1次式を最大化または最小化する値を求める方法である。線形計画法の対象となる最適化問題を線型計画問題という。 出典:[Wikipedia]
目的の変数に対して、複数の1次不等式や1次等式で制約を設けて最も大きい（小さい）目的変数を求めるやり方
ハンズオン
問題
example1
- 下記の制約条件をもとに、利益を最大化するにはどうすればよいか
- 工程1は1日7時間まで
- 工程2は1日14時間まで
| table | 物品A | 物品B |
|---|---|---|
| 工程1 | 2時間 | 2時間 |
| 工程2 | 3時間 | 5時間 |
| 利益 | 4千円 | 5千円 |
ソースコード
from pulp import *
# 問題オブジェクトを生成 prob = LpProblem(name='整数計画法exapmle1',sense=LpMaximize) # 変数設定 x1 = LpVariable('x1',lowBound=0) x2 = LpVariable('x2',lowBound=0) # 目的変数の設定 prob += 4*x1 + 5*x2 # 制約条件設定 prob += 2*x1 + 2*x2 <= 7,'ineq1' prob += 3*x1 + 5*x2 <= 14,'ineq2' # 問題出力 print('-------問題情報出力-------') print(prob) # 解を求める prob.solve() # どういう状態で解けたか print('-------解情報-------') print(LpStatus[prob.status]) # 最適値出力 print('-------最適値出力-------') print('Optimal Value ={}'.format(value(prob.objective))) # 最適解出力 print('-------最適解出力-------') for val in prob.variables(): print('{}={}'.format(val.name,value(val)))
結果
-------問題情報出力------- 整数計画法exapmle1: MAXIMIZE 4*x1 + 5*x2 + 0 SUBJECT TO ineq1: 2 x1 + 2 x2 <= 7 ineq2: 3 x1 + 5 x2 <= 14 VARIABLES x1 Continuous x2 Continuous -------解情報------- Optimal -------最適値出力------- Optimal Value =15.75 -------最適解出力------- x1=1.75 x2=1.75
まとめ
- 簡単な例はなんとなくわかった。
- 社会問題では立式するのが大変そう。
- 混合整数線形計画もやりたい。
