貨物運輸與包裝的表上作業(yè)求解方法

1、 運輸問題的求解方法運輸問題的求解方法表上作業(yè)法表上作業(yè)法產(chǎn)銷平衡表與單位運價表產(chǎn)銷平衡表與單位運價表 表上作業(yè)法表上作業(yè)法產(chǎn)銷不平衡的運輸問題的求解方法產(chǎn)銷不平衡的運輸問題的求解方法一、產(chǎn)銷平衡表與單位運價表一、產(chǎn)銷平衡表與單位運價表 運輸問題還可用產(chǎn)銷平衡表與單位運價表進(jìn)行描述。 假設(shè)某種物資有m個生產(chǎn)地點Ai（i=1，2，m），其產(chǎn)量（供應(yīng)量）分別為ai（i=1，2，m），有n個銷地Bj（j=1，2，n），其銷量（需求量）分別為bj（j=1，2，n）。從Ai到Bj運輸單位物資的運價（單價）為Cij。將這些數(shù)據(jù)匯總可以得到產(chǎn)銷平衡表和單位運價表5.3.1。銷地產(chǎn)地產(chǎn)量銷量n21表5.3.1

2、 產(chǎn)銷平衡表與單位運價表mnmmnnccccccccc212222111211m21maaa21 運輸這一類特殊問題可用更加簡便的求解方法表上作業(yè)法求解，實質(zhì)仍是單純形法，步驟如下： （1）確定初始調(diào)運方案，即找出初始基可行解,在產(chǎn)銷平衡表上給出m+n-1個數(shù)字格。 二、表上作業(yè)法二、表上作業(yè)法 （2）求非基變量的檢驗數(shù)，即在表上計算空格的檢驗數(shù)，判別是否達(dá)到最優(yōu)解：是否存在負(fù)的檢驗數(shù)？如果存在負(fù)的檢驗數(shù)，則初始調(diào)運方案不是最優(yōu)方案；如果所有檢驗數(shù)都非負(fù)，則初始調(diào)運方案已經(jīng)是最優(yōu)方案了。如果已經(jīng)得到最優(yōu)調(diào)運方案，則停止計算，否則轉(zhuǎn)入下一步。 （3）確定換入變量和換出變量，找出新的調(diào)運方案（新的

