【正文】 ,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)在應(yīng)用LINGO軟件求解，在運行窗口中輸入以下內(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。（2）在現(xiàn)有的T標(biāo)號中，將最小的T標(biāo)號改為P標(biāo)號，即=4；此為第一次迭代的結(jié)果，然后再考察以點為始點的弧，按照第一次迭代的方法，由此求得 A(i,j)=(4 8 8 19 11 6 22 20。 T()=min[T(),P()+]=min[,0+8]=8。因均為T標(biāo)號點，所以修改這四點的T標(biāo)號如下 T()=min[T(),P()+]=min[,0+4]=4。為了敘述方便，現(xiàn)把收購點A記為，菜市場1,2，…，8依次記為。目標(biāo)函數(shù)總費用Z來表示,總費用包括兩部分: 蔬菜調(diào)運費P，各市場供給量小于需求量的短缺損失Q，即：Z=P+Q其中P=；市場j的短缺量為；則 Q=，所以目標(biāo)函數(shù)為 約束條件為： （1）從收購點i運送到菜市場j的蔬菜量小于等于收購點i的收購數(shù)量，即 （2）從收購點i運送到菜市場j的蔬菜量小于等于菜市場j的需求數(shù)量，即 （3）變量非負性限制。C(j)代表菜市場j的短缺損失；d(i)代表收購點i每天的蔬菜收購量。（5）假設(shè)各收購站可以作為中轉(zhuǎn)站。（3）假設(shè)各市場蔬菜只來源于三個收購站，而無其他來源。對于該問題，為了研究以及求解的方便，做出如下的基本假設(shè)和符號說明：基本假設(shè)：（1）只考慮運輸費用和短缺費用，不考慮裝卸等其他費用。設(shè)從收購點至各菜市場蔬菜調(diào)運費用為1元/（100kg*100m）。清晨5點前菜農(nóng)將蔬菜送至各收購點，再由各收購點分送到全市的8個菜市場。 重復(fù)以上步驟直到終點的T標(biāo)號改為P標(biāo)號為止。如果是P標(biāo)號法，則對點不再進行標(biāo)號；如果點是T標(biāo)號點，則進行如下的修改 其中，方括號內(nèi)的代表點舊的T標(biāo)號值。標(biāo)號過程分兩步： 第一步，修改T標(biāo)號。T標(biāo)號表示從始點到該點最短路的上界，根據(jù)到該點路線的不同它有可能變化。 標(biāo)號法是通過對圖上各點進行標(biāo)號來尋求最短路的方法。因此，從起點開始逐點尋找到鄰近點的最短路，直到將最短路延伸到指定的中點為止，就自然找到了從起點到中點的最短路。如果，是從的最短路，那么由點出發(fā)沿這條最短路到達中間的任何一點，也是從點到達該任意點的最短路。 所謂最短路問題就是尋找賦權(quán)圖中兩點間的最短路，或者說尋找連接這兩點的邊的總長度為最小的通路。重復(fù)（2）～（5），直到終止。（4）根據(jù)，確定為換入變量，按規(guī)則計算 可確定為換出變量，轉(zhuǎn)入下一步。（3）在中，若有某個對應(yīng)的系數(shù)列向量，則此問題是無界，停止計算。（2）檢驗各非基變量的檢驗數(shù)是 則已得到最優(yōu)解，可停止計算。但是，代數(shù)運算形式能詳細的說明單純形法的迭代過程。上述的迭代過程，可以用代數(shù)運算形式或表格形式來進行。單純形法的基本思想是：從線性規(guī)劃問題的標(biāo)準型出發(fā)，首先求出一個基本可行解（稱為初始基本可行解），然后按一定的方法迭代到另一個基本可行解，并使基本可行解所對應(yīng)的目標(biāo)函數(shù)值逐步增大。已知由產(chǎn)地（）運往銷地的單位運價為，問應(yīng)如何調(diào)運，才能使總運費最省？銷 地單位運價產(chǎn)地 . . . 產(chǎn)量 . . . . . . . . . . . . . . 原料單價 . . . 地當(dāng)產(chǎn)銷平衡（即）時，設(shè)表示由產(chǎn)地運往銷地的運量，則問題的數(shù)學(xué)模型為：求使得當(dāng)產(chǎn)大于銷（即）時，這一問題的數(shù)學(xué)模型為：求，使得 單純形法是用迭代法求解線性規(guī)劃問題的一種方法。光明市菜籃子工程問題就是一個運輸問題，研究如何利用現(xiàn)有的交通運輸條件，使蔬菜由收購點分配到各菜市場的短缺損失以及調(diào)運費用最小。大至國家如何安排全國物資的調(diào)運工作，小至一個工廠如何把生產(chǎn)的產(chǎn)品運到各個銷售點，都離不開運輸?shù)恼{(diào)度安排。這樣的例子在管理和生產(chǎn)的實踐中是很多的。如果利用數(shù)學(xué)方法來進行這種分析，這就是數(shù)學(xué)規(guī)劃。21 1運輸問題的線性規(guī)劃模型 在生產(chǎn)實踐和日常生活中，經(jīng)常會遇到規(guī)劃問題。因為使用單純形法解決線性規(guī)劃問題較為繁瑣，本文借助Lingo軟件來求解該問題。在求解問題的過程中，用到了上面提到的兩種方法。它研究的是在現(xiàn)有的交通條件下，如何制定出一套行之有效的調(diào)度安排，使得運輸費用及短缺損失最少。但是對于的情況，狄克斯托算法就失去了效用。最短路問題可以用線性規(guī)劃的方法求解，但是算法很不經(jīng)濟。許多優(yōu)化問題都可以描繪成圖論中的最短路問題。一般的線性規(guī)劃問題具有線性方程組的變量數(shù)大于方程的個數(shù)，這時有不定的解，但可以從線性方程組中找出一個個的單純形，每個單純形可以求得一組解，然后再判斷該組解使目標(biāo)函數(shù)值是增大還是變小，決定下一步選擇的單純形。本文所要研究的就是線性規(guī)劃問題的運輸模型。其實這是一個問題的兩個方面，就是尋求在一定的條件下，使某個指標(biāo)達到最優(yōu)的問題。關(guā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