《缓和法分枝限定法》由会员分享，可在线阅读，更多相关《缓和法分枝限定法（34页珍藏版）》请在金锄头文库上搜索。
1、12緩和法分枝限定法1、問題判定問題言語捉。、数理計画法問題定式化行。数理計画法、現実問題解重要技術。数理計画法定式化数理計画法、通常評価関数（目標関数）最大化問題最小化問題捉。、一般形次与。2最大化条件最大化問題最小化問題最大化問題区別、最適化呼。最小化条件最小化問題3：変数集合、表現、表現、表現、定数K判定問題関係数理計画法定式化対応判定問題作。最小化問題対応判定問題記述示。名称：P最小化問題問：？判定問題解、最小値求多項式時間得。4判定問題最適化問題判定問題、K持問題P(K)。判定問題入力、多項式構成目指。基本的、K値分探索特定。、判定問題多項式時間解、多項式時間最小値求示。（同様、手法
2、最大値求。）5MIN()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);最適値上界求。最適値求。6計算時間解析。最適値。、最適値上界求部分回繰返、最適値求部分再帰行。、判定問題回呼出最適値特定。、最適化問題出力。（判定問題、K入力注意。）、出力計算時間依存出力依存型（Output sensitive)。（判定問題、出力意味注意。）、判定問題解計算量時間。
3、（変数、条件式定入力。）、上議論、時間最適化問題解。以上、判定問題多項式時間解、最適化問題問題（入力出力）多項式時間解。7線形計画法、特徴、次表。線形計画法P最小化条件線形計画法数理計画法問題中，評価関数条件式全変数一次式、線形計画問題。8線形計画法、特徴各要素、実数。対，整数計画法、特徴（解）各要素整数。、次表。整数計画法P最小化条件整数計画法9数理計画法計算量PNPNP-hardNP-complete整数計画法線形計画法、線形計画法P属、1979年Khachiyan楕円体法発表。後、高速計算法、1984年Karmarkar内点法一種提案。発見以前、単体法（法）用。、線形計画法解単体法多項式
4、時間指数時間。（、現実問題単体法適用、高速解多。、特別対、多計算要。）10緩和法線形計画問題実用的解法。、整数計画問題NP完全、多項式時間構築難。、問題性質上整数解必要。場合、対応線形計画問題解、整数計画問題解対知見得。、難問題（原問題）制約条件緩、解易問題変換、変換後問題（緩和問題）解原問題対情報得解法緩和法。緩和問題、条件緩、解存在空間（解空間）原問題解空間広、緩和問題最適解（緩和解）原問題最適値限。、緩和解、原問題許容解（実行可能解）、原問題解得。、緩和解、原問題解存在範囲程度役目。、最大化問題、緩和解原問題上界。11原問題解空間緩和問題解空間緩和問題最適値原問題最適値12線形緩和整数問
5、題、整数制約緩和法線形緩和。例題： 問題、整数計画問題問題定式化。P最大化条件例（原問題）特徴整数条件13P最大化条件例（緩和問題）特徴緩和条件14問題場合、緩和解次得。、緩和解得。、原問題評価値整数注意、原問題最大値上界。15部分列挙法緩和行際、場合分行改善。、場合分行、緩和強化。方法部分列挙法。（、部分列挙法系統的繰返行手法分枝限定法。）、先例対部分列挙方考方示。先、線形緩和得緩和解、緩和解切捨、上界値求。、非整数解注目、問題分。16P0最大化条件子問題特徴P1最大化条件子問題特徴問題問題17P0緩和問題解、緩和値。、P0上界、値切捨得。一方、P1緩和問題解、緩和値。、P1上界、値切捨得。
6、、原問題P上界値考。P、関、0値、P最適値、P0緩和値P1緩和値大方小。大89原問題P上界求。値、単線形緩和場合良値。18部分列挙法問題領域19罰金法緩和法一種罰金法。、緩和法呼。方法、制約式単純取除変、制約式破解（罰金）方法。次最大化問題対、緩和例示。P最大化条件最大化問題20最大化条件緩和問題等式制約取除、適当数値倍目的関数組込、最大化問題対緩和問題構成。問題、1固定問題一特定。任意問題任意許容解対，成立、問題関数値原問題関数値等。各値原問題。、問題最適値、原問題最適値以上。21分枝限定法分枝限定法、最基本的適応範囲広方法。分枝限定法、緩和問題何度解原問題解方法。解法中心、分枝操作限定操作
7、。分枝操作：問題子問題分（場合分）操作。緩和問題、整数変数固定場合分多。22限定操作：解良子問題見，分枝操作省操作。限定操作行次状況。以下、最大化問題扱。(i)子問題実行不可能。(ii)子問題最適値上界、暫定解（原問題許容解、現在最良解）目的関数値良（同小。）(iii)子問題緩和問題最適解原問題許容解。子問題性質、子問題最適解目的関数値原問題最適解悪。232暫定解最適解出力終了。、適当子問題選、取除。原問題実行可能解場合実行可能領域分割子問題生成、加。、分枝限定法基本的枠組与。分枝限定法適当方法初期実行解求暫定解、目標関数値暫定値。問題集合。（原問題。）緩和問題解、得解、上界値。緩和問題許容解
8、持。原問題実行可能解場合。更新、。場合、。暫定解更新子問題生成24、。、以下例題基分枝限定法見。P0最大化条件例特徴、暫定解発見。25P0最大化条件P0線形緩和特徴緩和解、求。、上界値切捨5得。結果、次子問題生成。26P1最大化条件特徴P2最大化条件特徴27P1線形緩和、緩和解得。、上界値4得。、実行、次子問題生成。P3最大化条件特徴P4最大化条件特徴28P3線形緩和、緩和解得。、上界値4得。解、全整数、原問題実行可能解。、暫定解得。、暫定解更新。、P3子問題生成。P4線形緩和、緩和解得。、上界値3得。、上界値、暫定解小以上分枝操作繰返必要。（枝刈生。）、子問題残、問題対分枝可能性。29P線形
9、緩和、緩和解得。、上界値5得。場合次子問題生成。P5最大化条件特徴P6最大化条件特徴30P5線形緩和、緩和解得。、上界値5得。解、全整数、原問題実行可能解。、暫定解得。、暫定解更新。、P5子問題生成。P6明緩和解存在（実行不能）。、無条件削除。以上全子問題処理、暫定解真最適値。31分枝木分枝限定法、問題、子問題生成枝木構造表現。32分枝限定法性能分枝限定法、分枝木基列挙法一種、最悪場合、許容解列挙。、現実問題適用、性能良緩和法用効果的働、回数緩和問題解、大規模問題最適解（厳密解）得成功。（成功例多数報告。）33分枝限定法方針分枝限定法、子問題集合順序次処理子問題選択自由度。選択法、主方法多。深優先探索選択可能子問題内、最後生成選方法。用実現、深優先探索型分枝限定法。、記憶容量必要。大規模問題解選択枝。幅優先探索選択可能子問題内、最前生成選方法。用実現、幅優先探索型分枝限定法。、問題高速解。、必要記憶量膨大多。最良値探索緩和値最良選方法。緩和問題性質依存。34
