2運(yùn)輸問題解析

第二章運(yùn)輸問題【教學(xué)內(nèi)容】運(yùn)輸問題的基本概念，表上作業(yè)法，不平衡運(yùn)輸問題的求解?！窘虒W(xué)要求】要求學(xué)生理解運(yùn)輸問題基本概念、解的性質(zhì)，掌握表上作業(yè)法，并能將不平衡運(yùn)輸問題轉(zhuǎn)化為平衡運(yùn)輸問題求解，復(fù)雜的運(yùn)輸問題可用LINGO軟件求解?！窘虒W(xué)重點(diǎn)】運(yùn)輸問題解的性質(zhì)，運(yùn)輸問題的表上作業(yè)法，檢驗(yàn)數(shù)的求法及運(yùn)量的調(diào)整，運(yùn)輸模型的建立?！窘虒W(xué)難點(diǎn)】表上作業(yè)法、求檢驗(yàn)數(shù)的閉回路法及位勢法。【教材內(nèi)容及教學(xué)過程】運(yùn)輸問題（TransportationProblem，簡記為TP）是一類常見而且極其特殊的線性規(guī)劃問題.它最早是從物資調(diào)運(yùn)工作中提出來的，是物流優(yōu)化管理的重要的內(nèi)容之一.從理論上講，運(yùn)輸問題也可用單純形法來求解，但是由于運(yùn)輸問題涉及的變量及約束條件較多，而其數(shù)學(xué)模型具有特殊的結(jié)構(gòu)，所以存在一種比單純形法更簡便的計(jì)算方法，一一表上作業(yè)法，用表上作業(yè)法來求解運(yùn)輸問題比用單純形法可節(jié)約計(jì)算時(shí)間與計(jì)算費(fèi)用.但表上作業(yè)法的實(shí)質(zhì)仍是單純形法.本章首先介紹運(yùn)輸問題的數(shù)學(xué)模型及其特點(diǎn)；接著介紹表上作業(yè)法及主要步驟，表上作業(yè)法與單純形法的關(guān)系；通過運(yùn)輸問題的解決，可充分體現(xiàn)表上作業(yè)法的簡便和單純形法的魅力.最后給出運(yùn)輸問題的一些應(yīng)用例子.第一節(jié)運(yùn)輸問題的模型§1?1問題的提出一般的運(yùn)輸問題就是要解決把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地，在每個(gè)產(chǎn)地的供應(yīng)量與每個(gè)銷地的需求量已知，并知道各地之間的運(yùn)輸單價(jià)的前提下，如何確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案。例2?1?1某公司從兩個(gè)產(chǎn)地氣、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)最??？

表2.1.1銷產(chǎn)、、地地BBB3產(chǎn)量A1646200A2655300銷量150150200解：此為產(chǎn)銷平衡的運(yùn)輸問題，總產(chǎn)量=總銷量設(shè)七.為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表表2.1.2地B]B2B3產(chǎn)量Axx12x13200Ax21x22x23300銷量150150200模型為minf-6x+4x+6x+6x+5x+5x@十工+x+x+300s?l212223x+x=150<x12+x22=150x13+x23=200^xj>0(i=1,2;j=1,2,3)系數(shù)矩陣為111000000111100100010010001001可以看出運(yùn)輸問題模型系數(shù)矩陣有如下特征:（1）共有m+n行，分別表示各產(chǎn)地和銷地；mxn列，分別表示各決策變量；（2）每列只有兩個(gè)1，其余為0,分別表示只有一個(gè)產(chǎn)地和一個(gè)銷地被使用。一般運(yùn)輸問題的提法：

假設(shè)A,A,...A表示某物資的m個(gè)產(chǎn)地；B,B，…,B表示某物資的n個(gè)銷地;12m12nS表示產(chǎn)地A,的產(chǎn)量；dj表示銷地B的銷量；*表示把物資從產(chǎn)地A,運(yùn)往銷地Bj的單位運(yùn)價(jià)。如果則稱該運(yùn)輸問題為產(chǎn)銷平衡的運(yùn)輸問題;否則，稱為產(chǎn)銷不平衡的運(yùn)輸問題。則稱該運(yùn)輸問題為產(chǎn)銷平衡的運(yùn)輸問題;否則，稱為產(chǎn)銷不平衡的運(yùn)輸問題。將變量與數(shù)據(jù)表合并起來表2.1.3運(yùn)輸問題數(shù)據(jù)表將變量與數(shù)據(jù)表合并起來\銷產(chǎn)\地地\B]B2■…Bn產(chǎn)量ACC■…CS111121n1ACC■…CS221222n2::::::ACC■…CSmm1m2mnm銷量dd■…d12n表2.1.4運(yùn)輸問題變量表銷產(chǎn)^\地地B]B2■…Bn產(chǎn)量Axx■…xS111121n1Axx■…xS221222n2::::::Axx■…xSmm1m2mnm銷量dd■…d12n

