運(yùn)籌學(xué)小論文

1、課程名稱：運(yùn)籌學(xué) 姓名：趙希 學(xué)號：1412020126 運(yùn)輸問題摘要： 運(yùn)輸問題（transportation problem）一般是研究把某種商品從若干個產(chǎn)地運(yùn)至若干個銷地而使總運(yùn)費(fèi)最小的一 類問題。然而從更廣義上講，運(yùn)輸問題是具有一定模型特征的線性規(guī)劃問題。它不僅可以用來求解商品的調(diào)運(yùn)問題，還可以解決諸多非商品調(diào)運(yùn)問題。運(yùn)輸問題是一種特殊的線性規(guī)劃問題，由于其技術(shù)系數(shù)矩陣具有特殊的結(jié)構(gòu)，這就有可能找到比一般單純形法更簡便高效的求解方法，這正是單獨(dú)研究運(yùn)輸問題的目的所在。引言：物流的運(yùn)輸則專指“物”的載運(yùn)及輸送。它是在不同地域范圍間（如兩個城市.兩個工廠之間，或一大企業(yè)內(nèi)相距較遠(yuǎn)的兩車之間

2、），以改變“物”的空間位置為目的的活動，是對“物”進(jìn)行的空間位移。運(yùn)輸一般分為運(yùn)輸和配送。關(guān)于運(yùn)輸和配送的區(qū)分，有許多不同的觀點(diǎn)，可以這樣來說，所有物品的移動都是運(yùn)輸，而配送則專指短距離、小批量的運(yùn)輸。因此，可以說運(yùn)輸是指整體，配送則是指其中的一部分，而且配送的側(cè)重點(diǎn)在于一個''配''字，它的主要意義也體現(xiàn)在''配''字上；而''送''是為最終實(shí)現(xiàn)資源配置的''配''而服務(wù)的。運(yùn)輸功能要素。包括供應(yīng)及銷售物流中的車、船、飛機(jī)等方式的運(yùn)輸，生產(chǎn)物流中的管道、傳送帶等方式

3、的運(yùn)輸。運(yùn)輸是指把人.財.物由一個地方轉(zhuǎn)移到另外一個地方的過程.運(yùn)輸又被認(rèn)為是國民經(jīng)濟(jì)的根本運(yùn)輸?shù)闹饕ぞ哂凶孕熊?板車.三輪車.摩托車.汽車.火車.飛機(jī).輪船.宇宙飛船.火箭.等等運(yùn)輸按服務(wù)對象不同分為客運(yùn)和貨運(yùn)公共運(yùn)輸,泛指所有收費(fèi)提供交通服務(wù)的運(yùn)輸方式。轎車托運(yùn):(轎車運(yùn)輸)是指將汽車做為商品出廠后,通過大型汽車運(yùn)輸工具,到達(dá)指定地方的運(yùn)輸方式</CN>運(yùn)輸運(yùn)價的構(gòu)成發(fā)到基價，運(yùn)行基價構(gòu)成，貨物運(yùn)輸雜費(fèi)零擔(dān)貨物年車運(yùn)價=每噸運(yùn)價×計費(fèi)重量整車貨物每噸運(yùn)價= 發(fā)到基價+運(yùn)行基價×運(yùn)價里程集裝箱貨物每箱運(yùn)價= 發(fā)到基價+運(yùn)行基價×運(yùn)價里程運(yùn)輸問題的數(shù)

4、學(xué)模型某公司經(jīng)營某種產(chǎn)品，該公司下設(shè)A、B、C三個生產(chǎn)廠，甲、乙、丙、丁四個銷售點(diǎn)。公司每天把三個工廠生產(chǎn)的產(chǎn)品分別運(yùn)往四個銷售點(diǎn)，由于各工廠到各銷售點(diǎn)的路程不同，所以單位產(chǎn)品的運(yùn)費(fèi)也就不同案。各工廠每日的產(chǎn)量、各銷售點(diǎn)每日的銷量，以及從各工廠到各銷售點(diǎn)單位產(chǎn)品的運(yùn)價如表4-1所示。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷售點(diǎn)需要的前提下，使總運(yùn)費(fèi)最小。表4-1 甲乙丙丁產(chǎn)量（ai）A3113107B19284C741059銷量（bj）3656 設(shè)代表從第個產(chǎn)地到第個銷地的運(yùn)輸量（；），用代表從第個產(chǎn)地到第個銷地的運(yùn)價，于是可構(gòu)造如下數(shù)學(xué)模型：   （；運(yùn)出的

