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

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

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

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

5、NP COMPLETE”，是不確定性圖靈機(jī)在P時(shí)間內(nèi)能解決的問(wèn)題，是世界七大數(shù)學(xué)難題之一，是一類非常特殊的NP問(wèn)題。NP完全問(wèn)題目前沒(méi)有多項(xiàng)式的有效算法，只能用指數(shù)級(jí)甚至階乘級(jí)復(fù)雜度的搜索。對(duì)于這類問(wèn)題，其求解的計(jì)算時(shí)間不能隨著計(jì)算機(jī)性能的提高而有效縮短，因此不能指望依靠計(jì)算機(jī)性能的提高來(lái)解決。NP難問(wèn)題，即“NP-Hard”。4、你能舉出幾個(gè)約束最短路問(wèn)題嗎？多商品流問(wèn)題在生產(chǎn)實(shí)際中是否存在？舉一二例說(shuō)明。確定機(jī)組航班環(huán)是約束最短路問(wèn)題。多商品流問(wèn)題在生產(chǎn)實(shí)際中存在，例如：航線網(wǎng)絡(luò)規(guī)劃問(wèn)題。5、Lagrange分解算法、Danzig-Wolfe分解算法、Benders分解算法各有什么特點(diǎn)？請(qǐng)

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

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

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

9、造與原問(wèn)題等價(jià)的規(guī)劃模型該問(wèn)題又可以等價(jià)為 該問(wèn)題只含有實(shí)數(shù)變量和難處理變量，不含有變量，已實(shí)現(xiàn)“難”“易”兩種變量的分離，該模型為Berders 主問(wèn)題。5、試用Benders分解算法求解圖2-37的網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題。圖中分別表示邊（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，。該問(wèn)題的數(shù)學(xué)模型如下：首先，令=0，構(gòu)造子問(wèn)題該子問(wèn)題不可行，它的對(duì)偶問(wèn)題是其中對(duì)應(yīng)節(jié)點(diǎn)i的流平衡約束條件，對(duì)應(yīng)邊(i,j)的容量約束條件。該可行域存在，但無(wú)界，因此存在若干頂點(diǎn)和極方向。取極點(diǎn)，極方向，由此構(gòu)成第一次主問(wèn)題如下：求得該限制主問(wèn)題的解，則原問(wèn)題目標(biāo)函數(shù)的下界為L(zhǎng)B=。將主問(wèn)題的解帶入原問(wèn)題，得該次迭代的子問(wèn)題，若可行求得其解，且得到原問(wèn)題目標(biāo)函數(shù)的上界UB。當(dāng)LB=UB時(shí)，解，為原問(wèn)題的最優(yōu)解。否則，若還是不可行