スライド タイトルなし - Morito Lab. 森戸研究室

「ORーA」 第12回
2012/01/06
• カッティングストック問題
–
–
–
–
–
問題紹介と定式化
LP版カッティングストック問題の解法の基本的考え方
被約費用を最小化するパターンを求める問題
(整数値)ナップザック問題
ナップザック問題の解法
• 動的計画法
1
2
(1次元)カッティングストック問題
•
•
•
•
45cm の長さの板 x 97枚
36cm の長さの板 x 610枚
31cm の長さの板 x 395枚
14cm の長さの板 x 211枚
100cm
45cm
36cm
14cm
3
カッティングストック問題の定式化
最小化 z =x1+x 2+x3+x 4+x5+・・・
1

0
制約条件 0

0


0



1
x
+
 1 0



0



0 
0

 

0

 
0
x
+
x
+
 2 1  3 0

 


0 
1

 


1



1
x
+
 4 0



1





x 5+・・・≧



 97 


610


 395


 211


• xj=第j カッティングパターンの使用回数
• xj≧0,整数
4
LP版カッティングストック問題
• 整数計画は(LPに比べて)解きにくい
• そこでLP版CS問題を考える(切上げ解は必
ず実行可能)
• 板の長さLが、需要の長さに比べて長いと、
カッティングパターンの数は膨大になる
• あらかじめすべてのカッティングパターンを列
挙しておくことは無理。LP版CSも、列が膨大
だと困る→必要に応じパターンを生成できない
か?
→列生成法
→改訂単体法で必要な情報を復元
5
カッティングストック問題の定式化
最小化 z =x1+x 2+x3+x 4+x5+・・・
1

0
制約条件 0

0


0



1
x
+
 1 0



0



0 
0

 

0

 
0
x
+
x
+
 2 1  3 0

 


0 
1

 


1



1
x
+
 4 0



1





x 5+・・・≧



• xj=第jカッティングパターンの使用回数
• xj≧0,整数
 97 


610


 395


 211


6
スタート
初期可能基底解
(を示す単体表の一部)
-
cj=cj-πAj
Ajの生成
π
最適性の判定と
軸の列の生成
新しい可能基底解
改訂単体法
の1反復
ナップザック問題
B-1Aj
ストップ
復元された軸の列の追加
最適?
列生成
LP版カッティングストック問題
を列生成+改訂単体法で解く
標準的改訂単体法との違い
①初期可能基底形式の設定にあたって注意
(スラック変数でなく、実際のカッティングパター
ンに対応する変数を初期基底変数とするため)
②双対価格の現われ方が違うので注意
(「いつも、πが見えていたところにπ-1がある;
理由は、①と同じで、初期基底変数の元の問題
の目的関数の係数が1だから)
③列(=パターン)があらかじめ列挙されてい
ないので、その生成が必要(ナップザック問題)
7
8
LP版CS問題の初期可能基底解
No.00
元問題
x1
-1
1
0
0
0
x2
-1
0
1
0
0
x3
-1
0
0
1
0
x4
-1
0
0
0
1
…
-1
…
…
…
…
右辺定数 基底変数
0
z
97
x1
45cm
610
x2
36cm
395
x3
31cm
211
x4
14cm
これは、基底形式ではない!なぜ?
No.0
初期単体表
x1
0
1
0
0
0
x2
0
0
1
0
0
x3
0
0
0
1
0
x4
0
0
0
0
1
…
…
…
…
…
…
右辺定数 基底変数
1313
z
97
x1
45cm
610
x2
36cm
395
x3
31cm
211
x4
14cm
目的関数の行に、制約の各行を加えればよい
9
双対価格π=cBB-1の読み方に注意(∵
初期基底変数の目的関数の係数が1)
初期基底に対する双対価格π=cBB-1=cBI =cB =(1,1,1,1)
- c 1 =-(c1-πA1)=-1+
π 1π 2π 3π 4
=-1+π1
π-1
No.0
初期単体表
x1
0
1
0
0
0
x2
0
0
1
0
0
x3
0
0
0
1
0
x4
0
0
0
0
1
…
…
…
…
…
…
右辺定数 基底変数
1313
z
97
x1
45cm
610
x2
36cm
395
x3
31cm
211
x4
14cm
よって、 πの値は緑の数字+1;つまり、π1=π2=π3=π4 =1
1
0
0
0
双対価格自身が現れない理由
12
• 初期可能基底解の基底変数の目的関数の係
数cj が0でない場合(例:スラック変数でない場合)
– 基底の逆行列B-1の「上」に双対価格が現われない
-
– なぜなら、c
j=cj-πAjであり、cj ≠0のため(ただし、
Aj は単位ベクトル)、 B-1の「上」にπi-cjが現われる
-
(単体表には-cj が現われることに注意)ため、B-1の上に現わ
れる数値にcj を加えた値がπの値となる
(非基底)カッティングパターン 15
の被約費用は?
• パターンをa=(a1,a2,...,am)t (列ベクトル)と表記
• 最小化 c -πta
=1- (π1.π2,…,πm )(a1,a2,...,am)t
=1-(π1a1+π2a2+...+πmam)
• 最大化
(π1a1+π2a2+...+πmam)- 1
といっても、基本的に同じこと
• 制約条件
1a1+  2a2+...+  mam ≦ L
aiは非負整数、  i は需要iの長さ(定数)
被約費用最小の非基底カッティングパターンを求める 16
整数値ナップザック問題
• 最小化 c -πta =1- (π1.π2,…,πm )(a1,a2,...,am)t
• 最大化 π1a1+π2a2+...+πmam- 1
制約条件  1a1+  2a2+...+  mam ≦ L
aiは≧0かつ整数(変数)、
 i は需要iの長さ(定数)