5、商品總量等于其產(chǎn)量）   （；運(yùn)來的商品總量等于其銷量）通過該引例的數(shù)學(xué)模型，我們可以得出運(yùn)輸問題是一種特殊的線性規(guī)劃問題的結(jié)論，其特殊性就在于技術(shù)系數(shù)矩陣是由“1”和“0”兩個元素構(gòu)成的。將該引例的數(shù)學(xué)模型做一般性推廣，即可得到有個產(chǎn)地、個銷地的運(yùn)輸問題的一般模型。注意：在此僅限于探討總產(chǎn)量等于總銷量的產(chǎn)銷平衡運(yùn)輸問題，而產(chǎn)銷不平衡運(yùn)輸問題將在本章的后續(xù)內(nèi)容中探討。 （；運(yùn)出的商品總量等于其產(chǎn)量） （；運(yùn)來的商品總量等于其銷量）供應(yīng)約束確保從任何一個產(chǎn)地運(yùn)出的商品等于其產(chǎn)量，需求約束保證運(yùn)至任何一個銷地的商品等于其需求。除非負(fù)約束外，運(yùn)輸問題約束條件的

6、個數(shù)是產(chǎn)地與銷地的數(shù)量和，即；而決策變量個數(shù)是二者的積，即。由于在這個約束條件中，隱含著一個總產(chǎn)量等于總銷量的關(guān)系式，所以相互獨(dú)立的約束條件的個數(shù)是個。運(yùn)輸問題的求解：運(yùn)輸問題的求解采用表上作業(yè)法，該方法是單純形法求解運(yùn)輸問題的一種特定形式，其實(shí)質(zhì)是單純形法。既然表上作業(yè)法是一種特定形式的單純形法，它自然與單純形法有著完全相同的解題步驟，所不同的只是完成各步采用的具體形式。表上作業(yè)法的基本步驟可參照單純形法歸納如下：1  找出初始基可行解：即要在階產(chǎn)銷平衡表上給出“”個數(shù)字格（基變量）；2  求各非基變量（空格）的檢驗(yàn)數(shù)，判斷當(dāng)前的基可行解是否是最優(yōu)解，如已得到最優(yōu)解，則停

7、止計算，否則轉(zhuǎn)到下一步；3  確定入基變量，若，那么選取為入基變量；4  確定出基變量，找出入基變量的閉合回路，在閉合回路上最大限度地增加入基變量的值，那么閉合回路上首先減少為“0”的基變量即為出基變量；5  在表上用閉合回路法調(diào)整運(yùn)輸方案；6  重復(fù)2、3、4、5步驟，直到得到最優(yōu)解。 確定初始基可行解與一般的線性規(guī)劃不同，產(chǎn)銷平衡的運(yùn)輸問題一定具有可行解（同時也一定存在最優(yōu)解），這一點(diǎn)是顯然的。確定初始基可行解的方法有很多，下面是最小元素法。最小元素法最小元素法的基本思想是就近供應(yīng)，即從單位運(yùn)價表中最小的運(yùn)價開始確定產(chǎn)銷關(guān)系，依此類推，一直

8、到給出基本方案為止。下面就用例4-1說明最小元素法的應(yīng)用。第一步：從表4-1中找出最小運(yùn)價“1”，這表示先將B生產(chǎn)的產(chǎn)品供應(yīng)給甲。由于B每天生產(chǎn)4個單位產(chǎn)品，甲每天需求3個單位產(chǎn)品，即B每天生產(chǎn)的產(chǎn)品除滿足甲的全部需求外，還可多余1個單位產(chǎn)品。在（B，甲）的交叉格處填上“3”，形成表4-2；將運(yùn)價表的甲列運(yùn)價劃去得表4-3，劃去甲列表明甲的需求已經(jīng)得到滿足。表4-2 甲乙丙丁產(chǎn)量（ai）A    7B3   4C    9銷量（bj）3656 表4-3 甲

9、乙丙丁A311310B1928C74105 第二步：在表4-3的未被劃掉的元素中再找出最小運(yùn)價“2”，最小運(yùn)價所確定的供應(yīng)關(guān)系為（B，丙），即將B余下的1個單位產(chǎn)品供應(yīng)給丙，表4-2轉(zhuǎn)換成表4-4。劃去B行的運(yùn)價，劃去B行表明B所生產(chǎn)的產(chǎn)品已全部運(yùn)出，表4-3轉(zhuǎn)換成表4-5。表4-4 甲乙丙丁產(chǎn)量（ai）A    7B3 1 4C    9銷量（bj）3656  第三步：在表4-5中再找出最小運(yùn)價“3”，這樣一步步地進(jìn)行下去，直到單位運(yùn)價表上的所有元素均被

10、劃去為止。最后在產(chǎn)銷平衡表上得到一個調(diào)運(yùn)方案，見表4-6。這一方案的總運(yùn)費(fèi)為86個單位。表4-5 甲乙丙丁A311310B1928C74105 表4-6 甲乙丙丁產(chǎn)量（ai）A  437B3 1 4C 6 39銷量（bj）3656  最小元素法各步在運(yùn)價表中劃掉的行或列是需求得到滿足的列或產(chǎn)品被調(diào)空的行。一般情況下，每填入一個數(shù)相應(yīng)地劃掉一行或一列，這樣最終將得到一個具有“”個數(shù)字格（基變量）的初始基可行解。然而，問題并非總是如此，有時也會出現(xiàn)這樣的情況：在供需關(guān)系格（）處填入一數(shù)字，

