線性規(guī)劃運(yùn)輸問題

1、第四章 運(yùn)輸問題Chapter 4Transportation Problem4.1 運(yùn)輸問題的定義設(shè)有同一種貨物從 m 個(gè)發(fā)地 1，2， m 運(yùn)往 n 個(gè)收地 1，2， n 。第 i 個(gè)發(fā)地的供應(yīng)量（ Supply ）為 si（si0 ），第 j 個(gè)收地的需求量（ Demand ）為 dj （d j0 ）。每單位貨物從發(fā)地 i 運(yùn)到收地 j 的運(yùn)價(jià)為 cij。求一個(gè)使總運(yùn)費(fèi)最小的運(yùn)輸方案。我們假定從任一發(fā)地到任一收地都有道路通行。如果總供應(yīng)量等于總需求 量，這樣的運(yùn)輸問題稱為供求平衡的運(yùn)輸問題。我們先只考慮這一類問題。c11111jicincmcmjmn圖 4.1圖 4.1.1 是運(yùn)輸問題的

2、網(wǎng)絡(luò)表示形式。 運(yùn)輸問題也可以用線性規(guī)劃表示。設(shè) xij為從發(fā)地 i 運(yùn)往收地 j的運(yùn)量，則總運(yùn)費(fèi) 最小的線性規(guī)劃問題如下頁(yè)所示。運(yùn)輸問 題線性規(guī)劃變量個(gè)數(shù)為 nm 個(gè)，每個(gè)變量 與運(yùn)輸網(wǎng)絡(luò)的一條邊對(duì)應(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)輸

3、問題的特點(diǎn)，給出特殊的算法。minz c11x11 c12x12s.t. x11 x12c1nx1n c21x21 c22x22c2nx2ncm1xm1 cm2xm2cmnxmnx1nx21x22x2ns2x12x22xm2x1nx2nxmnx11 x12x1nx21x22x2nxm1xm2xmn在運(yùn)輸問題線性規(guī)劃模型中，令X= ( x 11 ，x 12 ， x 1n ， x21 ，x22 ，x2n ， xm1 ， xm2 ，C=(c11，c12 ， c1n ，c21 ，c22 ，c2n ， cm1 ， cm2 ，A=a11 ，a12 ， a 1n ， a21 ，a 22 ，a2n ， am1

4、 ， am2 ，111111m行=111111111n行111b=(s1，s2， sm， d1，d2，dn)Txm1xm2xmnx11x21xm1則運(yùn)輸問題的線性規(guī)劃可以寫成：xmn )cmn )amn smd1d2dn0min z= CTXs.t.AX=bX0其中 A 矩陣的列向量aij =ei+em+jei 和 em+j 是 m+n 維單位向量，1 分別在在第i 個(gè)分量和第 m+j個(gè)分量的位置上。 A 矩陣中的行與運(yùn)輸網(wǎng)絡(luò)中的節(jié)點(diǎn)對(duì)應(yīng)，前m行對(duì)應(yīng)于發(fā)地，后n 行對(duì)應(yīng)于收地； A 矩陣的列與運(yùn)輸網(wǎng)絡(luò)中的邊對(duì)應(yīng)。運(yùn)輸問題除了用網(wǎng)絡(luò)表示及線性規(guī)劃表示外，還可以用運(yùn)輸表表示：1 2 nc11x11

5、c12x12c1nx1nc21c22c2nx21x22x2ncm1cm2cmnxm1xm2xmns1s2d1d2smdn表 4.1=20=10表的行與發(fā)地對(duì)應(yīng)，列與收地對(duì)應(yīng)。第 i 行與第 j 列交叉的一格與網(wǎng)絡(luò)的一條 邊對(duì)應(yīng) （也就是與線性規(guī)劃約束矩陣的一列對(duì)應(yīng)） ，每一格的左上角小方格的數(shù)字表 明從相應(yīng)的發(fā)地 i到收地 j 的運(yùn)價(jià) cij，每一格右下角表明從相應(yīng)的發(fā)地 i到收地 j 的 運(yùn)量 xij 。表右方表明各發(fā)地的供應(yīng)量 s i ，表下方表明各需求第的需求量 d j。每一行 運(yùn)量之和表示從該發(fā)地運(yùn)往各收地的運(yùn)量之和， 它應(yīng)該等于該發(fā)地的供應(yīng)量； 同樣， 每一列運(yùn)量之和表示從各發(fā)地運(yùn)往

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

