交通運(yùn)輸線性規(guī)劃運(yùn)輸問題精編

1、（交通運(yùn)輸）線性規(guī)劃運(yùn)輸問題20XX年XX月（交通運(yùn)輸）線性規(guī)劃運(yùn)輸問題第四章運(yùn)輸問題Chapter4TransportationProblem§ 4.運(yùn)輸問題的定義設(shè)有同壹種貨物從 m個(gè)發(fā)地1 , 2,，m運(yùn)往n個(gè)收地1 , 2,，n。 第i個(gè)發(fā)地的供應(yīng)量(Supply )為si(si>0),第j個(gè)收地的需求量(Demand ) 為dj (dj>0)。每單位貨物從發(fā)地i運(yùn)到收地j的運(yùn)價(jià)為Cj。求壹個(gè)使總運(yùn) 費(fèi)最小的運(yùn)輸方案。我們假定從任壹發(fā)地到任壹收地都有道路通行。如果總 供應(yīng)量等于總需求量，這樣的運(yùn)輸問題稱為供求平衡的運(yùn)輸問題。我們先只 考慮這壹類問題。圖4.1.1是

2、運(yùn)輸問題的網(wǎng)絡(luò)表示形式。運(yùn)輸問題也能夠用線性規(guī)劃表示。設(shè)xij為從發(fā)地i運(yùn)往U地j的運(yùn)量，則總運(yùn)費(fèi)最小的線性規(guī)劃問題如下頁所示。運(yùn)輸問題線性規(guī)劃變量個(gè)數(shù)為 nm個(gè)，每個(gè)變量和運(yùn)輸網(wǎng)絡(luò)的壹條邊對應(yīng)，所有的變量都是非負(fù)的。約束 個(gè)數(shù)為m+n個(gè)，全部為等式約束。前 m個(gè)約束是發(fā)地的供應(yīng)量約束，后 n 個(gè)約束是收地的需求量約束。運(yùn)輸問題約束的特點(diǎn)是約束左邊所有的系數(shù)都 是0或1 ,而且每壹列中恰有倆個(gè)系數(shù)是1 ,其他都是0。運(yùn)輸問題是壹種線性規(guī)劃問題，當(dāng)然能夠用第壹章中的單純形法求解。 但由于它有特殊的結(jié)構(gòu)，因而有特殊的算法。在本章中，我們將在單純形法 原理的基礎(chǔ)上，根據(jù)運(yùn)輸問題的特點(diǎn)，給出特殊的算法

3、。在運(yùn)輸問題線性規(guī)劃模型中，令X= (X11 , X12 ,，X1n , X21 , X22 ,，X2n , ,Xm1 , Xm2 ,，Xmn ) TC=(C11,C12 ,，C1n ,C21,C22 ,，C2n, ,Cm1, Cm2 ,，Cmn )A=ail, ai2,，ain , a2i, a22,，a2n, ,ami , am2,，amn Tb= (si, S2,，Sm , di , d2,，dn) T則運(yùn)輸問題的線性規(guī)劃能夠?qū)懗桑簃inz= CTXs.t. AX = bX>0其中A矩陣的列向量aij= e i+ e m+jei和em+j是m+n維單位向量，元素i分別在在第i個(gè)分量

4、和第m+j個(gè)分量 的位置上。A矩陣中的行和運(yùn)輸網(wǎng)絡(luò)中的節(jié)點(diǎn)對應(yīng)，前m行對應(yīng)于發(fā)地，后n行對應(yīng)于收地；A矩陣的列和運(yùn)輸網(wǎng)絡(luò)中的邊對應(yīng)。運(yùn)輸問題除了用網(wǎng)絡(luò)表示及線性規(guī)劃表示外，仍能夠用運(yùn)輸表表示：表4.i表的行和發(fā)地對應(yīng)，列和收地對應(yīng)。第 i行和第j列交叉的壹格和網(wǎng)絡(luò)的壹條邊對應(yīng)（也就是和線性規(guī)劃約束矩陣的壹列對應(yīng)），每壹格的左上角小方格內(nèi)的數(shù)字表明從相應(yīng)的發(fā)地i到收地j的運(yùn)價(jià)cu,每壹格右下角表明從相應(yīng)的發(fā)地i到收地j的運(yùn)量Xijo表右方表明各發(fā)地的供應(yīng)量Si,表下方表明各需求第的需求量 djo每壹行運(yùn)量之和表示從該發(fā)地運(yùn)往各收地的運(yùn)量之和，它應(yīng)該等于該發(fā)地的供應(yīng)量；同樣，每壹列運(yùn)量之和表示從各