1C11xC12x12■…C1nx1nS]氣C21x21C22x22■…C2nx2nS2:■■■1■■■1:■■■1:AmCm1xm1Cm2xm2■…CmnxmnSm銷量d1d2■…dn于是得到一般運(yùn)輸問題的數(shù)學(xué)模型minf空i=1J=1Ex<S(i=1,2,—m)J=1(2.1.1)s.t2x寸J(>,=)dj(J=1,2,...n)iTxj>0(i=1,2,…m;J=1,2,…n)(2.1.1)此約束中前m個(gè)為產(chǎn)量約束，后n個(gè)為銷量約束。平衡的運(yùn)輸問題其約束條件為：minf點(diǎn)i=1J=1

Ex=S(i=1,2,...m)j=i(2.1.2)s.t<Ex=d(j=1,2,…n)i=1x>0(i=1,2,…m;j=1,2,…n)(2.1.2)可以看出：在產(chǎn)銷平衡問題中，前m個(gè)為產(chǎn)量約束式、后n個(gè)為銷量約束式成為等式。在實(shí)際問題建立運(yùn)輸問題模型時(shí)，還會(huì)出現(xiàn)如下一些變化：（1）有時(shí)問題表面看不是運(yùn)輸問題，但其仍要求費(fèi)用最低或要求目標(biāo)函數(shù)（利潤最大或營業(yè)額）最大化，仍可看成運(yùn)輸問題；（2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，模型中可直接加入（等式或不等式）約束；（3）產(chǎn)銷不平衡的情況。當(dāng)銷量大于產(chǎn)量時(shí)可加入一個(gè)虛設(shè)的產(chǎn)地去生產(chǎn)不足的物資，這相當(dāng)于在前m個(gè)產(chǎn)量約束式每一式中加上1個(gè)松弛變量，共m個(gè)；當(dāng)產(chǎn)量大于銷量時(shí)可加入一個(gè)虛設(shè)的銷地去消化多余的物資，這相當(dāng)于在后n個(gè)為銷量約束式每一式中加上1個(gè)松弛變量，共n個(gè)。運(yùn)輸問題是一種特殊的線性規(guī)劃問題，在求解時(shí)仍可以采用單純形法的思路，如圖所示。圖2.1.1圖2.1.1由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計(jì)算，則無法利用這些有利條件。人們?cè)诜治鲞\(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對(duì)運(yùn)輸問題的表上作業(yè)法。下面主要討論運(yùn)輸問題的一些性質(zhì)基本可行解、檢驗(yàn)數(shù)以及基的轉(zhuǎn)換等問題?！?.2運(yùn)輸問題數(shù)學(xué)模型解的性質(zhì)定理2.1.1產(chǎn)銷平衡運(yùn)輸問題（2.1.2）必有可行解，也必有最優(yōu)解.證明：設(shè)

則取乙=￡b=diji=1j=則取乙=￡b=diji=1j=1xij-,(i=1,2,…,m;j=1,2,..?n)d(2.1.3)顯然有Xjj>0,ijj=1二iji=1所以(2.1.3)又=￡ab=a&ddjj=1j=1=&。氣=七&ddii=1i=1=a(i=1,2,…m)=b(j=1,2,…m)j是(2.1.2)的一個(gè)可行解.又因?yàn)槠撸?,(i=1,2,—m;j=1,2,—n)，故對(duì)于任一可行解￡〃￡模型(2.1.2)的目標(biāo)函數(shù)值都不會(huì)為負(fù)數(shù)，即目標(biāo)函數(shù)值有下界零，對(duì)于求極小化問題，目標(biāo)函數(shù)值有下界，則必有最優(yōu)解.運(yùn)輸問題的矩陣屬于一種大型稀疏矩陣，所謂“大型”是指矩陣的規(guī)模大，矩陣A共有m+n行，mn列。當(dāng)m和n較大時(shí)，矩陣A的規(guī)模是很大的，所謂“稀疏”是指矩陣中的非零元素較少.如果將平衡運(yùn)輸問題的模型寫成矩陣形式記：X=(x11，x，12…氣，x21，x22…x2n，…，xm1，xm2C=(C11，c…12C1n,C21,C，…22?C2n，…，Cm1,Cm2，…',^mn)A=[P11,P12,…,P1n,P21,P22,..,Cn,m1,七2,…,Pmn]d,d，…d]t氏巳，S2,...，皿,，…x)T模型(3.1.2)的矩陣表示為minf=CX(2.1.4)XXXX???1n21222nXXX?mlm2mn11…11XXXX???1n21222nXXX?mlm2mn11…111…1A=1111111(m+n)xmn(2.1.5)矩陣A中相應(yīng)于x〔j的列的量為PjP=e.+e(i=1,2,…m;j=1,2,—n)imm+jei=(0,-0,1,0,-0)tem+j=(0,-0,0,-0,1,0,-0)t即%中的第i個(gè)分量和第m+j個(gè)分量為1,其余的元素均為0.定理2.1.2產(chǎn)銷平衡運(yùn)輸問題（2.1.2）約束方程系數(shù)矩陣A的秩等于m+n-1.證明：顯然m+n<mn,（m,n>2）,于是秩（A）Wm+n.又由平衡條件（2.1.2）可知，A的前m行之和等于后n行之和，因此A的行是線性相關(guān)的，故必須秩（A）Wm+n-1,但A中有m+n-1階子式其行列式不為零。定理2.1.3運(yùn)輸問題（2.1.2）的基可行解中應(yīng)包含m+n-1個(gè)基變量.因平衡運(yùn)輸問題有一個(gè)約束條件多余，而其系數(shù)矩陣的秩為m+n-1。定理2.1.4運(yùn)輸問題（2.1.2）的約束條件的系數(shù)矩陣A的所有各階子式只取0，1或-1三個(gè)值.可由數(shù)學(xué)歸納法證得。定理2.1.5如果運(yùn)輸問題（2.1.2）中的所有產(chǎn)量和銷量^,,氣都是整數(shù)，那么，它的任一基可行解都是整數(shù)解.'7證明：在約束條件Ax=b中，去掉多余約束，得到A'x=b'，b‘的分量都是整數(shù).設(shè)x是任一基可行解，其基變量為detBitjtdetBXjx2j,…XijB為對(duì)應(yīng)的基矩陣，(t=1,2,…，m+n-1)容易看出，detBt是個(gè)整數(shù)，而detB是A的某一個(gè)m+n-1階子式.由定理2.1.3知

detB=1.因此，XitJt(t=1,2,…，m+n-1)都是整數(shù).§1.3運(yùn)輸問題的基變量與基可行解運(yùn)輸問題是特殊的線性規(guī)劃，單純形法的原理仍適合于運(yùn)輸問題，為此需要了解其基可行解的性質(zhì)。為了說明基變量與基本可行解的特征，此處需要引入一些概念。下面的討論建立在表（2.1.4）中決策變量格的基礎(chǔ)上。定義2.1.1在上表的決策變量格中，凡是能夠排列成下列形式的x,x,x,x，…，x,x（2.1.6）abaddcdestsb(2.1.7)或x,x,x,x，…，x,xabcbcdedstat(2.1.7)其中，a,d,…,s各不相同；b,c,???,t各不相同，我們稱之為變量集合的一個(gè)閉回路，并將式（2.1.6）和式（2.1.7）中的變量稱為這個(gè)閉回路的頂點(diǎn)。例如，x，x，x，x，x，x；x，x，x，x，x，x131636342423235355454121等都是閉回路。若把閉回路的各變量格看作節(jié)點(diǎn)，在表中可以畫出如下形式的閉回路圖2.1.2根據(jù)定義可以看出閉回路的一些明顯特點(diǎn)，閉回路是一個(gè)具有如下條件的頂點(diǎn)格子的集合（1）每一個(gè)頂點(diǎn)格子都是轉(zhuǎn)角點(diǎn)；（2）每一行（或列）若有閉回路的頂點(diǎn)，則有兩個(gè)頂點(diǎn)；（3）每兩個(gè)頂點(diǎn)格子的連線都是水平的或垂直的；（4）閉回路中頂點(diǎn)的個(gè)數(shù)必為偶數(shù).根據(jù)運(yùn)輸問題（2.1.2）的約束方程系數(shù)矩陣A中的列向量%的特征，可以推出閉回路有如下代數(shù)性質(zhì)：性質(zhì)2.1.1構(gòu)成閉回路的變量組x,x,x,x，…，x,x所對(duì)應(yīng)的系數(shù)abaddcdestsb列向量P,P,P,P，…，P,P（2.1.8）abaddcdestsb必線性相關(guān).證明：由直接計(jì)算可知P-P+P-P+???+P-P=0abaddcdestsb故向量組（2.1.8）必線性相關(guān)性.性質(zhì)2.1.2若變量組x,x,x,x，…，x,x中有一個(gè)部分組構(gòu)成閉回abaddcdestsb路，則變量組對(duì)應(yīng)的列向量組七，七，P，P，…，P，七abaddcdestsb是線性相關(guān)的.證明：由性質(zhì)2.1.1知，向量組（2.1.8）中有一個(gè)部分組（與閉回路的頂點(diǎn)相對(duì)應(yīng)的向量組）是線性相關(guān)的.根據(jù)線性代數(shù)理論知，若向量組中有一部分線性相關(guān)，則全體也線性相關(guān)，因此向量組必線性相關(guān).推論2.1.2若變量組對(duì)應(yīng)的列向量組線性無關(guān)，則該變量組一定不包含閉回路.根據(jù)以上結(jié)論以及線性規(guī)劃基變量的特點(diǎn)，可以得到下面的定理。定理2.1.6變量組x，x，x，x，…，x，x所對(duì)應(yīng)的系數(shù)列向量abaddcdestsbP，P，P，P，…，P，P線性無關(guān)的充分必要條件是這個(gè)變量組中不包含閉回abaddcdestsb路。定理2.1.7產(chǎn)銷平衡運(yùn)輸問題的m+n-1個(gè)變量構(gòu)成基變量的充分含閉回路。定理2.1.7給出了運(yùn)輸問題基本解的重要性質(zhì)，也為尋求基本可行解提供了依據(jù)。第二節(jié)表上作業(yè)法表上作業(yè)法（又稱為運(yùn)輸單純形法）是根據(jù)單純形法的原理和運(yùn)輸問題的特征，設(shè)計(jì)出來的一種在表上運(yùn)算的求解運(yùn)輸問題的簡便而有效的方法，作為一種迭代算法，它的主要步驟是：（1）求一個(gè)初始調(diào)運(yùn)方案；（2）根據(jù)最優(yōu)性判別準(zhǔn)則來檢查這個(gè)基本可行解是不是最優(yōu)的？若是則迭代停止；否則轉(zhuǎn)下一步；（3）改進(jìn)當(dāng)前方案，得到新的方案，再返回（2）.直至求出最優(yōu)解為止§2.1初始基本可行解的確定根據(jù)上面的討論，要求得運(yùn)輸問題的初始基本可行解，必須保證找到m+n-1個(gè)不構(gòu)成閉回路的基變量。一般的方法步驟如下：（1）在運(yùn)輸問題求解作業(yè)數(shù)據(jù)表中任選一個(gè)單元格七（A,行Bj列交叉位置上的格）,令x「=min｛氣,b｝，即從A,向B運(yùn)最大量（使行或列在允許的范圍內(nèi)盡量飽和，即使一個(gè)約束方程得以滿足），填入七的相應(yīng)位置；（2）從氣和氣中分別減去x：的值，修正為新的氣和b，即調(diào)整a,的擁有量及Bj的需求量；（3）若氣=0,則劃去對(duì)應(yīng)的行（已經(jīng)把擁有的量全部運(yùn)走），若氣=0則劃去對(duì)應(yīng)的列（已經(jīng)把需要的量全部運(yùn)來），且每次只劃去一行或一列（即每次要去掉且只去掉一個(gè)約束）；（4）當(dāng)最終的運(yùn)輸量選定時(shí)，其所在行、列同時(shí)滿足，此時(shí)要同時(shí)劃去一行和一列。這樣，運(yùn)輸平衡表中所有的行與列均被劃去，則得到了一個(gè)初始基本可行解。否則在剩下的運(yùn)輸平衡表中選下一個(gè)變量，返回（1）。上述計(jì)算過程可用流程圖描述如下：注：為了方便，這里總記剩余產(chǎn)量和銷量為圖2.2.1注：為了方便，這里總記剩余產(chǎn)量和銷量為按照上述方法所產(chǎn)生的一組變量的取值將滿足下面條件：（1）所得的變量均為非負(fù)，且變量總數(shù)恰好為m+n-1個(gè)；（2）所有的約束條件均得到滿足；（3）所得的變量不構(gòu)成閉回路。因此，根據(jù)定理2.1.7，所得的解一定是運(yùn)輸問題的基本可行解。在上面的方法中，X的選取方法并沒有給予限制，若采取不同的規(guī)則來選取七/則得到不同的方法，較常用的方法有西北角法和最小元素法。下面分別舉例并予以介紹。西北角法從西北角（左上角）格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按行（列）標(biāo)下一格的數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。用西北角法初始方案的方法，雖然比較簡單，但因?yàn)樗鼪]有考慮到運(yùn)價(jià)，因此得到的初始方案一般離最優(yōu)方案較遠(yuǎn).最小元素法是一種考慮運(yùn)價(jià)的求初始方案的方法，遵循如下規(guī)則:優(yōu)先安排單位運(yùn)價(jià)最小的產(chǎn)地與銷地之間的運(yùn)輸業(yè)務(wù).一般來說，用這種方法制定的調(diào)運(yùn)方案，其總運(yùn)費(fèi)會(huì)比用西北角法得到的調(diào)運(yùn)方案更省，當(dāng)然也不一定是最省的.最小元素法最小元素法是從運(yùn)價(jià)最小的格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按運(yùn)價(jià)從小到大順序填數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。一般地說在用西北角法和最小元素法求初始方案時(shí)，應(yīng)注意以下幾點(diǎn)：（1）在填入一個(gè)數(shù)時(shí)，如果行和列同時(shí)飽和，規(guī)定只劃去一行或一列，而不能同時(shí)劃去行和列，這時(shí)行和列的修正量均為0.如果劃去的是行（或列）下次到修正量為0的列（或行）時(shí)，就必須取相應(yīng)的變量的值為0，填入相應(yīng)的格子，劃去該列（或行），以保證填數(shù)字的格子為m+n-1.（2）在剩下最后一個(gè)空格時(shí)，只能填數(shù)（必要時(shí)可取0），并劃去所在行和列.（3）在某一行（或列）填最后一個(gè)數(shù)時(shí)，如果行和列同時(shí)飽和，則規(guī)定只劃去該行（或列）.例2.2.1某食品公司下屬的A,A,A三個(gè)廠生產(chǎn)方便食品，要運(yùn)送到B,B,B,B四1231234個(gè)銷售點(diǎn)，數(shù)據(jù)如下表：表2.2.1銷產(chǎn)、^地B1B2B3B4產(chǎn)量氣3113107A219284A3741059銷量bj365620（產(chǎn)銷平衡）西北角法的初始調(diào)運(yùn)方案（基本可行解）表2.2.2產(chǎn)\地地B]B2BB4產(chǎn)量a43113o1°CZ57A2［。9284

