運(yùn)輸規(guī)劃問(wèn)題研究及應(yīng)用

1、運(yùn)籌學(xué)課程設(shè)計(jì)運(yùn)輸規(guī)劃問(wèn)題研究及應(yīng)用院（系）名稱(chēng) 信息工程學(xué)院 專(zhuān) 業(yè) 班 級(jí) * 學(xué) 號(hào) * 學(xué) 生 姓 名 * 指 導(dǎo) 教 師 * 2013 年 06 月 09日課程設(shè)計(jì)任務(wù)書(shū)20122013學(xué)年第二學(xué)期專(zhuān)業(yè)班級(jí)： 10普本信息與計(jì)算科學(xué) 學(xué)號(hào)： * 姓名： * 課程設(shè)計(jì)名稱(chēng)： 運(yùn)籌學(xué) 設(shè)計(jì)題目： 運(yùn)輸規(guī)劃問(wèn)題研究及應(yīng)用 完成期限：自 2013 年 06月 09 日至2013年06 月16日共 7天設(shè)計(jì)依據(jù)、要求及主要內(nèi)容： 一、設(shè)計(jì)目的 熟練掌握運(yùn)輸規(guī)劃問(wèn)題模型,并能理解運(yùn)輸規(guī)劃的概念與理論,能夠較熟練地應(yīng)用lingo軟件編寫(xiě)求解運(yùn)輸規(guī)劃方程的程序和應(yīng)用lingo軟件進(jìn)行案例求解. 二、

2、設(shè)計(jì)內(nèi)容 （1）認(rèn)真挑選有代表性的運(yùn)輸規(guī)劃案例（2）運(yùn)輸規(guī)劃在不同的環(huán)境情況下的模型建立（3）建立的模型對(duì)不同的問(wèn)題進(jìn)行求解分析（4）運(yùn)輸規(guī)劃模型在實(shí)際生活中的擴(kuò)展應(yīng)用. 三、設(shè)計(jì)要求 1先用運(yùn)輸規(guī)劃中的相應(yīng)模型選定案例. 2然后使用所用的案例編寫(xiě)lingo程序求解. 計(jì)劃答辯時(shí)間：2013年 06 月 16 日工作任務(wù)與工作量要求： 查閱文獻(xiàn)資料不少于3篇,課程設(shè)計(jì)報(bào)告1篇不少于3000字指導(dǎo)教師（簽字）： 教研室主任（簽字）： 批準(zhǔn)日期： 2013 年 06 月 09 日 課程設(shè)計(jì)說(shuō)明書(shū)（論文） 第 II頁(yè)運(yùn)輸規(guī)劃問(wèn)題研究及應(yīng)用摘 要 運(yùn)輸問(wèn)題是特殊的線(xiàn)性規(guī)劃問(wèn)題,在運(yùn)籌學(xué)中占有重要地位,

3、而費(fèi)用最小化是經(jīng)常遇到的一個(gè)問(wèn)題.在社會(huì)的經(jīng)濟(jì)生產(chǎn)活動(dòng)中,企業(yè)與客戶(hù)都會(huì)想方設(shè)法合理調(diào)撥資源、降低費(fèi)用,實(shí)現(xiàn)雙方利益最大化,完成資源優(yōu)化配置.本文以使費(fèi)用成本最低為研究對(duì)象,列舉多個(gè)實(shí)際問(wèn)題建立基本運(yùn)輸模型,并針對(duì)不同的模型用Lingo算法解決運(yùn)輸模型中的問(wèn)題. 關(guān)鍵詞：運(yùn)輸規(guī)劃,優(yōu)化配置, Lingo算法 目 錄1 研究背景12 運(yùn)輸規(guī)劃模型的建立12.1 產(chǎn)銷(xiāo)平衡問(wèn)題的模型建立12.2 產(chǎn)銷(xiāo)不平衡問(wèn)題的模型建立22.21 產(chǎn)大于銷(xiāo)的模型建立22.22 產(chǎn)大于銷(xiāo)的模型建立22.3 運(yùn)輸問(wèn)題的特點(diǎn)43 運(yùn)輸規(guī)劃問(wèn)題的實(shí)例分析53.1 運(yùn)輸問(wèn)題53.2 采購(gòu)問(wèn)題84 運(yùn)輸規(guī)劃問(wèn)題的應(yīng)用及前景11