7、56x11x12x13749x21x22x231231152251020101020表 4.24.2 運(yùn)輸問題約束矩陣的性質(zhì)4.2.1 約束矩陣的秩運(yùn)輸問題約束矩陣 A 的秩為 m+n-1 。證明：因?yàn)?A 矩陣的前 m 行和后 n 行之和分別等于向量（ 1 ，1， 1），因 此秩 A<m+n ?？紤] A 的一個(gè)子矩陣A' =a1n ，a 2n ， amn ，a11，a12 ， a1n，即11111m行1A'=11n行1111m列n列刪除 A '中的第 m+n 行和第 m+n 列，得到1 1 1 11m 行1 1m 行A ''=11n 1行m列n

8、1列容易看出，秩 A'' =m+n -1 。由此m+n-1= 秩 A''秩 A'秩 A<m+n秩 A =m+n-1 。在線性規(guī)劃問題中，約束的系數(shù)矩陣要求行滿秩的，為了使運(yùn)輸問題系數(shù)矩陣 行滿秩，在 A 矩陣中增加一個(gè)列向量 em+n 形成增廣矩陣00A em nA0010這樣增廣矩陣 A 的秩就等于 m+n ，因而是行滿秩的。并且 A 中任何一個(gè)基矩陣，都必定包含單位向量em+n 。例 4.2.1 設(shè)一個(gè)運(yùn)輸網(wǎng)絡(luò)如右圖，它的系數(shù)矩陣為x11 x12x13 x21x22x23111000s1000111s2A100100d1010010d20010

9、01d3增廣矩陣為x11x12x13x21x22x23xe1110000s10001110s2Ad110010000100100d20010011d3增加的單位列向量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)輸問題對(duì)應(yīng)于第三個(gè)收點(diǎn)的約束稱為x 13 +x 23 +x a=d 3由于圖 4.3因此，對(duì)運(yùn)輸問題的任何一個(gè)可行解，都有xa=0 。4.2.2 A 矩陣的單位模性質(zhì)運(yùn)輸問題的系數(shù)矩陣 A 具有以下性質(zhì)： A 矩陣中任何一個(gè) k 階子矩陣 A（k k=1 ， 2， m+n ），都有 det Ak=

10、0 或± 1。證明：在 A 中任取一個(gè) k 階方陣 Ak ，有以下三種情況：1 、 A k中任何一列都有兩個(gè) 1，這時(shí) Ak上部的行屬于 A矩陣的前 m 行，而下 部的行屬于 A 矩陣的后 n 行，Ak 上部的各行之和以及 Ak下部各行之和都 等于向量（ 1，1， 1），因而 Ak的行線性相關(guān)，即 det Ak=0。2、 Ak 中至少有一列元素全為 0 ，這時(shí)顯然有 det A k=0 。3 、 A k中至少有一列，其中只有一個(gè) 1 。這時(shí)可以將 det Ak 按這一列展開，設(shè) 對(duì)應(yīng)于這個(gè) 1 的代數(shù)余子式為 Ak-1 ，則有det Ak=± det A k-1其中 Ak-

11、1 是 k-1 階方陣。對(duì) Ak-1 同樣有det Ak-1 =0或者det Ak-1 =± det Ak-2最后有det Ak=0或者 det Ak=± det Ak-1 =± det Ak-2= =± det A1=0 或±1。4.2.3 基矩陣的三角性設(shè) B 是 A 的一個(gè)基， B 中至少有一列只包含一個(gè) 1，否則， det B=0 不成為 個(gè)基。將 B 的行列交換，總可以使 B 成為PTBm n 11 ，對(duì)0其中 det Bm+n-1 0 ，因而 Bm+n-1 中也至少有一列只有一個(gè)Bm+n-1 再進(jìn)行行列交換，得到1P01QTB

12、9;' 00Bm n 200依次不斷對(duì)剩下的方陣進(jìn)行行列交換，最后可以得到101RB0010 0 0 1是一個(gè)上三角矩陣。例 4.2 設(shè)一個(gè)運(yùn)輸問題的系數(shù)增廣矩陣為x11x12x13x21x22x23xe1110000s1300001110s220A=1001000bd1150100100d2100010011d325取其中一個(gè)基x13x23x11x12xa10110s13001000s220B00100bd11500010d21011001d325對(duì) B 進(jìn)行行列交換，成為以下上三角矩陣xax13x23x11x1211100d32501010s130B00100bs22000010d