氣74103569銷量bj365620最小元素法的初始調(diào)運(yùn)方案（基本可行解）表2.2.3^\銷產(chǎn)、地地、B2B3B4產(chǎn)量ai3^_^113107A2139^_^28o4A3741059銷量bj365620§2.2基本可行解的最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)就是檢查所得到的方案是不是最優(yōu)方案。檢查的方法與單純形方法中的原理相同，即計(jì)算檢驗(yàn)數(shù)。由于目標(biāo)函數(shù)要求取得極小，因此，當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案；否則就不是最優(yōu)，需要進(jìn)行調(diào)整。下面介紹兩種求檢驗(yàn)數(shù)的方法。1.閉回路法下面是閉回路法的理論基礎(chǔ)。（s=m+n-1）是運(yùn)輸問題（2.1.2）的一組基變定理2.2.1設(shè)l1j，l1j2，（s=m+n-1）是運(yùn)輸問題（2.1.2）的一組基變lrjrXlsXlsjs，Xirjr（2.2.1）中存在唯一的以xi］為頂點(diǎn)的閉回路.證明：首先證明存在性，寫出變量組中存在唯一的以xi］為頂點(diǎn)的閉回路.證明：首先證明存在性，寫出變量組P，P，l1j1l2j2對(duì)應(yīng)的列向量jPlj

