運(yùn)輸問題求解表上作業(yè)法經(jīng)典實(shí)用

1、運(yùn)輸問題求解運(yùn)輸問題求解 表上作業(yè)法表上作業(yè)法運(yùn)輸問題求解-表上作業(yè)法運(yùn)輸問題求解之表上作業(yè)法運(yùn)輸問題求解之表上作業(yè)法1.運(yùn)輸問題模型及其求解思路運(yùn)輸問題模型及其求解思路2.確定初始基本可行解確定初始基本可行解3.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)4.方案調(diào)整方案調(diào)整運(yùn)輸問題求解-表上作業(yè)法1.運(yùn)輸問題模型及其求解思路運(yùn)輸問題模型及其求解思路v運(yùn)輸問題： 研究把某種商品從若干個(gè)產(chǎn)地運(yùn)至若干個(gè)銷售地而使總運(yùn)費(fèi)最小的一類問題。v目標(biāo)：1總運(yùn)費(fèi)最小運(yùn)輸問題求解-表上作業(yè)法 1.運(yùn)輸問題模型及其求解思路運(yùn)輸問題模型及其求解思路 銷地產(chǎn)地b1b2bn產(chǎn)量a1a2 :amc11c21:cm1c12c22:cm2:c1n

2、c2n:cmna1a2:am銷量b1b2bnv 已知有m個(gè)產(chǎn)地ai（i=1,2， ， m ）可供應(yīng)某種物資，其供應(yīng)量（產(chǎn)量）分別為ai ，有n個(gè)銷地bj （j=1,2， ， n）其銷量（需求量）分別為bj ，從a到b的單位物資運(yùn)價(jià)為cij 。運(yùn)輸問題求解-表上作業(yè)法若設(shè)若設(shè) 代表從第代表從第ai個(gè)產(chǎn)地到第個(gè)產(chǎn)地到第bj個(gè)銷售地的調(diào)運(yùn)量，在個(gè)銷售地的調(diào)運(yùn)量，在產(chǎn)銷產(chǎn)銷平衡平衡的條件下（的條件下（ ），要確定總運(yùn)輸費(fèi)用最小的調(diào)運(yùn)），要確定總運(yùn)輸費(fèi)用最小的調(diào)運(yùn)方案，可表示為如下的數(shù)學(xué)模型方案，可表示為如下的數(shù)學(xué)模型ijxnjjmiiba11ijmnjijxcz11mini011ijjmiijinji

3、jxbxaxs.t.(i=1，2，m； j=1，2，n)矩陣形式：cxzmin0xaxbs.t. 1.運(yùn)輸問題模型及其求解思路運(yùn)輸問題模型及其求解思路運(yùn)輸問題求解-表上作業(yè)法1 1 1 1 1 11 1 11 1 11 1 11 1 1 a=m 行n 行 1.運(yùn)輸問題模型及其求解思路運(yùn)輸問題模型及其求解思路系數(shù)矩陣運(yùn)輸問題求解-表上作業(yè)法2 1.運(yùn)輸問題模型及其求解思路運(yùn)輸問題模型及其求解思路對于產(chǎn)銷平衡的運(yùn)輸問題，對于產(chǎn)銷平衡的運(yùn)輸問題，若產(chǎn)地為若產(chǎn)地為m個(gè)，銷地為個(gè)，銷地為n個(gè)，個(gè)，則則 變量個(gè)數(shù)為變量個(gè)數(shù)為mn個(gè)，個(gè)，約束條件個(gè)數(shù)為約束條件個(gè)數(shù)為m+n，其中包含：總產(chǎn)量總銷售其中包含：總