4、總 結(jié)12參考文獻(xiàn)12 課程設(shè)計(jì)說(shuō)明書(shū)（論文） 第 11 頁(yè)1 研究背景運(yùn)輸問(wèn)題是社會(huì)經(jīng)濟(jì)生活和軍事活動(dòng)中經(jīng)常出現(xiàn)的優(yōu)化問(wèn)題,是特殊的線(xiàn)性規(guī)劃問(wèn)題,它是早期的線(xiàn)性網(wǎng)絡(luò)最優(yōu)化的一個(gè)例子.運(yùn)輸問(wèn)題不僅代表了物資合理調(diào)運(yùn)、車(chē)輛合理調(diào)度等問(wèn)題,有些其他類(lèi)型的問(wèn)題經(jīng)過(guò)適當(dāng)變換后也可以歸結(jié)為運(yùn)輸問(wèn)題,如最小費(fèi)用流問(wèn)題、最短路問(wèn)題、指派問(wèn)題可轉(zhuǎn)化為運(yùn)輸問(wèn)題或轉(zhuǎn)運(yùn)問(wèn)題.運(yùn)輸問(wèn)題在運(yùn)籌學(xué)教學(xué)過(guò)程中占有重要地位,并且得到了眾多學(xué)者的廣泛關(guān)注,取得了許多重要的研究成果.但在我們的運(yùn)籌學(xué)教材中僅僅介紹運(yùn)輸問(wèn)題的基礎(chǔ)理論知識(shí),對(duì)于運(yùn)輸中的實(shí)際問(wèn)題及計(jì)算機(jī)的應(yīng)用都沒(méi)有深入介紹.為此,我小組在介紹運(yùn)輸問(wèn)題的基本理論和方法的

5、基礎(chǔ)上,列舉實(shí)例運(yùn)用傳統(tǒng)的表上作業(yè)法和LINGO軟件兩種方法解決問(wèn)題.2 運(yùn)輸規(guī)劃模型的建立一般的運(yùn)輸問(wèn)題就是要解決把某種產(chǎn)品從若干產(chǎn)（供應(yīng)）地調(diào)運(yùn)到若干銷(xiāo)地,在每個(gè)產(chǎn)地的供應(yīng)量與每個(gè)銷(xiāo)地的需求量已知（供銷(xiāo)近似相等）,并知道各地之間的運(yùn)輸單價(jià)的前提下,確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案.2.1 產(chǎn)銷(xiāo)平衡問(wèn)題的模型建立 已知有m個(gè)場(chǎng),其中表示某物資的m個(gè)產(chǎn)地；表示某物質(zhì)的n個(gè)銷(xiāo)地;表示產(chǎn)地的產(chǎn)量；表示銷(xiāo)地的銷(xiāo)量；表示把物資從產(chǎn)地Ai運(yùn)往銷(xiāo)地的單位運(yùn)價(jià).設(shè)為從產(chǎn)地運(yùn)往銷(xiāo)地的運(yùn)輸量,得到下列一般運(yùn)輸量問(wèn)題的模型：其中包含個(gè)變量,個(gè)約束條件,其系數(shù)矩陣是行,列的矩陣,即的系數(shù)向量分量中除第個(gè)和第個(gè)元素

6、為1外,其余都為0.對(duì)于產(chǎn)銷(xiāo)平衡的問(wèn)題有所以模型中最多有個(gè)獨(dú)立的約束方程,即系數(shù)矩陣的秩不超過(guò).2.2 產(chǎn)銷(xiāo)不平衡問(wèn)題的模型建立在實(shí)際生活中許多問(wèn)題都是產(chǎn)銷(xiāo)不平衡的問(wèn)題,即可以產(chǎn)大于銷(xiāo),亦可以銷(xiāo)大于產(chǎn).因此產(chǎn)銷(xiāo)不平衡問(wèn)題可以轉(zhuǎn)化為產(chǎn)銷(xiāo)平衡問(wèn)題來(lái)解決.2.21 產(chǎn)大于銷(xiāo)的模型建立當(dāng)產(chǎn)量大于銷(xiāo)量時(shí)則問(wèn)題模型為此時(shí),要將多余的物資在生產(chǎn)地儲(chǔ)存起來(lái),假設(shè)一虛擬銷(xiāo)售地的運(yùn)費(fèi)為0,即設(shè)表示產(chǎn)地多生產(chǎn)的物資數(shù)量,運(yùn)費(fèi)為,其目標(biāo)函數(shù)不變.于是問(wèn)題的模型變?yōu)榧崔D(zhuǎn)化為產(chǎn)銷(xiāo)平衡的為題了.2.22 產(chǎn)大于銷(xiāo)的模型建立當(dāng)產(chǎn)大于銷(xiāo)時(shí)有則問(wèn)題模型為此時(shí),實(shí)際中即出現(xiàn)了供不應(yīng)求的情況,可假設(shè)有一個(gè)虛擬的產(chǎn)地所缺的物資即設(shè)表示