srr…，Plsj由定理2.1.3，它們必線性相關(guān)，再由定理2.1.6，變量組（2.2.1）中一定存在閉回路.其次，再讓唯一性.設(shè)變量組（2.2.1）存在兩個(gè)不同的閉回路，那么，P就可用兩種lrj不同的方式表示成P，P，…，P的線性組合.顯然，這與P，P，…，P線l1j1l2j2lsjsl1j1l2j2lsjs性無關(guān)相矛盾，故變量組（2.2.1）存在唯一的閉回路.這樣，如果對(duì)閉回路的方向不加區(qū)別（即只要起點(diǎn)及其他所有頂點(diǎn)完全相同，而不區(qū)別行進(jìn)方向是順時(shí)針還是逆時(shí)針），那么以每一個(gè)非基量為起始頂點(diǎn)的閉回路就存在而且唯一。因此，當(dāng)基變量確定后對(duì)每一個(gè)非基變量可以找到而且只能找到唯一的一個(gè)閉回路。下表中用虛線畫出以非基變量七為起始頂點(diǎn)的閉回路表2.2.4地_—B?BB4產(chǎn)量a.311\410i37氣1392；8；41氣74；105；96■-■3銷量氣365620根據(jù)單純形法原理，檢驗(yàn)數(shù)是將基變量用非基變量表示代入目標(biāo)函數(shù)時(shí)，非基變量的系數(shù)，因此在運(yùn)輸問題中，要計(jì)算非基變量（即空格處）的檢驗(yàn)數(shù).表2.2.4為運(yùn)輸問題的一個(gè)基可行解，工=工=工=3，x=6，工=4，x=1，213414321323其余x^=0，將運(yùn)輸問題作線性規(guī)劃處理，在該基可行解下單純形表的目標(biāo)函數(shù)為f=86+。x+bx+bx+bx+bx+bx111112122222313133332424?！榉腔兞縳^的檢驗(yàn)數(shù)，現(xiàn)利用運(yùn)量的變化及運(yùn)輸?shù)膯挝毁M(fèi)用可計(jì)算出該變量對(duì)目標(biāo)函數(shù)的綜合影響，進(jìn)而求出檢驗(yàn)數(shù)。。22為非基變量x22對(duì)運(yùn)費(fèi)的影響，其經(jīng)濟(jì)意義表述為當(dāng)其余非基變量x〃保持不變時(shí)，x22增加一個(gè)單位時(shí)，總運(yùn)費(fèi)的增加量。如果僅x22變化其余非基變量與基變量保持不變，約束條件將被破壞。所以當(dāng)x22增加時(shí)部分基變量一定會(huì)發(fā)生變化。在上例中，x22增加一個(gè)單位，由B2的銷量約束及根據(jù)其余非基變量保持不變的，x32必減少一個(gè)單位，由A的產(chǎn)量約束x必增加一個(gè)單位，x必減少一個(gè)單位，x必增加3341413一個(gè)單位，x23必減少一個(gè)單位。至此，從x22出發(fā)，依次途經(jīng)基變量x—x—x—x—x—x，又回到x（也可選擇沿相反的方向）。這就得到22323414132322以x22為頂點(diǎn)，其余頂點(diǎn)為基變量的閉回路。運(yùn)費(fèi)增加的數(shù)目為。=9-4+5-10+3-2=1，這就是求檢驗(yàn)數(shù)的閉回路法。22用閉回路法求檢驗(yàn)數(shù)時(shí)，對(duì)于給定的調(diào)運(yùn)方案（基可行解）從非基變量x〃出發(fā)作一條閉回路，要求該閉回路上其余的頂點(diǎn)均為基變量，并從x^開始將該閉回路上的頂點(diǎn)順序編號(hào)（順時(shí)針或逆時(shí)針均可），起點(diǎn)為零，余類推。稱編號(hào)為奇數(shù)的點(diǎn)為奇點(diǎn)，編號(hào)為偶數(shù)的點(diǎn)為偶點(diǎn)，則x^處對(duì)應(yīng)的檢驗(yàn)數(shù)?！ǖ扔谠撻]回路上偶點(diǎn)處運(yùn)價(jià)的總和與奇點(diǎn)處運(yùn)價(jià)的總和之差，即'二偶點(diǎn)處運(yùn)價(jià)的總和一奇點(diǎn)處運(yùn)價(jià)的總和（2.2.2）下面求x的檢驗(yàn)數(shù)，以x為頂點(diǎn)的閉回路為x—x—x—x（也可選順時(shí)針242424141323方向），檢驗(yàn)數(shù)為。24=8-10+3-2=-1（或。24=8-2+3-10=-1）這就是求檢驗(yàn)數(shù)的閉回路法，其原理就是通過尋找閉回路來計(jì)算非基變量的檢驗(yàn)數(shù)。

