運籌學(xué)小論文

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

2、），以改變“物”的空間位置為目的的活動，是對“物”進行的空間位移。運輸一般分為運輸和配送。關(guān)于運輸和配送的區(qū)分，有許多不同的觀點，可以這樣來說，所有物品的移動都是運輸，而配送則專指短距離、小批量的運輸。因此，可以說運輸是指整體，配送則是指其中的一部分，而且配送的側(cè)重點在于一個配字，它的主要意義也體現(xiàn)在配字上；而送是為最終實現(xiàn)資源配置的配而服務(wù)的。運輸功能要素。包括供應(yīng)及銷售物流中的車、船、飛機等方式的運輸，生產(chǎn)物流中的管道、傳送帶等方式的運輸。運輸是指把人.財.物由一個地方轉(zhuǎn)移到另外一個地方的過程.運輸又被認為是國民經(jīng)濟的根本運輸?shù)闹饕ぞ哂凶孕熊?板車.三輪車.摩托車.汽車.火車.飛機.輪船

3、.宇宙飛船.火箭.等等運輸按服務(wù)對象不同分為客運和貨運公共運輸,泛指所有收費提供交通服務(wù)的運輸方式。轎車托運:(轎車運輸)是指將汽車做為商品出廠后,通過大型汽車運輸工具,到達指定地方的運輸方式運輸運價的構(gòu)成發(fā)到基價，運行基價構(gòu)成，貨物運輸雜費零擔(dān)貨物年車運價=每噸運價計費重量整車貨物每噸運價= 發(fā)到基價+運行基價運價里程集裝箱貨物每箱運價= 發(fā)到基價+運行基價運價里程運輸問題的數(shù)學(xué)模型某公司經(jīng)營某種產(chǎn)品，該公司下設(shè)A、B、C三個生產(chǎn)廠，甲、乙、丙、丁四個銷售點。公司每天把三個工廠生產(chǎn)的產(chǎn)品分別運往四個銷售點，由于各工廠到各銷售點的路程不同，所以單位產(chǎn)品的運費也就不同案。各工廠每日的產(chǎn)量、各銷售

4、點每日的銷量，以及從各工廠到各銷售點單位產(chǎn)品的運價如表4-1所示。問該公司應(yīng)如何調(diào)運產(chǎn)品，在滿足各銷售點需要的前提下，使總運費最小。表4-1甲乙丙丁產(chǎn)量（ai）A3113107B19284C741059銷量（bj）3656設(shè)代表從第個產(chǎn)地到第個銷地的運輸量（；），用代表從第個產(chǎn)地到第個銷地的運價，于是可構(gòu)造如下數(shù)學(xué)模型： （；運出的商品總量等于其產(chǎn)量） （；運來的商品總量等于其銷量）通過該引例的數(shù)學(xué)模型，我們可以得出運輸問題是一種特殊的線性規(guī)劃問題的結(jié)論，其特殊性就在于技術(shù)系數(shù)矩陣是由“1”和“0”兩個元素構(gòu)成的。將該引例的數(shù)學(xué)模型做一般性推廣，即可得到有個產(chǎn)地、個銷地的運輸問題的一般模型。注

5、意：在此僅限于探討總產(chǎn)量等于總銷量的產(chǎn)銷平衡運輸問題，而產(chǎn)銷不平衡運輸問題將在本章的后續(xù)內(nèi)容中探討。（；運出的商品總量等于其產(chǎn)量）（；運來的商品總量等于其銷量）供應(yīng)約束確保從任何一個產(chǎn)地運出的商品等于其產(chǎn)量，需求約束保證運至任何一個銷地的商品等于其需求。除非負約束外，運輸問題約束條件的個數(shù)是產(chǎn)地與銷地的數(shù)量和，即；而決策變量個數(shù)是二者的積，即。由于在這個約束條件中，隱含著一個總產(chǎn)量等于總銷量的關(guān)系式，所以相互獨立的約束條件的個數(shù)是個。運輸問題的求解：運輸問題的求解采用表上作業(yè)法，該方法是單純形法求解運輸問題的一種特定形式，其實質(zhì)是單純形法。既然表上作業(yè)法是一種特定形式的單純形法，它自然與單純形

6、法有著完全相同的解題步驟，所不同的只是完成各步采用的具體形式。表上作業(yè)法的基本步驟可參照單純形法歸納如下：1 找出初始基可行解：即要在階產(chǎn)銷平衡表上給出“”個數(shù)字格（基變量）；2 求各非基變量（空格）的檢驗數(shù)，判斷當(dāng)前的基可行解是否是最優(yōu)解，如已得到最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一步；3 確定入基變量，若，那么選取為入基變量；4 確定出基變量，找出入基變量的閉合回路，在閉合回路上最大限度地增加入基變量的值，那么閉合回路上首先減少為“0”的基變量即為出基變量；5 在表上用閉合回路法調(diào)整運輸方案；6 重復(fù)2、3、4、5步驟，直到得到最優(yōu)解。確定初始基可行解與一般的線性規(guī)劃不同，產(chǎn)銷平衡的運輸問題一