3、基可行解），即在表上用閉回路法進(jìn)行調(diào)整。 (4）重復(fù)（1）（2），直到求出最優(yōu)解為止。 （一）（一）確定初始可行基的方法確定初始可行基的方法n最小元素法最小元素法 從單位運價表中最小的運價開始確定供銷關(guān)系，然后考慮運價次小的，一直到給出初始基可行解為止。n伏格爾法伏格爾法 采用最小元素法可能造成其他處的更多浪費，伏格爾法考慮最小運費與次小運費之間的差額，差額越大，就按次小運費調(diào)運。 （二）（二）最優(yōu)解的判別最優(yōu)解的判別 計算非基變量（空格）的檢驗數(shù),當(dāng)所有的檢驗數(shù) 時，為最優(yōu)解。 求空格檢驗數(shù)的方法有：n閉回路法閉回路法 以某一空格為起點找一條閉回路，用水平或垂直線向前劃，每碰到一數(shù)字格轉(zhuǎn)90

4、0后，繼續(xù)前進(jìn)，直到回到起始空格為止。01ijBijPBCc 閉回路如圖5.3.1的（a）、（b）、（c）等所示。從每一個空格出發(fā)一定存在并且可以找到唯一的閉回路。因為，m+n-1個數(shù)字格（基變量）對應(yīng)的系數(shù)向量是一個基，任一空格（非基變量）對應(yīng)的系數(shù)向量是這個基的線性組合。圖5.3.1 閉回路示意圖 ujuslslkikjmusmusmlkmlkmijmuusmsmllkmkmijmiijPPPPPeeeeeeeeeeeeeeeeeeeeeeP)()()()()(BPPPPPujuslslkik, 舉例說明： 可表示為),(NjiPij而這些向量構(gòu)成了閉回路見圖 n位勢法位勢法 一種較為簡便

5、的求檢驗數(shù)的方法。 設(shè) 是對應(yīng)運輸問題的m+n個約束條件的對偶變量。B是含有一個人工變量Xa的初始基矩陣。 Xa在目標(biāo)函數(shù)中的系數(shù)Ca ，由線性規(guī)劃的對偶理論可知 而每一個決策變量Xij的系數(shù)向量 ，所以 由單純形法可知，所有基變量的檢驗數(shù)等于0，即nmvvvuuu,;,212, 1,;,21211nvvvmuuuBBCjmiijeeP)(1jiijijBijijvucPBCc),(0)(Bjivucjiij例1：假設(shè)某種物資共有3個產(chǎn)地，其日產(chǎn)量分別是：A1為7 t， A2為4 t， A3為9 t；該種物資的4個銷售地，其日銷量分別： B1為3 t， B2為6 t， B3為5 t， B4為6

6、 t；各產(chǎn)地到銷售地的單位物資的運價如表5.3.2所示。在滿足各銷售點需要量的前提下，如何調(diào)運該種物資，才能使總運費達(dá)到最?。夸N地產(chǎn)地B1B2B3B4A1A2A3317119432101085表5.3.2下面用具體例子說明表上作業(yè)法的計算步驟。解：首先列出這一問題的產(chǎn)銷平衡表，見表5.3.3。 表表5.3.3 某物資運輸?shù)漠a(chǎn)銷平衡表某物資運輸?shù)漠a(chǎn)銷平衡表 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3749銷量3656表表5.3.3 用最小元素法求解： 第1步，從表5.3.4中找出最小運價為1，表示應(yīng)先將A2 的產(chǎn)品供應(yīng) B1 。在表5.3.3中（ A2 B1 ）的交叉格處填上3，得表5.3.4。將

7、表5.3.4中的B1 列運價劃去，得表5.3.5。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A33749銷量3656表5.3.4銷地產(chǎn)地B1B2B3B4A1A2A3119432101085表5.3.5 第2步，在表5.3.5未劃去的元素中再找出最小運價為2，確定A2多余的1 t物資供應(yīng)B3 。得表5.3.6。將表5.3.5的行運價劃去，得表5.3.7。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A331749銷量3656表5.3.6銷地產(chǎn)地B1B2B3B4A1A2A3119432101085表5.3.7 第3步 ，按照上述方法直到單位運價表上的所有元素被劃去為止。最后在產(chǎn)銷平衡表上得到一個調(diào)運方案，即初始基

8、可行解，見表5.3.8。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A331749銷量3656表5.3.8 伏格爾法的步驟是： 第1步：在表5.3.2中分別計算出各行、各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行，見表5.3.9。銷地產(chǎn)地B1B2B3B4行差額 A1A2A3317119432101085011列差額 2513表5.3.9 第2步：從行或列差額中選出最大者，選擇它所在行或列中的最小元素。在表5.3.9中，可確定A3的產(chǎn)品應(yīng)首先供應(yīng)B2，得表5.3. 10。將單位運價表中的列的數(shù)字劃去，得表5.3.11。表5.3.10銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A36749銷量36

9、56銷地產(chǎn)地B1B2B3B4A1A2A331732101085表5.3.11 第3步,對表5.3.11中余下的元素再分別計算出各行、各列的最小運費和次最小運費的差額，重復(fù)第1、第2步，直到給出初始基可行解為止。初始基可行解列于表5.3.12。表5.3.12銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3365213749銷量3656 伏格爾法給出的初始基可行解更接近最優(yōu)解。本例中用伏格爾法給出的初始基可行解就是最優(yōu)解。 用閉回路法判別檢驗：閉回路法計算檢驗數(shù)的經(jīng)濟(jì)解釋為,在已給出初始基可行解的表中，可從任一空格出發(fā)，如（A1, B1），若讓A1的產(chǎn)品調(diào)運1 t給B1，為了保持產(chǎn)銷平衡，就要依次進(jìn)行調(diào)整