5、發(fā)地運(yùn) 往該收地的運(yùn)量之和，它應(yīng)該等于該收地的需求量。1525圖4.2102010運(yùn)輸問題的網(wǎng)絡(luò)圖、 線性規(guī)劃模型以及運(yùn)輸表之間的關(guān)系能夠用下表表示：網(wǎng)絡(luò)圖線性規(guī)劃模型運(yùn)輸表下點(diǎn)發(fā)點(diǎn)i約束前m個(gè)約束表的行收點(diǎn)j后n個(gè)約束表的列邊從節(jié)點(diǎn)i到節(jié)點(diǎn)j變量Xij ,列向量aij表中的壹格例4.1以下的運(yùn)輸問題線性規(guī)劃、網(wǎng)絡(luò)圖和運(yùn)輸表表示同壹運(yùn)輸問題。minz=8x11+5x 12+6X 13+7X 21+4X 22+ 9X 23s.t.X11+X 12+X 13=15X21+X 22+X 23=25X11+X 21=10X12+X 22=20X13+X 23=10X11 ,X12 ,X13 ,X21

6、,X22 ,X23>0表4.2§ 4 旄輸問題約束矩陣的性質(zhì)4.2.1 約束矩陣的秩運(yùn)輸問題約束矩陣 A的秩為m+n-1 。證明：因?yàn)锳矩陣白前m行和后n行之和分別等于向量（1, 1,， 1）,因此秩A<m+n 。考慮A的壹個(gè)子矩陣 A' =a1n, a2n,，amn , an , a 12,，am, 即A'=刪除A'中白第m+n行和第m+n歹U,得到A，二容易見出，秩 A' ' =m+n-1。由此m+n-1= 秩 A' ' w 秩 A' w 秩 A<m+n 即秩 A=m+n-1 。在線性規(guī)劃問題中，約

7、束的系數(shù)矩陣要求行滿秩的，為了使運(yùn)輸問題系數(shù)矩陣行滿秩，在 A矩陣中增加壹個(gè)列向量 em+n形成增廣矩陣 這樣增廣矩陣的秩就等于m+n ,因而是行滿秩的。且且中任何壹個(gè)基矩陣，都必定包含單位向量 em+n。例4.2.1設(shè)壹個(gè)運(yùn)輸網(wǎng)絡(luò)如右圖，它的系數(shù)矩陣為增廣矩陣為增加的單位列向量 em+n =e 5相當(dāng)于在在網(wǎng)絡(luò)圖中增加壹條邊， 它和收點(diǎn)3關(guān) 聯(lián)，但不和任何發(fā)點(diǎn)關(guān)聯(lián)，這條邊稱為人工邊。設(shè)這條邊上的運(yùn)輸量為xa,增廣運(yùn)輸問題對應(yīng)于第三個(gè)收點(diǎn)的約束稱為X13+X 23 +X a=d 3 由于X13 +X 23 =d 3因此，對運(yùn)輸問題的任何壹個(gè)可行解，都有Xa=0。4.2.2 A矩陣的單位模性質(zhì)運(yùn)

8、輸問題的系數(shù)矩陣A具有以下性質(zhì)：A矩陣中任何壹個(gè) k階子矩陣Ak ( k=1 , 2, m+n ),都有 det Ak=0 或±1。證明：在A中任取壹個(gè)k階方陣Ak,有以下三種情況：1、Ak中任何壹列都有倆個(gè) 1,這時(shí)Ak上部的行屬于 A矩陣的前m行, 而下部的行屬于 A矩陣的后n行，Ak上部的各行之和以及Ak下部各行之和都等于向量(1, 1,，1),因而Ak的行線性相關(guān)，即 det Ak=0。2、Ak中至少有壹列元素全為0,這時(shí)顯然有det Ak=0 o3、Ak中至少有壹列，其中只有壹個(gè)1。這時(shí)能夠?qū)et Ak按這壹列展 開，設(shè)對應(yīng)于這個(gè)1的代數(shù)余子式為 Ak-1,則有det A

9、k= ± detAk-1其中Ak-1是k-1階方陣。對 Ak-1同樣有det A k-1 =0或者det A k-1 = ± d et A k-2 最后有det Ak=0 或者det Ak= ± detAk-1 = ± detAk-2 = = ± detA 1=0 或 ±1。4.2.3 基矩陣的三角性設(shè)B是的壹個(gè)基，B中至少有壹列只包含壹個(gè) 1 ,否則，detB=0不成為壹個(gè)基。將B的行列交換，總能夠使 B成為其中det Bm+n-1 W0,因而Bm+n-1 中也至少有壹列只有壹個(gè) 1,對Bm+n-1再進(jìn)行行列交換，得到依次不斷對剩下

10、的方陣進(jìn)行行列交換，最后能夠得到是壹個(gè)上三角矩陣。例4.2設(shè)壹個(gè)運(yùn)輸問題的系數(shù)增廣矩陣為取其中壹個(gè)基對B進(jìn)行行列交換，成為以下上三角矩陣求解相應(yīng)的方程組由此得到X12 = 10 , X11 =15 , X23=20 , X13=5 , xa=0由A的基矩陣的三角性以及 A矩陣中僅含有元素 0和1 ,能夠知道，如果運(yùn) 輸問題各發(fā)地的供應(yīng)量和收地的需求量都是整數(shù)，運(yùn)輸問題的任何基礎(chǔ)可行 解都是整數(shù)，因而最優(yōu)解也是整數(shù)。§ 4.3S在網(wǎng)絡(luò)圖和運(yùn)輸表中的表示從前壹節(jié)已經(jīng)知道，運(yùn)輸問題的壹個(gè)基是由m+n個(gè)列向量組成的，其中包括壹個(gè)單位向量em+n。在網(wǎng)絡(luò)圖上，這 m+n 個(gè)列向量對應(yīng)m+n條邊

