線形計画法

線形計画法は第二次世界大戦の直後1947年にDantzigによって開発された。Dantzigのシンプレックス法の開発によって、その後急速に注目されるようになった。
線形計画法(linear programming)は、有限個の非負値変数からなる一次関数の最大または最小をそれらの変数からなる有限個の一次不等式あるいは一次等式の制約のもとに求めるもので、最大化あるいは最小化すべき関数を目的関数(objective function)、変数の満たすべき条件を制約条件(constraints)と呼ぶ。

問題定式化

ｎ個の変数、ｍ個の不等式制約条件からなる線形計画問題の典型的な形は次のように定式化されます。
制約条件：
A11X1 + A12X2 + ‥‥　+ A1nXn ≦ B1
A21X1 + A22X2 + ‥‥　+ A2nXn ≦ B2
‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
Am1X1 + Am2X2 + ‥‥　+ AmnXn ≦ Bm
X1, X2,‥‥,Xn ≧　0
目的関数： Z = C1X1 + C2X2 + ‥‥+ CnXn　の値を最大にする。

行列表現
max        Z = CX
sub to    AX ≦ B
             Xn ≧　0
最小化問題
min        Z = CX
sub to    AX ≧ B
             Xn ≧　0

[目標計画法へ戻る]