按上述作法，可計(jì)算出表2.2.4中的所有非基變量的檢驗(yàn)數(shù)，把它們填入相應(yīng)位置的方括號(hào)內(nèi)，如表2.2.5所示。表2.2.5產(chǎn):yBBB3B4產(chǎn)量ai氣3[1]11[2]3107A2139[1]28[-1]4A37[10]410[12]59銷量氣365620顯然，當(dāng)所有非基變量的檢驗(yàn)數(shù)均大于或等于零時(shí)，現(xiàn)行的調(diào)運(yùn)方案就是最優(yōu)方案，因?yàn)榇藭r(shí)對(duì)現(xiàn)行方案作任何調(diào)整都將導(dǎo)致總的運(yùn)輸費(fèi)用增加。閉回路法的主要缺點(diǎn)是當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路以及計(jì)算兩方面都會(huì)產(chǎn)生困難。2.位勢法當(dāng)運(yùn)輸向量的產(chǎn)地與銷地很多時(shí)，空格的數(shù)目很大，用閉回路法計(jì)算檢驗(yàn)數(shù)，要找很多的閉回路，計(jì)算量很大，而用位勢法(也稱對(duì)偶變量法)就要簡便得多.對(duì)產(chǎn)銷平衡運(yùn)輸問題，約束方程的系數(shù)矩陣的秩為m+n-1，模型為minf=SnCxi=1j=1ijij乙x=ai=1(i=1,2,—m)(2.2.3)s.t.▽Zx=bijjj=1(j=1,2,…n)x>0(i=1,2,…m;n=1,2,…n)設(shè)"],u2,-um分別表示前m個(gè)約束等式相應(yīng)的對(duì)偶變量，用V,七,…v分別表示后n個(gè)等式約束相應(yīng)的對(duì)偶變量，即有對(duì)偶變量向量，"],u尸…氣件運(yùn)輸問題的對(duì)偶規(guī)劃寫成WmaxZ=^u+，viijji=1j=1(2.2.4)u+v<c(i=1,2,???m;j=1,2,???n)ijij".，V為任意實(shí)數(shù)(2.2.4)由互補(bǔ)松弛定量可知，若X**,V*｝分別為原問題和對(duì)偶問題的可行解ij1j(i=1,2,…m;j=1,2,…n)，它們同為最優(yōu)解的充要條件是對(duì)一切i與j，有X*(u*+v*-C)=0(2.2.5)ijijij

