運籌學第4章表上作業(yè)法

1、第第4章章 運輸問題運輸問題p第1節(jié) 運輸問題的數(shù)學模型p第2節(jié) 表上作業(yè)法p第3節(jié) 產(chǎn)銷不平衡的運輸問題及其求解方法p第4節(jié) 應用舉例2第1節(jié) 運輸問題的數(shù)學模型v已知有m個生產(chǎn)地點Ai,i=1,2,，m?？晒撤N物資，其供應量(產(chǎn)量)分別為ai，i=1，2，m，有n個銷地Bj，j=1,2,n，其需要量分別為bj，j=1,2,n，從Ai到Bj運輸單位物資的運價(單價)為cij，這些數(shù)據(jù)可匯總于產(chǎn)銷平衡表和單位運價表中，見表3-1，表3-2。有時可把這兩表合二為一。 銷地產(chǎn)地1 2 n產(chǎn)量 12m A 1A2Am銷量B1 B2 BNn 第1節(jié) 運輸問題的數(shù)學模型0)23(, 2 , 1) 1

2、3(, 2 , 1. .min1111ijnjijijmijijminjijijxmiaxnjbxtsxcz4v若用xij表示從Ai到Bj的運量，那么在產(chǎn)銷平衡的條件下，要求得總運費最小的調運方案的數(shù)學模型為第1節(jié) 運輸問題的數(shù)學模型行行nmvvvuuuxxxxxxxxxnmmnmmnn11111111111111111121212122221112115v這就是運輸問題的數(shù)學模型。它包含mn個變量，(m+n)個約束方程，其系數(shù)矩陣的結構比較松散，且特殊。第1節(jié) 運輸問題的數(shù)學模型njminjmiimiijnjijjaxxb1111116該系數(shù)矩陣中對應于變量xij的系數(shù)向量Pij，其分量中除

3、第i個和第m+j個為1以外，其余的都為零。即 Pij=(0, ,1,0,0,1,0,0)T=ei+em+j對產(chǎn)銷平衡的運輸問題，由于有以下關系式存在：第2節(jié) 表上作業(yè)法 表上作業(yè)法是單純形法在求解運輸問題時的一種簡化方法，其實質是單純形法。但具體計算和術語有所不同?？蓺w納為： (1) 找出初始基可行解。即在(mn)產(chǎn)銷平衡表上用西北角法或最小元素法，Vogel法給出m+n-1個數(shù)字，稱為數(shù)字格。它們就是初始基變量的取值。 。 (2) 求各非基變量的檢驗數(shù)，即在表上計算空格的檢驗數(shù)，判別是否達到最優(yōu)解。如已是最優(yōu)解，則停止計算，否則轉到下一步。 (3) 確定換入變量和換出變量，找出新的基可行解。

4、在表上用閉回路法調整。 (4) 重復(2)，(3)直到得到最優(yōu)解為止。 7第2節(jié) 表上作業(yè)法 例例1 某公司經(jīng)銷甲產(chǎn)品。它下設三個加工廠。每日的產(chǎn)量分別是：A1為7噸，A2為4噸，A3為9噸。該公司把這些產(chǎn)品分別運往四個銷售點。各銷售點每日銷量為：B1為3噸，B2為6噸，B3為5噸，B4為6噸。已知從各工廠到各銷售點的單位產(chǎn)品的運價為表3-3所示。問該公司應如何調運產(chǎn)品，在滿足各銷點的需要量的前提下，使總運費為最少。 8第2節(jié) 表上作業(yè)法 解：解：先作出這問題的產(chǎn)銷平衡表和單位運價表，見表3-3，表3-4 銷 地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 7 4 9 銷量 3 6

5、 5 6 9表3-4 產(chǎn)銷平衡表表3-3 單位運價表 2.1 確定初始基可行解minjjidba1110與一般線性規(guī)劃問題不同，產(chǎn)銷平衡的運輸問題總是存在可行解。因有必存在xij0，i=1，m，j=1，n，這就是可行解。又因0 xijmin(aj，bj)，故運輸問題必存在最優(yōu)解。2.1 確定初始基可行解11確定初始基可行解的方法很多，有西北角法，最小元素法和伏格爾(Vogel)法。一般希望的方法是既簡便，又盡可能接近最優(yōu)解。下面介紹兩種方法： 1. 最小元素法基本思想是就近供應，即從單位運價表中最小的運價開始確定供銷關系，然后次小。一直到給出初始基可行解為止。以例1進行討論。第一步：從表3-3

6、中找出最小運價為1，這表示先將A2的產(chǎn)品供應給B1。因a2b1，A2除滿足B1的全部需要外，還可多余1噸產(chǎn)品。在表3-4的(A2，B1)的交叉格處填上3。得表3-5。并將表3-3的B1列運價劃去。得表3-6。2.1 確定初始基可行解12表 3-5 和表3-62.1 確定初始基可行解銷 地 加工廠 B1 B2 B3 B4 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 13第二步：在表3-6未劃去的元素中再找出最小運價2，確定A2多余的1噸供應B3，并給出表3-7，表3-8。2.1 確定初始基可行解銷 地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 3 6 4

7、 1 3 3 7 4 9 銷量 3 6 5 6 14第三步：在表3-8未劃去的元素中再找出最小運價3；這樣一步步地進行下去，直到單位運價表上的所有元素劃去為止，最后在產(chǎn)銷平衡表上得到一個調運方案，見表3-9。這方案的總運費為86元。 2.1 確定初始基可行解15用最小元素法給出的初始解是運輸問題的基可行解，其理由為：v(1) 用最小元素法給出的初始解，是從單位運價表中逐次地挑選最小元素，并比較產(chǎn)量和銷量。當產(chǎn)大于銷，劃去該元素所在列。當產(chǎn)小于銷，劃去該元素所在行。然后在未劃去的元素中再找最小元素，再確定供應關系。這樣在產(chǎn)銷平衡表上每填入一個數(shù)字，在運價表上就劃去一行或一列。表中共有m行n列，總

8、共可劃(n+m)條直線。但當表中只剩一個元素時，這時當在產(chǎn)銷平衡表上填這個數(shù)字時，而在運價表上同時劃去一行和一列。此時把單價表上所有元素都劃去了，相應地在產(chǎn)銷平衡表上填了(m+n-1)個數(shù)字。即給出了(m+n-1)個基變量的值。2.1 確定初始基可行解1111jmijieeP11jix11jiP16用最小元素法給出的初始解是運輸問題的基可行解，其理由為：v(2) 這(m+n-1)個基變量對應的系數(shù)列向量是線性獨立的。證若表中確定的第一個基變量為它對應的系數(shù)列向量為:因當給定 的值后，將劃去第i1行或第j1列，即其后的系數(shù)列向量中再不出現(xiàn)ei1或em+j1，因而 不可能用解中的其他向量的線性組合

9、表示。類似地給出第二個，第(m+n-1)個。這(m+n-1)個向量都不可能用解中的其他向量的線性組合表示。故這(m+n-1)個向量是線性獨立的。 2.1 確定初始基可行解17 用最小元素法給出初始解時，有可能在產(chǎn)銷平衡表上填入一個數(shù)字后，在單位運價表上同時劃去一行和一列。這時就出現(xiàn)退化。關于退化時的處理將在2.4節(jié)中講述。 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1 16A2 10A3 22銷量 814 12 14484285101112346911 821014 86課堂練習課堂練習總費用 z= =104+611+82+23+145+86=24634i=1 j=1cijijx2.1 確定初始基可行解1

10、9 2. 伏格爾法 最小元素法的缺點是：為了節(jié)省一處的費用，有時造成在其他處要多花幾倍的運費。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應，就考慮次小運費，這就有一個差額。差額越大，說明不能按最小運費調運時，運費增加越多。因而對差額最大處，就應當采用最小運費調運。2.1 確定初始基可行解20v伏格爾法的步驟是：v第一步：在表3-3中分別計算出各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行，見表3-10。2.1 確定初始基可行解21v第二步：從行或列差額中選出最大者，選擇它所在行或列中的最小元素。在表3-10中B2列是最大差額所在列。B2列中最小元素為4，可確定A3

11、的產(chǎn)品先供應B2的需要。得表3-112.1 確定初始基可行解銷 地 加工廠 B1 B2 B3 B4 行差額 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 0 1 2 列差額 2 1 3 22v同時將運價表中的B2列數(shù)字劃去。如表3-12所示。2.1 確定初始基可行解23v第三步：對表3-12中未劃去的元素再分別計算出各行、各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。重復第一、二步。直到給出初始解為止。用此法給出例1的初始解列于表3-13。2.1 確定初始基可行解24v由以上可見：伏格爾法同最小元素法除在確定供求關系的原則上不同外，其余步驟相同。伏格爾法給出的初始解比用最小元素法給出的初始解更接近最優(yōu)解。v本例用伏格爾法給出的初始解就是最優(yōu)解。沃格爾法 罰數(shù)=次小費用-最小費用 找出最大的罰數(shù)行或列所對應的最小費用優(yōu)先安排。 重復計算步驟1和2 銷地產(chǎn)地B1B2B3B4