1
標準形と基底解(復習)
標準形の問題
等式制約において( )
とおくと
は の解(基底解)
とくに は実行可能基底解
シンプレックス法(単体法)とは
実行可能基底解=実行可能集合の頂点 頂点には必ず最適解がある
ただし,最大 個(全探索は不可)
効率よく頂点を探索する方法
⇒シンプレックス法(単体法)
3
シンプレックス法の原理
N B
NB
N N B
B N
B
N B
N B
n m
x N B
c c
b B c
x c x
c x
c c c c
b Nx
x Bx x x
N B A
m A
n m
R A
x b Ax
1 T
T 1
T
T T
T
,
) rank
, (
: 0
,
標準形最適解 かつ
1
b 0 c
Tc
TB
1N 0
B
N B簡単のため フルランク
基底行列,正則
B,N
に対応して分割
0
1
b
x B
要素に負の ものがある
現在の基底解は最適解ではない でないとき
なる 非基底変数 と増加
目的関数値が減少
をどこまで大きくできるか?
5
まで大きくできる.
とおくと
で,
でなければならないの 基底変数
と減少 目的関数
とすると
m i
y y
b
A B
y b
B b
x
A B
b B
x b
B x
N B
c c
b B
c x
i i
i
k B
k B
B
B k N
B k
, ,
1 0
min , 0
0 0
:
1 1
1 1
1
1 T
T 1
T
行列 A の第 k 列
基底変数 非基底変数
に対応する基底変数 としたとき
k i
i i
i k
x x
x y
b x
0 0
0 :
基底変数の入れ替え
(ピボット操作)
0
x y x B B
有界でない
小さくできる 目的関数をいくらでも
る いくらでも大きくでき
がない となる
:
0 i
y
i7
シンプレックス法の手順
へ.
と更新し 基底変数
のまま.
は そのほかの非基底変数 非基底変数
を求める.
なる を計算し,
そうでなければ,
い.
ならば終了.有界でな を計算.
を選ぶ.
なる非基底変数 そうでなければ,
は最適解.
ならば終了.
とおく.
を選ぶ.
初期実行可能基底解
Step1
0 ,
: Step4
0 :
Step3 : Step2
0 0
: Step1
0 , ,
: Step0
1
1 T T
1 T T
1 1
y b
x x
i y
b y
A B y
x N
B c c
x N
B c c
b B b
b B x
x
B k
i i k
k k B
N
B B
N
N B
b
iy
iy
i0 i 1 , , m
min
例題
0 ,
0
6 2
6 2
s.t.
3 2
max
2 1
2 1
2 1
2 1
x x
x x
x x
x x
0 ,
, ,
6 2
6 2
s.t.
3 2
min
4 3
2 1
4 2
1
3 2
1
2 1
x x
x x
x x
x
x x
x
x x
標準形への変換
9
非基底変数になる 基底に入る
なる を基底変数に入れる
どちらも負
とする
【反復1】
:
3 , 0 1
, 2 3
6 , 6 ,
: 3 :
Step4
1 ,
3 6
, 3 :
Step3
0 1
, 2 :
Step2
3 , 2 2
1
1 0 2
, 0 3
, 2 :
Step1
6 , 6 1 ,
0
0 , 1
: Step0
3
T T
T 4
3 1
2 2
1 1
T 1
1
1
1 1
T T
1 T 4
3
x
y b
x x x
x
i y
b y
b y
b
A B y
x
B N
B c c
b B b
x B
x x x
B
i i B
N
B B
スラック変数を基底→基底行列は単位行列,目的関数値は0
2 1 , x x
目的関数値は-6
非基底変数になる
なる を基底変数に入れる 最適解ではない
【反復2】
:
0 , 2 2
/ 3 , 2 / 1 2
3 , 3 ,
2 :
Step4
2 ,
2 2
, 6 :
Step3
0 2
/ 3 , 2 / 1 :
Step2
1 , 0 2
2
1 0 1
, 2 0
, 3 :
Step1
1 1
0 , 2
3 , 3 ,
4
T T
T 4
1 2
2 2
1 1
T 2
1
2
1 1
T T
1 T 4
1
x
y b
x x x
x
i y
b y
b y
b
A B y
x
B N
B c c
B b
B b
x x x
B
i i B
N B
3 2
, x x
目的関数値は-
10
11
10
3 / 4 , 3 / 1
1 0
0 3 1
, 2 0
, 0 :
Step1
2 1
1 , 2
2 , 2 ,
1 1
T T
1 T 2
1
最適値は
は最適解,終了.
現在の
【反復3】
x
B N
B c c
B b
B b
x x x
B N
B
非負
図で見ると
シンプレックス法は,反 復ごとに隣の頂点へ移 動する.
Δ
の幾何学的意味=ある辺に沿ってどこま で進めるか
x
1x
26
3 6 3
0
3 c 2
①
②
③
13
実行時の問題点
1.Step1において
c
NT c
BTB
1N
k 0
となる が複数あるk
→
どれを選んでもよいが, が最小の ものを選ぶと実用上有効(とされている). c
NT c
BTB
1N
k2.Step3において
b
iy
i となる が複数あるi
→
複数の基底変数が同時に0
になる.退化 (degenerate) している
負で絶対値最大
退化が起こると
目的関数値は変化しないが 基底の入れ替えがおこる
同じ基底解で循環する.
↓
循環を防ぐ方法:最小添字規則(
Bland
の規則)x
1x
26
3 6 3
0
という制約を追加
9
3 x
1 x
2
3 つの直線が交差 → 退化
15
シンプレックス・タブロー
シンプレックス法を,表を用いて計算する.
【同じ例題】
0 ,
, ,
6 2
6 2
s.t.
3 2
min
4 3
2 1
4 2
1
3 2
1
2 1
x x
x x
x x
x
x x
x
x x
または,タブロー
4 3
2 1
4 3
6 1
0 2
1
6 0
1 1
2
0 0
0 3
2
x x
x x
x x
初期タブロー
A b
c T
基底変数
b B 1
目的関数値×(-1)
17
6 1
0 2
1
6 0
1 1
2
0 0
0 3
2 : Step1
4 3
1
x x
x
を選ぶ.
えば どちらも負なので,例
6 1
0 2
1
6 0
1 1
2
0 0
0 3
2 : Step2,3
4 3
x x
y b
i i
を求める.
を計算し,
3 /
11
y
b
6 /
22
y
b
反復を繰り返す へ
負の要素があるので 掃き出し演算
Step1 3 1
2 / 1 2
/ 3 0
3 0
2 / 1 2
/ 1 1
6 0
1 2
0
6 1
0 2
1
6 0
1 1
2
0 0
0 3
2 : Step4
4 1 4 3
x x x x
ピボット
①この行をピボットで割る
②-
2
倍して引く③
1
倍して引くピボット以外のピボット 列の要素を
0
にするが基底に入る
x
119
終了
を選ぶ
2 3
/ 2 3
/ 1 1
0
2 3
/ 1 3
/ 2 0
1
10 3
/ 4 3
/ 1 0
0
3 1
2 / 1 2
/ 3 0
3 0
2 / 1 2
/ 1 1
6 0
1 2
0 : Step1
2 1 4 1
2
x x x
x
x ピボット
2 /
6 /
2 2
1 1
y b
y b
すべて非負 → 最適
最適値は- 10
2 2
2 1
x
最適解 x
シンプレックス法のまとめ
実行可能解の隣にある頂点を探索する方法
→ 頂点の数は有限個 → 有限回で終了
計算機上ではタブローを用いて計算
残っている問題点
初期実行可能解? 計算量?
21
演習課題
次の例題をシンプレックス法(タブロー)を用い て解け.(締め切り: 5 月 9 日(木) 16 時Ⅳ系事務 室)
0 ,
0
4 . 2 3
. 0 4
. 0
6 5
. 0 2
. 1
5 . 1 3
. 0 1
. 0 s.t.
6 3
max
2 1
2 1
2 1
2 1
2 1