4、產(chǎn)量總銷售故線性無關(guān)的約束條件個(gè)數(shù)為故線性無關(guān)的約束條件個(gè)數(shù)為m+n-1，基本解中的基變量個(gè)數(shù)為基本解中的基變量個(gè)數(shù)為m+n-1。運(yùn)輸問題求解-表上作業(yè)法v運(yùn)輸問題求解思路運(yùn)輸問題求解思路表上作業(yè)法表上作業(yè)法v由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計(jì)算，則無法利用這些有利條性規(guī)劃單純形法求解計(jì)算，則無法利用這些有利條件。件。v人們在分析運(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了人們在分析運(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對運(yùn)輸問題的針對運(yùn)輸問題的表上作業(yè)法表上作業(yè)法。 1.運(yùn)輸問題模型及其求解思路運(yùn)輸問題模型及其求解思路運(yùn)輸問題求解

5、-表上作業(yè)法v 表上作業(yè)法是單純形法在求解產(chǎn)銷平衡的運(yùn)輸問題時(shí)的一表上作業(yè)法是單純形法在求解產(chǎn)銷平衡的運(yùn)輸問題時(shí)的一種簡化方法，其實(shí)質(zhì)仍是單純形法，所不同的只是完成各種簡化方法，其實(shí)質(zhì)仍是單純形法，所不同的只是完成各步采用的具體形式。步采用的具體形式。v 具體操作步驟如下：具體操作步驟如下：v （1）確定一個(gè)初始基本可行解：即在）確定一個(gè)初始基本可行解：即在mn階產(chǎn)銷平衡階產(chǎn)銷平衡表上給出表上給出m+n-1個(gè)數(shù)字格（個(gè)數(shù)字格（基變量基變量）；）；v （2）求各非基變量（空格）的檢驗(yàn)數(shù)，即在表上）求各非基變量（空格）的檢驗(yàn)數(shù)，即在表上計(jì)算空格的計(jì)算空格的檢驗(yàn)數(shù)檢驗(yàn)數(shù)。判別式否達(dá)到最優(yōu)解。如果是最

6、優(yōu)解，。判別式否達(dá)到最優(yōu)解。如果是最優(yōu)解，則停止計(jì)算，否則進(jìn)入下一步。則停止計(jì)算，否則進(jìn)入下一步。v （3）確定換入變量和換出變量，找出新的基可行解。）確定換入變量和換出變量，找出新的基可行解。v （4）重復(fù)）重復(fù)(2)、(3)直至得到最優(yōu)解為止直至得到最優(yōu)解為止。 1.運(yùn)輸問題模型及其求解思路運(yùn)輸問題模型及其求解思路運(yùn)輸問題求解-表上作業(yè)法2.確定初始基本可行解確定初始基本可行解1）最小元素法）最小元素法 基本思想：基本思想：就近供應(yīng)就近供應(yīng)，按運(yùn)價(jià)最小的優(yōu)先調(diào)運(yùn)原則確，按運(yùn)價(jià)最小的優(yōu)先調(diào)運(yùn)原則確定初始方案，即從單位運(yùn)價(jià)表中選擇運(yùn)價(jià)定初始方案，即從單位運(yùn)價(jià)表中選擇運(yùn)價(jià)最小的開始確定調(diào)運(yùn)關(guān)系，

7、然后次小。若最小的開始確定調(diào)運(yùn)關(guān)系，然后次小。若某行（列）的產(chǎn)量（銷量）已滿足，則把某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，該行（列）的其他格劃去。如此進(jìn)行下去，一直到給出初始基可行解為止一直到給出初始基可行解為止 。 運(yùn)輸問題求解-表上作業(yè)法v 例如，某公司經(jīng)營某種產(chǎn)品，該公司下設(shè)例如，某公司經(jīng)營某種產(chǎn)品，該公司下設(shè)a、b、c三個(gè)三個(gè)生產(chǎn)廠，有甲、乙、丙、丁四個(gè)銷售點(diǎn)。公司每天把三個(gè)生產(chǎn)廠，有甲、乙、丙、丁四個(gè)銷售點(diǎn)。公司每天把三個(gè)工廠生產(chǎn)的產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)，各工廠到各銷售點(diǎn)工廠生產(chǎn)的產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)，各工廠到各銷售點(diǎn)的路程不同，單位產(chǎn)品的運(yùn)費(fèi)不