13、11500001d210求解相應(yīng)的方程組11100xa2501011x133000100x232000010x111500001x1210xax13x2325x13x11x1230x2320x1115x1210x12 =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.3 基在網(wǎng)絡(luò)圖和運(yùn)輸表中的表示從前一節(jié)已經(jīng)知道，運(yùn)輸問題的一個(gè)基是由 m+n 個(gè)列向量組成的，其中包括一個(gè)單位向量

14、 em+n 。在網(wǎng)絡(luò)圖上，這 m+n 個(gè)列向量對(duì)應(yīng) m+n 條邊，其中與單位向量對(duì)應(yīng)的是從最后一個(gè)收地 出發(fā)的人工邊。 網(wǎng)絡(luò)圖中的一個(gè)基具有以下性質(zhì)：1 、 一個(gè)基由 m+n 條邊組成， 其中一條是人 工邊，其余 m+n-1 條邊是原網(wǎng)絡(luò)中的邊。2 、 組成基的邊不能形成閉合回路。 若不然， 如果組成一個(gè)基的若干條邊（ i，j），（k ，j），（i，l），（k ，l）組成一個(gè)閉合回路，則這些邊對(duì)應(yīng)的系數(shù)矩陣中的列向 量 aij，akj ，ail ，akl 的線性組合aij-akj+ail-akl=（ei+em+j）-（ek+em+k ）-（ei+em+l）+（ek+em+l）=0 這些列向量線

15、性相關(guān)，顯然不能包含在一個(gè)基中。000B0 節(jié)點(diǎn) k3 、 組成基的 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 對(duì)應(yīng)的一行全為 0，即 det B=0。 B 不可能成為一個(gè)基。 例 4.3 對(duì)于 2 個(gè)發(fā)點(diǎn) 3 個(gè)收點(diǎn)的運(yùn)輸問題， 網(wǎng)絡(luò)圖如圖 4.5（a）所示。圖 4.5（b ）、 （c）、（d ）都是這個(gè)問題的基， 這些基都由 m+n-1=2+3-1=4 條邊組成， 都不構(gòu)成 回路，并且與每一個(gè)節(jié)點(diǎn)關(guān)聯(lián)。正如線性規(guī)劃矩陣的列向量組成的基一樣，一個(gè)網(wǎng)絡(luò)的基的個(gè)數(shù)是非常多的， 以上只是這些基中的幾個(gè)例子。(c)第二個(gè)基(

16、d)第三個(gè)基圖 4.54.4 基在運(yùn)輸表中的表示我們已經(jīng)知道，運(yùn)輸表中的一行對(duì)應(yīng)于一個(gè)發(fā)地，一列對(duì)應(yīng)于一個(gè)收地，表中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 的兩條邊（見下表和圖）（i，j）（i，k）（l，k）j k表 4.3如果運(yùn)輸表中有若干個(gè)格子，他們中相鄰的兩個(gè)都分

17、別位于同一行或同一列，例如在下表中六個(gè)格子（ i，j），（i，k），（l，k），（l，n），（m，n）和（ m，j），將位于同一行和同一列的兩個(gè)格子連結(jié)起來，在運(yùn)輸表中構(gòu)成一個(gè)閉回路。在相應(yīng)的網(wǎng)絡(luò)圖中，這六個(gè)格子對(duì)應(yīng)的六條邊也組成一個(gè)閉回路。（i，j）（i，k）（l，k）（l，n）（m ，n）（m，j）ilmj k n表 4.4圖 4.7iknm運(yùn)輸表中的閉回路還可以出現(xiàn)更復(fù)雜的情況，如下表和下圖所示。（i，j）（i，k）（l，j）（l，n）（m，k）（m ，n）kn表 4.5ilknm圖 4.8綜上所述，總結(jié)運(yùn)輸表中一個(gè)基必須具備的特點(diǎn)：1 、 一個(gè)基應(yīng)占表中的 m+n-1 格；2 、 構(gòu)成

