オペレーションズリサーチA 第4回改訂単体法 10/23 椎名孝之 • • • • • • • • 授業サポートページ http://www.morito.mgmt.waseda.ac.jp/ora/ ソフトウェアAMPL＋CPLEXインストール（確認）問題がある場合[email protected] 10/23 第4回レポート課題提示（締切10/30） 10/30 第5回双対理論 11/6 第6回分枝限定法 11/13 第7回ソフトウェアを用いた演習 11/20 第8回ネットワーク最適化 1 単体法：効率化 • 単体表の軸演算を全て計算しなければならないか？基底変数 z x3 x4 定数項 z x1 x2 x3 x4 θ 0 1 2 3 0 0 ― 4 0 1 1 1 0 4/1 6 0 1 2 0 1 6/2 • 新たに基底変数となる候補の非基底変数を選ぶには、目的関数（単体基準すなわち（負の）被約費用）行の計算が必要 • 基底から出る基底変数の選択には、新たに基底となる列と定数項の列の計算が必要 2 単体法：1反復の計算 • 入力データA, b, c を保存して、必要となる場合、その都度元データから使用（列B,Nの情報も保持） cBTB-1 b B-1b z 1 0 xB 0 I xN pT=cBT B-1 N － cNT B-1N yk=B-1ak 基底変数定数項 z 0 x3 4 x4 6 z x1 x2 x3 x4 1 2 3 0 0 0 1 1 1 0 0 1 2 0 1 z x3 x2 -9 1 1/2 0 0 -3/2 1 0 1/2 0 1 -1/2 3 0 1/2 1 0 1/2 • 必要な情報：他には？ B-1 3 B-1に軸演算を施すと、(B’)-1 • 基底B =(a1,...,ah ,..., am) がB’ =(a1,...,ak ,..., am) に変わるものとする (ただし、yk=B-1 ak) • (B’)-1 B’Jhk B-1 = (B’)-1 B B-1 • これよりJhk B-1 = (B’)-1 4 改訂単体法：保持すべきデータ • 入力データA, b, c を保存して、必要となる場合、その都度元データから使用 z xB xN cBTB-1 b 1 0 pT=cBT B-1 N － cNT B-1ak B-1b 0 I B-1N • 必要な情報： B-1の計算のために、□を保持しながら更新 z xB xN cBTB-1 b 1 0 pT=cBT B-1 N － cNT B-1b 0 I B-1N B-1ak • n >> m の場合、単体表全体を計算するよりも、計算の手間が大幅に減少 5 改訂単体法：逆行列の更新 • 必要な情報： B-1の計算のために、□を保持しながら更新 z xB xN cBTB-1 b 1 0 pT=cBT B-1 N － cNT 基底 B B-1b 0 I B-1N ↓軸演算後 T cB’ (B’) 基底 (B’)-1b B’ -1 b (π’)T T =cB’ (B’) (B’) -1 -1 B-1ak 初期単体表でB＝I, cB=0 ならば, xB に対する目的関数の係数部分に (π’)T= cB’T (B’) –1が現れるそうでない場合は当該箇所にπTを入れておけばよい 6 まとめ • ステップ1：p 計算 • ステップ2：yk =B-1ak z xB xN cBTB-1 b 1 0 B-1b 0 I • ステップ3：軸演算前 B=(a1,...,ah ,..., am) cBTB-1 b πT =cBT B -1 B-1b B-1 pT=cBT B-1 N － cNT B-1N B-1ak pk y1k … yhk … ymk • ステップ3：軸演算後 B’=(a1,...,ak ,..., am) cB’T (B’) -1 b (B’)-1b (π’)T =cB’ T (B’) -1 (B’) -1 0 0 … 1 yk =B-1ak yhk>0 軸演算 ak:基底 ah:非基底 … 0 7 レポート課題 • 10/30（金）13:00まで51号館13-01森戸研ポスト 8