10、,就構(gòu)成了以（ A1, B1）空格為起點，其他為數(shù)字格的閉回路，如表5.3.13中的虛線所示。閉回路各頂點所在格的右上角數(shù)字是單位運價。 表5.3.13元）(11) 1(2) 1(3) 1(3) 1(調(diào)整的方案使運費增加 將“1”填（A1, B1）格中，這就是檢驗數(shù)。按上述辦法，可找出所有空格的檢驗數(shù)，見表5.3.14。當(dāng)檢驗數(shù)還有負(fù)數(shù)時，需要對原方案進(jìn)行改造。表5.3.14 用位勢法檢驗: 第1步,按最小元素法給出表5.3.8的初始基可行解，作表5.3.15。在對應(yīng)表5.3.8的數(shù)字格處填入單位運價。銷地產(chǎn)地B1B2B3B4A1A2A31432105表5.3.15 第2步,在上表增加一行一列

11、，在列中填入 ，在行中填入 ，得表5.3.16。iujv銷地產(chǎn)地B1B2B3B4A1A2A314321050-1-529310jviu表5.3.16 首先令u1=0,然后按 可確定所有和的數(shù)值。 第3步,按 計算所有空格的檢驗數(shù)，特設(shè)計計算表5.3.17。表5.3.17),(Bjicvuijji),(0)(Njivucjiijij 改進(jìn)的方法閉回路調(diào)整法: 在表5.3.17中，(A2, B4)為調(diào)入格，以此格為出發(fā)點，作一閉回路,得表5.3.18。表5.3.18 格的調(diào)入量 是選擇閉回路上具有（-1）的數(shù)字格中的最小者即 ，然后，按閉回路上的正、負(fù)號，加、減此值得到調(diào)整方案，如表5.3.19所

12、示。再用閉回路法或位勢法求各空格的檢驗數(shù)，得表5.3.20。在表5.3.20中，因為所有檢驗數(shù)都非負(fù)，故得最優(yōu)解，這時，得到最小運費為85（元）。),(42BA1) 3 , 1min(銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3365213749銷量3656銷地產(chǎn)地B1B2B3B4A1A2A30922112表5.3.19表5.3.20三、產(chǎn)銷不平衡的運輸問題的求解方法三、產(chǎn)銷不平衡的運輸問題的求解方法 前面求解運輸問題的表上作業(yè)法，是以產(chǎn)銷平衡為前提的 ，即 實際情況需要把產(chǎn)銷不平衡的問題化成產(chǎn)銷平衡的問題。 當(dāng)產(chǎn)大于銷 運輸問題的數(shù)學(xué)模型為求使 minjjiba11minjjiba11), 2

13、, 1;, 2 , 1(njmixij minjijijxcZ11min),2, 1;,2, 1(0),2, 1(),2, 1(11njmixnjbxmiaxijmijijnjiij且滿足 考慮多余的物資在哪一個產(chǎn)地就地儲存的問題。設(shè) 是產(chǎn)地Ai的儲存量，于是有1, nixijijcc miminjnjinimijijnjnjiijniijbbaxnjbxmiaxxx11111,11111,), 2 , 1(), 2 , 1(njmi, 2 , 1, 2 , 11, 2 , 1njmi0ijc當(dāng) 時，令當(dāng) 時，令產(chǎn)銷不平衡的運輸問題就可以改寫成：求 使 ) 1, 2 , 1;, 2 , 1(nnjmixijminjijijminjmininiijijminjijijxcxcxcxcZ111111,1,111min) 1, 2 , 1