11、，其中和單位向量對應(yīng)的是從最后壹個(gè)收地出發(fā)的人工邊。網(wǎng)絡(luò)圖中的壹個(gè)廣、基具有以下性質(zhì)：I)' / /人1、壹個(gè)基由m+n條邊組成，其中壹條是人工邊，其余m+n-1條邊是原網(wǎng)絡(luò)中的邊。圖4.42、組成基的邊不能形成閉合回路。若不然，如果組成壹個(gè)基的若干條邊(i, j), (k, j), (i, l), (k, l)組成壹個(gè)閉合回路，則這些邊對應(yīng)的系數(shù)矩陣中的列向量 aij, akj, ail, a kl的線性組合aij-akj+ ail-akl=(ei+ em+j )-(ek+ em+k)-(ei + em+l)+(ek+ em+l )= 0這些列向量線性相關(guān)，顯然不能包含在壹個(gè)基中。3

12、、組成基的m+n條邊必須到達(dá)網(wǎng)絡(luò)的每壹個(gè)節(jié)點(diǎn)。若不然，這m+n條邊都不和某壹節(jié)點(diǎn) k關(guān)聯(lián)，那么相應(yīng)的基矩陣和節(jié)點(diǎn)k對應(yīng)的壹行全為 0,即det B=0。B不可能成為壹個(gè)基。例4.3對于2個(gè)發(fā)點(diǎn)3個(gè)收點(diǎn)的運(yùn)輸問題，網(wǎng)絡(luò)圖如圖4.5 (a)所示。圖m+n-1=2+3-1=44.5 (b)、(c)、(d)都是這個(gè)問題的基，這些基都由(a)網(wǎng)絡(luò)圖(b)第壹個(gè)基圖4.5邊組成，都不構(gòu)成回路，且且和每壹個(gè)節(jié)點(diǎn)關(guān)聯(lián)。正如線性規(guī)劃矩陣的列向量組成的基壹樣，壹個(gè)網(wǎng)絡(luò)的基的個(gè)數(shù)是非常 多的，之上只是這些基中的幾個(gè)例子。§ 4.基在運(yùn)輸表中的表示我們已經(jīng)知道，運(yùn)輸表中的壹行對應(yīng)于壹個(gè)發(fā)地，壹列對應(yīng)于壹個(gè)收

13、地，表中i行j列相交的格子表示網(wǎng)絡(luò)從發(fā)地節(jié)點(diǎn)i到收地節(jié)點(diǎn)j的壹條邊。運(yùn)輸表中同壹行i而不同列j和k的倆個(gè)格子（i, j） （i, k）,分別表示網(wǎng)絡(luò)中從 同壹發(fā)地節(jié)點(diǎn)i出發(fā)到達(dá)不同收地節(jié)點(diǎn) j和節(jié)點(diǎn)k的倆條邊；同樣，運(yùn)輸表 中位于同壹列k而不同行i和l的倆個(gè)格子（i, k）和（l, k）分別表示從不 同的發(fā)地節(jié)點(diǎn)出發(fā)，到達(dá)同壹收地節(jié)點(diǎn)j的倆條邊（見下表和圖）。jk(i, j)(i, k)(l, k)表4.3如果運(yùn)輸表中有若干個(gè)格子，他們中相鄰的倆個(gè)都分別位于同壹行或同壹列，例如在下表中六個(gè)格子（i, j）, （i, k）, （l, k）, （l, n）, （m , n） 和（m, j）,將位于

14、同壹行和同壹列的倆個(gè)格子連結(jié)起來，在運(yùn)輸表中構(gòu)成 壹個(gè)閉回路。在相應(yīng)的網(wǎng)絡(luò)圖中，這六個(gè)格子對應(yīng)的六條邊也組成壹個(gè)閉回路。i(l, k)(l, n)11(m, j)(m ； n )lm表4.4運(yùn)輸表中的閉回路仍能夠出現(xiàn)更復(fù)雜的情況，如下表和下圖所示。jkn(i, j)(i, k)(l, j)(l, n)(m , k)(m , n)表4.5綜上所述，總結(jié)運(yùn)輸表中壹個(gè)基必須具備的特點(diǎn)：1、壹個(gè)基應(yīng)占表中的 m+n-1 格；2、構(gòu)成基的同行同列格子不能構(gòu)成閉回路；3、壹個(gè)基在表中所占的m+n-1個(gè)格子應(yīng)包括表的每壹行和每壹列。例4.4在例4.3.1中的運(yùn)輸網(wǎng)絡(luò)的幾個(gè)基分別用網(wǎng)絡(luò)和運(yùn)輸表的表示如下:(a

15、)系數(shù)矩陣、網(wǎng)絡(luò)圖和運(yùn)輸表1(1,1 )(1,2)(1,3)2(2,1 )(2,2)(2,3)123(b)第壹個(gè)基的矩陣、網(wǎng)絡(luò)圖和運(yùn)輸表圖4.91 2(1,1 )(1,2)(1,3)(2,1 )(c)第二個(gè)基的矩陣、網(wǎng)絡(luò)圖和運(yùn)輸表123(1,1 )(1,3)(2,2)(2,3)12123§ 4 非基列向量用基向量表示在線性規(guī)劃中，設(shè) B是A矩陣的壹個(gè)基，且 B= aBi , aB2,，aBm, 則A中的任壹非基向量 aj （j C R）必定能夠用基向量 aBi, aB2,，aBm 唯壹地線性表出，其線性組合的系數(shù)就是 Yj,這是因?yàn)閅j= B-1aj即這就是說，向量 Yj就是用基向量