8、同。各工廠每日的產(chǎn)量、的路程不同，單位產(chǎn)品的運(yùn)費(fèi)不同。各工廠每日的產(chǎn)量、各銷售點(diǎn)每日的銷量，以及從各工廠到各銷售點(diǎn)單位產(chǎn)品各銷售點(diǎn)每日的銷量，以及從各工廠到各銷售點(diǎn)單位產(chǎn)品的運(yùn)價(jià)如下表。問該公司如何調(diào)運(yùn)產(chǎn)品，在滿足各銷售點(diǎn)的運(yùn)價(jià)如下表。問該公司如何調(diào)運(yùn)產(chǎn)品，在滿足各銷售點(diǎn)需要的前提下，使需要的前提下，使總運(yùn)費(fèi)最小總運(yùn)費(fèi)最小。甲甲乙乙丙丙丁丁產(chǎn)量產(chǎn)量a3113107b19284c741059銷量銷量36562.確定初始基本可行解確定初始基本可行解運(yùn)輸問題求解-表上作業(yè)法34333231242322211413121151047829103113minxxxxxxxxxxxxz0656394734

9、2414332313322212312111343332312423222114131211ijxxxxxxxxxxxxxxxxxxxxxxxxxs.t2.確定初始基本可行解確定初始基本可行解ijxv 若設(shè) 代表從第i個(gè)產(chǎn)地到第j個(gè)銷售地的運(yùn)輸量（i=1,2,3；j=1,2,3,4)運(yùn)輸問題求解-表上作業(yè)法b1b2b3b4產(chǎn)量產(chǎn)量a13113107a219284a3741059銷量銷量36563431632.確定初始基本可行解確定初始基本可行解z=43+310+31+12+64+35=86運(yùn)輸問題求解-表上作業(yè)法為保證基變量的個(gè)數(shù)有為保證基變量的個(gè)數(shù)有m+n-1個(gè)，個(gè)，v1、每次填完數(shù)，只能劃

10、去一行或一列，只、每次填完數(shù)，只能劃去一行或一列，只有最后一個(gè)格子例外。有最后一個(gè)格子例外。v2、用最小元素法時(shí)，可能會出現(xiàn)基變量個(gè)、用最小元素法時(shí)，可能會出現(xiàn)基變量個(gè)數(shù)還差兩個(gè)以上但只剩下一行或一列的情數(shù)還差兩個(gè)以上但只剩下一行或一列的情況，此時(shí)不能將剩下行或列按空格劃掉，況，此時(shí)不能將剩下行或列按空格劃掉，應(yīng)在剩下的空格中標(biāo)上應(yīng)在剩下的空格中標(biāo)上0。（退化的基本可。（退化的基本可行解）行解）2.確定初始基本可行解確定初始基本可行解注意：注意：運(yùn)輸問題求解-表上作業(yè)法b1b2b3b4產(chǎn)量產(chǎn)量a13113108a219283a3741059銷量銷量36563530632.確定初始基本可行解確定

11、初始基本可行解運(yùn)輸問題求解-表上作業(yè)法v）伏格爾法）伏格爾法v 伏格爾法的基本思想：如果某一地的產(chǎn)品不能按最小運(yùn)費(fèi)伏格爾法的基本思想：如果某一地的產(chǎn)品不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，兩者間就有一個(gè)差額。差額就近供應(yīng)，就考慮次小運(yùn)費(fèi)，兩者間就有一個(gè)差額。差額越大，說明越大，說明費(fèi)用增量費(fèi)用增量越大。因而對差額最大處，優(yōu)先采用越大。因而對差額最大處，優(yōu)先采用最小運(yùn)費(fèi)調(diào)運(yùn)。最小運(yùn)費(fèi)調(diào)運(yùn)。v 步驟：步驟：v 分別計(jì)算表中各行和各列中分別計(jì)算表中各行和各列中最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差 額額，并填入表中的最右列和最下行。，并填入表中的最右列和最下行。v 從行和列的差額中選出最大者

12、，選擇其所在行或列中的從行和列的差額中選出最大者，選擇其所在行或列中的最小元素，按類似于最小元素法優(yōu)先供應(yīng)，劃去相應(yīng)的行最小元素，按類似于最小元素法優(yōu)先供應(yīng)，劃去相應(yīng)的行或列?；蛄小 對表中未劃去的元素，重復(fù)對表中未劃去的元素，重復(fù) ，直到所有的行和列，直到所有的行和列都劃完為止。都劃完為止。2.確定初始基本可行解確定初始基本可行解運(yùn)輸問題求解-表上作業(yè)法b1b2b3b4兩最小元素之差兩最小元素之差a1311310a21928a374105兩最小元素之差兩最小元素之差2.確定初始基本可行解確定初始基本可行解0112513運(yùn)輸問題求解-表上作業(yè)法b1b2b3b4兩最小元素之差兩最小元素之差a1

