2.線形計画
Linear Programming (LP)
はじめに
例題1(生産計画問題)のような問題
変数は全て連続値
目的関数,等式・不等式制約が全て一次式
(線形)
1975 ノーベル経済学賞(最適資源割り当て
の理論 Kantrovich 1939,Koopmans 1947 )
シンプレックス法( Dantzig 1947 )
(等式)標準形
0 ,
s.t.
min T
b x Ax
x c
1.最小化問題
2.等式制約のみ
3.変数には非負制約
どのような問題も標準形で表現できるか?
補足
行 列
標準形への変換
1. →
2. 変数 に制約がない →
3. →
4. →
x c
Tmax
i j
j
ij
x b
a
i j
j
ij
x b
a
x
ix c )
T(
min
1
を掛けてを追加 とおきかえ,
0 , 0
i
i i ii
x x x x
x
j
i i
j ij
i
b y
x a
y を用い
スラック変数 0
ij j i ii
a x z b
z を用い
数)
スラック変数(剰余変
0
は制約なし
2 1
2 1
2 1
2 1
, 0
6 5
4
15 8
2 s.t.
5 2
max
x x
x x
x x
x x
標準形への変換(例題)
1.最大化 → 最小化
は制約なし
2 1
2 1
2 1
2 1
, 0
6 5
4
15 8
2 s.t.
5 2
max
x x
x x
x x
x x
標準形への変換(例題)
は制約なし
2 1
2 1
2 1
2 1
, 0
6 5
4
15 8
2 s.t.
5 2
min
x x
x x
x x
x x
は制約なし
2 1
2 1
2 1
2 1
, 0
6 5
4
15 8
2 s.t.
5 2
min
x x
x x
x x
x x
0 ,
0 ,
0
6 5
5 4
15 8
8 2
s.t.
5 5
2 min
3 2
1
3 2
1
3 2
1
3 2
1
x x
x
x x
x
x x
x
x x
x
標準形への変換(例題)
2.制約なし → 非負制約
は制約なし
2 1
2 1
2 1
2 1
, 0
6 5
4
15 8
2 s.t.
5 2
min
x x
x x
x x
x x
0 ,
, ,
,
6 5
5 4
15 8
8 2
s.t.
5 5
2 min
5 4
3 2
1
5 3
2 1
4 3
2 1
3 2
1
x x
x x
x
x x
x x
x x
x x
x x
x
3.4.スラック変数,等式制約
標準形への変換(例題)
0 ,
0 ,
0
6 5
5 4
15 8
8 2
s.t.
5 5
2 min
3 2
1
3 2
1
3 2
1
3 2
1
x x
x
x x
x
x x
x
x x
x
0 ,
0 ,
0
6 5
5 4
15 8
8 2
s.t.
5 5
2 min
3 2
1
3 2
1
3 2
1
3 2
1
x x
x
x x
x
x x
x
x x
x
は制約なし
2 1
2 1
2 1
2 1
, 0
6 5
4
15 8
2 s.t.
5 2
max
x x
x x
x x
x x
標準形への変換のまとめ
標準形
0 ,
, ,
,
6 5
5 4
15 8
8 2
s.t.
5 5
2 min
5 4
3 2
1
5 3
2 1
4 3
2 1
3 2
1
x x
x x
x
x x
x x
x x
x x
x x
x
基底解と最適解
0 ,
0
6 2
6 2
s.t.
max
2 1
2 1
2 1
2 1
x x
x x
x x
x x
【例題】
x
1x
26
3 6 3
実行可能集合 0
1 c 1
大
小
最適解
0 ,
0
6 2
6 2
s.t.
2 max
2 1
2 1
2 1
2 1
x x
x x
x x
x x
目的関数を変更
x
1x
26
3 6 3
0
2 c 1
大
小
最適解集合
両端は頂点
非基底変数 基底変数
非基底行列 基底行列
は実行可能基底解 とくに
凸多面体の頂点 基底解
の解 は
とおくと
とする 列
行
: ,
:
: ,
:
0
solution) (Basic
, 0
) (
: 0
,
1
1
N B
x x
N B
x b
B
b b Ax
x B x
x x N
B A
n m
n m
A x
b Ax
x
の要素のうちn-m
個を0
に固定し残りを計算→
頂点0
1
,
NB
B b x
x
はスラック変数
4 3
4 3
2 1
4 2
1
3 2
1
2 1
, 0
, ,
,
6 2
6 2
s.t.
min
x x
x x
x x
x x
x
x x
x
x x
例題を標準形に変換
6 , 6
1 0
2 1
0 1
1
2 b
A
基底解は6個
①
②
③
T1
2 1
0 0
2 2
2 2 6
6 2
1
1 , 2
2 1
1 2
x
x x x
B
B 6 0 6 0
T0 , 1
1
2
x
B
3 0 0 3
T1 , 1
0
2
x
B
A
の1列目A
の2列目)
(非基底変数は 基底変数は
4 3
2 1
, ,
x x
x
A
の1列目A
の3列目x
3 1
, x
x
基底変数は④
⑤
⑥
0 3 3 0
T0 , 2
1
1
x
B
0 6 0 6
T1 , 2
0
1
x
B
0 0 6 6
T1 , 0
0
1
x
B
x
1x
26
3 6 3
0
①
③ ②
⑤
④
⑥
実行可能基底解は
①,③,④,⑥の4つ
目的関数値
① ー4,③ ー3
④ ー3,⑥ 0
2
1