16、表出壹個(gè)非基向量aj的系數(shù)。在運(yùn)輸問題中如果確定了壹個(gè)基， 非基向量aij也能夠由基向量唯壹地表 出，由于運(yùn)輸問題的特殊性，表出系數(shù)Yij能夠很方便地確定。請見下壹例子。例4.5以具有2個(gè)發(fā)地，3個(gè)收地的運(yùn)輸問題為例子，這個(gè)運(yùn)輸問題的網(wǎng)絡(luò) 圖和系數(shù)矩陣如下：取基B= aii, ai2, a i3, a23, ea,非基向量為a2i,基矩陣、網(wǎng)絡(luò)圖中的 非基邊（用虛線表示）、基邊（用實(shí)線表示），且取從發(fā)地到收地的方向?yàn)楦?邊的方向。圖 4.I4由于任何壹個(gè)非基向量總是和基向量實(shí)線性相關(guān)的，因此在網(wǎng)絡(luò)圖中任壹 非基邊必定和若干條基邊形成閉回路。根據(jù)運(yùn)輸矩陣的結(jié)構(gòu)，a2i = e2+ e2+i =

17、e2+ e3向量aij,有aij=ei+em+j。在上面的問題中，非基向量基向量aii , ai2 , ai3, a23 能夠表示為:aii = ei+ e2+i = ei + e3 ai2 = ei+ e2+2 = ei + e4 ai3 = ei+ e2+3 = ei + e5 a23 = e2+ e2+3 = e2+ e5因此a2i - a ii + ai3-a23=( e2 + e3)-( ei+ e3)+( ei + e5)-(e2+ e5)= 0a2i = aii-ai3+ a23由于基向量a12和ea不在這個(gè)回路中，它在 a12此非基向量a21用所有基向量的表出形式為： 由此能夠

18、見出從這個(gè)例子能夠見出，非基向量由基向量 表出的方法和表出的系數(shù)能夠由該非基向量 和有關(guān)的基向量形成的回路來確定（見上圖）。 選定該非基邊的方向作為閉回路的方向，如果不在回路中，表出系數(shù)為0。的表達(dá)式中的系數(shù)是 0,因壹個(gè)基邊出當(dāng)下該回路中， 且且和回路的方向 相同，則表出系數(shù)為-1 ,如果基邊的方向和回 路的方向相反，則表出系數(shù)為 +1 ,如果基邊從給定非基邊的起點(diǎn)（發(fā)地）出發(fā)，沿著回路方向前進(jìn)，第壹次遇到的 基邊的方向壹定和回路方向相反，第二次遇到的基邊方向壹定和回路方向相同,現(xiàn)。同向和反向交替出現(xiàn)，因此，各基邊的表出系數(shù)壹定是+1 , -1交替出到。和網(wǎng)絡(luò)圖對應(yīng)，在運(yùn)輸表中非基向量用基向

19、量表示的方法也能夠相應(yīng)得 例如之上的運(yùn)輸問題，相應(yīng)的運(yùn)輸表如下左表所示。(1,1 )(1,2)(1,3)B(+1)B(0)B(-1)(2,1 )(2,2)(2,3)B(+1)表4.6對應(yīng)于基 B= a 11, a 12, a13, a23, ea的格子為用 B表不，非基向量 a21 相應(yīng)的格子用 N表示，見上面右表。運(yùn)輸表中非基向量用用基向量表出的系數(shù)是這樣確定的：（按任壹方向）沿著表中的閉回路前進(jìn)，在第壹個(gè)轉(zhuǎn)角處基向量的表出系數(shù)為+1 ,下壹個(gè)轉(zhuǎn)角處基向量的表出系數(shù)為 -1 ,以后依次交替變化，由于沿閉回路回到出 發(fā)的非基向量以前壹定要經(jīng)過奇數(shù)次轉(zhuǎn)角，因此最后壹個(gè)轉(zhuǎn)角處的基向量的表出系數(shù)壹定

20、也是+1。凡是不在閉回路上或不在閉回路轉(zhuǎn)角處的基向量的表 出系數(shù)均為0。在上面的表中，非基向量N (2, 1)和基向量B (1, 1)、B (1, 3)、B (2, 3)構(gòu)成壹個(gè)閉回路，相應(yīng)的表出系數(shù)依次為+1、-1和+1 ;基向量B (1, 2)不在閉回路的轉(zhuǎn)角處，表出系數(shù)為 0。因此，非基向量 a21的表 出形式為：圖 4.17表4.7取其中 m+n-1=4+5=9 個(gè)基向量 an, a 12,a14 , a21, a31, a33, a34, a35 和 a45,非基向量a42和基向量構(gòu)成的閉回路如右圖。根據(jù)基向量的表出系數(shù)由+1開始，+1、-1交替的 原則，之上非基向量用這些基向量表出

