缓和法分枝限定法.ppt

《缓和法分枝限定法.ppt》由会员分享，可在线阅读，更多相关《缓和法分枝限定法.ppt（34页珍藏版）》请在三一办公上搜索。

1、1,12緩和法分枝限定法,2,、問題判定問題言語捉。、数理計画法問題定式化行。数理計画法、現実問題解重要技術。,数理計画法定式化,数理計画法、通常評価関数（目標関数）最大化問題最小化問題捉。、一般形次与。,3,最大化,条件,最大化問題,最小化問題最大化問題区別、最適化呼。,最小化,条件,最小化問題,4,：変数集合、表現、表現、表現、定数K,判定問題関係,数理計画法定式化対応判定問題作。最小化問題対応判定問題記述示。,名称：P,最小化問題,問：？,判定問題解、最小値求多項式時間得。,5,判定問題最適化問題,判定問題、K持問題P(K)。判定問題入力、多項式構成目指。基本的、K値分探索特定。,、判定

2、問題多項式時間解、多項式時間最小値求示。（同様、手法最大値求。）,6,MIN()K=1;while(P(K)=TURE)K=2*K;K=OPT(K/2,K);return(K);,OPT(K_l,K_r)if(K_l=K_r)return(K_r);K_m=(K_l+K_r)/2;if(P(K_m)=TRUE)OPT(K_m,K_r);elseOPT(K_l,K_m);,最適値上界求。,最適値求。,7,計算時間解析。最適値。、最適値上界求部分回繰返、最適値求部分再帰行。、判定問題回呼出最適値特定。,、最適化問題出力。（判定問題、K入力注意。）、出力計算時間依存出力依存型（Output sens

3、itive)。（判定問題、出力意味注意。）,、判定問題解計算量時間。（変数、条件式定入力。）、上議論、時間最適化問題解。,以上、判定問題多項式時間解、最適化問題問題（入力出力）多項式時間解。,8,線形計画法、特徴、次表。,線形計画法,P,最小化,条件,線形計画法,数理計画法問題中，評価関数条件式全変数一次式、線形計画問題。,9,線形計画法、特徴各要素、実数。対，整数計画法、特徴（解）各要素整数。、次表。,整数計画法,P,最小化,条件,整数計画法,10,数理計画法計算量,P,NP,NP-hard,NP-complete,整数計画法,線形計画法,、線形計画法P属、1979年Khachiyan楕円体

4、法発表。後、高速計算法、1984年Karmarkar内点法一種提案。発見以前、単体法（法）用。、線形計画法解単体法多項式時間指数時間。（、現実問題単体法適用、高速解多。、特別対、多計算要。）,11,緩和法,線形計画問題実用的解法。、整数計画問題NP完全、多項式時間構築難。、問題性質上整数解必要。場合、対応線形計画問題解、整数計画問題解対知見得。、難問題（原問題）制約条件緩、解易問題変換、変換後問題（緩和問題）解原問題対情報得解法緩和法。緩和問題、条件緩、解存在空間（解空間）原問題解空間広、緩和問題最適解（緩和解）原問題最適値限。、緩和解、原問題許容解（実行可能解）、原問題解得。、緩和解、原問題

5、解存在範囲程度役目。、最大化問題、緩和解原問題上界。,12,原問題解空間,緩和問題解空間,緩和問題最適値,原問題最適値,13,線形緩和,整数問題、整数制約緩和法線形緩和。,例題：,問題,、整数計画問題問題定式化。,P,最大化,条件,例（原問題）,特徴,整数条件,14,P,最大化,条件,例（緩和問題）,特徴,緩和条件,15,問題場合、緩和解次得。,、,緩和解得。、原問題評価値整数注意、原問題最大値上界。,16,部分列挙法,緩和行際、場合分行改善。、場合分行、緩和強化。方法部分列挙法。（、部分列挙法系統的繰返行手法分枝限定法。）,、先例対部分列挙方考方示。,先、線形緩和得緩和解、,、緩和解切捨、上