13、3113100a219281a3741052兩最小元素之兩最小元素之差差2132.確定初始基本可行解確定初始基本可行解運(yùn)輸問題求解-表上作業(yè)法b1b2b3b4兩最小元素之差兩最小元素之差a13113100a219281a374105兩最小元素之兩最小元素之差差2122.確定初始基本可行解確定初始基本可行解運(yùn)輸問題求解-表上作業(yè)法b1b2b3b4兩最小元素之差兩最小元素之差a13113107a219286a374105兩最小元素之兩最小元素之差差122.確定初始基本可行解確定初始基本可行解運(yùn)輸問題求解-表上作業(yè)法b1b2b3b4兩最小元素之差兩最小元素之差a1311310a21928a37410

14、5兩最小元素之兩最小元素之差差22.確定初始基本可行解確定初始基本可行解運(yùn)輸問題求解-表上作業(yè)法b1b2b3b4兩最小元素之差兩最小元素之差a1311310a21928a374105兩最小元素之兩最小元素之差差2.確定初始基本可行解確定初始基本可行解運(yùn)輸問題求解-表上作業(yè)法b1b2b3b4產(chǎn)量產(chǎn)量a1527a2314a3639銷量銷量36562.確定初始基本可行解確定初始基本可行解z=53+210+31+18+64+35=85運(yùn)輸問題求解-表上作業(yè)法3.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)v檢驗(yàn)數(shù)的意義：非基變量增加一個(gè)單位，檢驗(yàn)數(shù)的意義：非基變量增加一個(gè)單位，使目標(biāo)函數(shù)值增加的數(shù)量。使目標(biāo)函數(shù)值增加的數(shù)量。

15、v運(yùn)輸問題中目標(biāo)函數(shù)值要求最小化，因此，運(yùn)輸問題中目標(biāo)函數(shù)值要求最小化，因此，當(dāng)所有的檢驗(yàn)數(shù)都當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零大于或等于零時(shí)該調(diào)運(yùn)時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案；否則不是。方案就是最優(yōu)方案；否則不是。v下面介紹兩種計(jì)算檢驗(yàn)數(shù)的方法：下面介紹兩種計(jì)算檢驗(yàn)數(shù)的方法：運(yùn)輸問題求解-表上作業(yè)法v1 1、閉回路法、閉回路法v閉回路：在已給出基本解的運(yùn)輸表上，從一個(gè)非基閉回路：在已給出基本解的運(yùn)輸表上，從一個(gè)非基變量出發(fā)，沿水平或豎直方向前進(jìn)，只有碰到基變變量出發(fā)，沿水平或豎直方向前進(jìn)，只有碰到基變量，才能向右或向左轉(zhuǎn)量，才能向右或向左轉(zhuǎn)9090o o ( (當(dāng)然也可以不改變方向）當(dāng)然也可以不改變方

16、向）繼續(xù)前進(jìn)。繼續(xù)前進(jìn)。v這樣繼續(xù)下去，總能回到出發(fā)的那個(gè)非基變量，由這樣繼續(xù)下去，總能回到出發(fā)的那個(gè)非基變量，由此路線形成的封閉曲線，叫閉回路。此路線形成的封閉曲線，叫閉回路。3.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)運(yùn)輸問題求解-表上作業(yè)法3.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)b1b2b3b4產(chǎn)量產(chǎn)量a13113 410 37a21 392 184a374 6105 39銷量銷量3656v若讓若讓x111，則總運(yùn)費(fèi)變化：，則總運(yùn)費(fèi)變化：31+231 。 11 =1v若讓若讓x311，則總運(yùn)費(fèi)變化：，則總運(yùn)費(fèi)變化：75+103+2-110 。 31 =10運(yùn)輸問題求解-表上作業(yè)法3.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)63 24 = -1