21、的形式 為：a42=( +1) a12+(-1) a11+(+1) a31 +(-1) a35+(+1) a45+ 0ea如果所有基向量按以下次序排列B=a11, a12 , a21, a31, a33 , a34 , a35,a45 , ea因而a42用這些基向量表示的表出系數(shù)Y42=-1 , +1 , 0 , +1 , 0, 0, -1 , +1 , 0T§ e運(yùn)輸問題單純形法運(yùn)輸問題單純形法的基本步驟和線性規(guī)劃壹樣，包括以下步驟，但具體實(shí)施是在運(yùn)輸表上實(shí)現(xiàn)。1、求得壹個(gè)初始基礎(chǔ)可行解；2、對非基變量xij計(jì)算檢驗(yàn)數(shù)zij-cij,根據(jù)各非基變量的檢驗(yàn)數(shù)zij-cij值，確定最優(yōu)

22、性或選擇進(jìn)基變量；3、當(dāng)進(jìn)基變量xij進(jìn)基時(shí)，根據(jù)基變量的變化， 求出最先降為0的基變 量確定為離基變量；4、進(jìn)行基變換，獲得新的基礎(chǔ)可行解且轉(zhuǎn)步驟2。4.6.1 確定初始基礎(chǔ)可行解1、西北角法西北角法是按發(fā)地和收地的編號(hào)為序，依次順序供給的原則獲得初始基礎(chǔ)可行解的壹種方法。它是從確定發(fā)地1到收地1的運(yùn)量開始。這個(gè)位置按地圖的方位來說是西北角，因而得名。從發(fā)地1到收地1的運(yùn)量取發(fā)地1的供應(yīng)量（30）和收地1的需求量（15）倆者中小的壹個(gè)安排，如果發(fā)地 1的供應(yīng)量沒有用完，則將剩余的供應(yīng)量向收地2發(fā)送，依次類推，直到最后壹個(gè)發(fā)地的供應(yīng)量全部運(yùn)出，最后壹個(gè)收地的需求量全部滿足為止。例4.7給出運(yùn)輸

23、表如下。發(fā)地 1的供應(yīng)量為30 ,收地1的需求量為15 ,在（1,（1） 排運(yùn)量15。發(fā)地1和收地1的供應(yīng)量和需求量分別變?yōu)?5和0。發(fā)地1234的供應(yīng)量為15 ,收地2的需求量為20 ,在（1 , 2）上安排運(yùn)量的供應(yīng)量變?yōu)?,收地2的需求量變?yōu)?需求量為5 ,發(fā)地2的供應(yīng)量為45 ,在（2 , 2）上安排運(yùn)量5,15 ,發(fā)地收地發(fā)地2的供應(yīng)量變?yōu)?0 ,收地2的需求量變?yōu)?;045-5發(fā)地2的供應(yīng)量為40 ,收地3的需求量為31 ,在（2, 3）上安排運(yùn)量的供應(yīng)量變?yōu)? ,收地3的需求量變?yōu)?；10240-31350254發(fā)地2的供應(yīng)量為9。收地4的需求量

24、為84 ,在（2, 4）上安排運(yùn)量9,31 ,發(fā)地發(fā)地2的供應(yīng)量變?yōu)?,收地4的需求量變?yōu)?5 ;123409-9502584-9收地4的需求量為75 ,發(fā)地3的供應(yīng)量為50 ,安排（3,4）上的運(yùn)量為50 ,發(fā)地3的供應(yīng)量0,收地4的需求量25 ;發(fā)地4的供應(yīng)量為25 ,收地4的需求量為25 ,安排（4,4）上的運(yùn)量 25 ,發(fā)地4的供應(yīng)量為0,收地4的需求量為0 ,供求和需求都得到滿足。00025-25=0用西北角法確定初始可行解方法簡單，不會(huì)出現(xiàn)回路，而且壹般情況下基變量的個(gè)數(shù)恰為 m+n-1 個(gè)（退化的情況基變量可能少于m+n-1 ,處理的方法在4.7節(jié)中介紹），而且基變量位于每壹行每

25、壹列，因而得到的是壹個(gè)基 礎(chǔ)可行解。西北角法的缺點(diǎn)是在安排運(yùn)量時(shí)不考慮運(yùn)價(jià)，因而得到的初始解 可能離開最優(yōu)解比較遠(yuǎn)。之上例子中用西北角法得到的初始解的目標(biāo)函數(shù)值 為z=2CijXij=10 15+1115+12 5+16 31+9 9+10 50+13 25=17772、最小元素法這種方法是按運(yùn)價(jià)由小到大的順序安排運(yùn)量。先從各運(yùn)價(jià)中找到最小運(yùn)價(jià)，設(shè)為cij,然后比較供應(yīng)量 si和需求量dj,如果si>d j,取xij =d j,且將 發(fā)地i的供應(yīng)量改為Si-d j,將收地j的需求量改為0；如果Si<dj,取Xij=Si, 且將發(fā)地i的供應(yīng)量改為0,將收地j的需求量改為dj-si；如