6、界値求。、非整数解注目、問題分。,17,P0,最大化,条件,子問題,特徴,P1,最大化,条件,子問題,特徴,問題,問題,18,P0緩和問題解、緩和値。、P0上界、値切捨得。,一方、P1緩和問題解、緩和値。、P1上界、値切捨得。,、原問題P上界値考。P、関、0値、P最適値、P0緩和値P1緩和値大方小。大89原問題P上界求。値、単線形緩和場合良値。,19,部分列挙法問題領域,20,罰金法,緩和法一種罰金法。、緩和法呼。方法、制約式単純取除変、制約式破解（罰金）方法。次最大化問題対、緩和例示。,P,最大化,条件,最大化問題,21,最大化,条件,緩和問題,等式制約取除、適当数値倍目的関数組込、最大化問

7、題対緩和問題構成。,問題、1固定問題一特定。任意問題任意許容解対，成立、問題関数値原問題関数値等。各値原問題。、問題最適値、原問題最適値以上。,22,分枝限定法,分枝限定法、最基本的適応範囲広方法。分枝限定法、緩和問題何度解原問題解方法。解法中心、分枝操作限定操作。,分枝操作：問題子問題分（場合分）操作。緩和問題、整数変数固定場合分多。,23,限定操作：解良子問題見，分枝操作省操作。限定操作行次状況。以下、最大化問題扱。,(i)子問題実行不可能。,(ii)子問題最適値上界、暫定解（原問題許容解、現在最良解）目的関数値良（同小。）,(iii)子問題緩和問題最適解原問題許容解。,子問題性質、子問題

8、最適解目的関数値原問題最適解悪。,24,2暫定解最適解出力終了。、適当子問題選、取除。,原問題実行可能解場合実行可能領域分割子問題生成、加。,、分枝限定法基本的枠組与。,分枝限定法,適当方法初期実行解求暫定解、目標関数値暫定値。問題集合。（原問題。）,緩和問題解、得解、上界値。緩和問題許容解持。,原問題実行可能解場合。更新、。,場合、。,暫定解更新,子問題生成,25,、。,、以下例題基分枝限定法見。,P0,最大化,条件,例,特徴,、暫定解発見。,26,P0,最大化,条件,P0線形緩和,特徴,緩和解、求。、上界値切捨5得。,結果、次子問題生成。,27,P1,最大化,条件,特徴,P2,最大化,条件

9、,特徴,28,P1線形緩和、緩和解得。、上界値4得。,、実行、次子問題生成。,P3,最大化,条件,特徴,P4,最大化,条件,特徴,29,P3線形緩和、緩和解得。、上界値4得。解、全整数、原問題実行可能解。、暫定解得。、暫定解更新。、P3子問題生成。,P4線形緩和、緩和解得。、上界値3得。、上界値、暫定解小以上分枝操作繰返必要。（枝刈生。）,、子問題残、問題対分枝可能性。,30,P線形緩和、緩和解得。、上界値5得。場合次子問題生成。,P5,最大化,条件,特徴,P6,最大化,条件,特徴,31,P5線形緩和、緩和解得。、上界値5得。解、全整数、原問題実行可能解。、暫定解得。、暫定解更新。、P5子問題

10、生成。,P6明緩和解存在（実行不能）。、無条件削除。,以上全子問題処理、暫定解真最適値。,32,分枝木,分枝限定法、問題、子問題生成枝木構造表現。,33,分枝限定法性能,分枝限定法、分枝木基列挙法一種、最悪場合、許容解列挙。、現実問題適用、性能良緩和法用効果的働、回数緩和問題解、大規模問題最適解（厳密解）得成功。（成功例多数報告。）,34,分枝限定法方針,分枝限定法、子問題集合順序次処理子問題選択自由度。選択法、主方法多。,深優先探索,選択可能子問題内、最後生成選方法。用実現、深優先探索型分枝限定法。、記憶容量必要。大規模問題解選択枝。,幅優先探索,選択可能子問題内、最前生成選方法。用実現、幅優先探索型分枝限定法。、問題高速解。、必要記憶量膨大多。,最良値探索,緩和値最良選方法。緩和問題性質依存。,