1、航空運輸規劃學作業 學院： 民航學院 學號： B0807109 姓名： 倪金霞 Email: njx1210 日期：2009年3月24日第二章 思考題和練習題思考題1、整數規劃求解的困難在哪里？你學過的整數規劃求解算法有哪些？這些算法的效率如何？整數規劃求解的困難在于：整數規劃屬于組合優化問題，具有NP難解性。大規模的整數規劃問題的難解性，已經成為解決問題難以逾越的障礙，不得以放棄最優解的獲得，退而求其次，用啟發式算法獲得次優解或滿意解。整數規劃求解算法有：（i）分枝定界法可求純或混合整數線性規劃。（ii）割平面法可求純或混合整數線性規劃。（iii）枚舉法窮舉法和隱枚舉法。其中隱枚舉法可求解“

2、0-1”整數規劃，包括：過濾隱枚舉法；分枝隱枚舉法。（iv）匈牙利法解決指派問題（“0-1”規劃特殊情形）。（v）蒙特卡洛法求解各種類型規劃。分枝定界法由于使用靈活且便于用計算機求解，已是求解整數規劃的重要方法。現在它已成功地應用于求解生產進度問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題等，但不是多項式算法，有時需要與其它算法結合才能解決問題；割平面法用于求解純整數規劃問題時，會遇到收斂很慢的情形，有時和分枝定界法配合使用；枚舉法不能用于求解大規模整數規劃問題。2、什么是組合優化問題？整數規劃和網絡流問題是組合優化問題嗎？你能舉出幾個組合優化的典型問題嗎？問題的可行解個數是用問題規模

3、的排列或組合數來計算的，這一類問題叫做組合優化問題。如果對這類問題采用枚舉法尋找最優解，算法的復雜度是用問題規模的階乘來表示的，因此是指數型算法。一般這類問題不易找到多項式算法，通常是NP完全問題。整數規劃問題和網絡流問題屬于組合優化問題。典型的組合優化問題有：旅行推銷員問題、運輸問題、工作指派問題、貨物裝箱問題、最短路問題、最大（小）支撐樹問題、最優邊無關集問題、最小截集問題等。3、什么是算法的復雜度？如何分析算法的復雜度？什么叫做NP問題，什么叫做NP完全問題，什么叫做NP難問題？以問題的變量數或/和約束條件數表達問題的規模，當把求解該問題的計算量表達成問題規模的函數形式時，且不計常數項和

4、常系數，寫成如O(n3)或O(2n)形式，叫做算法的復雜度。即解決問題的一個具體的算法的執行時間，這是算法的性質。算法的復雜度分析總是考慮最壞的情形，因此如果這種最壞情形很難發生，則這種計算復雜度的代表性比較差。有時指數型算法的表現好于多項式的算法。例如線性規劃問題的單純形算法在最壞的情形下被證明是指數型的，內點法是多項式的。但通常情況下，單純形算法比內點法還快。NP里面的N代表Non-Deterministic（意思是非確定性的），P代表Polynomial倒是對的。NP就是Non-deterministic Polynomial的問題，也即是多項式復雜程度的非確定性問題。NP完全問題，即“

5、NP COMPLETE”，是不確定性圖靈機在P時間內能解決的問題，是世界七大數學難題之一，是一類非常特殊的NP問題。NP完全問題目前沒有多項式的有效算法，只能用指數級甚至階乘級復雜度的搜索。對于這類問題，其求解的計算時間不能隨著計算機性能的提高而有效縮短，因此不能指望依靠計算機性能的提高來解決。NP難問題，即“NP-Hard”。4、你能舉出幾個約束最短路問題嗎？多商品流問題在生產實際中是否存在？舉一二例說明。確定機組航班環是約束最短路問題。多商品流問題在生產實際中存在，例如：航線網絡規劃問題。5、Lagrange分解算法、Danzig-Wolfe分解算法、Benders分解算法各有什么特點？請

6、分析它們的優缺點。Lagrange分解算法采用了Lagrangian乘子，解除了模型中的困難約束,將難解問題分解成易解問題。在Lagrangian松弛算法中最關鍵的是如何更新Lagrangian乘子，一般情況下，Lagrangian松弛算法收斂速度較慢，而且是振蕩收斂。最大Lagrangian函數值也不一定等于最小目標函數值，可能會存在所謂的對偶間隙。Danzig-Wolfe分解算法是結合列生成方法，由限制主問題和子問題交替求解的。與列生成算法相比，列生成算法沒有區分“難處理”和“易處理”約束條件，也就是認為都是“易處理”的約束條件，而Danzig-Wolfe分解算法則可將“難處理”和“易處理

7、”的約束條件分開處理。Danzig-Wolfe分解算法需要求解一個線性規劃問題，還需要求出子問題的各頂點（基本可行解），這在計算上并不劃算。但可以與列生成結合使用，構建有用的算法。Benders分解算法利用對偶理論將“易處理”變量和“難處理”變量分離開來，分別形成Benders主問題和子問題來進行迭代求解，其中只含有“易處理”變量的模型是子問題，含有“難處理”變量的模型是Benders主問題。使用Benders分解算法進行網絡設計時，主問題一般都存在最優解，而子問題在開始迭代的幾步則可能不可行，這引起幾個問題：無法給出較好的目標函數上界；對偶問題無界，如何尋找對偶問題可行域的極點和極方向？難處

8、理變量初始值對求解效率影響很大，如何確定它們？練習題3、試推導網絡設計問題的Benders分解算法的限制主問題和子問題模型。設網絡中各邊的流變量為，選擇變量為，其中。選擇變量是0-1變量，當邊(i,j)被選中，yij=1，否則=0。若分別表示邊（i,j）的容量、單位流費用和邊選擇成本，則此該問題的數學模型如下：首先令（取），構造模型：該模型中只含有“易處理”變量，此模型為原問題的子問題。通常該子問題不可行，它的對偶問題是根據對偶定理，對偶問題的最優解的目標函數等于原問題的最優目標函數值（不包括常數項），若對偶問題可行域存在，并且已知它的k個頂點，l個極方向ri,i=1,2,.,l，則我們可以構

9、造與原問題等價的規劃模型該問題又可以等價為 該問題只含有實數變量和難處理變量，不含有變量，已實現“難”“易”兩種變量的分離，該模型為Berders 主問題。5、試用Benders分解算法求解圖2-37的網絡設計問題。圖中分別表示邊（i,j）的容量、單位流費用和邊選擇成本，要求從源點s運送6個單位流量到匯點t。解：設網絡中各邊的流變量為，選擇變量為。選擇變量是0-1變量，當邊(i,j)被選中，yij=1，否則=0，。該問題的數學模型如下：首先，令=0，構造子問題該子問題不可行，它的對偶問題是其中對應節點i的流平衡約束條件，對應邊(i,j)的容量約束條件。該可行域存在，但無界，因此存在若干頂點和極方向。取極點，極方向，由此構成第一次主問題如下：求得該限制主問題的解，則原問題目標函數的下界為LB=。將主問題的解帶入原問題，得該次迭代的子問題，若可行求得其解，且得到原問題目標函數的上界UB。當LB=UB時，解，為原問題的最優解。否則，若還是不可行