對(duì)于原問題的任意基可行解X*LX*為非基變量時(shí)，式（3.2.5）顯然成立，當(dāng)x*為ijijij基變量時(shí)可令X*據(jù)是原問題的ij然后代入（2.2.4）u*+v*-C.=0（2.2.6）X*據(jù)是原問題的ij然后代入（2.2.4）U*與v*同時(shí)滿足（2.2.6）與（2礦4），常常是不現(xiàn)實(shí)的，這恰說明最優(yōu)解。實(shí)際中對(duì)于給定的基可行解X*慶通過（2.2.6）求出u*與v*，ijij檢驗(yàn)u*+v*-C.V0是否對(duì)（i=1,2,…m;j=1,2,…n）成立。原問題的任意基可行解所對(duì)應(yīng)的（2.2.6）給出了m+n個(gè)變量的m+n-1個(gè)方程，其系數(shù)矩陣為原問題的系數(shù)矩陣^中基變量所對(duì)應(yīng)的列向量的轉(zhuǎn)置，該方程組的系數(shù)矩陣與增廣矩陣的秩相等，都是m+n-1，從而該方程組永遠(yuǎn)有解。這樣求得伽*與v*分別對(duì)應(yīng)、一-一,、一x*一.一調(diào)運(yùn)方案的弟1行的行位勢”與弟j列的列位勢”，而u*+v*為變量萬的位勢?？梢酝╥j過求位勢求得非基變量的檢驗(yàn)數(shù)。仍將例2.2.1中b的計(jì)算過程進(jìn)行分析，按閉回路法得七=C22-CLC34Y14+C1廣C23由于閉回路上其余變量都為基變量b=C一(u+v)+(u+v)一(u+v)+(u+v)一(u+v)=C-u-v222232341413232222所以，一般的結(jié)論是(2.2.7)b..=C—u—v式中C為x對(duì)應(yīng)的運(yùn)價(jià)，u,v分別為x對(duì)應(yīng)的行位勢和列位勢，這樣可用位勢法求出檢ijijijij驗(yàn)數(shù)。(2.2.7)位勢法的步驟：（1）求出的運(yùn)輸問題的基可行解，設(shè)其基變量是：%j，七2,/???，七,人（s=m+n-1）（2）解方程組：u+v=cTOC\o"1-5"\h\zij1ij1u+v=ci2j2i2j2(2.2.8)u+v=cijij(2.2.8)求出一個(gè)特解（解不唯一）（3）求檢驗(yàn)數(shù)：b=C-u-v.§2.2出基變量的選擇（方案的調(diào)整）'當(dāng)非基變量的檢驗(yàn)數(shù)出現(xiàn)負(fù)值時(shí)，則表明當(dāng)前的基本可行解不是最優(yōu)解。在這種情況下，應(yīng)該對(duì)基本可行解進(jìn)行調(diào)整，即找到一個(gè)新的基本可行解使目標(biāo)函數(shù)值下降，這一過程通常稱為換基（或主元變換）過程。在運(yùn)輸問題的表上作業(yè)法中，換基的過程是如下進(jìn)行：（1）選負(fù)檢驗(yàn)數(shù)中最小者o詼，那么乂詼為主元，作為進(jìn)基變量（表2.2.5中的x24）；（2）以乂化為起點(diǎn)找一條閉回路，除；汶外其余頂點(diǎn)必須為基變量格；（3）對(duì)閉回路的每一個(gè)頂點(diǎn)標(biāo)號(hào)，x「為0,沿一個(gè)方向（順時(shí)針或逆時(shí)針）依次給各頂點(diǎn)標(biāo)號(hào)；'（4）求0=min{xIx對(duì)應(yīng)閉回路上的奇數(shù)標(biāo)號(hào)格}=x那么確定^（當(dāng)有若干可ijpqpq個(gè)時(shí)只選一個(gè)）為出基變量，0為調(diào)整量；（5）對(duì)閉回路的各偶標(biāo)號(hào)頂點(diǎn)調(diào)整后的結(jié)果為：x^+0，對(duì)各奇標(biāo)號(hào)頂點(diǎn)調(diào)整后的結(jié)果為：x「-0，特別x-0=0，x變?yōu)榉腔兞?。重?fù)（2）、（3）步，直到所有檢驗(yàn)數(shù)均司非負(fù)，得到最優(yōu)解。在例2.2.1中以x24為頂點(diǎn)的閉回路為xTxTxTx，0=min（x,x}=1241413231423x23出基并對(duì)閉回路的運(yùn)量調(diào)整，調(diào)整后為x24=1,氣4=2,x13=3,x23=0，其余變量不變。調(diào)整后求檢驗(yàn)數(shù)（位勢法）。表2.2.6v■-24-25uBBB3B4產(chǎn)量a53[0]11[2]31073氣139[2]2[1]840A37[9]410[12]59銷量bj365620bN0，得到最優(yōu)解x=5,x=2,x=3,x=1,x=6,x=3,ij131421243234其余x^=0;最優(yōu)值：f*=3X5+10X2+1X3+8X1+4X6+5X3=85第三節(jié)不平衡的運(yùn)輸問題§3.1產(chǎn)銷不平衡運(yùn)輸問題前面講述的解運(yùn)輸問題的算法，是以總產(chǎn)量等于總銷量（產(chǎn)銷平衡）為前提的.實(shí)際上，在很多運(yùn)輸問題中總產(chǎn)量不等于總銷量.這時(shí)，為了使用前面的表上作業(yè)法求解，就需將產(chǎn)銷不平衡運(yùn)輸問題化為產(chǎn)銷平衡運(yùn)輸向量.如果總產(chǎn)量大于總銷量乙＞為Iji=1j=1這時(shí)的數(shù)學(xué)模型是（以下取a=s,b=d）minz空乙..x..i=0j=0

