【正文】 山東交通學(xué)院題目：光明市菜籃子工程問題研究院(系)別 理學(xué)院 專 業(yè) 信息與計(jì)算科學(xué) 班 級 信息081 學(xué) 號 080111125 姓 名 王麗麗 指導(dǎo)教師 張海燕 二○一二年六月 1原 創(chuàng) 聲 明本人王麗麗鄭重聲明：所呈交的論文“光明市菜籃子工程問題研究”，是本人在導(dǎo)師張海燕的指導(dǎo)下開展研究工作所取得的成果。除文中特別加以標(biāo)注和致謝的地方外，論文中不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的研究成果，對本文的研究做出重要貢獻(xiàn)的個人和集體均已在文中以明確方式標(biāo)明，本人完全意識到本聲明的法律后果，尊重知識產(chǎn)權(quán)，并愿為此承擔(dān)一切法律責(zé)任。 論文作者(簽字)： 日期： 年 月 山東交通學(xué)院畢業(yè)設(shè)計(jì)摘 要光明市菜籃子工程問題研究了如何利用現(xiàn)有的交通運(yùn)輸條件制定出一套調(diào)運(yùn)方案，使得預(yù)期的短缺損失以及運(yùn)輸費(fèi)用最省。本文首先介紹了運(yùn)輸問題的線性規(guī)劃模型，以及線性規(guī)劃問題的解法，并且詳細(xì)說明了單純形法的基本思想以及計(jì)算步驟。然后介紹了什么是最短路問題，解決最短路問題的基本思路，狄克斯托算法。最后提出了光明市菜籃子工程問題，問題分析和模型建立，模型求解以及對結(jié)果的分析，最后對模型進(jìn)行優(yōu)化，提出了光明市菜籃子工程問題的改進(jìn)方案。關(guān)鍵字：運(yù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運(yùn)輸問題的線性規(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參考文獻(xiàn) 213 前 言從管理的角度來看，任何一個企業(yè)可供利用的資源（包括人力、物力和財(cái)力等）都是有限的。如何合理的利用和調(diào)配人力、物力，如何充分發(fā)揮現(xiàn)有資金和設(shè)備的能力，不斷提高生產(chǎn)效率，使企業(yè)獲得最大的效益；或者是在既定任務(wù)的條件下，如何統(tǒng)籌安排，盡量做到用最少的人力、物力和財(cái)力資源，去完成這一任務(wù)，這些都是企業(yè)的決策者和管理人員十分關(guān)心的問題。其實(shí)這是一個問題的兩個方面，就是尋求在一定的條件下，使某個指標(biāo)達(dá)到最優(yōu)的問題。這也正是線性規(guī)劃所要研究的問題。本文所要研究的就是線性規(guī)劃問題的運(yùn)輸模型。單純形法是運(yùn)用迭代思想求解線性規(guī)劃問題的一種方法。一般的線性規(guī)劃問題具有線性方程組的變量數(shù)大于方程的個數(shù)，這時(shí)有不定的解，但可以從線性方程組中找出一個個的單純形，每個單純形可以求得一組解，然后再判斷該組解使目標(biāo)函數(shù)值是增大還是變小，決定下一步選擇的單純形。這就是迭代，直到目標(biāo)函數(shù)實(shí)現(xiàn)最大值或最小值為止。許多優(yōu)化問題都可以描繪成圖論中的最短路問題。所謂最短路問題就是尋找賦權(quán)圖中兩點(diǎn)間的最短路，或者說尋找連接這兩點(diǎn)的邊的總長度為最短的通路。最短路問題可以用線性規(guī)劃的方法求解，但是算法很不經(jīng)濟(jì)。求解最短路問題的標(biāo)號法是狄克斯托于1959年提出的，適用于各邊上的權(quán)0的情況，它被公認(rèn)是最有效的算法之一。但是對于的情況，狄克斯托算法就失去了效用。光明市菜籃子工程問題就是一個運(yùn)輸問題。它研究的是在現(xiàn)有的交通條件下，如何制定出一套行之有效的調(diào)度安排，使得運(yùn)輸費(fèi)用及短缺損失最少。在對問題進(jìn)行一系列合理假設(shè)的基礎(chǔ)上，得出該問題的數(shù)學(xué)模型。在求解問題的過程中，用到了上面提到的兩種方法。通過對現(xiàn)有交通網(wǎng)絡(luò)的分析，根據(jù)狄克斯托算法求出收購點(diǎn)到各菜市場的最短路徑。因?yàn)槭褂脝渭冃畏ń鉀Q線性規(guī)劃問題較為繁瑣，本文借助Lingo軟件來求解該問題。在對結(jié)果進(jìn)行分析的基礎(chǔ)上又對上述模型進(jìn)行優(yōu)化，從而得出光明市菜籃子工程的優(yōu)化模型。21 1運(yùn)輸問題的線性規(guī)劃模型 在生產(chǎn)實(shí)踐和日常生活中，經(jīng)常會遇到規(guī)劃問題。所謂規(guī)劃問題，簡單地說，是指如何最合理的利用有限的資源（如資金、勞力、材料、機(jī)器、時(shí)間等），以便使產(chǎn)出的消耗最小，利潤最大。如果利用數(shù)學(xué)方法來進(jìn)行這種分析，這就是數(shù)學(xué)規(guī)劃。當(dāng)所建立的模型，都是線性代數(shù)方程時(shí)，這就是一個線性規(guī)劃問題。這樣的例子在管理和生產(chǎn)的實(shí)踐中是很多的。 運(yùn)輸問題是一類特殊的線性規(guī)劃問題，在國民經(jīng)濟(jì)的各個領(lǐng)域中都存在運(yùn)輸問題。大至國家如何安排全國物資的調(diào)運(yùn)工作，小至一個工廠如何把生產(chǎn)的產(chǎn)品運(yùn)到各個銷售點(diǎn)，都離不開運(yùn)輸?shù)恼{(diào)度安排。那么如何利用現(xiàn)有的交通條件，以最低的運(yùn)費(fèi)安排計(jì)劃，就是一個線性規(guī)劃問題。光明市菜籃子工程問題就是一個運(yùn)輸問題，研究如何利用現(xiàn)有的交通運(yùn)輸條件，使蔬菜由收購點(diǎn)分配到各菜市場的短缺損失以及調(diào)運(yùn)費(fèi)用最小。 運(yùn)輸問題的一般提法是：設(shè)某種物資有m個產(chǎn)地，其產(chǎn)量分別為，另有n個銷地，其銷量分別為。已知由產(chǎn)地（）運(yùn)往銷地的單位運(yùn)價(jià)為，問應(yīng)如何調(diào)運(yùn)，才能使總運(yùn)費(fèi)最?。夸N 地單位運(yùn)價(jià)產(chǎn)地 . . . 產(chǎn)量 . . . . . . . . . . . . . . 原料單價(jià) . . . 地當(dāng)產(chǎn)銷平衡（即）時(shí)，設(shè)表示由產(chǎn)地運(yùn)往銷地的運(yùn)量，則問題的數(shù)學(xué)模型為：求使得當(dāng)產(chǎn)大于銷（即）時(shí)，這一問題的數(shù)學(xué)模型為：求，使得 單純形法是用迭代法求解線性規(guī)劃問題的一種方法。迭代法是一種計(jì)算方法，用這種方法可以產(chǎn)生一系列有次序的點(diǎn)，除初始點(diǎn)以外的每一個點(diǎn)，都是根據(jù)它前面的點(diǎn)計(jì)算出來的。單純形法的基本思想是：從線性規(guī)劃問題的標(biāo)準(zhǔn)型出發(fā)，首先求出一個基本可行解（稱為初始基本可行解），然后按一定的方法迭代到另一個基本可行解，并使基本可行解所對應(yīng)的目標(biāo)函數(shù)值逐步增大。經(jīng)過有限次迭代，當(dāng)目標(biāo)函數(shù)達(dá)