【正文】 （元/100kg）見(jiàn)表。 第二步，產(chǎn)生新的P標(biāo)號(hào)點(diǎn)，其原則如下：在現(xiàn)有的T標(biāo)號(hào)中將值最小者改為P標(biāo)號(hào)。P標(biāo)號(hào)表示從始點(diǎn)到該點(diǎn)的最短路權(quán)，它的值不再改變。322136124237圖 求解最短路問(wèn)題的標(biāo)號(hào)法是 狄克斯托于1959年提出的，適用于各邊上的權(quán)0的情況，它被公認(rèn)是最有效的算法之一。狄克斯托（Dijkstra）標(biāo)號(hào)法是求解最短路問(wèn)題的有效算法之一，他的基本思路是逐點(diǎn)求最短路。（5）以為主元素進(jìn)行迭代（即用高斯消去法或稱為旋轉(zhuǎn)運(yùn)算），把所對(duì)應(yīng)的列向量將列中的換為，得到新的單純性表。否則轉(zhuǎn)入下一步。代數(shù)運(yùn)算形式比較繁瑣，表格形式比較簡(jiǎn)練。迭代法是一種計(jì)算方法，用這種方法可以產(chǎn)生一系列有次序的點(diǎn)，除初始點(diǎn)以外的每一個(gè)點(diǎn)，都是根據(jù)它前面的點(diǎn)計(jì)算出來(lái)的。那么如何利用現(xiàn)有的交通條件，以最低的運(yùn)費(fèi)安排計(jì)劃，就是一個(gè)線性規(guī)劃問(wèn)題。當(dāng)所建立的模型，都是線性代數(shù)方程時(shí)，這就是一個(gè)線性規(guī)劃問(wèn)題。在對(duì)結(jié)果進(jìn)行分析的基礎(chǔ)上又對(duì)上述模型進(jìn)行優(yōu)化，從而得出光明市菜籃子工程的優(yōu)化模型。在對(duì)問(wèn)題進(jìn)行一系列合理假設(shè)的基礎(chǔ)上，得出該問(wèn)題的數(shù)學(xué)模型。求解最短路問(wèn)題的標(biāo)號(hào)法是狄克斯托于1959年提出的，適用于各邊上的權(quán)0的情況，它被公認(rèn)是最有效的算法之一。這就是迭代，直到目標(biāo)函數(shù)實(shí)現(xiàn)最大值或最小值為止。這也正是線性規(guī)劃所要研究的問(wèn)題。最后提出了光明市菜籃子工程問(wèn)題，問(wèn)題分析和模型建立，模型求解以及對(duì)結(jié)果的分析，最后對(duì)模型進(jìn)行優(yōu)化，提出了光明市菜籃子工程問(wèn)題的改進(jìn)方案。除文中特別加以標(biāo)注和致謝的地方外，論文中不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫過(guò)的研究成果，對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體均已在文中以明確方式標(biāo)明，本人完全意識(shí)到本聲明的法律后果，尊重知識(shí)產(chǎn)權(quán)，并愿為此承擔(dān)一切法律責(zé)任。 論文作者(簽字)： 日期： 年 月 山東交通學(xué)院畢業(yè)設(shè)計(jì)摘 要光明市菜籃子工程問(wèn)題研究了如何利用現(xiàn)有的交通運(yùn)輸條件制定出一套調(diào)運(yùn)方案，使得預(yù)期的短缺損失以及運(yùn)輸費(fèi)用最省。關(guān)鍵字：運(yùn)輸問(wèn)題，線性規(guī)劃，單純形法，最短路問(wèn)題AbstractBright city vegetable basket project problem on how to use the existing traffic conditions to develop a scheduling scheme, the expected loss and shortage of transport cost the paper introduces the linear programming model of transportation problem, and the solution of linear programming problem, and explains in detail the simplex method the basic idea and putational describes what is the shortest path problem, to solve the shortest path problem of the basic ideas, Dix supporting , the bright city vegetable basket project problem, problem analysis and model building, model and the analysis of the results, and finally to optimize the model, put forward the bright city vegetable basket project of improvement scheme.Key words: Transportation problem，Linear programming, Simplex method, The shortest path problem 目 錄前 言 11運(yùn)輸問(wèn)題的線性規(guī)劃模型 2 2 3 3 42最短路問(wèn)題 5 5 5 5 53光明市菜籃子工程問(wèn)題 7 7 8 9 124 光明市菜籃子工程問(wèn)題的優(yōu)化模型 14 14 14 16 16 17 18致 謝 20參考文獻(xiàn) 213 前 言從管理的角度來(lái)看，任何一個(gè)企業(yè)可供利用的資源（包括人力、物力和財(cái)力等）都是有限的。本文所要研究的就是線性規(guī)劃問(wèn)題的運(yùn)輸模型。許多優(yōu)化問(wèn)題都可以描繪成圖論中的最短路問(wèn)題。但是對(duì)于的情況，狄克斯托算法就失去了效用。在求解問(wèn)題的過(guò)程中，用到了上面提到的兩種方法。21 1運(yùn)輸問(wèn)題的線性規(guī)劃模型 在生產(chǎn)實(shí)踐和日常生活中，經(jīng)常會(huì)遇到規(guī)劃問(wèn)題。這樣的例子在管理和生產(chǎn)的實(shí)踐中是很多的。光明市菜籃子工程問(wèn)題就是一個(gè)運(yùn)輸問(wèn)題，研究如何利用現(xiàn)有的交通運(yùn)輸條件，使蔬菜由收購(gòu)點(diǎn)分配到各菜市場(chǎng)的短缺損失以及調(diào)運(yùn)費(fèi)用最小。單純形法的基本思想是：從線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型出發(fā)，首先求出一個(gè)基本可行解（稱為初始基本可行解），然后按一定的方法迭代到另一個(gè)基本可行解，并使基本可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值逐步增大。但是，代數(shù)運(yùn)算形式能詳細(xì)的說(shuō)明單純形法的迭代過(guò)程。（3）在中，若有某個(gè)對(duì)應(yīng)的系數(shù)列向量，則此問(wèn)題是無(wú)界，停止計(jì)算。重復(fù)（2）～（5），直到終止。如果，是從的最短路，那么由點(diǎn)出發(fā)沿這條最短路到達(dá)中間的任何一點(diǎn)，也是從點(diǎn)到達(dá)該任意點(diǎn)的最短路。 標(biāo)號(hào)法是通過(guò)對(duì)圖上各點(diǎn)進(jìn)行標(biāo)號(hào)來(lái)尋求最短路的方法。標(biāo)號(hào)過(guò)程分兩步： 第一步，修改T標(biāo)號(hào)。 重復(fù)以上步驟直到終點(diǎn)的T標(biāo)號(hào)改為P標(biāo)號(hào)為止。設(shè)從收購(gòu)點(diǎn)至各菜市場(chǎng)蔬菜調(diào)運(yùn)費(fèi)用為1元/（100kg*100m）。（3）假設(shè)各市場(chǎng)蔬菜只來(lái)源于三個(gè)收購(gòu)站，而無(wú)其他來(lái)源。C(j)代表菜市場(chǎng)j的短缺損失；d(i)代表收購(gòu)點(diǎn)i每天的蔬菜收購(gòu)量。為了敘述方便，現(xiàn)把收購(gòu)點(diǎn)A記為，菜市場(chǎng)1,2，…，8依次記為。 T()=min[T(),P()+]=min[,0+8]=8。 20 19 11 14 6 15 5 10)適當(dāng)改變符號(hào)x(i,j)為：x(1,j)記為xj,x(2,j)記為yj,x(3,j)記為zj，那么各菜市場(chǎng)的短缺量分別為 （75x1y1z1）、（60x2y2z2）、（80x3y3z3）、（70x4y4z4）、（100x5y5z5）、（55x6y6z6）、（90x7y7z7）、（80x8y8z8），那么短缺損失為 10（75x1y1z1）+8（60x2y2z2）+5（80x3y3z3）+10（70x4y4z4）+10（100x5y5z5）+8（55x6y6z6）+5（90x7y7z7）+8（80x8y8z8），運(yùn)費(fèi)為4x1+8x2+8x3+19x4+11x5+6x6+22x7+20x8+14y1+7y2+7y3+16y4+12y5+16y6+23y7+17y8+20z1+19z2+11z3+14z4+6z5+15z6+5z7+10z8，那么總費(fèi)用即為Z=6x1+3x3+9x4+x52x6+17x7+12x8+4y1y2+2y3+6y4+2y5+8y6+18y7+9y8+10z1+11z2+6z3+4z44z5+7z6+2z8+4860,約束條件表示為 這是一個(gè)線性規(guī)劃模型，由于變量數(shù)較多，用單純形法求解較為繁瑣，現(xiàn)在應(yīng)用LINGO軟件求解，在運(yùn)行窗口中輸入以下內(nèi)容：min=6*x1+3*x3+9*x4+x52*x6+17*x7+12*x8+4*y1y2+2*y3+6*y4+2*y5+8*y6+18*y7+9*y8+10*z1+11*z2+6*z3+4*z44*z5+7*z6+2*z8+4860。 x1+y1+z1=75。 x5+y5+z5=100。運(yùn)行結(jié)果為： Global optimal solution found.