11、剛好使第個產(chǎn)地的產(chǎn)品調(diào)空，同時也使第個銷地的需求得到滿足。按照前述的處理方法，此時需要在運(yùn)價表上相應(yīng)地劃去第行和第列。填入一數(shù)字同時劃去了一行和一列，如果不加入任何補(bǔ)救措施的話，那么最終必然無法得到一個具有“”個數(shù)字格（基變量）的初始基可行解。為了使在產(chǎn)銷平衡表上有“”個數(shù)字格，這時需要在第行或第列此前未被劃掉的任意一個空格上填一個“0”。填“0”格雖然所反映的運(yùn)輸量同空格沒有什么不同；但它所對應(yīng)的變量卻是基變量，而空格所對應(yīng)的變量是非基變量。表4-7 甲乙丙丁產(chǎn)量（ai）A3113104B19284C7410512銷量（bj）3656 將例4-1的各工廠的產(chǎn)量做適當(dāng)調(diào)整（

12、調(diào)整結(jié)果見表4-7），就會出現(xiàn)此類特殊情況。第一步在（B，甲）處填入“3”，劃去甲列運(yùn)價；第二步在（B，丙）處填入“1”，劃去B行運(yùn)價，此二步的結(jié)果見表4-8和表4-9。表4-8 甲乙丙丁產(chǎn)量（ai）A    4B3 1 4C    12銷量（bj）3656 表4-9 甲乙丙丁產(chǎn)量（ai）A3113104B19284C7410512銷量（bj）3656  表4-10 甲乙丙丁產(chǎn)量（ai）A 04 4B3 1

13、 4C    12銷量（bj）3656  表4-11 甲乙丙丁產(chǎn)量（ai）A3113104B19284C7410512銷量（bj）3656  表4-9中剩下的最小元素為“3”，其對應(yīng)產(chǎn)地A的產(chǎn)量是4，銷地丙的剩余需要量也是4，在格（A，丙）中填入“4”，需同時劃去A行和丙列。在填入“4”之前A行和丙列中除了（A，丙）之外，還有（A，乙）、（A，丁）和（C，丙）三個空格未被劃去；因此，可以在（A，乙）、（A，?。┖停–，丙）任選一格填加一個“0”，不妨選擇（A，乙），結(jié)果可見表4-10和表4-11

14、。注意這個“0”是不能填入（A，甲）或（B，丙）的，因?yàn)樵谔钊搿?”之前它們已經(jīng)被劃去了。實(shí)例分析：有三個化肥廠供應(yīng)四個地區(qū)的化肥需求，假定等量化肥在這些地區(qū)的使用效果相同。各化肥廠年產(chǎn)量、各地區(qū)年需要量及從各化肥廠到各地區(qū)運(yùn)送單位化肥的單位運(yùn)價如表38所示，試求出總的運(yùn)費(fèi)最節(jié)省的化肥調(diào)撥方案。表38（單位：萬噸） 地區(qū)1地區(qū)2地區(qū)3地區(qū)4年產(chǎn)量化肥廠A1613221750化肥廠B1413191560化肥廠C192023M50年需要量最低需求3070010 最高需求507030不限 這是一個產(chǎn)銷不平衡的運(yùn)輸問題，總產(chǎn)量為160萬噸，四個地區(qū)的最低需求為110萬噸，

15、最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，除滿足地區(qū)1、地區(qū)2和地區(qū)3的最低需求外，地區(qū)4每年最多能分配到60（）萬噸，這樣其不限的最高需求可等價認(rèn)為是60萬噸。按最高需求分析，總需求為210萬噸，大于總產(chǎn)量160萬噸，將此問題定義為銷大于產(chǎn)的運(yùn)輸問題。為了求得平衡，在產(chǎn)銷平衡表中增加一個假想的化肥廠D，令其年產(chǎn)量為50（）萬噸。各地區(qū)的需要量包含最低和最高兩部分：如地區(qū)1，其中30萬噸是最低需求，故這部分需求不能由假想的化肥廠D來供給，因此相應(yīng)的運(yùn)價定義為任意大正數(shù)M；而另一部分20萬噸滿足與否都是可以的，因此可以由假想化肥廠D來供給，按前面講的，令相應(yīng)運(yùn)價為“0”。凡是需求分兩種情況的地區(qū)，實(shí)際上可按

16、照兩個地區(qū)來看待，這樣可以將表4-38所示的運(yùn)輸問題轉(zhuǎn)換為表39所示的運(yùn)輸問題。表39 （單位：萬噸） 地區(qū)1地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)4年產(chǎn)量化肥廠A16161322171750化肥廠B14141319151560化肥廠C19192023MM50化肥廠DM0M0M050年需要量302070301050  這個問題的最優(yōu)方案，如表40所示。表40 （單位：萬噸） 地區(qū)1地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)4年產(chǎn)量化肥廠A  50   50化肥廠B  20 103060化肥廠C30200   50化肥廠D   30 2