線形計画法の概要
線型計画法（せんけいけいかくほう 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千円 |
ソースコード
- pulpを用いて、利益の最大化問題を解く
- pulpは最適化問題を解くためのライブラリ
ライブラリインポート
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
まとめ
- 簡単な例はなんとなくわかった。
- 社会問題では立式するのが大変そう。
- 混合整数線形計画もやりたい。