7、產(chǎn)地多生產(chǎn)的物資數(shù)量,運(yùn)費(fèi)為,其目標(biāo)函數(shù)不變.于是問(wèn)題的模型變?yōu)榧崔D(zhuǎn)化為產(chǎn)銷(xiāo)平衡的為題了.2.3 運(yùn)輸問(wèn)題的特點(diǎn)運(yùn)輸問(wèn)題具有的特點(diǎn)：（1）約束條件系數(shù)矩陣的元素等于0或1；（2）約束條件系數(shù)矩陣的每一列有兩個(gè)非零元素,這對(duì)應(yīng)于每一個(gè)變量在前m個(gè)約束方程中出現(xiàn)一次,在后n個(gè)方程中也出現(xiàn)一次.對(duì)產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題,還有以下特點(diǎn)：（1）所有結(jié)構(gòu)約束條件都是等式約束；（2）各產(chǎn)地產(chǎn)量之和等于各銷(xiāo)地銷(xiāo)量之和.3 運(yùn)輸規(guī)劃問(wèn)題的實(shí)例分析3.1 運(yùn)輸問(wèn)題 重慶有三家電子廠(chǎng)分別是新普,隆宇和恒華,生產(chǎn)的筆記本電腦將要運(yùn)向北京,天津,廣東,上海四個(gè)城市銷(xiāo)售,其產(chǎn)量和銷(xiāo)售量見(jiàn)下表：（單位：萬(wàn)臺(tái)）表：1-1北京天津廣

8、東上海產(chǎn)量新普626730隆宇495325恒華881521銷(xiāo)量15172212-問(wèn)：哪種銷(xiāo)售方案將會(huì)取得最少的運(yùn)輸費(fèi)用,費(fèi)用為多少？針對(duì)該運(yùn)輸問(wèn)題,為了方便計(jì)算,可以設(shè)新普（A1）,隆宇（A2）和恒華（A3）分別銷(xiāo)往北京（B1）、天津（B2）、廣東（B3）和上海（B4）四個(gè)城市銷(xiāo)售量為.建立以下模型：表：1-2B1B2B3B4產(chǎn)量A1626730A2495325A3881521銷(xiāo)量15172212-目標(biāo)（The objective）最少費(fèi)用：約束條件：供應(yīng)限制（The supply constrains） 指標(biāo)約束（The damand constrains） LINGO模型：model:se