18、基的同行同列格子不能構(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）系數(shù)矩陣、網(wǎng)絡(luò)圖和運(yùn)輸表x11x12x13x21x22x23xa111000000011101001000010010000100111231（ 1,1 ）（1,2 ）（ 1,3 ）2（ 2,1 ）（2,2 ）（ 2,3 ）（b） 第一個(gè)基的矩陣、網(wǎng)絡(luò)圖和運(yùn)輸表x11 x12 x13 x21 xa11100 00010 10010 01000 001011 2 3（1,1）（1,2 ）（ 1,3 ）（2,

19、1）12（c） 第二個(gè)基的矩陣、網(wǎng)絡(luò)圖和運(yùn)輸表x11 x12x22 x23 x a0010000011（1,1）（ 1,2 ）（ 2,2 ）（2,3 ）1 2 312（d）第三個(gè)基的矩陣、網(wǎng)絡(luò)圖和運(yùn)輸表x11x13x22x23xa1100000110100000010001011圖 4.12（1,1）（1,3 ）（ 2,2 ）（2,3 ）1 2 31a j BY j aB1 aB 2aBy2j4.5 非基列向量用基向量表示在線性規(guī)劃中，設(shè) B是A 矩陣的一個(gè)基，且 B=aB1，aB2，aBm，則A 中 的任一非基向量 aj（ j R）必定可以用基向量 aB1，aB2 ，a Bm 唯一地線性表出

20、， 其線性組合的系數(shù)就是 Yj，這是因?yàn)閅j=B-1aj即y1j y mjy1jaB1y2jaB2y mjaBm這就是說，向量 Yj 就是用基向量表出一個(gè)非基向量a j的系數(shù)。在運(yùn)輸問題中如果確定了一個(gè)基，非基向量aij 也可以由基向量唯一地表出， 由 于運(yùn)輸問題的特殊性，表出系數(shù) Yij 可以很方便地確定。請(qǐng)看下一例子。例 4.5 以具有 2 個(gè)發(fā)地， 3 個(gè)收地的運(yùn)輸問題為例子，這個(gè)運(yùn)輸問題的網(wǎng)絡(luò)圖和系 數(shù)矩陣如下：(1,1)(1,2)(1,3)(2,1)(2,2)( 2,3) e11100000001110100100001001000010011圖 4.13取基 B=a11 ，a12

21、，a13 ，a23 ，e a，非基向量為 a21 ，基矩陣、 網(wǎng)絡(luò)圖中的非基邊 （用 虛線表示）、基邊（用實(shí)線表示） ，并取從發(fā)地到收地的方向?yàn)楦鬟叺姆较颉?1,1)1(1,2)1(1,3)1(2,3)00B1由于任何一個(gè)非基向量總是與基向量實(shí)線性相關(guān)的，因此在網(wǎng)絡(luò)圖中任一條非基邊a ij ，有必定與若干條基邊形成閉回路。根據(jù)運(yùn)輸矩陣的結(jié)構(gòu)，對(duì)任何一個(gè)列向量aij=ei+em+j 。在上面的問題中，非基向量a21=e2+e2+1=e2 +e3基向量 a11 ，a12 ， a13， a23 可以表示為a11=e1+e2+1=e1 +e3a12=e1+e2+2=e1 +e4a13=e1+e2+3=

22、e1 +e5a23=e2+e2+3=e2 +e5a21 可以表示為：因此a21 -a11 +a13 -a23 =(e2+e3)-(e1+e3)+(e1+e5)-(e2+e5)=0a21 =a11 -a13 +a23由于基向量 a12 和 ea 不在這個(gè)回路中，它在a12 的表達(dá)式中的系數(shù)是 0 ，因此非基向量 a21 用所有基向量的表出形式為：a21 1 a11 0 a12 ( 1) a13a230 eaa11a12 a13 a23eaBy 21圖 4.15由此可以看出10Y21110從這個(gè)例子可以看出，非基向量由基向量表出的方法和表出的系數(shù)可以由該非 基向量與有關(guān)的基向量形成的回路來確定 （