7、定具有可行解（同時也一定存在最優(yōu)解），這一點是顯然的。確定初始基可行解的方法有很多，下面是最小元素法。最小元素法最小元素法的基本思想是就近供應(yīng)，即從單位運價表中最小的運價開始確定產(chǎn)銷關(guān)系，依此類推，一直到給出基本方案為止。下面就用例4-1說明最小元素法的應(yīng)用。第一步：從表4-1中找出最小運價“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；將運價表的甲列運價劃去得表4-3，劃去甲列表明甲的需求已經(jīng)得到滿足。表4-2甲乙丙丁產(chǎn)量（ai）A7B34

8、C9銷量（bj）3656表4-3甲乙丙丁A311310B1928C74105第二步：在表4-3的未被劃掉的元素中再找出最小運價“2”，最小運價所確定的供應(yīng)關(guān)系為（B，丙），即將B余下的1個單位產(chǎn)品供應(yīng)給丙，表4-2轉(zhuǎn)換成表4-4。劃去B行的運價，劃去B行表明B所生產(chǎn)的產(chǎn)品已全部運出，表4-3轉(zhuǎn)換成表4-5。表4-4甲乙丙丁產(chǎn)量（ai）A7B314C9銷量（bj）3656第三步：在表4-5中再找出最小運價“3”，這樣一步步地進行下去，直到單位運價表上的所有元素均被劃去為止。最后在產(chǎn)銷平衡表上得到一個調(diào)運方案，見表4-6。這一方案的總運費為86個單位。表4-5甲乙丙丁A311310B1928C74

9、105表4-6甲乙丙丁產(chǎn)量（ai）A437B314C639銷量（bj）3656最小元素法各步在運價表中劃掉的行或列是需求得到滿足的列或產(chǎn)品被調(diào)空的行。一般情況下，每填入一個數(shù)相應(yīng)地劃掉一行或一列，這樣最終將得到一個具有“”個數(shù)字格（基變量）的初始基可行解。然而，問題并非總是如此，有時也會出現(xiàn)這樣的情況：在供需關(guān)系格（）處填入一數(shù)字，剛好使第個產(chǎn)地的產(chǎn)品調(diào)空，同時也使第個銷地的需求得到滿足。按照前述的處理方法，此時需要在運價表上相應(yīng)地劃去第行和第列。填入一數(shù)字同時劃去了一行和一列，如果不加入任何補救措施的話，那么最終必然無法得到一個具有“”個數(shù)字格（基變量）的初始基可行解。為了使在產(chǎn)銷平衡表上有

10、“”個數(shù)字格，這時需要在第行或第列此前未被劃掉的任意一個空格上填一個“0”。填“0”格雖然所反映的運輸量同空格沒有什么不同；但它所對應(yīng)的變量卻是基變量，而空格所對應(yīng)的變量是非基變量。表4-7甲乙丙丁產(chǎn)量（ai）A3113104B19284C7410512銷量（bj）3656將例4-1的各工廠的產(chǎn)量做適當(dāng)調(diào)整（調(diào)整結(jié)果見表4-7），就會出現(xiàn)此類特殊情況。第一步在（B，甲）處填入“3”，劃去甲列運價；第二步在（B，丙）處填入“1”，劃去B行運價，此二步的結(jié)果見表4-8和表4-9。表4-8甲乙丙丁產(chǎn)量（ai）A4B314C12銷量（bj）3656表4-9甲乙丙丁產(chǎn)量（ai）A3113104B1928

11、4C7410512銷量（bj）3656表4-10甲乙丙丁產(chǎn)量（ai）A044B314C12銷量（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，?。┖停–，丙）三個空格未被劃去；因此，可以在（A，乙）、（A，?。┖停–，丙）任選一格填加一個“0”，不妨選擇（A，乙），結(jié)果可見表4-10和表4-11。注意這個“0”是不能填入（A，甲）或

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

13、區(qū)4每年最多能分配到60（）萬噸，這樣其不限的最高需求可等價認為是60萬噸。按最高需求分析，總需求為210萬噸，大于總產(chǎn)量160萬噸，將此問題定義為銷大于產(chǎn)的運輸問題。為了求得平衡，在產(chǎn)銷平衡表中增加一個假想的化肥廠D，令其年產(chǎn)量為50（）萬噸。各地區(qū)的需要量包含最低和最高兩部分：如地區(qū)1，其中30萬噸是最低需求，故這部分需求不能由假想的化肥廠D來供給，因此相應(yīng)的運價定義為任意大正數(shù)M；而另一部分20萬噸滿足與否都是可以的，因此可以由假想化肥廠D來供給，按前面講的，令相應(yīng)運價為“0”。凡是需求分兩種情況的地區(qū)，實際上可按照兩個地區(qū)來看待，這樣可以將表4-38所示的運輸問題轉(zhuǎn)換為表39所示的運輸問題。表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)量化肥廠A5050化肥廠B20103060化肥廠C3020050化肥廠D302050年需要量302070301050結(jié)論：運輸問題（trans