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

線性規(guī)劃運(yùn)輸問題Chapter4TransportationProblem§4.1運(yùn)輸效果的定義設(shè)有同一種貨物從m個發(fā)地XE"發(fā)地"1，2，…，m運(yùn)往n個收地XE"收地"1，2，…，n。第i個發(fā)地的供應(yīng)量XE"供應(yīng)量"〔Supply〕為si〔si≥0〕，第j個收地的需求量XE"需求量"〔Demand〕為dj〔dj≥0〕。每單位貨物從發(fā)地i運(yùn)到收地j的運(yùn)價為cij。求一個使總運(yùn)費(fèi)最小的運(yùn)輸方案。我們假定從任一發(fā)地就任一收地都有路途通行。假設(shè)總供應(yīng)量等于總需求量，這樣的運(yùn)輸效果稱為供求平衡XE"供求平衡"的運(yùn)輸效果。我們先只思索這一類效果。iim1jn1c11c1jc1nnci1cijcincm1cmjcmn圖4.1圖4.1.1是運(yùn)輸效果的網(wǎng)絡(luò)表示方式。運(yùn)輸效果也可以用線性規(guī)劃表示。設(shè)xij為從發(fā)地XE"發(fā)地"i運(yùn)往收地XE"收地"j的運(yùn)量，那么總運(yùn)費(fèi)最小的線性規(guī)劃效果如下頁所示。運(yùn)輸效果線性規(guī)劃變量個數(shù)為nm個，每個變量與運(yùn)輸網(wǎng)絡(luò)XE"運(yùn)輸網(wǎng)絡(luò)"的一條邊對應(yīng)，一切的變量都是非負(fù)的。約束個數(shù)為m+n個，全部為等式約束。前m個約束是發(fā)地的供應(yīng)量XE"供應(yīng)量"約束，后n個約束是收地的需求量XE"需求量"約束。運(yùn)輸效果約束的特點(diǎn)是約束左邊一切的系數(shù)都是0或1，而且每一列中恰有兩個系數(shù)是1，其他都是0。運(yùn)輸效果是一種線性規(guī)劃效果，當(dāng)然可以用第一章中的單純形法求解。但由于它有特殊的結(jié)構(gòu)，因此有特殊的算法。在本章中，我們將在單純形法原理的基礎(chǔ)上，依據(jù)運(yùn)輸效果的特點(diǎn)，給出特殊的算法。在運(yùn)輸效果線性規(guī)劃模型中，令X=〔x11，x12，…，x1n，x21，x22，…，x2n，……，xm1，xm2，…，xmn〕TC=〔c11，c12，…，c1n，c21，c22，…，c2n，……，cm1，cm2，…，cmn〕TA=[a11，a12，…，a1n，a21，a22，…，a2n，……，am1，am2，…，amn]T=b=〔s1，s2，…，sm，d1，d2，…，dn〕T那么運(yùn)輸效果的線性規(guī)劃可以寫成：minz=CTXs.t. AX=b X≥0其中A矩陣的列向量aij=ei+em+jei和em+j是m+n維單位向量，元素1區(qū)分在在第i個重量和第m+j個重量的位置上。A矩陣中的行與運(yùn)輸網(wǎng)絡(luò)XE"運(yùn)輸網(wǎng)絡(luò)"中的節(jié)點(diǎn)對應(yīng)，前m行對應(yīng)于發(fā)地XE"發(fā)地"，后n行對應(yīng)于收地XE"收地"；A矩陣的列與運(yùn)輸網(wǎng)絡(luò)中的邊對應(yīng)。運(yùn)輸效果除了用網(wǎng)絡(luò)表示及線性規(guī)劃表示外，還可以用運(yùn)輸表XE"運(yùn)輸表"表示：12…n1c11c12…c1ns1x11x12…x1n2c21c22…c2ns2x21x22…x2n…………mcm1cm2…cmnsmxm1xm2…xmnd1d2…dn表4.SEQ表\*ARABIC1表的行與發(fā)地XE"發(fā)地"對應(yīng)，列與收地XE"收地"對應(yīng)。第i行與第j列交叉的一格與網(wǎng)絡(luò)的一條邊對應(yīng)〔也就是與線性規(guī)劃約束矩陣的一列對應(yīng)〕，每一格的左上角小方格內(nèi)的數(shù)字說明從相應(yīng)的發(fā)地i到收地j的運(yùn)價cij，每一格右下角說明從相應(yīng)的發(fā)地i到收地j的運(yùn)量xij。表右方說明各發(fā)地的供應(yīng)量XE"供應(yīng)量"si，表下方說明各需求第的需求量XE"需求量"dj。每一行運(yùn)量之和表示從該發(fā)地運(yùn)往各收地的運(yùn)量之和，它應(yīng)該等于該發(fā)地的供應(yīng)量；異樣，每一列運(yùn)量之和表示從各發(fā)地運(yùn)往該收地的運(yùn)量之和，它應(yīng)該等于該收地的需求量。運(yùn)輸效果的網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"、線性規(guī)劃模型以及運(yùn)輸表XE"運(yùn)輸表"之間的關(guān)系可以用下表表示：網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"線性規(guī)劃模型運(yùn)輸表XE"運(yùn)輸表"節(jié)點(diǎn)發(fā)點(diǎn)i約束前m個約束表的行收點(diǎn)j后n個約束表的列邊從節(jié)點(diǎn)i到節(jié)點(diǎn)j變量xij，列向量aij表中的一格例4.1以下的運(yùn)輸效果線性規(guī)劃、網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"和運(yùn)輸表XE"運(yùn)輸表"表示同一運(yùn)輸效果。minz=8x11+5x12+6x13+7x21+4x22+9x23s.t.x11+x12+x13=15x21+x22+x23=25x11+x21=10x12+x22=20x13+x23=10x11,x12,x13,x21,x22,x23≥01122311525102010856749圖4.2123185615x11x12x13274925x21x22x23102010 表4.SEQ表\*ARABIC2§4.2運(yùn)輸效果約束矩陣的性質(zhì)4.2.1約束矩陣的秩運(yùn)輸效果約束矩陣A的秩為m+n-1。證明：由于A矩陣的前m行和后n行之和區(qū)分等于向量〔1，1，…，1〕，因此秩A<m+n。思索A的一個子矩陣A’=[a1n，a2n，…，amn，a11，a12，…，a1n]，即A’=刪除A’中的第m+n行和第m+n列，失掉A’’=容易看出，秩A’’=m+n-1。由此 m+n-1=秩A’’≤秩A’≤秩A<m+n即 秩A=m+n-1。在線性規(guī)劃效果中，約束的系數(shù)矩陣要求行滿秩的，為了使運(yùn)輸效果系數(shù)矩陣行滿秩，在A矩陣中添加一個列向量em+n構(gòu)成增廣矩陣XE"增廣矩陣"這樣增廣矩陣XE"增廣矩陣"的秩就等于m+n，因此是行滿秩的。并且中任何一個基矩陣，都肯定包括單位向量em+n。例4.2.1設(shè)一個運(yùn)輸網(wǎng)絡(luò)XE"運(yùn)輸網(wǎng)絡(luò)"如右圖，它的系數(shù)矩陣為增廣矩陣XE"增廣矩陣"為12231圖4.3添加的單位列向量em+n=e5相當(dāng)于在在網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"中添加一條邊，它與收點(diǎn)3關(guān)聯(lián)，但不與任何發(fā)點(diǎn)關(guān)聯(lián)，這條邊稱為人工邊XE"人工邊"。設(shè)這條邊上的運(yùn)輸量為xa，增廣運(yùn)輸12231圖4.3x13+x23+xa=d3由于x13+x23=d3因此，對運(yùn)輸效果的任何一個可行解，都有xa=0。4.2.2A矩陣的單位模性質(zhì)運(yùn)輸效果的系數(shù)矩陣A具有以下性質(zhì)：A矩陣中任何一個k階子矩陣Ak〔k=1，2，…m+n〕，都有detAk=0或±1。證明：在A中任取一個k階方陣Ak，有以下三種狀況：Ak中任何一列都有兩個1，這時Ak上部的行屬于A矩陣的前m行，而下部的行屬于A矩陣的后n行，Ak上部的各行之和以及Ak下部各行之和都等于向量〔1，1，…，1〕，因此Ak的行線性相關(guān)，即detAk=0。Ak中至少有一列元素全為0，這時顯然有detAk=0。Ak中至少有一列，其中只要一個1。這時可以將detAk按這一列展開，設(shè)對應(yīng)于這個1的代數(shù)余子式為Ak-1，那么有detAk=±detAk-1其中Ak-1是k-1階方陣。對Ak-1異樣有detAk-1=0或許detAk-1=±detAk-2最后有detAk=0或許detAk=±detAk-1=±detAk-2=…=±detA1=0或±1。4.2.3基矩陣的三角性設(shè)B是的一個基，B中至少有一列只包括一個1，否那么，detB=0不成為一個基。將B的行列交流，總可以使B成為其中detBm+n-1≠0，因此Bm+n-1中也至少有一列只要一個1，對Bm+n-1再停止行列交流，失掉依次不時對剩下的方陣停止行列交流，最后可以失掉是一個上三角矩陣XE"三角矩陣"。例4.2設(shè)一個運(yùn)輸效果的系數(shù)增廣矩陣XE"增廣矩陣"為=取其中一個基對B停止行列交流，成為以下上三角矩陣XE"三角矩陣"求解相應(yīng)的方程組由此失掉x12=10，x11=15，x23=20，x13=5，xa=0由A的基矩陣的三角性以及A矩陣中僅含有元素0和1，可以知道，假設(shè)運(yùn)輸效果各發(fā)地XE"發(fā)地"的供應(yīng)量XE"供應(yīng)量"和收地XE"收地"的需求量XE"需求量"都是整數(shù)，運(yùn)輸效果的任何基礎(chǔ)可行解都是整數(shù)，因此最優(yōu)解也是整數(shù)?！?.3基在網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"和運(yùn)輸表XE"運(yùn)輸表"中的表示kkj li圖4.4從前一節(jié)曾經(jīng)知道，運(yùn)輸效果的一個基是由m+n個列向量組成的，其中包括一個單位向量em+n。在網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"上，這m+n個列向量對應(yīng)m+n條邊，其中與單位向量對應(yīng)的是從最后一個收地XE"收地"動身的人工邊XE"人工邊"。網(wǎng)絡(luò)圖中的一個基具有以下性質(zhì)：一個基由m+n條邊組成，其中一條是人工邊XE"人工邊"，其他m+n-1條邊是原網(wǎng)絡(luò)中的邊。組成基的邊不能構(gòu)成閉合回路。假定不然，假設(shè)組成一個基的假定干條邊〔i，j〕，〔k，j〕，〔i，l〕，〔k，l〕組成一個閉合回路，那么這些邊對應(yīng)的系數(shù)矩陣中的列向量aij，akj，ail，akl的線性組合aij-akj+ail-akl=(ei+em+j)-(ek+em+k)-(ei+em+l)+(ek+em+l)=0這些列向量線性相關(guān)，顯然不能包括在一個基中。組成基的m+n條邊必需抵達(dá)網(wǎng)絡(luò)的每一個節(jié)點(diǎn)。假定不然，這m+n條邊都不與某一節(jié)點(diǎn)k關(guān)聯(lián)，那么相應(yīng)的基矩陣與節(jié)點(diǎn)k對應(yīng)的一行全為0，即detB=0。B不能夠成為一個基。例4.3關(guān)于2個發(fā)點(diǎn)3個收點(diǎn)的運(yùn)輸效果，網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"如圖4.5〔a〕所示。圖4.5〔b〕、〔c〕、〔d〕都是這個效果的基，這些基都由m+n-1=2+3-1=4條邊組成，都不構(gòu)成回路，并且與每一個節(jié)點(diǎn)關(guān)聯(lián)。正如線性規(guī)劃矩陣的列向量組成的基一樣，一個網(wǎng)絡(luò)的基的個數(shù)是十分多的，以上只是這些基中的幾個例子。 (a)網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖" (b)第一個基 (c)第二個基 (d)第三個基圖4.5§4.4基在運(yùn)輸表XE"運(yùn)輸表"中的表示我們曾經(jīng)知道，運(yùn)輸表XE"運(yùn)輸表"中的一行對應(yīng)于一個發(fā)地XE"發(fā)地"，一列對應(yīng)于一個收地XE"收地"，表中i行j列相交的格子表示網(wǎng)絡(luò)從發(fā)地節(jié)點(diǎn)i到收地節(jié)點(diǎn)j的一條邊。運(yùn)輸表中同一行i而不同列j和k的兩個格子〔i，j〕〔i，k〕，區(qū)分表示網(wǎng)絡(luò)中從同一發(fā)地節(jié)點(diǎn)i動身抵達(dá)不同收地節(jié)點(diǎn)j和節(jié)點(diǎn)k的兩條邊；異樣，運(yùn)輸表中位于同一列k而不同行i和l的兩個格子〔i，k〕和〔l，k〕區(qū)分表示從不同的發(fā)地節(jié)點(diǎn)動身，抵達(dá)同一收地節(jié)點(diǎn)j的兩條邊〔見下表和圖〕。iijkl圖4.6jki〔i，j〕〔i，k〕l〔l，k〕表4.SEQ表\*ARABIC3假設(shè)運(yùn)輸表XE"運(yùn)輸表"中有假定干個格子，他們中相鄰的兩個都區(qū)分位于同一行或同一列，例如在下表中六個格子〔i，j〕，〔i，k〕，〔l，k〕，〔l，n〕，〔m，n〕和〔m，j〕，將位于同一行和同一列的兩個格子連結(jié)起來，在運(yùn)輸表中構(gòu)成一個閉回路XE"閉回路"。在相應(yīng)的網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"中，這六個格子對應(yīng)的六條邊也組成一個閉回路。llnmjki圖4.7jkni〔i，j〕〔i，k〕l〔l，k〕〔l，n〕m〔m，j〕〔m，n〕 表4.SEQ表\*ARABIC4運(yùn)輸表XE"運(yùn)輸表"中的閉回路XE"閉回路"還可以出現(xiàn)更復(fù)雜的狀況，如下表和以下圖所示。llnmjki圖4.8jkni〔i，j〕〔i，k〕l〔l，j〕〔l，n〕m〔m，k〕〔m，n〕表4.SEQ表\*ARABIC5綜上所述，總結(jié)運(yùn)輸表XE"運(yùn)輸表"中一個基必需具有的特點(diǎn)：一個基應(yīng)占表中的m+n-1格；構(gòu)成基的同行同列格子不能構(gòu)成閉回路XE"閉回路"；一個基在表中所占的m+n-1個格子應(yīng)包括表的每一行和每一列。例4.4在例4.3.1中的運(yùn)輸網(wǎng)絡(luò)XE"運(yùn)輸網(wǎng)絡(luò)"的幾個基區(qū)分用網(wǎng)絡(luò)和運(yùn)輸表XE"運(yùn)輸表"的表示如下：112231圖4.9(a)系數(shù)矩陣、網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"和運(yùn)輸表XE"運(yùn)輸表"1231〔1,1〕〔1,2〕〔1,3〕2〔2,1〕〔2,2〕〔2,3〕(b)第一個基的矩陣、網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"和運(yùn)輸表XE"運(yùn)輸表"1212231圖4.101231〔1,1〕〔1,2〕〔1,3〕2〔2,1〕112231圖4.11(c)第二個基的矩陣、網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"和運(yùn)輸表XE"運(yùn)輸表" 1231〔1,1〕〔1,2〕2〔2,2〕〔2,3〕112231圖4.12(d)第三個基的矩陣、網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"和運(yùn)輸表XE"運(yùn)輸表" 1231〔1,1〕〔1,3〕2〔2,2〕〔2,3〕§4.5非基列向量用基向量表示在線性規(guī)劃中，設(shè)B是A矩陣的一個基，且B=[aB1，aB2，…，aBm]，那么A中的任一非基向量aj〔j∈R〕肯定可以用基向量aB1，aB2，…，aBm獨(dú)一地線性表出，其線性組合的系數(shù)就是Yj，這是由于Yj=B-1aj即 這就是說，向量Yj就是用基向量表出一個非基向量aj的系數(shù)。在運(yùn)輸效果中假設(shè)確定了一個基，非基向量aij也可以由基向量獨(dú)一地表出，由于運(yùn)輸效果的特殊性，表出系數(shù)Yij可以很方便地確定。請看下一例子。12231圖4.13例4.5以具有2個發(fā)地XE"發(fā)地"，3個收地XE"收地"的運(yùn)輸效果為例子，這個運(yùn)輸效果的網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖12231圖4.13取基B=[a11，a12，a13，a23，ea]，非基向量為a21，基矩陣、網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"中的非基邊〔用虛線表示〕、基邊〔用實(shí)線表示〕，并取從發(fā)地XE"發(fā)地"到收地XE"收地"的方向?yàn)楦鬟叺姆较颉?212231圖4.14由于任何一個非基向量總是與基向量實(shí)線性相關(guān)的，因此在網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"中任一條非基邊肯定與假定干條基邊構(gòu)成閉回路XE"閉回路"。依據(jù)運(yùn)輸矩陣的結(jié)構(gòu)，對任何一個列向量aij，有aij=ei+em+j。在下面的效果中，非基向量a21可以表示為：a21=e2+e2+1=e2+e3基向量a11，a12，a13，a23可以表示為：a11=e1+e2+1=e1+e3a12=e1+e2+2=e1+e4a13=e1+e2+3=e1+e5a23=e2+e2+3=e2+e5因此a21-a11+a13-a23=(e2+e3)-(e1+e3)+(e1+e5)-(e2+e5)=0即a21=a11-a13+a23由于基向量a12和ea不在這個回路中，它在a12的表達(dá)式中的系數(shù)是0，因此非基向量a21用一切基向量的表出方式為：2121231圖4.15由此可以看出從這個例子可以看出，非基向量由基向量表出的方法和表出的系數(shù)可以由該非基向量與有關(guān)的基向量構(gòu)成的回路來確定〔見上圖〕。選定該非基邊的方向作為閉回路XE"閉回路"的方向，假設(shè)一個基邊出如今該回路中，并且與回路的方向相反，那么表出系數(shù)為-1，假設(shè)基邊的方向和回路的方向相反，那么表出系數(shù)為+1，假設(shè)基邊不在回路中，表出系數(shù)為0。從給定非基邊的終點(diǎn)〔發(fā)地XE"發(fā)地"〕動身，沿著回路方向行進(jìn)，第一次遇到的基邊的方向一定和回路方向相反，第二次遇到的基邊方向一定和回路方向相反，同向和反向交替出現(xiàn)，因此，各基邊的表出系數(shù)一定是+1，-1交替出現(xiàn)。與網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"對應(yīng)，在運(yùn)輸表XE"運(yùn)輸表"中非基向量用基向量表示的方法也可以相應(yīng)失掉。例如以上的運(yùn)輸效果，相應(yīng)的運(yùn)輸表如下左表所示。1231231〔1,1〕〔1,2〕〔1,3〕1B(+1)B(0)B(-1)2〔2,1〕〔2,2〕〔2,3〕2NB(+1)表4.SEQ表\*ARABIC6對應(yīng)于基B=[a11，a12，a13，a23，ea]的格子為用B表示，非基向量a21相應(yīng)的格子用N表示，見下面右表。運(yùn)輸表XE"運(yùn)輸表"中非基向量用用基向量表出的系數(shù)是這樣確定的：〔按任一方向〕沿著表中的閉回路XE"閉回路"行進(jìn)，在第一個轉(zhuǎn)角處基向量的表出系數(shù)為+1，下一個轉(zhuǎn)角處基向量的表出系數(shù)為-1，以后依次交替變化，由于沿閉回路回到動身的非基向量以前一定要經(jīng)過奇數(shù)次轉(zhuǎn)角，因此最后一個轉(zhuǎn)角處的基向量的表出系數(shù)一定也是+1。凡是不在閉回路上或不在閉回路轉(zhuǎn)角處的基向量的表出系數(shù)均為0。在下面的表中，非基向量N〔2，1〕與基向量B〔1，1〕、B〔1，3〕、B〔2，3〕構(gòu)成一個閉回路XE"閉回路"，相應(yīng)的表出系數(shù)依次為+1、-1和+1；基向量B〔1，2〕不在閉回路的轉(zhuǎn)角處，表出系數(shù)為0。因此，非基向量a21的表出方式為：例4.6設(shè)有4個發(fā)地XE"發(fā)地"，5個收地XE"收地"的運(yùn)輸效果，運(yùn)輸表XE"運(yùn)輸表"和網(wǎng)絡(luò)圖XE"網(wǎng)絡(luò)圖"如下：1134223451圖4.16123451BB2B3BBBB4NB表4.SEQ表\*ARABIC71134223451y=-1y=+1y=+1y=-1y=+1圖4.17取其中m+n-1=4+5=9個基向量a11，a12，a14，a21，a31，a33，a34，a35和a45，非基向量a42與基向量構(gòu)成的閉回路XE"閉回路" 如右圖。依據(jù)基向量的表出系數(shù)由+1末尾，+1、-1交替的原那么，以上非基向量用這些基向量表出的方式為：a42=(+1)a12+(-1)a11+(+1)a31+(-1)a35+(+1)a45+0ea假設(shè)一切基向量按以下次第陳列B=[a11，a12，a21，a31，a33，a34，a35，a45，ea]因此a42用這些基向量表示的表出系數(shù)Y42=[-1，+1，0，+1，0，0，-1，+1，0]T§4.6運(yùn)輸效果單純形法運(yùn)輸效果單純形法的基本步驟和線性規(guī)劃一樣，包括以下步驟，但詳細(xì)實(shí)施是在運(yùn)輸表XE"運(yùn)輸表"上完成。求得一個初始基礎(chǔ)可行解；對非基變量xij計(jì)算檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij，依據(jù)各非基變量的檢驗(yàn)數(shù)zij-cij值，確定最優(yōu)性或選擇進(jìn)基變量；當(dāng)進(jìn)基變量xij進(jìn)基時，依據(jù)基變量的變化，求出最先降為0的基變量確定為離基變量；停止基變換，取得新的基礎(chǔ)可行解并轉(zhuǎn)步驟2。4.6.1確定初始基礎(chǔ)可行解西北角法XE"西北角法"西北角法XE"西北角法"是按發(fā)地XE"發(fā)地"和收地XE"收地"的編號為序，依次順序供應(yīng)的原那么取得初始基礎(chǔ)可行解的一種方法。它是從確定發(fā)地1到收地1的運(yùn)量末尾。這個位置按地圖的方位來說是西北角，因此得名。從發(fā)地1到收地1的運(yùn)量取發(fā)地1的供應(yīng)量XE"供應(yīng)量"〔30〕和收地1的需求量XE"需求量"〔15〕兩者中小的一個布置，假設(shè)發(fā)地1的供應(yīng)量沒有用完，那么將剩余的供應(yīng)量向收地2發(fā)送，…，依次類推，直到最后一個發(fā)地的供應(yīng)量全部運(yùn)出，最后一個收地的需求量全部滿足為止。例4.7給出運(yùn)輸表XE"運(yùn)輸表"如下。發(fā)地XE"發(fā)地"1的供應(yīng)量XE"供應(yīng)量"為30，收地XE"收地"1的需求量XE"需求量"為15，在〔1，1〕上布置運(yùn)量15。發(fā)地1和收地1的供應(yīng)量和需求量區(qū)分變?yōu)?5和0。12341101191530-151521312169453118710504141312132515-15203184發(fā)地XE"發(fā)地"1的供應(yīng)量XE"供應(yīng)量"為15，收地XE"收地"2的需求量XE"需求量"為20，在〔1，2〕上布置運(yùn)量15，發(fā)地1的供應(yīng)質(zhì)變?yōu)?，收地2的需求質(zhì)變?yōu)?；12341101191515-151515213121694531187105041413121325020-153184收地XE"收地"2的需求量XE"需求量"為5，發(fā)地XE"發(fā)地"2的供應(yīng)量XE"供應(yīng)量"為45，在〔2，2〕上布置運(yùn)量5，發(fā)地2的供應(yīng)質(zhì)變?yōu)?0，收地2的需求質(zhì)變?yōu)?；123411011915015152131216945-553118710504141312132505-53184發(fā)地XE"發(fā)地"2的供應(yīng)量XE"供應(yīng)量"為40，收地XE"收地"3的需求量為31，在〔2，3〕上布置運(yùn)量31，發(fā)地3的供應(yīng)質(zhì)變?yōu)?，收地3的需求量XE"需求量"變?yōu)?；123411011915015152131216940-31531311871050414131213250031-3184發(fā)地XE"發(fā)地"2的供應(yīng)量XE"供應(yīng)量"為9。收地XE"收地"4的需求量XE"需求量"為84，在〔2，4〕上布置運(yùn)量9，發(fā)地2的供應(yīng)質(zhì)變?yōu)?，收地4的需求質(zhì)變?yōu)?5；12341101191501515213121699-953193118710504141312132500084-9收地XE"收地"4的需求量XE"需求量"為75，發(fā)地XE"發(fā)地"3的供應(yīng)量XE"供應(yīng)量"為50，布置〔3，4〕上的運(yùn)量為50，發(fā)地3的供應(yīng)量0，收地4的需求量25；123411011915015152131216905319311871050-50504141312132500075-50發(fā)地XE"發(fā)地"4的供應(yīng)量XE"供應(yīng)量"為25，收地XE"收地"4的需求量XE"需求量"為25，布置〔4，4〕上的運(yùn)量25，發(fā)地4的供應(yīng)量為0，收地4的需求量為0，供求和需求都失掉滿足。123411011915015152131216905319311871005041413121325-25=02500025-25=0用西北角法XE"西北角法"確定初始可行解方法復(fù)雜，不會出現(xiàn)回路，而且普通狀況下基變量的個數(shù)恰為m+n-1個〔退步的狀況基變量能夠少于m+n-1，處置的方法在4.7節(jié)中引見〕，而且基變量位于每一行每一列，因此失掉的是一個基礎(chǔ)可行解。西北角法的缺陷是在布置運(yùn)量時不思索運(yùn)價，因此失掉的初始解能夠分開最優(yōu)解比擬遠(yuǎn)。以上例子中用西北角法失掉的初始解的目的函數(shù)值為z=Σcijxij=1015+1115+125+1631+99+1050+1325=1777最小元素法XE"最小元素法"這種方法是按運(yùn)價由小到大的順序布置運(yùn)量。先從各運(yùn)價中找到最小運(yùn)價，設(shè)為cij，然后比擬供應(yīng)量XE"供應(yīng)量"si和需求量XE"需求量"dj，假設(shè)si>dj，取xij=dj，并將發(fā)地XE"發(fā)地"i的供應(yīng)量改為si-dj，將收地XE"收地"j的需求量改為0；假設(shè)si<dj，取xij=si，并將發(fā)地i的供應(yīng)量改為0，將收地j的需求量改為dj-si；假設(shè)si和dj中有一個為0，那么不分配運(yùn)量給xij。分配完最小運(yùn)價的運(yùn)量后，用異樣的方法分配運(yùn)價次小的運(yùn)量，依次類推，直到每一個發(fā)地的供應(yīng)量和每一個收地的需求量都為0。以下是用最小元素法確定運(yùn)輸效果的初始可行解的例子。例4.8給出運(yùn)輸表XE"運(yùn)輸表"如下。最小運(yùn)價為c33=7，發(fā)地XE"發(fā)地"3的供應(yīng)量XE"供應(yīng)量"為50，收地XE"收地"3的需求量XE"需求量"為31，布置運(yùn)量x33=31。發(fā)地3和收地3的供應(yīng)量和需求量區(qū)分變?yōu)?9和0。123411011915302131216945311871050-313141413121325152031-3184關(guān)于c32=8，發(fā)地XE"發(fā)地"3的供應(yīng)量XE"供應(yīng)量"為19，收地XE"收地"2的需求量XE"需求量"為20，布置x32=19，發(fā)地3的供應(yīng)量為0，收地2的需求量為1。123411011915302131216945311871019-191931414131213251520-19084關(guān)于c13=9，c24=9，可以任選一個，但是〔1，3〕中收地XE"收地"3的需求量XE"需求量"為0，布置x24=45，發(fā)地XE"發(fā)地"2的供應(yīng)量XE"供應(yīng)量"為0，收地4的需求量為39。123411011915302131216945-454531187100193141413121325151084-45關(guān)于c11=10和c34=10，由于發(fā)地XE"收地"3的需求量XE"需求量"曾經(jīng)為0，布置x11=15，發(fā)地XE"發(fā)地"1的供應(yīng)量XE"供應(yīng)量"為15，收地1的需求量為0；12341101191530-1515213121690453118710019314141312132515-151039關(guān)于c12=11，布置x12=1，發(fā)地XE"發(fā)地"1的供應(yīng)量XE"供應(yīng)量"為14，收地XE"收地"2的需求量XE"需求量"為0；12341101191515-1151213121690453118710019314141312132501-1039關(guān)于c44=13，布置x44=25，發(fā)地XE"發(fā)地"4的供應(yīng)量XE"供應(yīng)量"為0，收地XE"收地"4的需求量XE"需求量"為14。123411011915141512131216904531187100193141413121325-252500039-25最后布置x14=14，一切發(fā)地XE"發(fā)地"和收地XE"收地"的供應(yīng)量XE"供應(yīng)量"、需求量XE"需求量"都等于0。12341101191514-14=0151142131216904531187100193141413121302500014-14=0這樣就失掉一個運(yùn)輸效果的初始基礎(chǔ)可行解。這個初始基礎(chǔ)可行解的目的函數(shù)值為z=1015+111+1514+945+819+731+1325=1470比用西北角法XE"西北角法"失掉的初始基礎(chǔ)可行解的目的函數(shù)值小。4.6.2計(jì)算非基變量的檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij4.5.2.1閉回路XE"閉回路"法關(guān)于非基變量xij，檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"為其中向量Yij可由該非基變量與基變量構(gòu)成的閉回路XE"閉回路"來確定，這個閉回路轉(zhuǎn)角處的基變量對應(yīng)于y=±1，其他的基變量對應(yīng)于y=0。這樣就等于轉(zhuǎn)角處基變量對應(yīng)的cij依次加減的值。例4.91234110119153015152131216945531931187105050414131213252515203184非基變量〔1，3〕相應(yīng)的閉回路XE"閉回路"為1234+61+610119153015152131216945531931187105050414131213252515203184因此x13的檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)" z13-c13=(c12-c22+c23)-c13=(11-12+16)-9=+6。非基變量〔1，4〕相應(yīng)的閉回路XE"閉回路"為1234-71-710119153015152131216945531931187105050414131213252515203184因此x14的檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)" z14-c14=(c12-c22+c24)-c14=(11-12+9)-15=-7非基變量〔2，1〕相應(yīng)的閉回路XE"閉回路"為123411011915301515-22-2131216945531931187105050414131213252515203184因此x21的檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)" z21-c21=(c11-c12+c22)-c21=(10-11+12)-13=-2非基變量〔3，1〕相應(yīng)的閉回路XE"閉回路"為12341101191530151521312169455319+13+11187105050414131213252515203184因此x31的檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"z31-c31=(c11-c12+c22-c24+c34)-c31=(10-11+12-9+10)-11=+1用異樣的方法可以求得其他非基變量的檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"z32-c32=(c22-c24+c34)-c32=(12-9+10)-8=+5z33-c33=(c23-c24+c34)-c33=(16-9+10)-7=+10z41-c41=(c11-c12+c23-c24+c44)-c41=(10-11+12-9+13)-14=+1z42-c42=(c22-c24+c44)-c42=(12-9+13)-13=+3z43-c43=(c23-c24+c44)-c43=(16-9+13)-12=+8將以上檢驗(yàn)數(shù)填入運(yùn)輸表XE"運(yùn)輸表"，用〝○〞表示。1234+3+1+1+8-2+3+1+1+8-2+6+5-7101191530151521312169455319+10+101187105050414131213252515203184對用最小元素法失掉的初始基礎(chǔ)可行解，也可以用異樣的方法求得各非基變量的檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij，計(jì)算進(jìn)程略，計(jì)算結(jié)果見下表。1234-9-9-7-12-4+2-6-4-4+1111011915301511421312169454531187105019314141312132525152031844.5.2.2對偶變量法XE"對偶變量法"設(shè)運(yùn)輸效果的原始效果為：其中xa是為了使矩陣A滿秩而添加的變量。設(shè)與前m個約束對應(yīng)的對偶變量為u1，u2，…，um，與后n個約束對應(yīng)的對偶變量為v1，v2，…，vn。那么對偶效果為：maxy=s1u1+s2u2+…+smum+d1v1+d2v2+…+dnvns.t. u1+v1≤c11 … u1+vn≤c1n … u2+v1≤c21 … u2+vn≤c2n … um+v1≤cm1 … um+vn≤cmn vn=0 u1，u2，…，um，v1，v2，…，vn：unr以上對偶效果，可以簡寫成： ui+vj≤cij (i=1,2,…,m；j=1,2,…,n) vn=0 ui，vj：unr對偶效果中由m+n個變量，mn+1個約束。關(guān)于運(yùn)輸效果的一個基B，假設(shè)可以求出相應(yīng)的對偶變量WT=CBTB-1，就可以計(jì)算非基變量xij的檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij：zij-cij=CBTB-1aij-cij=WTaij-cij=WT(ei+em+j)-cij=WTei+WTem+j-cij=ui+vj-cij關(guān)于一個確定的基，假設(shè)xij是基變量，那么xij>0。由于單純形疊代在每一步都滿足互補(bǔ)松弛條件，因此關(guān)于基變量xij>0，相應(yīng)的對偶約束條件ui+vj≤cij的松弛變量一定等于0，即ui+vj=cij由于基變量一共有m+n-1個，因此對偶效果一共有m+n-1個等式約束，再加上vn=0，一共有m+n個等式，因此可以確定m+n個對偶變量的值，并且由對偶約束等式的特點(diǎn)，可以由vn=0末尾，逐一遞推求得ui和vj。求出ui、vj的值以后，就可以進(jìn)一步計(jì)算各非基變量的檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij=ui+vj-cij。例4.9用對偶變量法XE"對偶變量法"計(jì)算例4.7中用西北角法XE"西北角法"失掉的初始基礎(chǔ)可行解的各非基變量的檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij。123411011915u1=8151521312169u2=953193118710u3=1050414131213u4=1325v1=2v2=3v3=7v4=0關(guān)于表中的7個基變量，相應(yīng)的對偶效果的約束條件為：u1+v1=c11=10 u1+v2=c12=11 u2+v2=c22=12 u2+v3=c23=16 u2+v4=c24=9 u3+v4=c34=10u4+v4=c44=13以及 v4=0從v4=0末尾依次可以失掉： u4=13-v4=13-0=13 u2=9-v4=9-0=9 u3=10-v4=10-0=10 v2=12-u2=12-9=3 v3=16-u2=16-9=7 u1=11-v2=11-3=8 v1=10-u1=10-8=2在求得各對偶變量ui，vj的值以后，再計(jì)算檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij=ui+vj-cijz13-c13=u1+v3-c13=8+7-9=+6 z14-c14=u1+v4-c14=8+0-15=-7z21-c21=u2+v1-c21=9+2-13=-2 z31-c31=u3+v1-c31=10+2-11=+1z32-c32=u3+v2-c32=10+3-8=+5 z33-c33=u3+v3-c33=10+7-7=+10z41-c41=u4+v1-c41=13+2-14=+1 z42-c42=u4+v2-c42=13+3-13=+3z43-c43=u4+v3-c43=13+7-12=+8將以上結(jié)果記在運(yùn)輸表XE"運(yùn)輸表"上，失掉1234+3+1+1+8-2+6+5-71+3+1+1+8-2+6+5-7101191530151521312169455319+103+101187105050414131213252515203184這個結(jié)果與用閉回路XE"閉回路"法失掉的結(jié)果完全相反。例4.10用對偶變量法XE"對偶變量法"計(jì)算例4.7中用最小元素法失掉的初始基礎(chǔ)可行解的各非基變量的檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij。123411011915u11511421312169u2453118710u31931414131213u425v1v2v3v4關(guān)于表中的7個基變量，相應(yīng)的對偶效果的約束條件為：u1+v1=c11=10u1+v2=c12=11u1+v4=c14=15u2+v4=c24=9u3+v2=c32=8u3+v3=c33=7u4+v4=c44=13以及 v4=0從v4=0末尾依次可以失掉： u4=13-v4=13-0=13 u1=15-v4=15-0=15 u2=9-v4=9-0=9 v1=10-u1=10-15=-5 v2=11-u1=11-15=-4 u3=8-v2=8-(-4)=12 v3=7-u3=7-12=-5在求得各對偶變量ui，vj的值以后，再計(jì)算檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij=ui+vj-cijz13-c13=u1+v3-c13=15+(-5)-9=+1z21-c21=u2+v1-c21=9+(-5)-13=-9z22-c22=u2+v2-c22=9+(-4)-12=-7z23-c23=u2+v3-c23=9+(-5)-16=-12z31-c31=u3+v1-c31=12+(-5)-11=-4z34-c34=u3+v4-c34=12+0-10=+2z41-c41=u4+v1-c41=13+(-5)-14=-6z42-c42=u4+v2-c42=13+(-4)-13=-4z43-c43=u4+v3-c43=13+(-5)-12=-4將以上結(jié)果記在運(yùn)輸表XE"運(yùn)輸表"上，失掉1234-9-7-9-7-12-4+2-6-4-4+1101191530151142131216945453118710501931414131213252515203184這個結(jié)果與用閉回路XE"閉回路"法失掉的結(jié)果完全相反。4.6.3確定進(jìn)基變量由單純形法原理可以知道，凡檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij≥0的非基變量都可以進(jìn)基。通?？偸沁x取檢驗(yàn)數(shù)zij-cij≥0中最大的進(jìn)基。例如在上一運(yùn)輸表XE"運(yùn)輸表"中，選取z34-c34=2，即x34進(jìn)基。4.6.4確定離基變量設(shè)進(jìn)基變量為xpq，離基變量可依據(jù)下式求出：其中〔p，q〕是進(jìn)基變量的下標(biāo)，〔i，j〕是與基變量對應(yīng)的下標(biāo)，以后基中各基變量的值，yij是非基變量xpq用基變量表出的系數(shù)Ypq中與基變量〔i，j〕對應(yīng)的元素。由前面的討論可以知道，Ypq中元素取值為0或±1，而且閉回路XE"閉回路"轉(zhuǎn)角處相應(yīng)的yij的值+1，-1相間變化。因此以上求極小化的式子相當(dāng)于在閉回路中，對yij取+1的那些基變量的值取最小的一個，即上式表示，當(dāng)非基變量〔p，q〕進(jìn)基時，招致xst=0離基。例如在運(yùn)輸表XE"運(yùn)輸表"1234-4+1+2-4-6-4-12-71-4+1+2-4-6-4-12-710119153015114-92-9131216945453118710501931414131213252515203184中，當(dāng)x34進(jìn)基時，沿閉回路XE"閉回路"1115+2+211481019取min{x14,x32}=min{14,19}=14，因此當(dāng)x34=14進(jìn)基時，x14=0離基。4.6.5停止基變換當(dāng)進(jìn)基變量xpq的值由0變?yōu)?，離基變量xst的值由變?yōu)?時，其他基變量的值也要相應(yīng)變化：由上式可以看出，只要y=±1的那些〔即在閉回路XE"閉回路"轉(zhuǎn)角上的〕基變量，當(dāng)xpq值增大時才相應(yīng)改動，其他基變量都堅(jiān)持不變。對應(yīng)于y=+1轉(zhuǎn)角上的基變量增加，對應(yīng)于y=-1轉(zhuǎn)角上的基變量添加。例如，在以下運(yùn)輸表XE"運(yùn)輸表"中，當(dāng)x34進(jìn)基時，基變量x12=1添加，x14=14和x32=19增加，當(dāng)進(jìn)基變量x34=14時，x12=15，x14=0離基，x32=5。新的運(yùn)輸表成為：1234-7-10-7-10-4-4-2-2-2-9+1101191530151521312169454531187105053114414131213252515203184其中，x34成為新的基變量，x14成為新的非基變量。用閉回路XE"閉回路"法或?qū)ε甲兞糠╔E"對偶變量法"重新計(jì)算各非基變量的檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij，失掉的結(jié)果見上表。其中x13的檢驗(yàn)數(shù)z13-c13=+1>0，繼續(xù)選取x13進(jìn)基，相應(yīng)的閉回路為：+111+191587531取min{x12，x33}=min{15，31}=15，當(dāng)x13=15時，x12=15-15=0，x32=5+15=20，x33=31-15=16，新的運(yùn)輸表XE"運(yùn)輸表"為1234-7-1-7-1-10-4-4-2-2-2-91011915301515213121694545311871050201614414131213252515203184重新計(jì)算非基變量的檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij填入上表?？梢钥闯?，一切非基變量的檢驗(yàn)數(shù)zij-cij<0，曾經(jīng)取得最優(yōu)解。最優(yōu)解的目的函數(shù)值為z=1015+915+945+820+716+1014+1325=1427。為了總結(jié)運(yùn)輸效果單純形法，現(xiàn)將例4.5.1的運(yùn)輸效果1234110119153021312169453118710504141312132515203184用單純形法完整地求解如下：首先用西北角法XE"西北角法"失掉一個初始基礎(chǔ)可行解：1234110119153015152131216945531931187105050414131213252515203184表中深色的格子表示基變量。用閉回路XE"閉回路"法或?qū)ε甲兞糠ㄊУ舴腔兞康臋z驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij1234-7+5-7+5+6-2+10+8+1+1+3101191530151521312169455319311871050504141312132525152031844、選擇進(jìn)基和離基變量。x33進(jìn)基，x23離基，失掉新的運(yùn)輸表XE"運(yùn)輸表"并計(jì)算檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij1234+5+3+1-4-2+1-10-2-71+5+3+1-4-2+1-10-2-7101191530151521312169455403118710503119414131213252515203184x32進(jìn)基，x41離基，失掉新的運(yùn)輸表XE"運(yùn)輸表"并計(jì)算檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij1234+1-2-2-4-4-10-5-21+1-2-2-4-4-10-5-21011915301515-72-71312169454531187105053114414131213252515203184x13進(jìn)基，x12離基，失掉新的運(yùn)輸表XE"運(yùn)輸表"并計(jì)算檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij1234-3-6-3-6-5-10-4-4-2-2-11011915301515213121694545311871050201614414131213252515203184一切非基變量的檢驗(yàn)數(shù)XE"檢驗(yàn)數(shù)"zij-cij≤0，失掉最優(yōu)解。最優(yōu)解為x11=15，x13=15，x24=45，x32=20，x33=16，x34=14，x44=25，其他xij=0min z=1015+915+945+820+716+1014+1325=1427§4.7幾種特殊的運(yùn)輸效果4.7.1運(yùn)輸路途不完全的效果設(shè)從發(fā)地XE"發(fā)地"i到收地XE"收地"j不允許經(jīng)過，可虛設(shè)一條從發(fā)地i到收地j的運(yùn)輸線路，并設(shè)這條運(yùn)輸線路上的運(yùn)費(fèi)cij=M，M為足夠大的正數(shù)，這樣優(yōu)化的結(jié)果在〔i，j〕上不會布置運(yùn)量。例4.7.1設(shè)一個運(yùn)輸效果如以下圖所示。其中從發(fā)點(diǎn)2到收點(diǎn)2沒有運(yùn)輸路途。虛設(shè)一條從發(fā)點(diǎn)2到收點(diǎn)2的運(yùn)輸路途，并設(shè)相應(yīng)的運(yùn)價c22=M。運(yùn)輸表XE"運(yùn)輸表"及用西北角法XE"西北角法"失掉的初始解如下表：221