26、果si和dj中有 壹個(gè)為0,則不分配運(yùn)量給 Xij。分配完最小運(yùn)價(jià)的運(yùn)量后，用同樣的方法分 配運(yùn)價(jià)次小的運(yùn)量，依次類推，直到每壹個(gè)發(fā)地的供應(yīng)量和每壹個(gè)收地的需求量都為0。以下是用最小元素法確定運(yùn)輸問題的初始可行解的例子。例4.8給出運(yùn)輸表如下。 最小運(yùn)價(jià)為C33=7 ,發(fā)地3的供應(yīng)量為50 ,收地3 的需求量為31 ,安排運(yùn)量X33=31 。發(fā)地3和收地3的供應(yīng)量和需求量分別變?yōu)?9和0。1234101191530對于發(fā)地3的供應(yīng)量為0,收地2的需求量為1。1234C32=8 ,發(fā)地3的供應(yīng)量為19 ,收地2的需求量為20 ,安排X32=19 ,對于C13=9 , C24=9 ,能夠任選壹個(gè)，

27、可是（1,3）中收地3的需求量為0,安排X24=45 ,發(fā)地2的供應(yīng)量為0,收地4的需求量為39。3045-45014131213254151084-45對于cii=10和C34=10 ,由于發(fā)地3的需求量已經(jīng)為0,安排x11=15的供應(yīng)量為15,收地1的需求量為0;1234對于C12=110；對于,安排X12=1 ,發(fā)地1的供應(yīng)量為14 ,收地2的需求量為1234C44=13 ,安排X44 =25 ,發(fā)地4的供應(yīng)量為0,收地4的需求量為14。12341234140025-25最后安排X14=14 ,所有發(fā)地和收地的供應(yīng)量、需求量都等于0。123414-14=0000這樣就得到壹個(gè)運(yùn)輸問題的初

28、始基礎(chǔ)可行解。這個(gè)初始基礎(chǔ)可行解的目標(biāo)函數(shù)值為z=10 15+111+15 14+9 45+8 19+7 31+13 25=1470比用西北角法得到的初始基礎(chǔ)可行解的目標(biāo)函數(shù)值小O4.6.2 計(jì)算非基變量的檢驗(yàn)數(shù)zij-c ij4.5.2.1閉回路法對于非基變量xij ,檢驗(yàn)數(shù)為其中向量 Yij可由該非基變量和基變量形成的閉回路來確定，這個(gè)閉回路轉(zhuǎn) 角處的基變量對應(yīng)于y= ± 1 ,其余的基變量對應(yīng)于y=0 。這樣就等于轉(zhuǎn)角處基變量對應(yīng)的Cij依次加減的值。例4.9在例4.7中，用西北角法得到初始基礎(chǔ)可行解，計(jì)算各非基變量的檢驗(yàn)數(shù)zij-Cij非基變量（1,3）相應(yīng)的閉回路為3045

29、34因此 X13 的檢驗(yàn)數(shù) Z13-C13=(C 12-C22+C 23)-C13=(11-12+16)-9=+6非基變量（1, 4）相應(yīng)的閉回路為453050252, 1）相應(yīng)的閉回路為30455025因此 X14 的檢驗(yàn)數(shù) Z14-C14=(C 12-C22+C 24)-C 14=(11-12+9)-15=-7非基變量（2515203184因此 X21 的檢驗(yàn)數(shù) Z21 -C21 =(C 11-C 12+C 22)-C21 =(10-11 + 12)-13=-2非基變量（3, 1）相應(yīng)的閉回路為123430455025因此X31的檢驗(yàn)數(shù)Z31-C31 =(C 11-C12+C 22-C24

30、+C 34)-C31 =(10-11+12-9+10)-11=+1用同樣的方法能夠求得其他非基變量的檢驗(yàn)數(shù)Z32 -C 32 =(C 22 -C 24+C 34)-C 32 =(12-9+10)-8=+5Z33-C 33 =(C 23-C 24+C 34)-C 33 =(16-9+10)-7=+10Z41 -C41 =(C 11-C 12+C 23-C 24+C 44)-C 41 =(10-11+12-9+13)-14=+1Z42 -C 42 =(C 22 -C 24+C 44)-C 42 =(12-9+13)-13=+3Z43-C 43 =(C 23-C 24+C 44)-C 43=(16-

31、9+13)-12=+8將之上檢驗(yàn)數(shù)填入運(yùn)輸表，用”表示。304534152031845025對用最小元素法得到的初始基礎(chǔ)可行解，也能夠用同樣的方法求得各非基變 量的檢驗(yàn)數(shù)zij-cij,計(jì)算過程略，計(jì)算結(jié)果見下表。4.5.2.2對偶變量法設(shè)運(yùn)輸問題的原始問題為: 其中Xa是為了使矩陣A滿秩而增加的變量。應(yīng)的對偶變量為 V1, V2, ,vn。則對偶問題為:n個(gè)約束對設(shè)和前m個(gè)約束對應(yīng)的偶變量為 ui , u2, maxy=s 1u1+s2u2+ +smum+d 1Vl+d 2v2+ +d nvnu 1+v n< C1nU2+V 1 < C21U2+V n< C2n U m +