• π=(1,1,1,1)
• 最大化
a 1 + a2 + a3 + a4 - 1
制約条件 45a1+36a2+ 31a3+14a4 ≦100
ai ≧0かつ整数(変数)
• 最小被約費用の値は、1-「ナップザック問題の最適値」
注:CS問題の解の改善という観点からは、被約費用が負でさえあればよく、 KPが最適に解けていなくてもよい
No.0
初期単体表
45cm
36cm
31cm
14cm
x1
0
1
0
0
0
x2
0
0
1
0
0
x3
0
0
0
1
0
π=(1,1,1,1)
x4
0
0
0
0
1
x5
6
0
0
0
(7)
右辺定数 基底変数
1313
z
97
x1
610
x2
395
x3
211
x4
17
No.0
初期単体表
45cm
36cm
31cm
14cm
x1
0
1
0
0
0
x2
0
0
1
0
0
x3
0
0
0
1
0
x4
0
0
0
0
1
x5
6
0
0
0
(7)
右辺定数 基底変数
1313
z
97
x1
610
x2
395
x3
211
x4
x4
-6/7
0
0
0
1/7
x6
2
0
1
(2)
0
右辺定数 基底変数
7925/7
z
97
x1
610
x2
395
x3
211/7
x5
x4
-6/7
0
0
0
1/7
x7
9/7
0
2
0
(2)
右辺定数 基底変数
5160/7
z
97
x1
825/2
x2
395/2
x6
211/7
x5
18
π=(1,1,1,1)
No.1
初期単体表
45cm
36cm
31cm
14cm
x1
0
1
0
0
0
x2
0
0
1
0
0
x3
0
0
0
1
0
1132.14
30.14
π=(1,1,1,1/7)
No.2
初期単体表
45cm
36cm
31cm
14cm
x1
0
1
0
0
0
x2
0
0
1
0
0
x3
-1
0
0
1/2
0
π=(1,1,0,1/7)
737.14
412.5
197.5
30.14
19
(整数値)ナップザック問題
• 整数値ナップザック問題(KP):一般形
max z = ∑i=1,…,m πi ai ( - 1)
s.t.
∑i=1,…,m  i ai ≦ L
ai ≧ 0, 整数
• 具体的数値例 (カッティングストック問題の例)
max z = ∑i=1,…,4 ai ( - 1) (各πi =1の場合)
s.t.
45a1+36a2+ 31a3+14a4 ≦100
ai ≧ 0, 整数
20
(整数値)ナップザック問題の最適解法
max z = ∑i=1,…,m πiai ( - 1)
s.t.
∑i=1,…,m  j ai ≦ L,
ai ≧ 0, 整数
• 動的計画法(Dynamic Programming; DP)
f (y) = 重量制限yのナップザックに詰め込むことの
できる最大の価値
f (y) = max i=1,…,m { πi + f (y - i )} 漸化式
y = min ,..., L に対して、順次f (y)を計算。最終的に、
f (L)が解きたい問題の最適値。ただし、
 min = min i=1,…,m {  i }
