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