線形計画法の概要

線型計画法（せんけいけいかくほう 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

まとめ

簡単な例はなんとなくわかった。
社会問題では立式するのが大変そう。
混合整数線形計画もやりたい。

参考

最適化におけるPython