s.t.2X1j=1<aii=1,2,…，m.(2.3.1)欄X=bj=1,2,…s.t.2X1j=1<aii=1,2,…，m.(2.3.1)欄X=bj=1,2,…,n..ji=1X.,>0為借助于產(chǎn)銷平衡時(shí)的表上作業(yè)法，可增加一個(gè)假想的銷地B，由于實(shí)際上它不存n+1在，因而由產(chǎn)地氣（.=1,2,…,m）調(diào)運(yùn)到這個(gè)假想銷地的物品數(shù)量X.（n+1）（相當(dāng)于松馳變量），實(shí)際上是就地存貯在A的物品數(shù)量，就地存貯的物品不經(jīng)運(yùn)輸，故其單位運(yùn)價(jià)C('=1,2,…,m).i,(n+1)=0令假想銷地的銷量為b(n+1)則模型（2.3.1）變?yōu)?￡a—￡bjj=1aii=12x=ai=1,2,…,m.s.tj=1lJ1（2.3.2）*x=bj=1,2,,n+1.i=1x..>0例2.3.1某公司從兩個(gè)產(chǎn)地A、A將物品運(yùn)往三個(gè)銷地B、B、B，各產(chǎn)地的產(chǎn)量、12123各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？表2.3.1地'、、、B]B2B3產(chǎn)量A1646300A655300銷量150150200解：增加一個(gè)虛設(shè)的銷地運(yùn)輸費(fèi)用為0,得表2.3.2