32、V 1 W Cm1 u m +v nW cmnVn=0U1 , U2,，Um , V1 , V2,，Vn: Unr 之上對偶問題，能夠簡寫成：Ui+VjW Cij(i=1,2,m-； j=1,2, ,n)Vn=0Ui, Vj： Unr對偶問題中由m+n個(gè)變量，mn+1個(gè)約束。對于運(yùn)輸問題的壹個(gè)基B,如果能夠求出相應(yīng)的對偶變量Wt=CbtB-1,就能夠計(jì)算非基變量 xij的檢驗(yàn)數(shù)Zij-Cij：zij-c ij = CbtB-1 aij -cij = W Taij-cij = W T(ei+ em+j )-Cij=WTei+WTem+j-Cij=U i+v j-Cij對于壹個(gè)確定白基，如果Xij

33、是基變量，則Xij >0 o由于單純形疊代在每壹步都滿足互補(bǔ)松弛條件，因此對于基變量Xij>0 ,相應(yīng)的對偶約束條件Ui+VjWCij的松弛變量壹定等于0 ,即u i+v j=c ij由于基變量壹共有 m+n-1個(gè)，因此對偶問題壹共有 m+n-1個(gè)等式約束， 再加上vn=0 ,壹共有m+n個(gè)等式，因此能夠確定 m+n個(gè)對偶變量的值，且且由對偶約束等式的特點(diǎn)，能夠由 vn=0開始，逐個(gè)遞推求得 Ui和Vj。求 出ui、vj的值以后，就能夠進(jìn)壹步計(jì)算各非基變量的檢驗(yàn)數(shù) zij-cij= Ui+Vj-Cijo例4.9用對偶變量法計(jì)算例 4.7中用西北角法得到的初始基礎(chǔ)可行解的各非基變量的

34、檢驗(yàn)數(shù) Zij-c ij。1234U1=8U2=9U3=10U4=13對于表中的7個(gè)基變量，相應(yīng)的對偶問題的約束條件為:u 1+v 1=c 11=10U 1+v 2=c 12 = 11U2+v 2=c 22=12U2+v 3=c 23 = 16U2+v 4=c 24=9U 3+V 4=c 34 = 10U4+V 4=C 44 = 13以及V4=0從V4=0開始依次能夠得到：U4=13-v 4=13-0=13u 2=9_v 4 =9-0=9u 3=10-v 4=10-0=10V2=12-u 2=12-9=3V3=16-u 2=16-9=7u1=11-v 2=11-3=8vi=10-u 1=10-

35、8=2Zij-Cij=u i+V j-Cij在求得各對偶變量 Ui, Vj的值以后，再計(jì)算檢驗(yàn)數(shù)Z13-C13=U 1+V 3-C 13=8+7-9=4-6Z14-C14=U 1 +V 4-C 14=8+0-1 5=-7Z21 -C21 =U 2+V 1 -C21 =9+2-13=-2Z31-C31=U 3+V 1-C31 =10+2-11=4-1Z32-C32 =u 3+V 2-C32=10+3-8=+5Z33-C33=U 3+V 3-C 33 = 10+7-7=+10Z41 -C41 =U 4+V 1 -C41 =13+2-14=4-1Z42-C42=U 4+V 2-C42 = 13+3-

36、13=+3Z43-C43=U 4+V 3-C43 = 13+7-12=+8將之上結(jié)果記在運(yùn)輸表上，得到30455025這個(gè)結(jié)果和用閉回路法得到的結(jié)果完全相同。例4.10用對偶變量法計(jì)算例4.7中用最小元素法得到的初始基礎(chǔ)可行解的各非基變量的檢驗(yàn)數(shù)Zij-Cij。u 1U2U3U4對于表中的7個(gè)基變量，相應(yīng)的對偶問題的約束條件為:u 1+v i=c 11 =10U 1+V 2=c 12 = 11U 1+V 4=C 14 = 15U2+V 4=C 24=9U 3+V 2=C 32=8U 3+V 3=C 33=7U4+V 4=C 44 = 13以及V4=0從V4=0開始依次能夠得到：U4=13-v

37、4=13-0=1 3u 1 =15-v 4=15-0=15u 2=9-v 4=9-0=9v 1 =10-u 1 =10-15=-5V2=11-u 1=11-15=-4u3=8-v 2=8-(-4)=12V3=7-u 3=7-12=-5Zij-Cij=u i+V j-Cij在求得各對偶變量Ui, Vj的值以后，再計(jì)算檢驗(yàn)數(shù)Z13-C13=U 1 +V 3-C 13 = 15+(-5)-9=+1Z21 -C21 =u 2+V 1-c 21 =9+(-5)-13=-9Z22-C22=U 2+V 2-C22=9+(-4)-12=-7Z23-C23=U 2+V 3-C23=9+(-5)-16=-12Z3

