「ORーA」 2011/01/07 • 前回の続き（インディケータ変数による定式化） – 公式の再確認 – 前回宿題の解説 • 露天掘り • 施設配置問題に関する論理条件 – OR条件の応用（非凸領域の表現） – 今回宿題の問題解説 • カッティングストック問題に対する列生成法 1 論理条件に対応する数式の「作成公式」ステップ１「δ＝１→Σjａjｘj≦ｂ」形の論理条件にする。ステップ２右辺ｂを左辺に移項しΣjａjｘj－ｂ≦０の形に。ステップ３右辺０の代わりに、δの（１次）関数を考える。この関数はδ＝１のとき０、そうでないときは制約条件式が無意味、すなわち、すべての解が生成される制約条件式を満足するようにしたい。このため、右辺を□（１－δ）の形（□は適当な定数）にすると、Σjａjｘj－ｂ≦Ｍ（１－δ）が望む制約条件式となる。ただし、ＭはΣjａjｘj－ｂの上界値とする。 2 論理条件と０－１変数 δiが０－１のインディケータ変数とし、Ｘi がδi＝１という状態を示すこととする。（A）Ｘ 1∨Ｘ 2 δ1＋δ2≧１（B）Ｘ 1・Ｘ 2 δ1＝１，δ2＝１（C）～Ｘ 1 δ1＝０（１－δ1＝１）（D）Ｘ 1→Ｘ 2 δ1－δ2≦０（E）Ｘ１←→Ｘ 2 δ1－δ2＝０ 3 露天掘り • ブロックiを掘る（xi＝１）ときには、その「上に位置する」ブロックjも掘らなければならない（ xj＝１） • xi＝１ ⇒ xj＝１ • xiー xj≦０（ xi≦ xj） 4 問題例1 候補地１、２、３の中から一つ選択し、候補地４、５の中から一つ選択より正確には、候補地１、２、３の中から一つ選択し、かつ、候補地４、５の中から一つ選択数理計画では、制約条件は AND でかかる δ1＋ δ2＋ δ3＝１ δ4＋ δ5＝１ 5 問題例2 候補地２を選択したときには、候補地４または５の少なくともいずれか選択 δ2＝１ ⇒ δ4＋ δ5≧１備考：この場合、別途δを導入する必要はない δ2＝１ ⇒ ーδ4ーδ5＋１≦０ーδ4ー δ5＋１≦□（１ー δ2 ）ーδ4ーδ5＋１≦（１ーδ2） ∴ δ2 ーδ4ー δ5≦０ (必ず、「検算」する） 6 問題例3 候補地２を選択したときには、候補地４または５のいずれか1つを選択 δ2＝１ ⇒ δ4＋ δ5＝１間違った解答例： 1) δ4＋ δ5＝δ2 （δ2が0のとき、δ4＋δ5＝０？，No!） 2) δ2 ーδ＝０，－δ4ー δ5 ＋δ ＝０正しい考え方： δ2＝１ ⇒ ーδ4ー δ5＋１≦０ ① （前と同じ）かつ δ2＝１ ⇒ δ4＋ δ5ー１≦０ ② δ4＋ δ5ー１≦□（１ーδ2） δ4 ＋ δ5 ー１ ≦ （１ー δ2 ） ∴ δ2 ＋δ4＋ δ5≦２ ② ∴ δ2 ーδ4ー δ5≦０ ① 7 問題例4 候補地１または２を選択したときは、候補地３、４、５のいずれかを選択解釈が4つありうる解釈1：候補地1,2の少なくとも1つを選択したときは、候補地 3,4,5の少なくとも1つを選択 δ1＋ δ2≧１ ⇒ δ3 ＋ δ4＋ δ5≧１解釈2：候補地1,2のいずれか1つを選択したときには、候補地3,4,5の少なくとも1つを選択 δ1＋ δ2＝１ ⇒ δ3 ＋ δ4＋ δ5≧１解釈3：候補地1,2の少なくとも1つを選択したときは、候補地 3,4,5のいずれか1つを選択 δ1＋ δ2≧１ ⇒ δ3 ＋ δ4＋ δ5＝１解釈4：候補地1,2のいずれか1つを選択したときには、候補地3,4,5のいずれか1つを選択 δ1＋ δ2＝１ ⇒ δ3 ＋ δ4＋ δ5＝１ 8 問題例4（解釈1a）候補地1,2の少なくとも 1つを選択したときは、候補地3,4,5の少なくとも1つを選択 δ1＋ δ2≧１ ⇒ δ3 ＋ δ4＋ δ5≧１スマートな解答：候補地ｉを選択するという事象をＸｉとすると、解釈１はＸ 1∪Ｘ 2⇒Ｘ 3∪Ｘ 4∪Ｘ 5 と等価；ところが、これは、Ｘ 1⇒Ｘ 3∪Ｘ 4∪Ｘ 5 、かつ、Ｘ 2⇒Ｘ 3∪Ｘ 4∪Ｘ 5 と等価 δ1＝１ ⇒ δ3 ＋ δ4＋ δ5≧１ ∴ δ3 ＋ δ4＋ δ5≧δ1 δ2＝１ ⇒ δ3 ＋ δ4＋ δ5≧１ ∴ δ3 ＋ δ4＋ δ5≧δ2 ① ① ② ② 9 問題例4（解釈1b）候補地1,2の少なくとも 1つを選択したときは、候補地3,4,5の少なくとも1つを選択 δ1＋ δ2≧１ ⇒ δ3 ＋ δ4＋ δ5≧１「公式」に忠実な解答： δ1＋ δ2≧１ ⇒ δ＝１ ⇒ δ3 ＋ δ4＋ δ5≧１㊧の対偶 δ＝０ ⇒ δ1＋ δ2≦０ ① ∴ δ1 ＋ δ2 ≦ ２δ ① ㊨ δ＝１ ⇒ δ3 ＋ δ4＋ δ5≧１ ② ∴ δ3 ＋ δ4＋ δ5≧δ ② 10 問題例4（解釈2）候補地1,2のいずれか1つを選択したときには、候補地 3,4,5の少なくとも1つを選択 δ1＋ δ2＝１ ⇒ δ3 ＋ δ4＋ δ5≧１「公式」に忠実な解答： δ1＋ δ2＝１ ⇒ δ＝１ ⇒ δ3 ＋ δ4＋ δ5≧１㊧㊨㊧の対偶㊨ δ＝０ ⇒ δ1＋ δ2≦０ or δ1＋ δ2≧２ ① δ＝０ ⇒ γ1＋ γ2≧１ ② γ1＝1 ⇒ δ1＋ δ2≧２ ③ γ2＝1 ⇒ δ1＋ δ2≦０ ④ ∴ γ1 ＋ γ2 ＋δ ≧１ ② ∴ δ1 ＋ δ2 ー２ γ1 ≧ ０ ③ ∴ δ1 ＋ δ2 ＋２ γ2 ≦ ２ ④ δ＝１ ⇒ δ3 ＋ δ4＋ δ5≧１ ⑤ ∴ δ3 ＋ δ4＋ δ5≧δ ⑤ 11 OR条件の一般化，拡張（A）Ｘ1∨Ｘ2 δ1＋δ2≧１ ↓ 複数項のOR条件（A’）Ｘ1∨Ｘ2∨･･･∨Ｘn δ1＋δ2 ＋･･･＋δn≧１複数項の中から少なくともｋ個以上（A’’）Ｘ1，Ｘ2，･･･，Ｘnの中からｋ個以上 δ1＋δ2 ＋･･･＋δn≧ｋ OR条件ではないが，同様に，複数項の中から高々ｋ個（A’’’）Ｘ1，Ｘ2，･･･，Ｘnの中から高々ｋ個 δ1＋δ2 ＋･･･＋δn≦ｋ 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 １＝一連の変数の集まり（実数変数でも整数変数でも可；SOS１変数群）の中からちょうど１個が０でない SOS ２＝順序が定められた一連の変数の集まり（実数変数でも整数変数でも可； SOS２変数群）の中から，「隣りあう」高々２個が０でない 17 SOS１変数制約（SOS＝Specially Ordered Set) SOS １＝一連の変数の集まり（実数変数でも整数変数でも可；SOS１変数群）の中からちょうど１個が０でない実数変数：ｘ1 ，ｘ2 ，･･･，ｘn の中で1個が正 0-1変数： δ1＋δ2 ＋･･･＋δn ＝１どんな例があるか考えてみよう 18 OR条件の拡張の応用例解の中の変数の数を制限する • 正の値をとる変数の数を一定個数以下（以上）にしたい – 例：株式jへの投資金額xjの決定の決定にあたって、投資対象の株式数をk以下に抑えたい xj＞0 ⇒ δj＝1 xjーMjδj≦0 ただし、Mjは株式jへの投資金額xjの上限 δ1＋ δ2 ＋･･･＋δn ≦ k 19 SOS２変数制約（SOS＝Specially Ordered Set) SOS ２＝順序が定められた一連の変数の集まり（実数変数でも整数変数でも可； SOS２変数群）の中から，「隣りあう」高々２個が０でない（λ1 ，λ2 ，･･･，λn ）の中で「隣りあう」高々２個が正 λ1＋λ2 ＋λ3＋λ4 ＋･･･＋λn ＝１ 20 SOS２制約の例（SOS＝Specially Ordered Set) Minimize ｚ＝ｘ12－4ｘ1－2ｘ2 s.t. ｘ1 ＋ｘ2 ≦ 4 2ｘ1 ＋ｘ2 ≦ 5 －ｘ1＋4ｘ2 ≧ 2 ｘ1 ，ｘ2 ≧ 0 非線形関数を含むモデルが解けない場合に何ができるかヒント： Minimize ｚ＝ｙ－4ｘ1－2ｘ2 ｙ＝・・・（λ1 ，λ2 ，･･･，λn ）≧0 の中で「隣りあう」高々２個が正 λ1＋λ2 ＋λ3＋λ4 ＋･･･＋λn ＝１ 21 非線形関数の折れ線近似 λ1 λ2 λ3 λ4 λ5 22 SOS２制約の例（SOS＝Specially Ordered Set) Minimize ｚ＝ｙ－4ｘ1－2ｘ2 s.t. ｘ1 ＋ｘ2 ≦ 4 2ｘ1 ＋ｘ2 ≦ 5 －ｘ1＋4ｘ2 ≧ 2 ｘ1 ，ｘ2 ≧ 0 ｘ1 ＝ 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 ，λ2 ，･･･，λn ）≧0 の中で「隣りあう」高々２個が正 23 非線形関数の折れ線近似 λ1 0 λ2 λ3 λ4 0.5 0.5 λ5 0 0 24 宿題１２宿題１２．１ 3次元3目並べ（配布資料p.16，問４）の定式化を示せ．なお，余裕がある人は Excel ソルバーで解け．（ソルバーファイルは，メールの添付にて[email protected]宛に題名「OR-A：学籍番号氏名」で送付のこと）宿題１２．２スライド28のシナリオを定式化せよ．締切：2011年1月13日（木） 17時森戸研メールボックス 25 3次元3目並べ（配布資料p.1６） • 各マスに1から27まで番号をつける • 各マス j （ j ＝ 1,…,27) に白なら 0 、黒なら 1 という 0-1変数xjを定義 • 「線」に番号をつける（「線」は何本あるか？） • 同色の線の本数を数え，その本数を最小化する 26 線形計画モデルの特殊形最大値の最小化 • 通常の線形計画モデル Min ｚ＝ｃｘ＝Σj=1,…,nｃjｘj s.t. Aｘ≦ｂ，ｘ≧0 • 最大値の最小化 Min （Maxi=1,…,mΣj=1,…,nｃijｘj） s.t. Aｘ≦ｂ，ｘ≧0 （通常の1次制約式） • 最大値の最小化は通常のLPに変換可能 Min ｚ s.t. Σj=1,…,nｃijｘj ーｚ≦0, i=1,…,m Aｘ≦ｂ，ｘ≧0 （通常の1次制約式） 27 特殊な定式化の応用宿題１２．２以下のシナリオを定式化せよ • ある議会の議員定員はM人である • 議員はN（＜M）個の選挙区から選挙される • 選挙区jの人口（選挙権を持つ人の人口）ｐjは既知である • 人口1人当たりの議員数（逆に、議員1人当たりの人口、でもよい）の最大値と最小値の差を最小化する議員定数の配分（各選挙区の議員定数）を決めたい 28 ハブ＆スポークネットワークの設計 29 ハブ＆スポーク定式化所与のデータ • ｈij ＝点ｉと点ｊ間の輸送需要 • cij ＝ノンハブ点ｉからハブ点ｊにの間の単位需要当たりの輸送費用 • α＝ハブ間の輸送費用に対するディスカウントファクタハブ間の単位需要当たりの輸送費用はα＊ｃij • p ＝ハブの数 30 ハブ＆スポーク定式化変数 • zij＝1 ノンハブ点ｉがハブ点ｊに接続しているとき（ｉ ≠ｊの場合）＝0 そうでないとき • zii＝1 点ｉがハブであるとき＝0 そうでないとき 31 ハブ＆スポーク定式化０－１二次計画問題最小化 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」第１２回 2011/01/07 • カッティングストック問題 – – – – – 問題紹介と定式化 LP版カッティングストック問題の解法の基本的考え方被約費用を最小化するパターンを求める問題（整数値）ナップザック問題ナップザック問題の解法 • 動的計画法 35 （１次元）カッティングストック問題 • • • • 45cｍの長さの板 x 97枚 36cm の長さの板 x 610枚 31cm の長さの板 x 395枚 14cm の長さの板 x 211枚 100cm 45cm 36cm 14cm 36 カッティングストック問題の定式化最小化　ｚ＝ｘ1＋ｘ 2＋ｘ3＋ｘ 4＋ｘ5＋・・・ １  ０制約条件　０  ０   ０    １ｘ＋  1 ０    ０    0  ０     ０    ０ｘ＋ｘ＋  2 １  3 ０      ０  １      １    １ｘ＋  4 ０    １      ｘ 5＋・・・≧     97    610    395    211   • ｘｊ＝第ｊカッティングパターンの使用回数 • ｘｊ≧0，整数 37 LP版カッティングストック問題 • 整数計画は（LPに比べて）解きにくい • そこでLP版CS問題を考える（切上げ解は必ず実行可能） • 板の長さLが、需要の長さに比べて長いと、カッティングパターンの数は膨大になる • あらかじめすべてのカッティングパターンを列挙しておくことは無理。LP版CSも、列が膨大だと困る→必要に応じパターンを生成できないか？ →列生成法 →改訂単体法で必要な情報を復元 38 カッティングストック問題の定式化最小化　ｚ＝ｘ1＋ｘ 2＋ｘ3＋ｘ 4＋ｘ5＋・・・ １  ０制約条件　０  ０   ０    １ｘ＋  1 ０    ０    0  ０     ０    ０ｘ＋ｘ＋  2 １  3 ０      ０  １      １    １ｘ＋  4 ０    １      ｘ 5＋・・・≧     97    610    395    211   • ｘｊ＝第ｊカッティングパターンの使用回数 • ｘｊ≧0，整数 39 スタート初期可能基底解（を示す単体表の一部）－ｃj＝ｃj－πAj Aｊの生成 π 最適性の判定と軸の列の生成新しい可能基底解改訂単体法の１反復ナップザック問題 B-1Aｊストップ復元された軸の列の追加最適？列生成 40 LP版カッティングストック問題を列生成+改訂単体法で解く標準的改訂単体法との違い ①初期可能基底形式の設定にあたって注意（スラック変数でなく、実際のカッティングパターンに対応する変数を初期基底変数とするため） ②双対価格の現われ方が違うので注意（「いつも、πが見えていたところにπ－１がある；理由は、①と同じで、初期基底変数の元の問題の目的関数の係数が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 双対価格π＝ｃBB-1の読み方に注意（∵ 初期基底変数の目的関数の係数が1）初期基底に対する双対価格π＝ｃBB-1＝ｃBI ＝ｃB ＝（1,1,1,1）－ c 1 ＝－（ｃ１－πA１）＝－１＋ π 1π 2π 3π 4 ＝－１＋π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＝π２＝π３＝π４＝１ 43 1 0 0 0 双対価格自身が現れない理由 • 初期可能基底解の基底変数の目的関数の係数ｃｊが0でない場合（例：スラック変数でない場合） – 基底の逆行列B-1の「上」に双対価格が現われない－ – なぜなら、ｃｊ＝ｃｊ－πAjであり、ｃｊ ≠0のため（ただし、 Aj は単位ベクトル）、 B-1の「上」にπi－cｊが現われる－（単体表には－ｃｊが現われることに注意）ため、B-1の上に現われる数値にｃｊを加えた値がπの値となる 46 （非基底）カッティングパターンの被約費用は？ • パターンをa＝(a1,a2,...,am)t (列ベクトル)と表記 • 最小化 c －πta ＝１－ (π1.π2,…,πm )（a1,a2,...,am）t ＝１－（π1a1＋π2a2＋．．．＋πmam） • 最大化（π1a1＋π2a2＋．．．＋πmam）－１といっても、基本的に同じこと • 制約条件 1a1＋  2a2＋．．．＋  mam ≦ L 49 aiは非負整数、  i は需要iの長さ(定数）被約費用最小の非基底カッティングパターンを求める整数値ナップザック問題 • 最小化 c －πta ＝１－ (π1.π2,…,πm )（a1,a2,...,am）t • 最大化 π1a1＋π2a2＋...＋πmam－１制約条件  1a1＋  2a2＋...＋  mam ≦ L aiは≧0かつ整数（変数）、  i は需要iの長さ(定数） • π＝(1,1,1,1) • 最大化 a 1 ＋ a2 ＋ a3 ＋ a4 －１制約条件 45a1＋36a2＋ 31a3＋14a4 ≦100 ai ≧0かつ整数（変数） • 最小被約費用の値は、１－「ナップザック問題の最適値」 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 ａi （－１） s.t. ∑i＝1,…,m  i ａi ≦ L ａi ≧ 0, 整数 • 具体的数値例（カッティングストック問題の例） max z = ∑i＝1,…,４ａi （－１）（各πi ＝1の場合） s.t. 45a1＋36a2＋ 31a3＋14a4 ≦100 ａi ≧ 0, 整数 53 （整数値）ナップザック問題の最適解法 max z = ∑i＝1,…,m πiａi （ - １） s.t. ∑i＝1,…,m  j ａi ≦ L，ａi ≧ 0, 整数 • 動的計画法（Dynamic Programming; DP） f (ｙ) = 重量制限ｙのナップザックに詰め込むことのできる最大の価値 f (ｙ) = max i＝1,…,m { πi + f (ｙ - i )} 漸化式ｙ = ｍｉｎ ,..., L に対して、順次f (y)を計算。最終的に、 f (L)が解きたい問題の最適値。ただし、  ｍｉｎ = min i＝1,…,m {  i } • DPの他に分枝限定法による列挙解法もあり 54 ナップザック問題のDP解法：数値例 max z = ∑i＝1,…,m ａi s.t. 45a1＋36a2＋ 31a3＋14a4 ≦100 j ａi ≧ 0, 整数 • f (ｙ) = 重量制限ｙのナップザックに詰め込むことのできる最大の価値 – 自明に、f (ｙ) = 0，ｙ＝0,…,13； f (ｙ) =－∞，ｙ＝負 • f (ｙ) = max i＝1,…,m { πi + f (ｙ -  i )} 漸化式 • ｙ = ｍｉｎ ,..., L に対して、順次f (y)を計算。最終的に、 f (L)＝ f (100)が解きたい問題の最適値。ただし、 ｍｉｎ = min i＝1,…,m {  i } = 14 – ほぼ自明に、f (ｙ) =1＝14,…,27 55 y ０～１３１４～２７２８～３０３１～３５３６～４１４２～４４４５～４９５０～５５５６～５８５９～６１６２～６３６４～６５６６～７０７０～７１７２７３～７５７６７７７８～７９８０８１～８３８４８５～８６（中略）９８９９ L=１００ｆ（y）０１２２２３３３４４４４４５５５５５５５６６６７７７ i＝１　i＝２　i＝３　i＝４ 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 ｄ(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 ０４４４４４４４４４４４４４４４４４４４４４４ 1+ 4=5 1+ 4=5 1+ 4=5 1+ 6=7 1+ 6=7 1+ 6=7 ４４４ F(100) = 7 被約費用＝ 1－7＝－6 a4=7, その他0 追加する列＝ (0,0,0,7) 注：CS問題の解の改善という観点からは、被約費用が負でさえあればよく、 KPが最適に解けていなくてもよい 56 スタート初期可能基底解（を示す単体表の一部）－ｃj＝ｃj－πAj Aｊの生成 π 最適性の判定と軸の列の生成新しい可能基底解改訂単体法の１反復ナップザック問題 B-1Aｊストップ復元された軸の列の追加最適？列生成 57 第１２回のまとめ • カッティングストック問題 – 問題紹介と定式化（復習） – 「列生成」による解法の考え方と改訂単体法 – 整数値ナップザック問題による最適性の判定と列生成 • 動的計画法（DP） – 動的計画法による整数値ナップザック問題の解法 58