17、3b49 33 = 126 31 = 10a3563銷量銷量41 22= 13a274 12 = 2a1產(chǎn)量產(chǎn)量b3b2b1 11 = 1v最優(yōu)標(biāo)準(zhǔn)：所有檢驗(yàn)數(shù)最優(yōu)標(biāo)準(zhǔn)：所有檢驗(yàn)數(shù) ij 0運(yùn)輸問題求解-表上作業(yè)法v2、位勢法、位勢法v 閉回路法的缺點(diǎn)：當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路以及計(jì)算閉回路法的缺點(diǎn)：當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路以及計(jì)算兩方面都容易出錯。兩方面都容易出錯。位勢法檢驗(yàn)步驟：位勢法檢驗(yàn)步驟：v 1）設(shè)產(chǎn)地）設(shè)產(chǎn)地ai對應(yīng)的位勢量為對應(yīng)的位勢量為ui ，銷地，銷地bj對應(yīng)的位勢量為對應(yīng)的位勢量為vj；v 2）由）由 ij=cij-（ui+vj）,利用對基變量而言有利用對基變量而言

18、有 ij=0，計(jì)算位計(jì)算位勢勢ui ， vj ，即即cij-（ui+vj） = 0，令，令u1=0；v 3）再由）再由 ij=cij-（ui+vj）計(jì)算非基變量的檢驗(yàn)數(shù)計(jì)算非基變量的檢驗(yàn)數(shù) ij3.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)運(yùn)輸問題求解-表上作業(yè)法b1b2b3b4uia13 11 3 410 3a21 39 2 18a37 4 6105 3vju1 u2u3v1v2v3v40103-1-5293.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)運(yùn)輸問題求解-表上作業(yè)法b1b2b3b4uia13 11 3 410 30a21 39 2 18-1a37 4 6105 3-5vj29310 ij=cij-（ui+vj） 11=c11

19、-（u1+v1）=3-(0+2)=1 12=c12-（u1+v2）=11-(0+9)=2(1)(2)3.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)運(yùn)輸問題求解-表上作業(yè)法b1b2b3b4產(chǎn)量產(chǎn)量a1437a2314a3639銷量銷量36563.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn) 33=12 11=1 22=1 31=10 24= -1 12=2當(dāng)存在非基變量的檢驗(yàn)數(shù)當(dāng)存在非基變量的檢驗(yàn)數(shù) ij 0，說明現(xiàn)行方案為最，說明現(xiàn)行方案為最優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。運(yùn)輸問題求解-表上作業(yè)法3.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)v1、閉回路法計(jì)算式：、閉回路法計(jì)算式：v ij = (閉回路上的奇數(shù)頂點(diǎn)運(yùn)

20、價(jià)之和閉回路上的奇數(shù)頂點(diǎn)運(yùn)價(jià)之和) - (閉回路上閉回路上的偶數(shù)頂點(diǎn)運(yùn)價(jià)之和的偶數(shù)頂點(diǎn)運(yùn)價(jià)之和)v2、位勢法計(jì)算式：、位勢法計(jì)算式：v ij = cij - ui vj 當(dāng)存在非基變量的檢驗(yàn)數(shù)當(dāng)存在非基變量的檢驗(yàn)數(shù) ij 0，說明現(xiàn)行方案為，說明現(xiàn)行方案為最優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。最優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。運(yùn)輸問題求解-表上作業(yè)法4.方案調(diào)整方案調(diào)整閉回路調(diào)整法步驟：閉回路調(diào)整法步驟：1、入基變量的確定：選負(fù)檢驗(yàn)數(shù)中最小者、入基變量的確定：選負(fù)檢驗(yàn)數(shù)中最小者 rk，那，那么么 xrk 作為進(jìn)基變量；（使總運(yùn)費(fèi)盡快減少）作為進(jìn)基變量；（使總運(yùn)費(fèi)盡快減少）2、出基變量的