23、見上圖）。選定該非基邊的方向作為閉回 路的方向，如果一個(gè)基邊出現(xiàn)在該回路中，并且與回路的方向相同，則表出系數(shù)為 -1 ，如果基邊的方向和回路的方向相反，則表出系數(shù)為 +1 ，如果基邊不在回路中， 表出系數(shù)為 0 。從給定非基邊的起點(diǎn)（發(fā)地）出發(fā)，沿著回路方向前進(jìn)，第一次遇到的基邊的 方向一定和回路方向相反，第二次遇到的基邊方向一定和回路方向相同，同向和反 向交替出現(xiàn)，因此，各基邊的表出系數(shù)一定是+1 ，-1 交替出現(xiàn)。與網(wǎng)絡(luò)圖對(duì)應(yīng)，在運(yùn)輸表中非基向量用基向量表示的方法也可以相應(yīng)得到。例 如以上的運(yùn)輸問題，相應(yīng)的運(yùn)輸表如下左表所示。1231231( 1,1 )（1,2 ）( 1,3 )1B(+1

24、)B(0)B(-1)2( 2,1 )（2,2 ）( 2,3 )2NB(+1)表 4.6對(duì)應(yīng)于基 B=a11 ，a12 ， 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ù)一定也是 +1 。凡是不在 閉回路上或不在閉回路轉(zhuǎn)角處的基向量的表出系數(shù)均為 0 。在上面的

25、表中，非基向量 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 的表出形式為： a21 1 a11 0 a12 ( 1) a13 1 a23例 4.6 設(shè)有 4 個(gè)發(fā)地， 5 個(gè)收地的運(yùn)輸問題，運(yùn)輸表和網(wǎng)絡(luò)圖如下：表 4.7取其中 m+n-1=4+5=9 個(gè)基向量 a11 ，a12 ，a14 ， a21 ，a31 ，a33 ，a34 ，a35 和 a45 ，非基向量 a42 與 基向量構(gòu)成的閉回路 如右圖。根據(jù)基向量的表出 系數(shù)由 +1

26、 開始， +1 、-1 交替的原則，以上非基向 量用這些基向量表出的形式為：a 42 =(+1) a12 +( -1) a 11 +(+1) a31 +( -1) a 35 +(+1) a 45 + 0ea如果所有基向量按以下次序排列B = a 11 ，a 12 ，a21 ，a 31 ，a33，a34，a35，a45， ea因而 a42 用這些基向量表示的表出系數(shù)圖 4.17Y42 =-1 ，+1，0，+1，0，0，-1，+1，0T4.6 運(yùn)輸問題單純形法運(yùn)輸問題單純形法的基本步驟和線性規(guī)劃一樣，包括以下步驟，但具體實(shí)施是 在運(yùn)輸表上實(shí)現(xiàn)。1 、 求得一個(gè)初始基礎(chǔ)可行解；2、 對(duì)非基變量 xi

27、j 計(jì)算檢驗(yàn)數(shù) zij-cij，根據(jù)各非基變量的檢驗(yàn)數(shù) zij-c ij 值，確定 最優(yōu)性或選擇進(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)

28、量沒有用完，則將剩余 的供應(yīng)量向收地 2 發(fā)送，依次類推，直到最后一個(gè)發(fā)地的供應(yīng)量全部運(yùn)出，最 后一個(gè)收地的需求量全部滿足為止。15 和 0 。例 4.7 給出運(yùn)輸表如下。發(fā)地 1 的供應(yīng)量為 30 ，收地 1 的需求量為 15 ，在（ 1 ，10119151513121691187101413121330-11524535025415-152031841 ）上安排運(yùn)量 15。發(fā)地 1和收地 1 的供應(yīng)量和需求量分別變?yōu)? 2 3 4發(fā)地 1 的供應(yīng)量為 15，收地 2 的需求量為 20，在（ 1 ， 2 ）上安排運(yùn)量 15，1011915151513121691187101413121341

29、24535025415-15發(fā)地 1 的供應(yīng)量變?yōu)?0 ，收地 2 的需求量變?yōu)?5 ；1 2 30 的需求量為 地 2 的供應(yīng)量變?yōu)?40 ，1收地20-15 31 84 5，發(fā)地 2 的供應(yīng)量為 45 ，在（ 2，2） 收地 2 的需求量變?yōu)?0 ；2 3上安排運(yùn)量 5，發(fā)101191515151312169511871014131213410245-5350254發(fā)地0 5-5 31 84 的供應(yīng)量為 40，收地 3 的需求量為 31，在（ 2 ， 3 ）上安排運(yùn)量 31， 發(fā)地 3 的供應(yīng)量變?yōu)?9 ，收地 3 的需求量變?yōu)?0 ；101191515151312169531118710

