資源描述：
《優(yōu)化建模與LINGO第07章.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、歡迎各位同學學習第七章內(nèi)容導航概述7.1運輸問題與轉(zhuǎn)運問題7.2最短路問題和最大流問題7.3最優(yōu)連線問題與旅行商問題7.4計劃評審方法和關鍵路線法習題七第7章 圖論與網(wǎng)絡模型本章內(nèi)容概述本章介紹圖論與網(wǎng)絡(GraphTheoryandNetwork)的有關優(yōu)化問題模型。在這里，我們并不打算全面系統(tǒng)介紹圖論與網(wǎng)絡的知識，而著重介紹與LINDO、LINGO軟件有關的組合優(yōu)化模型和相應的求解過程。如果讀者打算深入地了解圖論與網(wǎng)絡的更全面的知識，請參閱圖論或運籌學中的有關書籍.LINDO軟件和LINGO軟件可以求解一些著名的組合
2、優(yōu)化問題，這包括最短路問題、最大流問題、運輸和轉(zhuǎn)運問題、最優(yōu)匹配和最優(yōu)指派問題、最優(yōu)連線或最小生成樹問題、旅行商問題、關鍵路線法與計劃評審方法等。7.1運輸問題與轉(zhuǎn)運問題本節(jié)內(nèi)容導航7.1.1運輸問題7.1.2指派問題7.1.3轉(zhuǎn)運問題§7.1.1運輸問題運輸問題(TransportationProblem)是圖論與網(wǎng)絡中的一個重要問題，也是一個典型的線性規(guī)劃問題.例7.1（運輸問題）返回導航例7.1就是典型的運輸問題，圖7-1給出了個產(chǎn)地，個銷地運輸問題的圖形.關于它的求解方法有兩類，一類是按照圖論的方法求解，另一類是
3、化成線性規(guī)劃問題.這里介紹第二類方法，即用LINDO或LINGO軟件求解運輸問題.但為便于后面的敘述，先給出圖論中有關圖的部分定義.圖7-1:個產(chǎn)地,個銷售地運輸問題的圖形1.圖的基本定義從直觀上看,所謂圖是由點和邊組成的圖形,如圖7-1所示.下面我們給出圖的定義.注：通常有向圖的邊稱為弧，由弧構成的集記為因此，有向圖記為,而無向圖記為.為方便起見，在后面的論述中，有時也用 表示有向圖.在無向圖中,每條至多有一條邊的圖稱為簡單圖(SimpleGraph).若每一對不同的頂點都有一條邊相連的簡單圖稱為完全圖(Compl
4、eteGraph).若一個圖中的頂點集可以分解為兩個子集 和,使得任何一條邊都有一個端點在 中,另一個端點在 中,這種圖稱為二部圖或偶圖(BipartiteGraph).運輸問題所構成的圖7-1是偶圖.2.運輸問題的數(shù)學表達式第 個產(chǎn)地的運出量應小于或等于該地的生產(chǎn)量，即：第 個銷地的運入量應等于該地的需求量，即：因此，運輸問題的數(shù)學表達式為:稱具有形如式的線性規(guī)劃問題為運輸問題.3.運輸問題的求解過程為了便于討論，以一個運輸問題實例的求解過程來介紹如何用LINDO或LINGO軟件求解運輸問題模型.例7.2(繼例7.1)
5、設即為有3個產(chǎn)地和4個銷地的運輸問題，其產(chǎn)量、銷量及單位運費如表7-1所示.試求總運費最少的運輸方案，以及總運費.解：從前面的分析來看，運輸問題屬于線性規(guī)劃問題，因此，不論是LINDO軟件或LINGO軟件都可以對該問題求解.為了便于比較兩種軟件的優(yōu)缺點，以及各自的特點，我們用兩種軟件分別求解該運輸問題.首先寫出LINDO軟件的模型（程序），程序名：exam0702.ltx.!3Warehouse,4CustomerTransportationProblem!Theobjectivemin6x11+2x12+6x13+7x
6、14+4x21+9x22+5x23+3x24+8x31+8x32+x33+5x34subjectto!Thesupplyconstraints2)x11+x12+x13+x14<=303)x21+x22+x23+x24<=254)x31+x32+x33+x34<=21!Thedemandconstraints5)x11+x21+x31=156)x12+x22+x32=177)x13+x23+x33=228)x14+x24+x34=12endLINDO軟件的計算結(jié)果如下：LPOPTIMUMFOUNDATSTEP6OBJEC
7、TIVEFUNCTIONVALUE1)161.0000VARIABLEVALUEREDUCEDCOSTX112.0000000.000000X1217.0000000.000000X131.0000000.000000X140.0000002.000000X2113.0000000.000000X220.0000009.000000X230.0000001.000000X2412.0000000.000000X310.0000007.000000X320.00000011.000000X3321.0000000.0000
8、00X340.0000005.000000ROWSLACKORSURPLUSDUALPRICES2)10.0000000.0000003)0.0000002.0000004)0.0000005.0000005)0.000000-6.0000006)0.000000-2.0000007)0.000000-6.00000