21、確定：在進(jìn)基變量、出基變量的確定：在進(jìn)基變量xrk 的閉回路上，的閉回路上，選取偶數(shù)頂點(diǎn)上調(diào)運(yùn)量最小的值，將其對應(yīng)的運(yùn)量選取偶數(shù)頂點(diǎn)上調(diào)運(yùn)量最小的值，將其對應(yīng)的運(yùn)量作為出基變量。（剛好有一個(gè)基變量出基，其它基作為出基變量。（剛好有一個(gè)基變量出基，其它基變量都為正）變量都為正）運(yùn)輸問題求解-表上作業(yè)法4.方案調(diào)整方案調(diào)整 即求即求 =minxij 閉回路上的偶數(shù)頂點(diǎn)的閉回路上的偶數(shù)頂點(diǎn)的xij= xpq。那么那么確定確定xpq為出基變量，為出基變量， 為調(diào)整量；為調(diào)整量； 3、換基調(diào)整：對閉回路的奇數(shù)頂點(diǎn)運(yùn)量調(diào)整為：、換基調(diào)整：對閉回路的奇數(shù)頂點(diǎn)運(yùn)量調(diào)整為：xij+ ，對各偶數(shù)頂點(diǎn)運(yùn)量調(diào)整為：，

22、對各偶數(shù)頂點(diǎn)運(yùn)量調(diào)整為：xij- ，特別，特別 xpq- =0，xpq變?yōu)榉腔兞俊Ｗ優(yōu)榉腔兞俊?重復(fù)以上步驟，直到所有檢驗(yàn)數(shù)均非負(fù)，即得到最優(yōu)重復(fù)以上步驟，直到所有檢驗(yàn)數(shù)均非負(fù)，即得到最優(yōu)解。解。運(yùn)輸問題求解-表上作業(yè)法4.方案調(diào)整方案調(diào)整b1b2b3b4產(chǎn)量產(chǎn)量a13 （1）11 （2）3 410 37a21 39 （1）2 18 （-1）4a37 （10）4 610 （12）5 39銷量銷量3656最小檢驗(yàn)數(shù)最小檢驗(yàn)數(shù)原則，確定原則，確定進(jìn)基變量進(jìn)基變量最小偶點(diǎn)原則，最小偶點(diǎn)原則，確定出基變量和確定出基變量和調(diào)整量調(diào)整量+1-1+1-1 13 , 1minmin14,23 xx運(yùn)輸問題

23、求解-表上作業(yè)法四、方案調(diào)整b1b2b3b4產(chǎn)量產(chǎn)量aia13 11 3 5 10 2 7a21 39 2 8 14a37 4 610 5 39銷量銷量bj3656v得到新的基變量：得到新的基變量：x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3。重新計(jì)算檢驗(yàn)數(shù)。重新計(jì)算檢驗(yàn)數(shù)。（1）（2）（2）（1）（9）（12）運(yùn)輸問題求解-表上作業(yè)法四、方案調(diào)整v經(jīng)過一次基變換，所有經(jīng)過一次基變換，所有 ij 0，已得到最優(yōu)解：，已得到最優(yōu)解： x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3

24、，其它為，其它為0。v最優(yōu)值：最優(yōu)值：vf* =35+102+13+81+46+53 = 85運(yùn)輸問題求解-表上作業(yè)法表上作業(yè)法計(jì)算中的相關(guān)問題表上作業(yè)法計(jì)算中的相關(guān)問題v1.無窮多最優(yōu)解v 當(dāng)最優(yōu)方案中存在某空格（非基變量）檢驗(yàn)數(shù)為當(dāng)最優(yōu)方案中存在某空格（非基變量）檢驗(yàn)數(shù)為0,時(shí)，則時(shí)，則該運(yùn)輸問題一定有多重最優(yōu)解。該運(yùn)輸問題一定有多重最優(yōu)解。v2.退化解v 當(dāng)運(yùn)輸問題的最優(yōu)表中有數(shù)格（基變量）的運(yùn)量為當(dāng)運(yùn)輸問題的最優(yōu)表中有數(shù)格（基變量）的運(yùn)量為0，則，則出現(xiàn)退化。出現(xiàn)退化。v 1）確定基本可行解中，出現(xiàn)同時(shí)需要劃去一行和一列的）確定基本可行解中，出現(xiàn)同時(shí)需要劃去一行和一列的情況，則需要在填寫數(shù)格的行或列上，寫上一個(gè)情況，則需要在填寫數(shù)格的行或列上，寫上一個(gè)0數(shù)格。數(shù)格。v 2）在閉回路中進(jìn)行調(diào)整時(shí)，如同時(shí)有）在閉回路中進(jìn)行調(diào)整時(shí)，如同時(shí)有t(t1)個(gè)最小數(shù)個(gè)最小