整数計画問題(Integer Programming) n min ci xi i 1 n s.t. aij x j bi , i 1, ,m j 1 xi 0 i 1, xi : 整数 i ,n J 1 2016/7/22 (0-1)ナップサック問題の例 max 4 x1 5 x2 12 x3 14 x4 s.t. 2 x1 3 x2 xi 5 x3 6 x4 0 または 1 i 1, 9 ,4 欲張り法の解:(1,0,1,0),目的関数値16 けちけち法の解:(0,0,1,0),目的関数値12 いずれも最適解ではない (最適解は(0,1,0,1)でした) 2016/7/22 2 近似解法・発見的解法の役割 近似解法(発見的解法)は,方法により求ま る(近似)解が異なる (大域的)最適性は保証されない 計算時間は早い メタ戦略の初期解や探索解の生成に有効 2016/7/22 3 分枝限定法(ぶんしげんていほう) 全列挙法の一つ 小さな問題に分割して,そのすべてを解くとい う考え方に基づく方法 探索の途中で,不要な場合分けを省略するこ とで,計算時間を短縮する 2016/7/22 4 ナップサック問題で考える n max ci xi i 1 n s.t. ai xi b, xi 0 or 1 i 1, ,n i 1 問題の分割:一部の変数の0-1割り当てを固定 探索:すべての変数の0-1割り当てを調べる 5 2016/7/22 分枝図 x1 x2 x3 0 (0,0,0) 2016/7/22 0 x3 1 (0,0,1) 0 x1 1 x2 x2 1 0 x3 1 (0,1,0) (0,1,1) x3 x3 0 (1,0,0) 0 x2 x3 1 x3 (1,0,1) 1 0 x3 1 (1,1,0) (1,1,1) 6 探索の過程は,分枝図で表現できる それぞれの節点は,部分問題に対応 一部の変数を固定した0-1ナップサック問題 問題のサイズは原問題より小さい 既知の実行可能解の中で最も良いものを暫 定解という 7 2016/7/22 分枝図 x1 x1 0 x1 1と固定した x1 1 0 1ナップサック問題 0, x2 1と固定した x2 0 0 1ナップサック問題 x3 0 (0,0,0) 2016/7/22 x3 1 (0,0,1) x2 x2 1 0 x3 1 (0,1,0) (0,1,1) x3 x3 0 (1,0,0) 0 x2 x3 1 x3 (1,0,1) 1 0 x3 1 (1,1,0) (1,1,1) 8 分枝操作 一つの変数を固定して(二つの)問題(子問 題)を生成すること 限定操作 部分問題が実行不能,または 部分問題の最適解が暫定値より良くない ときに,その下の探索を省略すること 9 2016/7/22 分枝図 部分問題の x1 x2 x3 0 (0,0,0) 0 x3 1 (0,0,1) 0 x2 1 x1 1 0 x3 1 (0,1,0) (0,1,1) x3 探索しない 2016/7/22 x2 実行不能 x3 0 (1,0,0) 最適値<暫定値 0 x2 x3 1 x3 (1,0,1) 1 0 x3 1 (1,1,0) (1,1,1) 探索しない 10 ナップサック問題の限定操作の例 LP緩和問題 n max ci xi i 1 n s.t. ai xi b, 0 xi 1 i 1, ,n i 1 はナップサック問題の最適解の上界値を与える 部分問題の上界値が暫定値以下であればそ の下を探索する必要はない(最大化問題であ ることに注意) 11 2016/7/22 分枝限定法の実行例 max 4 x1 5 x2 12 x3 14 x4 s.t. 2 x1 3 x2 xi 5 x3 6 x4 0 または 1 i 1, 9 ,4 暫定解:欲張り法の解(1,0,1,0),暫定値16 緩和問題の解:(0,0,1,2/3),上界値21+1/3 ci ai の大きい順から1 を割り当て,端数を分数で埋める 暫定値<上界値なので,子問題を作成 2016/7/22 12 暫定解(1,0,1,0),暫定値16 上界値21+1/3 1 x4 1 x4 0 2 3 max 4 x1 5 x2 12 x3 14 max 4 x1 5 x2 12 x3 s.t. 2 x1 3x2 s.t. 2 x1 3x2 xi 5 x3 3 xi 0 または 1 i 1,2,3 5 x3 9 0 または 1 i 1,2,3 緩和問題の最適解(0,0,3/5,1) 緩和問題の最適解(1,2/3,1,0) 上界値21+1/5→子問題を作成 上界値19+1/3 13 2016/7/22 暫定解(1,0,1,0),暫定値16 上界値21+1/3 1 x4 1 x4 0 上界値21+1/5 2 x3 x3 1 上界値19+1/3 0 上界値19+2/3 4 実行不能 3 5 x2 1 6 x2 0 max 4 x1 14 s.t. 7 2 x1 x1 3 0 または 1 実行可能解は(0,1,0,1)のみ 暫定値19(=上界値) 緩和問題の最適解(1,0,0,1) 上界値18<暫定値なので終端 2016/7/22 14 上界値21 1 x4 1 x4 0 上界値21 2 x3 x3 1 0 x2 1 上界値19 4 実行不能 3 5 x2 1 x2 6 暫定解(0,1,0,1) 最適解(0,1,0,1) 暫定値19(=上界値) 最適値19 0 8 上界値19+1/3 x2 0 9 緩和問題の最適解 (1/2,1,1,0)上界値19 7 緩和問題の最適解 (1,0,1,0)上界値16 いずれも暫定解を超えないので終了 上界値18 2016/7/22 15 動的計画法 最適性の原理に基づく方法 効率的な列挙法の一つ 最短路問題のダイクストラ法は動的計画法の 一つ 2016/7/22 16 0-1ナップサック問題に対する動的計 画法の例 f ( j , k ) : 要素1 ~ jからいくつか選んで, 容量kの ナップサックに詰める場合の最適値 j max ci xi i 1 j s.t. ai xi k, xi 0 or 1 i 1, ,j i 1 17 2016/7/22 f ( j , k )は以下の漸化式によって与えられる f (1, k ) 0, 0 k c1 , a1 k a1 b f ( j , k ) max f ( j 1, k ), f ( j 1, k j j 1,2, 2,3, , n, k aj) cj b , nの順にそれぞれすべてのk 0,1, , bを計算 f (n, b)は最適値 2016/7/22 18 動的計画法の実行例 max 4 x1 5 x2 12 x3 14 x4 s.t. 2 x1 3 x2 xi 5 x3 6 x4 0 または 1 i 1, 9 ,4 ステップ1: f (1, k )を計算 0, k 4, k f (1, k ) 0,1 2,3, ,9 19 2016/7/22 ステップ2:漸化式 f (2, k ) max f (1, k ), f (1, k a2 ) c2 , k 0, ,9 に従ってf (2, k )を計算. f (2,3) max f (1,3), f (1,3 3) 5 max 4,0 5 5 f (2,5) max f (1,5), f (1,5 3) 5 max 4,4 5 9 要素 j\容量 k 1 0 1 2 3 4 5 6 7 8 9 0 0 4 4 4 4 4 4 4 4 2 2016/7/22 20 ステップ2:漸化式 f (2, k ) max f (1, k ), f (1, k a2 ) c2 , k 0, ,9 に従ってf (2, k )を計算. f (2,3) max f (1,3), f (1,3 3) 5 max 4,0 5 5 f (2,5) max f (1,5), f (1,5 3) 5 max 4,4 5 9 0 1 2 3 4 5 6 7 8 9 0 0 4 4 4 4 4 4 4 4 0 0 4 5 5 9 9 9 9 9 要素 j\容量 k 1 2 21 2016/7/22 以下,これを繰り返す 要素 j\容量 k 1 2 0 1 2 3 4 5 6 7 8 9 0 0 4 4 4 4 4 4 4 4 0 0 4 5 5 9 9 9 9 9 3 19 4 最適値=19が求まる 最適解は, f (4,9) f (3,3) 14よりx4 1 f (3,3) f ( 2,3)よりx3 0 のように,逆に辿ることで得られる. 2016/7/22 22 動的計画法の計算量はO(nb)(擬多項式) nがある程度大きい場合は,単純な全列挙よ りも早い. 0-1ナップサック問題に対しては,要素数が1 万くらいでも分枝限定法であっという間に解 ける 2016/7/22 23
© Copyright 2025 ExpyDoc