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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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