簡介
分枝定界法(branch and bound method)是指以有限投資為約束,迫切度為權值,將問題的所有可行解空間恰當地進行系統搜尋,以求得最優解的方法。可行解空間反覆分割為越來越小的子集(分枝),並為每個子集內的解值計算下一個界(定界),直到不再分割為止,為有限投資方向決策模型之一,亦是一種最佳化方法 。
決策模型
決策模型由主程式和交通流分配、最短路網費用等子程式所組成 。
最佳化問題發展現狀
最最佳化理論與算法是一個重要的數學分支,它所討論的問題是怎樣在眾多的方案中找到一個最優的方案。例如,在工程設計中,選擇怎樣的設計參數,才能使設計方案既滿足要求又能降低成本;在資源分配中,資源有限時怎樣分配,才能使分配方案既可以滿足各方面的要求,又可以獲得最多的收益;在生產計畫安排中,怎樣設計生產方案才能提高產值和利潤;在軍事指揮中,確定怎樣的最佳作戰方案,才能使自己的損失最小,傷敵最多,取得戰爭的勝利;在我們的生活中,諸如此類問題,到處可見,最最佳化作為數學的一個分支,為這些問題的解決提供了一些理論基礎和求解方法。
最最佳化是個古老的課題,長期以來,人們一直對最最佳化問題進行著探討和研究,在二十世紀四十年代末,Dantzig提出了單純形法,有效地解決了線性規劃問題,從而最最佳化成為了一門獨立的學科 。
線性規劃
有關線性規劃方面的理論和算法發展得相當完善,但是關於非線性規劃問題的理論和算法還有待進一步的研究,實際套用中還有待進一步的完善。傳統的非線性全局最最佳化方法只能求出問題的局部最優解,但由於許多問題的局部最優解不一定是全局最優解,使得傳統的非線性最最佳化方法不能直接成功地套用於求解非線性全局最最佳化問題。另外,沒有一個固定的評判標準來判斷得到的局部最優解是否為全局最優解。隨著科學技術的發展和計算機計算能力的提高,最最佳化理論得到了迅速的發展,湧現出了許多新的算法,如打洞函式法,填充函式法,lagrangian乘子函式方法,信賴域方法,慮子方法等 。