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