• DPの他に分枝限定法による列挙解法もあり
ナップザック問題のDP解法:数値例
21
max z = ∑i=1,…,m ai
s.t.
45a1+36a2+ 31a3+14a4 ≦100
j
ai ≧ 0, 整数
• f (y) = 重量制限y のナップザックに詰め込むことので
きる最大の価値
– 自明に、f (y) = 0,y=0,…,13; f (y) =-∞,y=負
• f (y) = max i=1,…,m { πi + f (y -  i )} 漸化式
• y = min ,..., L に対して、順次f (y)を計算。最終的に、
f (L)= f (100)が解きたい問題の最適値。ただし、
min = min i=1,…,m {  i } = 14
– ほぼ自明に、f (y) =1=14,…,27
y
0~13
14~27
28~30
31~35
36~41
42~44
45~49
50~55
56~58
59~61
62~63
64~65
66~70
70~71
72
73~75
76
77
78~79
80
81~83
84
85~86
(中略)
98
99
L=100
f(y)
0
1
2
2
2
3
3
3
4
4
4
4
4
5
5
5
5
5
5
5
6
6
6
7
7
7
i=1 i=2 i=3 i=4
1+f (y-45) 1+f (y-36)
1+f(y-31)
1+f(y-14)
1+(-∞)=-∞
1+(-∞)=-∞
1+(-∞)=-∞
1+(-∞)=-∞
1+(-∞)=-∞
1+0=1 1+0=1 1+0=1 1+1=2 1+1=2 1+1=2 1+1=2 1+1=2 1+1=2 1+2=3 1+2=3 1+2=3 1+2=3 1+2=3 1+2=3 1+2=3 1+2=3 -∞ -∞ -∞ 1+ 0=1
1+ 0=1
1+ 0=1
1+ 1=2
1+ 1=2
1+ 1=2
1+ 2=3
1+ 2=3
1+ 2=3
1+ 2=3
1+ 2=3
1+ 2=3
1+ 2=3
1+ 2=3
1+ 3=4
1+ 3=4
1+ 3=4
1+ 3=4
1+ 3=4
1+3=4 1+ 4=5
1+3=4 1+ 4=5
1+3=4 1+ 4=5
d(y)
-∞
-∞
1+ 0=1
1+ 0=1
1+ 0=1
1+ 1=2
1+ 1=2
1+ 1=2
1+ 2=3
1+ 2=3
1+ 2=3
1+ 2=3
1+ 2=3
1+ 2=3
1+ 3=4
1+ 3=4
1+ 3=4
1+ 3=4
1+ 3=4
1+ 3=4
1+ 3=4
1+ 3=4
1+ 0=1
1+ 1=2
1+ 1=2
1+ 1=2
1+ 2=3
1+ 2=3
1+ 2=3
1+ 3=4
1+ 3=4
1+ 3=4
1+ 3=4
1+ 3=4
1+ 4=5
1+ 4=5
1+ 4=5
1+ 4=5
1+ 4=5
1+ 4=5
1+ 4=5
1+ 4=5
1+ 5=6
1+ 5=6
0
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
1+ 4=5
1+ 4=5
1+ 4=5
1+ 6=7
1+ 6=7
1+ 6=7
4
4
4
22
F(100) = 7
被約費用=
1-7=-6
a4=7, その他0
追加する列=
(0,0,0,7)
注:CS問題の解の改善という観点からは、被約費用が
負でさえあればよく、 KPが最適に解けていなくてもよい
23
スタート
初期可能基底解
(を示す単体表の一部)
-
cj=cj-πAj
Ajの生成
π
最適性の判定と
軸の列の生成
新しい可能基底解
改訂単体法
の1反復
ナップザック問題
B-1Aj
ストップ
復元された軸の列の追加
最適?
列生成
第12回宿題(締切: 1月12日18時)
24
宿題12.1 ppt2に示したカッティングストック問
題を、以下の指示に従って、授業で解説した
列生成法により解け。解答は計算のプロセス
が分かるように要点を示す。
– 一部の列(カッティングパターン)からなるLP版カッティング
ストック問題を適当な数理計画ソフトウェア(Excelソルバー、
または、AMPL)、または、手計算で解く
– 初期基底は単位行列のカッティングパターンとする
– 列生成(パターン生成)と最適性の判定のための整数値
ナップザック問題も適当な数理計画ソフトウェア、または、
手計算で解く
– 初期列と生成された列(だけ)からなる整数計画問題も適
当な数理計画ソフトウェアで解く
25
第12回のまとめ
• カッティングストック問題
– 問題紹介と定式化(復習)
– 「列生成」による解法の考え方と改訂単体法
– 整数値ナップザック問題による最適性の判定
と列生成
• 動的計画法(DP)
– 動的計画法による整数値ナップザック問題の
解法