30、14131213410235025440-311 2 3發(fā)地 2 的供應(yīng)量為 9。收地 4 的需求量為 84 ，在（ 2，4） 地 2 的供應(yīng)量變?yōu)?0 ，收地 4 的需求量變?yōu)?75 ；1 2 3上安排運(yùn)量 9 ，發(fā)10119151515131216953191187101413121341029-93502540 0 0 84-9收地 4 的需求量為 75 ，發(fā)地 3 的供應(yīng)量為 50 ，安排（ 3 ， 發(fā)地 3 的供應(yīng)量 0，收地 4 的需求量 25 ；1 2 34 ）上的運(yùn)量為 50 ，1011915151513121695319118710501413121341020325450-

31、500 0 0 75-50的供應(yīng)量為 25 ，收地 4 的需求量為 25 ，安排（ 4，發(fā)地 4 的供應(yīng)量為 0 ，收地 4 的需求量為 0 ，供求和需求都得到滿足。1 2 3 4發(fā)地 44 ）上的運(yùn)量 25 ，5-25=000025-25=0用西北角法確定初始可行解方法簡(jiǎn)單，不會(huì)出現(xiàn)回路，而且一般情況下基變量 的個(gè)數(shù)恰為 m+n-1 個(gè)（退化的情況基變量可能少于 m+n-1 ，處理的方法在 4.7 節(jié) 中介紹），而且基變量位于每一行每一列，因而得到的是一個(gè)基礎(chǔ)可行解。西北角法 的缺點(diǎn)是在安排運(yùn)量時(shí)不考慮運(yùn)價(jià)，因而得到的初始解可能離開最優(yōu)解比較遠(yuǎn)。以 上例子中用西北角法得到的初始解的目標(biāo)函數(shù)值

32、為z=cijxij=10 15+11 15+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-dj，將收地 j的需求量改為 0；如果 si<dj，取 xij =si，并將發(fā)地 i 的供應(yīng)量改為 0，將收地 j 的需求量改為 dj-si；如果 si和 d j中有一個(gè)為 0，則不分配運(yùn)量給 xij。 分配完最小運(yùn)價(jià)的運(yùn)量后，用同樣的方法分配運(yùn)價(jià)次小的運(yùn)量，依次類推