表2.3.2地'、B]B2B3B4(虛銷產(chǎn)量A16460300A26550300銷量150150200100總產(chǎn)量小于總銷量的情形二v以

Iji=1j=1這時(shí)的數(shù)學(xué)模型是（以下取a=s,b=d）minzU乙.x.i=0j=0命=a（i=1,2,...,m）j=1（2.3.3）s.t并x..<b(j=1,2,…,n)i=1x>0ij（2.3.3）可仿照上述類似方法處理，即增加一個(gè)假想的產(chǎn)地A，它的產(chǎn)量等于m+1am+1（2.3.4）j=1iam+1由于這個(gè)假想的產(chǎn)地并不存在，求出的由它發(fā)往各個(gè)銷地的物品數(shù)量x(m+1)jC(m+1)=0(j=1,2,…n)但當(dāng)這種短缺有其他成本(違約賠償或機(jī)會(huì)成本)，cm+1)?不為零為其成本。(j=1,2,…n)，實(shí)際上是各銷地知所需物品的欠缺額，所以一般地有例C(m+1)=0(j=1,2,…n)但當(dāng)這種短缺有其他成本(違約賠償或機(jī)會(huì)成本)，cm+1)?不為零為其成本。表2.3.3地\B]BB3產(chǎn)量A646200

A655300銷量250200200增加虛擬銷地后得到表2.3.4地、'、'B2B3產(chǎn)量A】646200A655300a3（虛產(chǎn)地）000150銷量250200200§3.2運(yùn)輸問題的應(yīng)用例2.3.3石家莊北方研究院有一、二、三，三個(gè)區(qū)。每年分別需要用煤3000、1000、2000T，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價(jià)格、質(zhì)量相同。供應(yīng)能力分別為1500、4000T，運(yùn)價(jià)如下表。由于需大于供，經(jīng)院研究決定一區(qū)供應(yīng)量可減少0—300T，二區(qū)必須滿足需求量，三區(qū)供應(yīng)量不少于1700T，試求總費(fèi)用為最低的調(diào)運(yùn)方案。表2.3.5地、'\一區(qū)二區(qū)三區(qū)產(chǎn)量山西孟縣1.651.71.754000河北臨城1.601.651.701500需要量300010002000解:根據(jù)題意，作出產(chǎn)銷平衡問題的運(yùn)價(jià)表：取M代表一個(gè)很大的正數(shù)，其作用是強(qiáng)迫相應(yīng)的X31，%3,*34取值為0。表2.3.6地\表2.3.6地\一區(qū)一區(qū)二區(qū)三區(qū)三區(qū)產(chǎn)量山西孟縣1.651.651.71.751.754000河北臨城1.601.601.651.701.701500假想生產(chǎn)點(diǎn)M0MM0500需要量270030010001700300例2.3.3設(shè)有A、B、C三個(gè)化肥廠供應(yīng)1、2、3、4四個(gè)地區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表。試求總費(fèi)用為最低的化肥調(diào)撥方案。表2.3.7地、\1234產(chǎn)量A1613221750B1413191560C19202350最低需求量3070010最高需求量507030不限解：根據(jù)題意，作出產(chǎn)銷平衡問題及運(yùn)價(jià)表:最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為M，而最高要求與最低要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為0。對(duì)應(yīng)4”的銷量50是考慮問題本身適當(dāng)取的數(shù)據(jù)，根據(jù)產(chǎn)銷平衡要求確定D的產(chǎn)量為50。表2.3.8\銷產(chǎn)、地地\1'1''234'4''產(chǎn)量A16161322171750B14141319151560C19192023MM50DM0M0M050最高需求量302070301050下面是生產(chǎn)與儲(chǔ)存問題例2.3.4某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用0.15萬元。試求在完成合同的情況

下，使該廠全年生產(chǎn)總費(fèi)