38、1 -C31 =U 3+V 1-C31=12+(-5)-11=-4Z34-C34=U 3+V 4-C34 = 12+0-10=+2Z41 -C41 =U 4+V 1-C41 =13+(-5)-14=-6Z42-C42=U 4+V 2-C42 = 13+(-4)-13=-4Z43-C43=U 4+V 3-C43 = 13+(-5)-12=-4將之上結(jié)果記在運(yùn)輸表上，得到123430455025這個(gè)結(jié)果和用閉回路法得到的結(jié)果完全相同。4.6.3 確定進(jìn)基變量由單純形法原理能夠知道，凡檢驗(yàn)數(shù)Zij-C ij> 0的非基變量都能夠進(jìn)基。通?？偸沁x取檢驗(yàn)數(shù)Zij-C ij>0中最大的進(jìn)基。例

39、如在上壹運(yùn)輸表中，選取Z34-C 34=2 ,即 X34 進(jìn)基。4.6.4 確定離基變量設(shè)進(jìn)基變量為Xpq ,離基變量可根據(jù)下式求出：其中（p, q）是進(jìn)基變量的下標(biāo)，（i, j）是和基變量對應(yīng)的下標(biāo)，當(dāng)前基中各基變量的值，yij是非基變量Xpq用基變量表出的系數(shù) Ypq中和基變量（i,j）對應(yīng)的元素。由前面的討論能夠知道，Ypq中元素取值為0或土 1,而且閉回路轉(zhuǎn)角處相應(yīng)的 yij的值+1 , -1相間變化。因此之上求極小化的式子相當(dāng)于在閉回路中，對 yij取+1的那些基變量的值取最小的壹個(gè)，即上式表示，當(dāng)非基變量（p, q）進(jìn)基時(shí)，導(dǎo)致 xst=0離基。例如在運(yùn)輸表123430455025

40、中，當(dāng)X34進(jìn)基時(shí)，沿閉回路4.6.5進(jìn)行基變換當(dāng)進(jìn)基變量Xpq的值由0變?yōu)椋x基變量 Xst的值由變?yōu)?時(shí)，其余基 變量的值也要相應(yīng)變化：由上式能夠見出，只有y= ±1的那些（即在閉回路轉(zhuǎn)角上的） 基變量，當(dāng)xpq 值增大時(shí)才相應(yīng)改變，其余基變量都保持不變。對應(yīng)于 y=+1轉(zhuǎn)角上的基變量減少，對應(yīng)于y=-1轉(zhuǎn)角上的基變量增加。 例如，在以下運(yùn)輸表中，當(dāng)X34進(jìn)基時(shí)，基變量 X12=1增加，X14 = 14和X32=19減少，當(dāng)進(jìn)基變量 X34 = 14時(shí)，X12=1530455025,X14=0 iSjiU?) X32=5。新的運(yùn)輸表成為:其中，X34成為新的基變量，X14成為新的

41、非基變量。用閉回路法或?qū)ε甲兞繑?shù)Z13-C 13=+1>0 ,繼續(xù)選取X13進(jìn)基，相應(yīng)的閉回路為:時(shí)，X12=15-15=0取 minX 12 ,法重新計(jì)算各非基變量的檢驗(yàn)數(shù)Zij-Cij,得到的結(jié)果見上表。其中X13的檢驗(yàn)X32 =5+15=20, X33 =31-15=16 ,新的運(yùn)輸表為30455014131213252515203184重新計(jì)算非基變量的檢驗(yàn)數(shù)Zij-Cij填入上表。能夠見出，所有非基變量的檢驗(yàn)數(shù)zij-cij<0 ,已經(jīng)獲得最優(yōu)解。最優(yōu)解的目標(biāo)函數(shù)值為25=1427 。z=10 15+9 15+9 45+8 20+7 16+10 14+13為了總結(jié)運(yùn)輸問題

42、單純形法，現(xiàn)將例 4.5.1的運(yùn)輸問題用單純形法完整地求解如下:1、首先用西北角法得到壹個(gè)初始基礎(chǔ)可行解:1520318425表中深色的格子表示基變量。2、用閉回路法或?qū)ε甲兞糠ǖ玫椒腔兞康臋z驗(yàn)數(shù)zij-c ij1112341012341314151213151612311013503045502525152031844、選擇進(jìn)基和離基變量。X33進(jìn)基，X23離基，得到新的運(yùn)輸表且計(jì)算檢驗(yàn)數(shù)Zij -C ij12343045502515203184X32進(jìn)基，X41離基，得到新的運(yùn)輸表且計(jì)算檢驗(yàn)數(shù)zij-c ij123430455025X13進(jìn)基，X12離基，得到新的運(yùn)輸表且計(jì)算檢驗(yàn)數(shù)Zij-Cij123430455025所有非基變量的檢驗(yàn)數(shù)Zij-Cij W0,得到最優(yōu)解。最優(yōu)解為,X34=14 , X44 =25 ,其X11=15 , X13 = 15 , X24 =45 , X32 =20 , X33