倪金霞(B0807109)二章航空運(yùn)輸規(guī)劃作業(yè)(第二章習(xí)題)

航空運(yùn)輸規(guī)劃學(xué)作業(yè) 學(xué)院： 民航學(xué)院 學(xué)號(hào)： B 姓名： 倪金霞 Email: 日期：2009年3月24日第二章 思考題和練習(xí)題思考題1、整數(shù)規(guī)劃求解的困難在哪里？你學(xué)過的整數(shù)規(guī)劃求解算法有哪些？這些算法的效率如何？整數(shù)規(guī)劃求解的困難在于：整數(shù)規(guī)劃屬于組合優(yōu)化問題，具有NP難解性。大規(guī)模的整數(shù)規(guī)劃問題的難解性，已經(jīng)成為解決問題難以逾越的障礙，不得以放棄最優(yōu)解的獲得，退而求其次，用啟發(fā)式算法獲得次優(yōu)解或滿意解。整數(shù)規(guī)劃求解算法有：（i）分枝定界法可求純或混合整數(shù)線性規(guī)劃。（ii）割平面法可求純或混合整數(shù)線性規(guī)劃。（iii）枚舉法窮舉法和隱枚舉法。其中隱枚舉法可求解“0-1”整數(shù)規(guī)劃，包括：過濾隱枚舉法；分枝隱枚舉法。（iv）匈牙利法解決指派問題（“0-1”規(guī)劃特殊情形）。（v）蒙特卡洛法求解各種類型規(guī)劃。分枝定界法由于使用靈活且便于用計(jì)算機(jī)求解，已是求解整數(shù)規(guī)劃的重要方法?，F(xiàn)在它已成功地應(yīng)用于求解生產(chǎn)進(jìn)度問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題等，但不是多項(xiàng)式算法，有時(shí)需要與其它算法結(jié)合才能解決問題；割平面法用于求解純整數(shù)規(guī)劃問題時(shí)，會(huì)遇到收斂很慢的情形，有時(shí)和分枝定界法配合使用；枚舉法不能用于求解大規(guī)模整數(shù)規(guī)劃問題。2、什么是組合優(yōu)化問題？整數(shù)規(guī)劃和網(wǎng)絡(luò)流問題是組合優(yōu)化問題嗎？你能舉出幾個(gè)組合優(yōu)化的典型問題嗎？問題的可行解個(gè)數(shù)是用問題規(guī)模的排列或組合數(shù)來計(jì)算的，這一類問題叫做組合優(yōu)化問題。如果對(duì)這類問題采用枚舉法尋找最優(yōu)解，算法的復(fù)雜度是用問題規(guī)模的階乘來表示的，因此是指數(shù)型算法。一般這類問題不易找到多項(xiàng)式算法，通常是NP完全問題。整數(shù)規(guī)劃問題和網(wǎng)絡(luò)流問題屬于組合優(yōu)化問題。典型的組合優(yōu)化問題有：旅行推銷員問題、運(yùn)輸問題、工作指派問題、貨物裝箱問題、最短路問題、最大（?。┲螛鋯栴}、最優(yōu)邊無關(guān)集問題、最小截集問題等。3、什么是算法的復(fù)雜度？如何分析算法的復(fù)雜度？什么叫做NP問題，什么叫做NP完全問題，什么叫做NP難問題？以問題的變量數(shù)或/和約束條件數(shù)表達(dá)問題的規(guī)模，當(dāng)把求解該問題的計(jì)算量表達(dá)成問題規(guī)模的函數(shù)形式時(shí)，且不計(jì)常數(shù)項(xiàng)和常系數(shù)，寫成如O(n3)或O(2n)形式，叫做算法的復(fù)雜度。即解決問題的一個(gè)具體的算法的執(zhí)行時(shí)間，這是算法的性質(zhì)。算法的復(fù)雜度分析總是考慮最壞的情形，因此如果這種最壞情形很難發(fā)生，則這種計(jì)算復(fù)雜度的代表性比較差。有時(shí)指數(shù)型算法的表現(xiàn)好于多項(xiàng)式的算法。例如線性規(guī)劃問題的單純形算法在最壞的情形下被證明是指數(shù)型的，內(nèi)點(diǎn)法是多項(xiàng)式的。但通常情況下，單純形算法比內(nèi)點(diǎn)法還快。NP里面的N代表Non-Deterministic（意思是非確定性的），P代表Polynomial倒是對(duì)的。NP就是Non-deterministic Polynomial的問題，也即是多項(xiàng)式復(fù)雜程度的非確定性問題。NP完全問題，即“NP COMPLETE”，是不確定性圖靈機(jī)在P時(shí)間內(nèi)能解決的問題，是世界七大數(shù)學(xué)難題之一，是一類非常特殊的NP問題。NP完全問題目前沒有多項(xiàng)式的有效算法，只能用指數(shù)級(jí)甚至階乘級(jí)復(fù)雜度的搜索。對(duì)于這類問題，其求解的計(jì)算時(shí)間不能隨著計(jì)算機(jī)性能的提高而有效縮短，因此不能指望依靠計(jì)算機(jī)性能的提高來解決。NP難問題，即“NP-Hard”。4、你能舉出幾個(gè)約束最短路問題嗎？多商品流問題在生產(chǎn)實(shí)際中是否存在？舉一二例說明。確定機(jī)組航班環(huán)是約束最短路問題。多商品流問題在生產(chǎn)實(shí)際中存在，例如：航線網(wǎng)絡(luò)規(guī)劃問題。5、Lagrange分解算法、Danzig-Wolfe分解算法、Benders分解算法各有什么特點(diǎn)？請(qǐng)分析它們的優(yōu)缺點(diǎn)。Lagrange分解算法采用了Lagrangian乘子，解除了模型中的困難約束,將難解問題分解成易解問題。在Lagrangian松弛算法中最關(guān)鍵的是如何更新Lagrangian乘子，一般情況下，Lagrangian松弛算法收斂速度較慢，而且是振蕩收斂。最大Lagrangian函數(shù)值也不一定等于最小目標(biāo)函數(shù)值，可能會(huì)存在所謂的對(duì)偶間隙。Danzig-Wolfe分解算法是結(jié)合列生成方法，由限制主問題和子問題交替求解的。與列生成算法相比，列生成算法沒有區(qū)分“難處理”和“易處理”約束條件，也就是認(rèn)為都是“易處理”的約束條件，而Danzig-Wolfe分解算法則可將“難處理”和“易處理”的約束條件分開處理。Danzig-Wolfe分解算法需要求解一個(gè)線性規(guī)劃問題，還需要求出子問題的各頂點(diǎn)（基本可行解），這在計(jì)算上并不劃算。但可以與列生成結(jié)合使用，構(gòu)建有用的算法。Benders分解算法利用對(duì)偶理論將“易處理”變量和“難處理”變量分離開來，分別形成Benders主問題和子問題來進(jìn)行迭代求解，其中只含有“易處理”變量的模型是子問題，含有“難處理”變量的模型是Benders主問題。使用Benders分解算法進(jìn)行網(wǎng)絡(luò)設(shè)計(jì)時(shí)，主問題一般都存在最優(yōu)解，而子問題在開始迭代的幾步則可能不可行，這引起幾個(gè)問題：無法給出較好的目標(biāo)函數(shù)上界；對(duì)偶問題無界，如何尋找對(duì)偶問題可行域的極點(diǎn)和極方向？難處理變量初始值對(duì)求解效率影響很大，如何確定它們？練習(xí)題3、試推導(dǎo)網(wǎng)絡(luò)設(shè)計(jì)問題的Benders分解算法的限制主問題和子問題模型。設(shè)網(wǎng)絡(luò)中各邊的流變量為，選擇變量為，其中。選擇變量是0-1變量，當(dāng)邊(i,j)被選中，yij=1，否則=0。若分別表示邊（i,j）的容量、單位流費(fèi)用和邊選擇成本，則此該問題的數(shù)學(xué)模型如下：首先令（?。?，構(gòu)造模型：該模型中只含有“易處理”變量，此模型為原問題的子問題。通常該子問題不可行，它的對(duì)偶問題是根據(jù)對(duì)偶定理，對(duì)偶問題的最優(yōu)解的目標(biāo)函數(shù)等于原問題的最優(yōu)目標(biāo)函數(shù)值（不包括常數(shù)項(xiàng)），若對(duì)偶問題可行域存在，并且已知它的k個(gè)頂點(diǎn)，l個(gè)極方向ri,i=1,2,.,l，則我們可以構(gòu)造與原問題等價(jià)的規(guī)劃模型該問題又可以等價(jià)為 該問題只含有實(shí)數(shù)變量和難處理變量，不含有變量，已實(shí)現(xiàn)“難”“易”兩種變量的分離，該模型為Berders 主問題。5、試用Benders分解算法求解圖2-37的網(wǎng)絡(luò)設(shè)計(jì)問題。圖中分別表示邊（i,j）的容量、單位流費(fèi)用和邊選擇成本，要求從源點(diǎn)s運(yùn)送6個(gè)單位流量到匯點(diǎn)t。解：設(shè)網(wǎng)絡(luò)中各邊的流變量為，選擇變量為。選擇變量是0-1變量，當(dāng)邊(i,j)被選中，yij=1，否則=0，。該問題的數(shù)學(xué)模型如下：首先，令=0，構(gòu)造子問題該子問題不可行，它的對(duì)偶問題是其中對(duì)應(yīng)節(jié)點(diǎn)i的流平衡約束條件，對(duì)應(yīng)邊(i,j)的容量約束條件。該可行域存在，但無界，因此存在若干頂點(diǎn)和極方向。取極點(diǎn)，極方向，由此構(gòu)成第一次主問題如下：求得該限制主問題的解，則原問題目標(biāo)函數(shù)的下界為LB=。將主問題的解帶入原問題，得該次迭代的子問題，若可行求得其解，且得到原問題目標(biāo)函數(shù)的上界UB。當(dāng)LB=UB時(shí)，解，為原問題的最優(yōu)解。否則，若還是不可行