33、，直到每 一個(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 和發(fā)地 30。10119151312169118710311413121312341302453254152031-318450-31對(duì)于 c32 =8 ，發(fā)地 3 的供應(yīng)量為 19，收地 2 的需求量為 20，安排 x32 =19 ， 的供應(yīng)量為 0 ，收地 2 的需求量為 1 。1 2101191513

34、1216911871019311413121324532541520-1908419-19對(duì)于 c13 =9，c24 =9 ，可以任選一個(gè)，但是（ 1 ， 3 ）中收地 3 的需求量為 0，安排x 24 =45 ，發(fā)地 2 的供應(yīng)量為 0，收地 4 的需求量為 39 。10119151312169451187101931141312131234130230254151084-4545-45對(duì)于 c11 =10 和c34=10 ，由于發(fā)地 3 的需求量已經(jīng)為 0，安排x 11 =15 ，發(fā)地 1 的供應(yīng)量為101191515131216945118710193114131213341203025

35、430-1515，收地 1 的需求量為 0；1 2對(duì)于 c12 =11 ，安排 x12=1，發(fā)地 1的供應(yīng)量為 14，收地 2 的需求量為 0；1234123415-1002501-103914。對(duì)于 c44 =13 ，安排 x44=25 ，發(fā)地 4的供應(yīng)量為 0，收地 4 的需求量為10119151511312169451187101931141312132512341234140025-2500039-25最后安排 x 14 =14 ，所有發(fā)地和收地的供應(yīng)量、需求量都等于0。101191515114131216945121 2 3 414-14 =001187101931141312132

36、5400014-14=00這樣就得到一個(gè)運(yùn)輸問題的初始基礎(chǔ)可行解。這個(gè)初始基礎(chǔ)可行解的目標(biāo)函數(shù)值為 z=10 15+11 1+15 14+9 45+8 19+7 31+13 25=1470 比用西北角法得到的初始基礎(chǔ)可行解的目標(biāo)函數(shù)值小。4.6.2 計(jì)算非基變量的檢驗(yàn)數(shù) zij -c ij4.5.2.1 閉回路法對(duì)于非基變量 xij ，檢驗(yàn)數(shù)為zijcijCBB aijcijCBYijcij這個(gè)閉回路轉(zhuǎn)角處的基其中向量 Yij 可由該非基變量與基變量形成的閉回路來確定， 變量對(duì)應(yīng)于 y=± 1，其余的基變量對(duì)應(yīng)于 y=0 。這樣 CTBYij 就等于轉(zhuǎn)角處基變量對(duì) 應(yīng)的 cij 依次

37、加減的值。zij -c ij例 4.9 在例 4.7 中，用西北角法得到初始基礎(chǔ)可行解，計(jì)算各非基變量的檢驗(yàn)數(shù)10119151515131216953191187105014131213251234130245350415203184非基變量（ 1，3 ）相應(yīng)的閉回路為1 234130245350254152031841，4 ）相應(yīng)的閉回路為1 2非基變量（因此 x13 的檢驗(yàn)數(shù) z13 -c 13 =(c 12 -c 22 +c 23 )-c 13 =(11-12+16)-9=+6非基變量（因此 x14 的檢驗(yàn)數(shù) z14 -c 14 =(c 12 -c 22 +c 24 )-c 14 =(1

38、1-12+9)-15=-7101191515151312169-25319118710501413121325341302453502542 ， 1 ）相應(yīng)的閉回路為1 215203184因此 x21 的檢驗(yàn)數(shù) z21 -c 21 =(c 11 -c 12 +c 22 )-c 21 =(10-11+12)-13=-2非基變量（343 ， 1 ）相應(yīng)的閉回路為1 2因此 x31 的檢驗(yàn)數(shù)z31-c 31 =(c 11 -c 12 +c 22 -c 24 +c 34 )-c 31 =(10-11+12-9+10)-11=+1用同樣的方法可以求得其他非基變量的檢驗(yàn)數(shù)z43-c 43 =(c 23 -

39、c 24 +c 44 )-c 43 =(16-9+13)-12=+8 將以上檢驗(yàn)數(shù)填入運(yùn)輸表，用“”表示。1 24101511159+615 -713-212516319911+18+57+10105014+113+312+81325313024535025415203184z32 -c 32=(c 22 -c 24 +c34 )-c 32 =(12-9+10)-8=+5 z33-c 33 =(c 23 -c 24 +c 34 )-c 33 =(16-9+10)-7=+10 z41 -c 41=(c 11 -c 12 +c23 -c 24 +c 44 )-c 41 =(10-11+12-9+1

40、3)-14=+1 z42-c 42 =(c 22 -c 24 +c 44 )-c 42 =(12-9+13)-13=+3對(duì)用最小元素法得到的初始基礎(chǔ)可行解，也可以用同樣的方法求得各非基變量的檢驗(yàn)數(shù) zij-c ij，計(jì)算過程略，計(jì)算結(jié)果見下表。4.5.2.2 對(duì)偶變量法設(shè)運(yùn)輸問題的原始問題為：min z c11x11 c12x12c1nx1n c21x21 c22x22c2nx2ncm1xm1cm2xm2cmnxmns1s2s.t.x11 x12x1nx21x22x2nxm1xm2xmnsmx11x21xm1d1x12x22xm2d2x1nx2nxmnxadnx11 x12x1nx21x22x

41、2nxm1xm2xnm 0xa:unr其中 xa是為了使矩陣 A 滿秩而增加的變量。設(shè)與前 m 個(gè)約束對(duì)應(yīng)的對(duì)偶變量為 u1，u2， um，與后 n 個(gè)約束對(duì)應(yīng)的對(duì) 偶變量為 v1，v 2， vn。則對(duì)偶問題為：max y=s 1u1+s2u2+smum+d1v1+d2v2+ +dnvns.t.u 1+v 1c11u 1+v nc1nu 2+v n c2nu m +v 1 cm1， u m，v1，v2， vn ：unr ndjvjj1u m +v n cmn vn=0 u1，u2， 以上對(duì)偶問題，可以簡(jiǎn)寫成： m max ysi uii1ui+vjcij(i=1,2, ,m； j=1,2, ) ,nvn=0u i， vj： unr對(duì)偶問題中由 m+n 個(gè)變量， mn+1 個(gè)約束。T T -1 對(duì)于運(yùn)輸問題的一個(gè)基 B ，如果能夠求出相應(yīng)的對(duì)偶變量W T=CBTB-1，就可以計(jì)算非基變量 xij 的檢驗(yàn)數(shù) zij-c ij ：T -1 T T zij-c ij=CB B