OR-A 第3回

「ORーA」
2011/01/07
• 前回の続き(インディケータ変数による定式化)
– 公式の再確認
– 前回宿題の解説
• 露天掘り
• 施設配置問題に関する論理条件
– OR条件の応用(非凸領域の表現)
– 今回宿題の問題解説
• カッティングストック問題に対する列生成法
1
論理条件に対応する数式の「作成公式」
ステップ1 「δ=1→Σjajxj≦b」形の論理条件にする。
ステップ2 右辺bを左辺に移項しΣjajxj-b≦0の形に。
ステップ3 右辺0の代わりに、δの(1次)関数を考え
る。この関数はδ=1のとき0、そうでないときは制
約条件式が無意味、すなわち、すべての解が生成さ
れる制約条件式を満足するようにしたい。
このため、右辺を□(1-δ)の形(□は適当な定
数)にすると、Σjajxj-b≦M(1-δ)が望む制約条
件式となる。ただし、MはΣjajxj-bの上界値とする。
2
論理条件と0-1変数
δiが0-1のインディケータ変数とし、Xi
がδi=1という状態を示すこととする。
(A)
X 1∨X 2
δ1+δ2≧1
(B)
X 1・ X 2
δ1=1,δ2=1
(C)
~X 1
δ1=0(1-δ1=1)
(D)
X 1→X 2
δ1-δ2≦0
(E)
X 1←→X 2 δ1-δ2=0
3
露天掘り
• ブロックiを掘る(xi=1)ときには、その「上
に位置する」ブロックjも掘らなければなら
ない( xj=1)
• xi=1 ⇒ xj=1
• xiー xj≦0 ( xi≦ xj)
4
問題例1 候補地1、2、3の中から一つ
選択し、候補地4、5の中から一つ選択
より正確には、
候補地1、2、3の中から一つ選択し、かつ、
候補地4、5の中から一つ選択
数 理 計 画 で は 、 制 約 条 件 は AND で か か る
δ1+ δ2+ δ3=1
δ4+ δ5=1
5
問題例2 候補地2を選択したときには、候
補地4または5の少なくともいずれか選択
δ2=1 ⇒ δ4+ δ5≧1
備考:この場合、別途δを導入する必要はない
δ2=1 ⇒ ーδ4ーδ5+1≦0
ーδ4ー δ5+1≦□(1ー δ2 )
ーδ4ーδ5+1≦(1ーδ2)
∴ δ2 ーδ4ー δ5≦0 (必ず、「検算」する)
6
問題例3 候補地2を選択したときには、
候補地4または5のいずれか1つを選択
δ2=1 ⇒ δ4+ δ5=1
間違った解答例:
1) δ4+ δ5=δ2 (δ2が0のとき、δ4+δ5=0?,No!)
2) δ2 ーδ=0,-δ4ー δ5 +δ =0
正しい考え方:
δ2=1 ⇒ ーδ4ー δ5+1≦0 ① (前と同じ) かつ
δ2=1 ⇒
δ4+ δ5ー1≦0 ②
δ4+ δ5ー1≦□(1ーδ2)
δ4 + δ5 ー 1 ≦ ( 1 ー δ2 )
∴ δ2 +δ4+ δ5≦2
②
∴ δ2 ーδ4ー δ5≦0
①
7
問題例4 候補地1または2を選択したと
きは、候補地3、4、5のいずれかを選択
解釈が4つありうる
解釈1:候補地1,2の少なくとも1つを選択したときは、候補地
3,4,5の少なくとも1つを選択
δ1+ δ2≧1 ⇒ δ3 + δ4+ δ5≧1
解釈2:候補地1,2のいずれか1つを選択したときには、候補
地3,4,5の少なくとも1つを選択
δ1+ δ2=1 ⇒ δ3 + δ4+ δ5≧1
解釈3:候補地1,2の少なくとも1つを選択したときは、候補地
3,4,5のいずれか1つを選択
δ1+ δ2≧1 ⇒ δ3 + δ4+ δ5=1
解釈4:候補地1,2のいずれか1つを選択したときには、候補
地3,4,5のいずれか1つを選択
δ1+ δ2=1 ⇒ δ3 + δ4+ δ5=1
8
問題例4(解釈1a) 候補地1,2の少なくとも
1つを選択したときは、候補地3,4,5の
少なくとも1つを選択
δ1+ δ2≧1 ⇒ δ3 + δ4+ δ5≧1
スマートな解答:
候補地i を選択するという事象をXi とすると、解釈1は
X 1∪X 2⇒X 3∪X 4∪X 5
と等価; ところが、これは、
X 1⇒X 3∪X 4∪X 5 、かつ、X 2⇒X 3∪X 4∪X 5
と等価
δ1=1 ⇒ δ3 + δ4+ δ5≧1
∴ δ3 + δ4+ δ5≧δ1
δ2=1 ⇒ δ3 + δ4+ δ5≧1
∴ δ3 + δ4+ δ5≧δ2
①
①
②
②
9
問題例4(解釈1b) 候補地1,2の少なくとも
1つを選択したときは、候補地3,4,5の
少なくとも1つを選択
δ1+ δ2≧1 ⇒ δ3 + δ4+ δ5≧1
「公式」に忠実な解答:
δ1+ δ2≧1 ⇒ δ=1 ⇒ δ3 + δ4+ δ5≧1
㊧の対偶
δ=0 ⇒ δ1+ δ2≦0
①
∴ δ1 + δ2 ≦ 2δ
①
㊨
δ=1 ⇒ δ3 + δ4+ δ5≧1 ②
∴ δ3 + δ4+ δ5≧δ
②
10
問題例4(解釈2) 候補地1,2のいず
れか1つを選択したときには、候補地
3,4,5の少なくとも1つを選択
δ1+ δ2=1 ⇒ δ3 + δ4+ δ5≧1
「公式」に忠実な解答:
δ1+ δ2=1 ⇒ δ=1 ⇒ δ3 + δ4+ δ5≧1
㊧
㊨
㊧の対偶
㊨
δ=0 ⇒ δ1+ δ2≦0 or δ1+ δ2≧2 ①
δ=0 ⇒ γ1+ γ2≧1
②
γ1=1 ⇒ δ1+ δ2≧2
③
γ2=1 ⇒ δ1+ δ2≦0
④
∴ γ1 + γ2 +δ ≧1
②
∴ δ1 + δ2 ー 2 γ1 ≧ 0 ③
∴ δ1 + δ2 + 2 γ2 ≦ 2 ④
δ=1 ⇒ δ3 + δ4+ δ5≧1
⑤
∴ δ3 + δ4+ δ5≧δ
⑤
11
OR条件の一般化,拡張
(A)
X1∨X2
δ1+δ2≧1
↓
複数項のOR条件
(A’)
X1∨X2∨・・・∨Xn
δ1+δ2 +・・・+δn≧1
複数項の中から少なくともk 個以上
(A’’) X1,X2,・・・,Xnの中からk 個以上
δ1+δ2 +・・・+δn≧k
OR条件ではないが,同様に,複数項の中から高々k 個
(A’’’) X1,X2,・・・,Xnの中から高々k 個
δ1+δ2 +・・・+δn≦k
12
OR条件の応用例
凸でない実行可能領域の表現
ABJO S1={x=(x1,x2): x2≦3,x1+x2≦4,x≧0}
ODH S2= {x=(x1,x2): ーx1+x2≦0, 3x1ーx2≦8,x≧0}
KFGO S3= {x=(x1,x2): x2≦1,x1≦5,x≧0}
• もしも問題の条件が、 x∈ S1 ∪S2∪S3のとき...
実行可能領域は
非凸!!!
数理計画問題の
定式化で
「または」と
書けない 13
線形計画問題の実行可能領域
ABJO S1={x=(x1,x2): x2≦3,x1+x2≦4,x≧0}
ODH S2= {x=(x1,x2): ーx1+x2≦0, 3x1ーx2≦8,x≧0}
KFGO S3= {x=(x1,x2): x2≦1,x1≦5,x≧0}
• もしも、問題の条件が、 x∈ S1 ∩S2∩S3のとき...
14
凸でない実行可能領域
ABJO S1={x=(x1, x2): x2≦3,x1+x2≦4,x≧0}
ODH S2= {x=(x1, x2): ーx1+x2≦0, 3x1ーx2≦8,x≧0}
KFGO S3= {x=(x1, x2): x2≦1,x1≦5,x≧0}
• もしも問題の条件が、 x∈ S1 ∪S2∪S3のとき...
• インディケータ変数δ1 ,δ2 ,δ3を導入:
δ1 =1⇒x∈ S1 , δ2 =1⇒x∈ S2 , δ3 =1 ⇒x∈ S3
換言すると、 δ1 =1 ⇒ (x2≦3)・(x1+x2≦4)・ (x≧0)
①
δ2 =1 ⇒(ーx1+x2≦0)・(3x1ーx2≦8)・(x≧0) ②
δ3 =1 ⇒ (x2≦1)・(x1≦5)・ (x≧0)
③
• ①、②、③に加えて、δ1 +δ2 +δ3 ≧1
15
凸でない実行可能領域(続き)
ABJO S1={x=(x1, x2): x2≦3,x1+x2≦4,x≧0}
• 論理条件①は、数式に変換可能
δ1 =1 ⇒ (x2≦3)・(x1+x2≦4)・(x≧0)
①
• δ1 =1 ⇒ x2≦3
①’
δ1 =1 ⇒ x1+x2≦4
①”
δ1 =1 ⇒ x≧0 (非負条件が別途考慮されているならば不要)
• 論理条件②、③も同様
• ①’、①”、②’、②”、③’、③”、xの非負条件に
加えて、 δ1 +δ2 +δ3 ≧1
16
SOS(特殊順序集合)変数制約
(SOS=Specially Ordered Set)
SOS 1=一連の変数の集まり(実数変数で
も整数変数でも可;SOS1変数群)の中か
らちょうど1個が0でない
SOS 2=順序が定められた一連の変数の
集 ま り ( 実 数 変 数 で も 整 数 変 数 で も可 ;
SOS2変数群)の中から,「隣りあう」高々2
個が0でない
17
SOS1変数制約
(SOS=Specially Ordered Set)
SOS 1=一連の変数の集まり(実数変数で
も整数変数でも可;SOS1変数群)の中か
らちょうど1個が0でない
実数変数: x1 ,x2 ,・・・,xn の中で1個が正
0-1変数: δ1+δ2 +・・・+δn = 1
どんな例があるか考えてみよう
18
OR条件の拡張の応用例
解の中の変数の数を制限する
• 正の値をとる変数の数を一定個数以下(以
上)にしたい
– 例:株式jへの投資金額xjの決定の決定にあたっ
て、投資対象の株式数をk以下に抑えたい
xj>0 ⇒ δj=1
xjーMjδj≦0
ただし、Mjは株式jへの投資金額xjの上限
δ1+ δ2 +・・・+δn ≦ k
19
SOS2変数制約
(SOS=Specially Ordered Set)
SOS 2=順序が定められた一連の変数の
集 ま り ( 実 数 変 数 で も 整 数 変 数 で も可 ;
SOS2変数群)の中から,「隣りあう」高々2
個が0でない
(λ1 ,λ2 ,・・・,λn )の中で「隣りあう」高々
2個が正
λ1+λ2 +λ3+λ4 + ・・・+λn = 1
20
SOS2制約の例
(SOS=Specially Ordered Set)
Minimize z = x12-4x1-2x2
s.t.
x1 + x2 ≦ 4
2x1 + x2 ≦ 5
- x1+4x2 ≧ 2
x1 , x2 ≧ 0
非線形関数を含むモデルが解けない場合に何ができるか
ヒント: Minimize z = y -4x1-2x2
y =・・・
(λ1 ,λ2 ,・・・,λn )≧0 の中で「隣りあう」高々2個が正
λ1+λ2 +λ3+λ4 + ・・・+λn = 1
21
非線形関数の折れ線近似
λ1
λ2
λ3
λ4
λ5
22
SOS2制約の例
(SOS=Specially Ordered Set)
Minimize z =y -4x1-2x2
s.t.
x1 + x2 ≦ 4
2x1 + x2 ≦ 5
- x1+4x2 ≧ 2
x1 , x2 ≧ 0
x1 = 0λ1+ 0.5λ2 +1λ3+ 1.5λ4 + ・・・+?λn
y = 0λ1+0.25λ2 +1λ3+2.25λ4 + ・・・+?λn
λ1 + λ2 + λ3 + λ4 + ・・・+ λn = 1
(λ1 ,λ2 ,・・・,λn )≧0 の中で「隣りあう」高々2個が正
23
非線形関数の折れ線近似
λ1
0
λ2
λ3
λ4
0.5
0.5
λ5
0
0
24
宿題12
宿題12.1 3次元3目並べ(配布資料p.16,問
4)の定式化を示せ.なお,余裕がある人は
Excel ソルバーで解け.(ソルバーファイルは,
メールの添付にて[email protected]宛に題
名「OR-A: 学籍番号 氏名」で送付のこと)
宿題12.2 スライド28のシナリオを定式化せよ.
締切:2011年1月13日(木) 17時
森戸研メールボックス
25
3次元3目並べ(配布資料p.16)
• 各マスに1から27まで番号をつける
• 各 マ ス j ( j = 1,…,27) に 白 な ら 0 、 黒 な ら 1 と い う
0-1変数xjを定義
• 「線」に番号をつける(「線」は何本あるか?)
• 同色の線の本数を数え,その本数を最小化する
26
線形計画モデルの特殊形
最大値の最小化
• 通常の線形計画モデル
Min z =cx =Σj=1,…,ncjxj
s.t.
Ax≦b,x≧0
• 最大値の最小化
Min (Maxi=1,…,mΣj=1,…,ncijxj)
s.t.
Ax≦b,x≧0 (通常の1次制約式)
• 最大値の最小化は通常のLPに変換可能
Min
z
s.t.
Σj=1,…,ncijxj ー z≦0,
i=1,…,m
Ax≦b,x≧0 (通常の1次制約式)
27
特殊な定式化の応用
宿題12.2 以下のシナリオを定式
化せよ
• ある議会の議員定員はM人である
• 議員はN(<M)個の選挙区から選挙され
る
• 選挙区jの人口(選挙権を持つ人の人口)
pjは既知である
• 人口1人当たりの議員数(逆に、議員1人
当たりの人口、でもよい)の最大値と最小
値の差を最小化する議員定数の配分(各
選挙区の議員定数)を決めたい
28
ハブ&スポークネットワークの設計
29
ハブ&スポーク 定式化
所与のデータ
• hij = 点iと点j 間の輸送需要
• cij = ノンハブ点i からハブ点j にの間の単位
需要当たりの輸送費用
• α=ハブ間の輸送費用に対するディスカウント
ファクタ
ハブ間の単位需要当たりの輸送費用はα*cij
• p =ハブの数
30
ハブ&スポーク 定式化
変数
• zij=1 ノンハブ点i がハブ点j に接続して
いるとき(i ≠j の場合)
=0 そうでないとき
• zii=1 点i がハブであるとき
=0 そうでないとき
31
ハブ&スポーク 定式化
0-1二次計画問題
最小化 z =ΣiΣjΣ kΣm hij (cikzik +αckmzikzjm+ cjmzjm )
制約条件 Σj zij =1, ∀i
点iはハブかいずれかのハブに接続
Σi zii =p , ∀i ハブはp個
zij-zjj≦0 , ∀i,j
ノンハブには接続不可
zij ∈{0,1}, ∀i,j
接続不可制約の代替案 Σi zij-(n-p+1)zjj≦0 ,∀j
32
ハブ&スポーク 線形の定式化
変数の取り方
• zijkm=1 点i ,点j 間の輸送がハブ点kとハブ
点mを経由するとき
=0 そうでないとき
• xi =1 点i がハブであるとき
=0 そうでないとき
• この定式化では変数の個数がn4のオーダー
• 定数cijkm= cik +α ckm+ cmj を定義
33
ハブ&スポーク 定式化
(線形)整数計画問題
最小化 z =ΣiΣjΣ kΣm hij cijkmzijkm
制約条件 Σk Σm zijkm =1, ∀i,j
点iは点j間は、ハブkとハブmを経由
xi
Σi xi =p ,
∀i ハブはp個
zijkm-xk≦0 , ∀i,j,k,m
zijkm-xm≦0 , ∀i,j,k,m
ノンハブには接続不可
zijkm ∈{0,1}, ∀i,j,k,m
xi ∈{0,1},
∀i
34
「ORーA」 第12回
2011/01/07
• カッティングストック問題
–
–
–
–
–
問題紹介と定式化
LP版カッティングストック問題の解法の基本的考え方
被約費用を最小化するパターンを求める問題
(整数値)ナップザック問題
ナップザック問題の解法
• 動的計画法
35
(1次元)カッティングストック問題
•
•
•
•
45cm の長さの板 x 97枚
36cm の長さの板 x 610枚
31cm の長さの板 x 395枚
14cm の長さの板 x 211枚
100cm
45cm
36cm
14cm
36
カッティングストック問題の定式化
最小化 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,整数
37
LP版カッティングストック問題
• 整数計画は(LPに比べて)解きにくい
• そこでLP版CS問題を考える(切上げ解は必
ず実行可能)
• 板の長さLが、需要の長さに比べて長いと、
カッティングパターンの数は膨大になる
• あらかじめすべてのカッティングパターンを列
挙しておくことは無理。LP版CSも、列が膨大
だと困る→必要に応じパターンを生成できない
か?
→列生成法
→改訂単体法で必要な情報を復元
38
カッティングストック問題の定式化
最小化 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,整数
39
スタート
初期可能基底解
(を示す単体表の一部)
-
cj=cj-πAj
Ajの生成
π
最適性の判定と
軸の列の生成
新しい可能基底解
改訂単体法
の1反復
ナップザック問題
B-1Aj
ストップ
復元された軸の列の追加
最適?
列生成
40
LP版カッティングストック問題
を列生成+改訂単体法で解く
標準的改訂単体法との違い
①初期可能基底形式の設定にあたって注意
(スラック変数でなく、実際のカッティングパター
ンに対応する変数を初期基底変数とするため)
②双対価格の現われ方が違うので注意
(「いつも、πが見えていたところにπ-1がある;
理由は、①と同じで、初期基底変数の元の問題
の目的関数の係数が1だから)
③列(=パターン)があらかじめ列挙されてい
ないので、その生成が必要(ナップザック問題)
41
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
目的関数の行に、制約の各行を加えればよい
42
双対価格π=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
43
1
0
0
0
双対価格自身が現れない理由
• 初期可能基底解の基底変数の目的関数の係
数cj が0でない場合(例:スラック変数でない場合)
– 基底の逆行列B-1の「上」に双対価格が現われない
-
– なぜなら、c
j=cj-πAjであり、cj ≠0のため(ただし、
Aj は単位ベクトル)、 B-1の「上」にπi-cjが現われる
-
(単体表には-cj が現われることに注意)ため、B-1の上に現わ
れる数値にcj を加えた値がπの値となる
46
(非基底)カッティングパターン
の被約費用は?
• パターンを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
49
aiは非負整数、  i は需要iの長さ(定数)
被約費用最小の非基底カッティングパターンを求める
整数値ナップザック問題
• 最小化 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-「ナップザック問題の最適値」
50
注: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
x4
0
0
0
0
1
x5
6
0
0
0
(7)
右辺定数 基底変数
1313
z
97
x1
610
x2
395
x3
211
x4
π=(1,1,1,1)
51
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
π=(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
52
(整数値)ナップザック問題
• 整数値ナップザック問題(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, 整数
53
(整数値)ナップザック問題の最適解法
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の他に分枝限定法による列挙解法もあり
54
ナップザック問題のDP解法:数値例
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
55
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
F(100) = 7
被約費用=
1-7=-6
a4=7, その他0
追加する列=
(0,0,0,7)
注:CS問題の解の改善という観点からは、被約費用が
負でさえあればよく、 KPが最適に解けていなくてもよい
56
スタート
初期可能基底解
(を示す単体表の一部)
-
cj=cj-πAj
Ajの生成
π
最適性の判定と
軸の列の生成
新しい可能基底解
改訂単体法
の1反復
ナップザック問題
B-1Aj
ストップ
復元された軸の列の追加
最適?
列生成
57
第12回のまとめ
• カッティングストック問題
– 問題紹介と定式化(復習)
– 「列生成」による解法の考え方と改訂単体法
– 整数値ナップザック問題による最適性の判定
と列生成
• 動的計画法(DP)
– 動的計画法による整数値ナップザック問題の
解法
58