9、ts:origin/1.3/:a;sale/1.4/:b;routes(origin,sale):c,x;endsetsdata:a=30,25,21;b=15,17,22,12;c=6,2,6,7,4,9,5,3,8,8,1,5;enddataOBJmin=sum(routes:c*x);for(origin(i):SUPsum(sale(j):x(i,j)<=a(i);for(sale(j):DEMsum(origin(i):x(i,j)=b(j);endlingo結(jié)果： Global optimal solution found. Objective value: 161.0000

10、 Infeasibilities: 0.000000 Total solver iterations: 6 Variable Value Reduced Cost X( 1, 1) 2.000000 0.000000 X( 1, 2) 17.00000 0.000000 X( 1, 3) 1.000000 0.000000 X( 1, 4) 0.000000 2.000000 X( 2, 1) 13.00000 0.000000 X( 2, 2) 0.000000 9.000000 X( 2, 3) 0.000000 1.000000 X( 2, 4) 12.00000 0.000000 X(

11、 3, 1) 0.000000 7.000000 X( 3, 2) 0.000000 11.00000 X( 3, 3) 21.00000 0.000000 X( 3, 4) 0.000000 5.000000 Row Slack or Surplus Dual Price OBJ 161.0000 -1.000000 SUP( 1) 10.00000 0.000000 SUP( 2) 0.000000 2.000000 SUP( 3) 0.000000 5.000000 DEM( 1) 0.000000 -6.000000 DEM( 2) 0.000000 -2.000000 DEM( 3)

12、 0.000000 -6.000000 DEM( 4) 0.000000 -5.000000從計(jì)算結(jié)果可以得出,新普（A1）分別銷(xiāo)往北京（B1）、天津（B2）、廣東（B3）和上海（B4）四個(gè)城市銷(xiāo)售量為分別為2萬(wàn)臺(tái),17萬(wàn)臺(tái),1萬(wàn)臺(tái),0萬(wàn)臺(tái),剩余10萬(wàn)臺(tái)；隆宇（A2）分別銷(xiāo)往北京（B1）、天津（B2）、廣東（B3）和上海（B4）四個(gè)城市銷(xiāo)售量為別為13萬(wàn)臺(tái),0萬(wàn)臺(tái),0萬(wàn)臺(tái),12萬(wàn)臺(tái),剩余0萬(wàn)臺(tái)；恒華（A3）分別銷(xiāo)往北京（B1）、天津（B2）、廣東（B3）和上海（B4）四個(gè)城市銷(xiāo)售量為分別為0萬(wàn)臺(tái),0萬(wàn)臺(tái),21萬(wàn)臺(tái),0萬(wàn)臺(tái),剩余0萬(wàn)臺(tái)；總費(fèi)用為161個(gè)單位.3.2 采購(gòu)問(wèn)題某公司去外地采購(gòu)A、B

13、、C、D四種規(guī)格的商品,數(shù)量分別為：1500個(gè),2000個(gè),3000個(gè),3500個(gè)現(xiàn)有甲、乙、丙三個(gè)城市的供應(yīng)商可以供應(yīng)這些商品,供應(yīng)數(shù)量分別為2500個(gè),2500個(gè),5000個(gè)由于這三個(gè)供應(yīng)商的商品質(zhì)量、運(yùn)價(jià)不同,使銷(xiāo)售情況有差異,預(yù)計(jì)售出后的利潤(rùn)(元個(gè))也不同,詳見(jiàn)表3-5所示請(qǐng)幫助該公司制定一個(gè)預(yù)期盈利最大的采購(gòu)方案表3-5預(yù)計(jì)銷(xiāo)售利潤(rùn)表商品供應(yīng)商 利潤(rùn)/(元/個(gè))ABCD甲10567乙8276丙9348設(shè)表示第i(i=1,2,3)個(gè)城市供應(yīng)第j(j=1,2,3,4)種規(guī)格的產(chǎn)品的數(shù)量.則建立模型如下：s.t. (i=1,2,3;j=1,2,3,4)用lingo編程求解如下：model:

14、sets:demand/1.4/:a;supply/1.3/:b;link(supply,demand):c,x;endsetsdata:a=1500 2000 3000 3500;b=2500 2500 5000;c=10 5 6 78 2 7 69 3 4 8;enddatamin=sum(link:c*x);for(supply(i):sum(demand(j):x(i,j)<=b(i);for(demand(j):sum(supply(i):x(i,j)=a(j);for(link:gin(x);end運(yùn)行結(jié)果如下： Global optimal solution found.

15、Objective value: 53500.00 Extended solver steps: 0 Total solver iterations: 3 Variable Value Reduced Cost A( 1) 1500.000 0.000000 A( 2) 2000.000 0.000000 A( 3) 3000.000 0.000000 A( 4) 3500.000 0.000000 B( 1) 2500.000 0.000000 B( 2) 2500.000 0.000000 B( 3) 5000.000 0.000000 C( 1, 1) 10.00000 0.000000

16、 C( 1, 2) 5.000000 0.000000 C( 1, 3) 6.000000 0.000000 C( 1, 4) 7.000000 0.000000 C( 2, 1) 8.000000 0.000000 C( 2, 2) 2.000000 0.000000 C( 2, 3) 7.000000 0.000000 C( 2, 4) 6.000000 0.000000 C( 3, 1) 9.000000 0.000000 C( 3, 2) 3.000000 0.000000 C( 3, 3) 4.000000 0.000000 C( 3, 4) 8.000000 0.000000 X(

17、 1, 1) 0.000000 10.00000 X( 1, 2) 0.000000 5.000000 X( 1, 3) 0.000000 6.000000 X( 1, 4) 2500.000 7.000000 X( 2, 1) 1500.000 8.000000 X( 2, 2) 0.000000 2.000000 X( 2, 3) 0.000000 7.000000 X( 2, 4) 1000.000 6.000000 X( 3, 1) 0.000000 9.000000 X( 3, 2) 2000.000 3.000000 X( 3, 3) 3000.000 4.000000 X( 3,

18、 4) 0.000000 8.000000 Row Slack or Surplus Dual Price 1 53500.00 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000由以上結(jié)果不難看出分別從甲、乙、丙地采購(gòu)A、B、C、D四種規(guī)格商品的數(shù)量,從甲城市購(gòu)D商品2500個(gè),從乙購(gòu)A商品1500個(gè),D商品1000個(gè),從丙城市購(gòu)B商品2000,C商品3000個(gè)可以使得預(yù)期最佳盈利最大為53500元.4 運(yùn)輸規(guī)劃問(wèn)題的應(yīng)用及前景在社會(huì)、經(jīng)濟(jì)、軍事等領(lǐng)域中,經(jīng)常會(huì)遇到大宗物資的調(diào)運(yùn)問(wèn)題,如煤、鋼鐵、木材、糧食、軍事裝備等,在有若干生產(chǎn)地或存儲(chǔ)地時(shí),則需要根據(jù)已有的交通網(wǎng)制定調(diào)運(yùn)方案,將這些物資運(yùn)到消費(fèi)或使用地,使總的運(yùn)輸費(fèi)用最少或運(yùn)輸路