第3章 運(yùn)輸規(guī)劃

3.1運(yùn)輸問題概述第3章運(yùn)輸規(guī)劃一般來說，運(yùn)輸問題是指：某種物資由m個發(fā)送點(diǎn)（發(fā)點(diǎn)）運(yùn)往n個接收點(diǎn)（收點(diǎn)），已知各個發(fā)點(diǎn)的最大供給量（發(fā)量）、各個收點(diǎn)的需求量（收量），以及各發(fā)點(diǎn)向各收點(diǎn)的單位運(yùn)價，如下表所示，在各收點(diǎn)收量達(dá)到滿足的條件下，求總運(yùn)費(fèi)最低的運(yùn)輸方案的問題。3.1.1運(yùn)輸問題及相關(guān)概念收點(diǎn)發(fā)點(diǎn)B1B2…Bn發(fā)量A1c11c12…c1na1A2c21c22…c2na2………………Amcm1cm2…cmnam收量b1b2…bn∑ai∑bj若用xij表示從Ai到Bj的運(yùn)輸量，則運(yùn)輸方案如下表所示。根據(jù)總運(yùn)費(fèi)最小的目標(biāo)及相關(guān)約束，可得其模型表示如下：收點(diǎn)發(fā)點(diǎn)B1B2…Bn發(fā)量A1x11x12…x1na1A2x21x22…x2na2………………Amxm1xm2…xmnam收量b1b2…bn∑ai∑bj（各發(fā)點(diǎn)的發(fā)量約束）（各收點(diǎn)的收量約束）3.1.2運(yùn)輸問題的類型根據(jù)實(shí)踐應(yīng)用中的具體情況，運(yùn)輸問題一般可以分為以下幾種類型。（1）

產(chǎn)銷平衡的運(yùn)輸問題該類問題中總發(fā)量和總收量數(shù)值相等，且模型中發(fā)量約束和收量約束全部取等式。也簡稱為平衡運(yùn)輸問題，是運(yùn)輸問題的基本形式。（2）產(chǎn)銷不平衡運(yùn)輸問題該類問題中總發(fā)量不等于總收量，具體又可以分為一般不平衡運(yùn)輸問題和復(fù)雜不平衡運(yùn)輸問題兩種類型。①一般不平衡運(yùn)輸問題是指：總發(fā)量不等于總收量，且模型的收量約束中不存在“≥型”的約束，具體包括產(chǎn)大于銷和產(chǎn)小于銷兩種情況。②復(fù)雜不平衡運(yùn)輸問題主要是指：總發(fā)量不等于總收量，且模型的收量約束中存在“≥型”的約束。實(shí)踐中，復(fù)雜不平衡運(yùn)輸問題還有收點(diǎn)兼做發(fā)點(diǎn)，以及發(fā)點(diǎn)兼做收點(diǎn)等其它一些復(fù)雜情況，這些均不包括在本課程的講述范圍內(nèi)。3.1.3運(yùn)輸問題的特殊性通過以上的描述不難看出，運(yùn)輸問題總體來說仍屬于線性規(guī)劃問題，此處單列出來討論，是因?yàn)檩^之其它的線性規(guī)劃問題，運(yùn)輸問題在模型結(jié)構(gòu)上存在著顯著的不同之處。平衡運(yùn)輸問題在實(shí)踐中并不是常見的類型，但是由于其模型結(jié)構(gòu)，在所有運(yùn)輸問題中相對簡單、規(guī)范，便于研究與討論；且其它類型的運(yùn)輸問題都可以通過某種方式轉(zhuǎn)化為平衡運(yùn)輸問題。平衡運(yùn)輸問題便于討論與構(gòu)建求解方法，且通過問題類型的轉(zhuǎn)換，所構(gòu)建的解方法也可以在其它所有類型的運(yùn)輸問題上推廣應(yīng)用。因此，平衡運(yùn)輸問題被視為運(yùn)輸問題的基本形式。下面以平衡運(yùn)輸問題及其模型為基礎(chǔ)，來具體討論運(yùn)輸問題模型上的特殊性以及影響。例3-1問題背景：某公司的產(chǎn)品從兩個產(chǎn)地A1、A2銷往三個銷地B1、B2和B3，已知各個產(chǎn)地的月額定生產(chǎn)能力、各個銷地的月需求量（嚴(yán)格取表中數(shù)值），以及各產(chǎn)地向各銷地運(yùn)送產(chǎn)品的單位運(yùn)費(fèi)，如下表所示。問題目標(biāo)：應(yīng)如何安排產(chǎn)品的運(yùn)輸計劃，才能在每個銷地每個月的產(chǎn)品需求達(dá)到滿足的前提下，使總運(yùn)輸成本最低。通過分析建模，得該問題的運(yùn)籌學(xué)模型如下：模型中總發(fā)量和總收量相等，所以在各個收量約束取嚴(yán)格等式時，各發(fā)收量約束發(fā)量約束收點(diǎn)發(fā)點(diǎn)B1B2B3發(fā)量A156723A26111627收量1718155050量約束也必然取嚴(yán)格等式，所以發(fā)量約束直接改寫為等式約束。寫出其系數(shù)矩陣如下：（1）系數(shù)矩陣的特殊性①

可以看出，系數(shù)矩陣的列數(shù)（變量個數(shù)）隨著發(fā)點(diǎn)和收點(diǎn)個數(shù)呈積數(shù)態(tài)勢增加，實(shí)踐中一個稍具規(guī)模的運(yùn)輸問題，其系數(shù)矩陣便非常龐大。單純形法計算中的大多數(shù)工作，是通過系數(shù)矩陣的迭代運(yùn)算來完成的，如此龐大的系數(shù)矩陣，必然會帶來單純形表格繪制的困難，同時嚴(yán)重影響著單純形法的整體計算效率。②整個矩陣只有0和1兩種元素，且每列均為兩個1，在各個資源約束條件均為等式的前提下，用單純形法去進(jìn)行求解時，必須要添加大量的人工變量，進(jìn)一步增加了單純形法的求解難度，求解效率也進(jìn)一步被降低。③模型中的資源約束條件總數(shù)為m+n個，但是在總發(fā)量等于總收量的前提下，其中有一個約束條件其實(shí)是多余的，因此系數(shù)矩陣的行向量之間其實(shí)是線性相關(guān)的，即：系數(shù)矩陣雖然是m+n行，但系數(shù)矩陣基的維數(shù)也即系數(shù)矩陣的秩卻是m+n-1，這使得單純形法求解時的難度與效率問題再次被加重。（2）最優(yōu)解存在形式上的特殊性運(yùn)輸問題的特殊性還表現(xiàn)在最優(yōu)解的存在形式上，運(yùn)輸問題的最優(yōu)解存在形式只有唯一解和多重解兩種，即至少存在一個最優(yōu)解。①

目標(biāo)函數(shù)是由單位運(yùn)價和運(yùn)輸量組成的最小化目標(biāo)，非負(fù)的極小化目標(biāo)必然存在下界值0，所以不可能出現(xiàn)無界解的情況。②若令平衡點(diǎn)的運(yùn)輸量為∑ai=∑bj

=Q，則按下式所得的一組變量值，必為平衡運(yùn)輸問題的一個可行解。即：平衡運(yùn)輸問題一定存在至少一個可行解，不可能是無可行解。3.1.4運(yùn)輸規(guī)劃的提出運(yùn)輸問題雖然總體來說，仍然屬于線性規(guī)劃問題的范疇，但鑒于上述所討論的運(yùn)輸問題的特殊性，若將其視為普通的線性規(guī)劃問題，在其模型的求解方面，便存在著求解難度大，求解效率低下的問題。隨著社會與經(jīng)濟(jì)的發(fā)展，特別是伴隨著物流業(yè)的興起，運(yùn)輸問題越來越成為實(shí)踐中一個經(jīng)常性和重要性的問題；在線性規(guī)劃的其它應(yīng)用中，偶爾也會遇到和運(yùn)輸問題模型結(jié)構(gòu)相同的一些特殊問題。因此，對于這些特殊的線性規(guī)劃問題的求解，另尋其它更加有效的求解方法便成為一種必然需求。運(yùn)籌學(xué)的實(shí)踐中，將在模型結(jié)構(gòu)上具有前述特殊性的所有線性規(guī)劃問題，統(tǒng)稱為運(yùn)輸問題，并將這些問題從線性規(guī)劃中剝離出來，形成一支新的運(yùn)籌學(xué)應(yīng)用分支，即運(yùn)輸規(guī)劃。其目的是，針對這類線性規(guī)劃模型結(jié)構(gòu)上的特殊性，研究并構(gòu)建適用于這類模型的，專門的、更加有效的求解方法。3.2平衡運(yùn)輸問題的表上作業(yè)法（1）表上作業(yè)法的本質(zhì)表上作業(yè)法是結(jié)合運(yùn)輸問題模型結(jié)構(gòu)的特殊性，對單純形法的一種改良算法。其基本原理以及基本流程和單純形法相同，不同的只是其中的一些具體做法，主要表現(xiàn)在以下幾個方面。①

初始基本可行解的獲取，不再依靠初始基，從而避免的人工變量；②

最優(yōu)性判斷中，λ檢驗(yàn)數(shù)的含義不變，但計算方法作了改進(jìn)，避開了矩陣運(yùn)算，使求解效率得到提高；③

基變換中的迭代運(yùn)算，不再利用矩陣的初等變換運(yùn)算，而是通過閉回路進(jìn)行調(diào)整，同樣回避了矩陣龐大的問題，使求解效率提高。（2）基本可行解的表格表示表上作業(yè)法中，基本可行解的表格表示不同于單純形法，其表格如下：3.2.1表上作業(yè)法概述表格中間部分稱為方案區(qū)，方案區(qū)的每一個格子對應(yīng)一個變量，在格子的右上角標(biāo)注單位運(yùn)價，便于計算使用。值得注意的是，當(dāng)表示基本可行解時，基變量所在格子里填入該變量的取值，無論是否為0；而非基變量所在的格子不填數(shù)值，即空格表示非基變量。由于有數(shù)字格表示基變量，從前述運(yùn)輸問題特殊性的論述可知，對于m個發(fā)點(diǎn)和n個收點(diǎn)的運(yùn)輸問題，表中有數(shù)字格的個數(shù)應(yīng)為m+n-1。收點(diǎn)發(fā)點(diǎn)B1B2…Bn發(fā)量A1x11c11x12c12……x1nc1na1A2x21c21x22c22……x2nc2na2…………………………Amxm1cm1xm2cm2……xmncmnam收量b1b2…bn∑ai=∑bj=Q（3）閉回路畫法及概念①閉回路的畫法從方案表的某個空格開始，沿水平或豎直方向前進(jìn)，在不走出方案區(qū)的前提下，路經(jīng)有數(shù)字各格時，可以90度轉(zhuǎn)向，也可以不轉(zhuǎn)繼續(xù)前進(jìn)，在路經(jīng)空格時，一定不能轉(zhuǎn)向，最終回到出發(fā)點(diǎn)空格，所形成的閉合回路，就稱為出發(fā)點(diǎn)空格的閉回路。如果方案表表示的是一個正確的基本可行解，則表中每一個空格都有且僅有一條閉回路，且從任何有數(shù)字格出發(fā)，都不可能找到閉回路。收點(diǎn)發(fā)點(diǎn)B1B2B3發(fā)量A117566723A261211151627收量17181550②閉回路的拐點(diǎn)及其編號閉回路上發(fā)生了方向轉(zhuǎn)變的點(diǎn)，稱為閉回路的拐點(diǎn)。拐點(diǎn)的編號方法是：以出發(fā)點(diǎn)（即空格所在點(diǎn)）為0號點(diǎn)，沿著閉回路依次順序的給每個拐點(diǎn)進(jìn)行編號。其中編號為偶數(shù)的拐點(diǎn)稱為偶拐點(diǎn)；編號為奇數(shù)的點(diǎn)稱為奇拐點(diǎn)。收點(diǎn)發(fā)點(diǎn)B1B2B3發(fā)量A17205620A23081025355A31135415950收量305540125①②③④⑤3.2.2表上作業(yè)法的算法（1）初始方案的編制——確定初始基本可行解在表上作業(yè)法中，初始基本可行解的確定不再依賴初始基，常用的方法包括最小元素法、左上角法（西北角法）、伏格爾法等等。①最小元素法基本思想：優(yōu)先滿足單位運(yùn)費(fèi)最低的需求。操作方法：包括以下四個相關(guān)的步驟a、在方案區(qū)未被直線覆蓋的部分，選擇單位運(yùn)費(fèi)最低的格子。b、在選中的格子里填入行值與列值中的較小者。其中：行值=選中格對應(yīng)的發(fā)量-選中格所在行上已有物資量的總和列值=選中格對應(yīng)的收量-選中格所在列上已有物資量的總和c、填入的數(shù)值若為行值，則劃去所在行，為列值則劃去所在列；如果行值與列值相等，則需要同時劃去行和列，但必須在所劃去的，行或列的任意一個空格內(nèi)補(bǔ)填一個“0”。（此時所得到的基本可行解為退化解）d、重復(fù)a~c直至方案區(qū)全部被直線覆蓋，此時所得方案即初始方案。例3-2用最小元素法編制下面平衡運(yùn)輸問題的初始方案。②左上角法（西北角法）基本思想：優(yōu)先滿足最左上角（西北角）的格子的需求。操作方法：與最小元素法基本相同，只需將第a步改為：在未被直線覆蓋的部分，選擇最左上角（西北角）的格子，其它各步不變。因?yàn)樽钚≡胤P(guān)注的只是局部最優(yōu)，所以雖然每一步都是選單位運(yùn)費(fèi)最小的格子，但是所得方案并非最優(yōu)，也就是說，是否選擇單位運(yùn)費(fèi)最小的格子，和最優(yōu)性無關(guān)，選擇左上角的格子，識別效率更高。收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A11056745A2827635A3934820收量1520204510020200153015收點(diǎn)發(fā)點(diǎn)B1B2B3發(fā)量A156723A26111627收量17181550③伏格爾法無論最小元素法還是左上角法，都難免會遇到如下小的情況。定義：各行、各列中最小單位運(yùn)費(fèi)與次小單位運(yùn)費(fèi)的差額稱為罰值?；舅枷耄簝?yōu)先滿足罰值最大的行或列上，單位運(yùn)費(fèi)最小的格子。操作方法：與最小元素法基本相同，只需將第a步改為：在未被直線覆蓋的部分，選擇罰值最大的行或列上，單位運(yùn)費(fèi)最小的格子，其它不變。例3-3用伏格爾法編制下面平衡運(yùn)輸問題的初始方案。收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量罰值A(chǔ)11056745A2827635A3934820收值201411112114112200322145015（2）最優(yōu)性判斷①λ檢驗(yàn)數(shù)的含義表上作業(yè)法中，各變量（也即各個格子）的λ檢驗(yàn)數(shù)的含義并沒有變，仍然是指：在目標(biāo)函數(shù)只含非基變量時，各變量的系數(shù)。從數(shù)值上來說基變量（有數(shù)字格）：λ檢驗(yàn)數(shù)恒為零非基變量（空格）：λ檢驗(yàn)數(shù)的數(shù)值代表了，該非基變量（空格）作單位數(shù)值的變化，所能引起的目標(biāo)函數(shù)值的變化。②λ數(shù)值的閉回路法計算在表上作業(yè)法中，空格數(shù)值的變化，其實(shí)是沿著其閉回路，從0號拐點(diǎn)開始，在閉回路的偶、奇拐點(diǎn)間作一加一減的波浪狀的傳遞，最后重新使方案達(dá)到平衡，而最終完成的。（此處可以結(jié)合板書舉例）由此，結(jié)合λ檢驗(yàn)數(shù)的含義，不難得到空格的λ檢驗(yàn)數(shù)的計算公式為：λij=空格(i,j)閉回路上偶拐點(diǎn)單位運(yùn)費(fèi)總和-奇拐點(diǎn)單位運(yùn)費(fèi)總和這種算法的缺點(diǎn)是：當(dāng)空格數(shù)較多時，由于每個空格都要先畫閉回路才能計算，所以計算工作量較大；但是它與的λ含義結(jié)合緊密。上表中，若空格(1,2)的數(shù)值由0變?yōu)?，為了保持該行運(yùn)輸量平衡，則需要將閉回路①號拐點(diǎn)的運(yùn)輸量減少1，同時需要將②拐點(diǎn)運(yùn)輸量增加1，來保持第四列運(yùn)輸量平衡，同理③號拐點(diǎn)的運(yùn)輸量需要減少1，才能保持第二行的物資平衡，到此，空格(1,2)數(shù)量增加1的變化才算最終完成。從而，空格(1,2)數(shù)值的這一單位數(shù)值的變化，所引起的目標(biāo)函數(shù)的變化（即它的λ值）為：λ12

=5-7+6-2=(5+6)-(7+2)=2其含義為：非基變量x12數(shù)值每增加1，則目標(biāo)函數(shù)值增加2。收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A1151050630745A28202715635A393204820收②③③λ數(shù)值的位勢法計算（對偶變量法）假設(shè)u1,u2,…,um是與m個發(fā)量約束相對應(yīng)的對偶變量，v1,v2,…,vn是與n個收量約束相對應(yīng)的對偶變量，則由對偶問題的經(jīng)濟(jì)性質(zhì)（影子價格）可知：λij=

cij-(u1,u2,…,um,v1,v2,…,vn)Pj又由前述運(yùn)輸問題系數(shù)矩陣的特點(diǎn)可知，變量xij的系數(shù)列向量里，只有第i和第j個元素是1，其他都是0，從而可得：λij=

cij-(ui+vj)從而，只要能計算出ui和vj的數(shù)值，便可以計算所有的λ檢驗(yàn)數(shù)了。已知有數(shù)字格的λ值為0，帶入計算式λij=

cij-(ui+vj)中，便可得到m+n-1個關(guān)于ui和vj的方程，但是ui加vj總共是m+n個未知量，若再給ui加vj中任意一個變量賦任意一個初始值，這樣便可以構(gòu)成一個變量和方程數(shù)都是m+n的線性方程組，解方程組便可得到所有的ui加vj值。由于ui加vj中，任意一個變量的初始值無論怎么賦，最終所求得的λ數(shù)值都一樣，所以該方法又被稱為位勢法，與勢能特性相仿。位勢法（對偶變量法）的表格算法的基本步驟如下：a、繪制如下的位勢表，將當(dāng)前方案表中有數(shù)字格的單位運(yùn)費(fèi)，填入位勢表的相應(yīng)格子里，并加括弧。b、令u1=0，利用有數(shù)字格λ值為0以及計算式λij=cij-(ui+vj)，直接在計算所有ui和vj的值，即ui和vj的和等于它倆交會處的，括弧中的數(shù)值。c、再次計算式λij=cij-(ui+vj)，以及上面已經(jīng)算出的ui和vj的值，計算所有空格的λ檢驗(yàn)數(shù)，并將結(jié)果填入表中相應(yīng)的格子里。④最優(yōu)性判斷方法若所有空格的λ值均為非負(fù)，則當(dāng)前目標(biāo)值達(dá)到最小值，當(dāng)前方案為最優(yōu)方案，否則為非最優(yōu)。此時，若存在某個空格的λ值為0，則為多重最優(yōu)解。收點(diǎn)發(fā)點(diǎn)B1B2B3B4uiA1(10)2(6)(7)0A2-1(2)2(6)-1A312(4)3-2vj10367（3）方案調(diào)整——基變換①確定調(diào)整對象——確定入基變量由λ值的含義可知，當(dāng)某個空格的λ值為負(fù)，則沿革它的閉回路作運(yùn)輸量調(diào)整，目標(biāo)函數(shù)值必然減小，所以選擇調(diào)整對象（入基變量）的原則為：選負(fù)λ值中的最小者所對應(yīng)的空格，作為調(diào)整對象（入基變量）。②確定最大調(diào)整量——確定出基變量因?yàn)榭崭襁\(yùn)輸量發(fā)生變化，必然會導(dǎo)致其閉回路上所有奇拐點(diǎn)的運(yùn)輸量減少，所以，允許的最大調(diào)整量，即奇拐點(diǎn)上的最小運(yùn)輸量，否則，下一個方案中最小運(yùn)輸量所在的格子必出現(xiàn)負(fù)數(shù)（不可行）。調(diào)整后，奇拐點(diǎn)上運(yùn)輸量最小的格子變?yōu)?值，即它就是出基變量，又非基變量用空格表示，所以調(diào)整后，0不用填入表中。③閉回路法完成方案調(diào)整確定最大調(diào)整量后，在閉回路的所有偶拐點(diǎn)處加上最大調(diào)正量；在所有奇拐點(diǎn)處減去最大調(diào)整量，便完成了方案的調(diào)整。新方案再返回到（2），進(jìn)行最有性判斷。值得注意的是，調(diào)整后0的填寫方法。由上一步位勢表可知λ21=-1<0，即當(dāng)前方案非最優(yōu)。選空格(2,1)作為調(diào)整對象，畫出其閉回路并進(jìn)行拐點(diǎn)編號如圖所示。奇拐點(diǎn)上兩個量相等，都是最小值15，所以調(diào)整量取15。按照“偶加奇減”的原則調(diào)整得如下方案。收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A1151050630745A28202715635A393204820收②③收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A11050645745A215820270635A393204820收整后，兩個奇拐點(diǎn)的運(yùn)輸量都變?yōu)榱?，但是出基變量只有一個，所以兩處中，必須有一處要填上0，表示它是一個等于0的非基變量。對調(diào)整后的新方案，畫位勢表，計算空格λ檢驗(yàn)數(shù)如下?？梢?，此時表中所有空格的λ檢驗(yàn)數(shù)均為非負(fù)數(shù)，即當(dāng)前方案已經(jīng)為最優(yōu)方案，按此方案進(jìn)行運(yùn)輸時，最小總運(yùn)輸費(fèi)用為：Minz=45×7+15×8+20×2+20×4=555從最優(yōu)方案的位勢表可見，不存在空格的λ檢驗(yàn)數(shù)為0，所以此時的最優(yōu)運(yùn)輸方案，是該運(yùn)輸問題唯一的總費(fèi)用最小化運(yùn)輸方案。收點(diǎn)發(fā)點(diǎn)B1B2B3B4uiA112(6)(7)0A2(8)(2)2(6)-1A322(4)3-2vj93673.3非平衡運(yùn)輸問題的解法（1）供大于銷的問題指總發(fā)量大于總收量，收量約束中不存在“≥型”約束的運(yùn)輸問題。其求解方法包括如下幾個步驟：①

添加一個虛擬收點(diǎn)，令其收量等于總發(fā)量與原總收量的差額；②

各實(shí)發(fā)點(diǎn)與虛收點(diǎn)間的單位運(yùn)費(fèi)按如下方法確定：A、剩余時不產(chǎn)生任何損失，則該發(fā)點(diǎn)到虛收點(diǎn)的單位運(yùn)費(fèi)為：零；B、剩余時產(chǎn)生一定的損失，該發(fā)點(diǎn)到虛收點(diǎn)單位運(yùn)費(fèi)：單位損失費(fèi)；C、剩余時會產(chǎn)生巨大的損失，或者指令性要求該發(fā)點(diǎn)發(fā)量必須全部發(fā)出，則該發(fā)點(diǎn)到虛收點(diǎn)的單位運(yùn)費(fèi)為：M；③

表上作業(yè)法求解，最優(yōu)方案中，虛收點(diǎn)對各實(shí)發(fā)點(diǎn)的物資接收量，表示對應(yīng)發(fā)點(diǎn)，在總運(yùn)輸費(fèi)用最小化時的物資剩余量。3.3.1一般非平衡運(yùn)輸問題的解法例3-4將下面的非平衡運(yùn)輸問題，轉(zhuǎn)換為平衡運(yùn)輸問題。已知三個發(fā)點(diǎn)的情況：

A1如果有剩余的話，單位剩余物資會造成損失7；A2的剩余物資沒有任何損失；指令性的要求A3必須全部發(fā)出。則，問題轉(zhuǎn)化為平衡運(yùn)輸問題后如下表所示：收點(diǎn)發(fā)點(diǎn)B1B2B3發(fā)量A1105645A282735A393420收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A11056745A2827035A3934M20收2）供小于銷的問題指總發(fā)量小于總收量，收量約束中不存在“≥型”約束的運(yùn)輸問題。其求解方法包括如下幾個步驟：①

添加一個虛擬發(fā)點(diǎn)，令其發(fā)量等于原總發(fā)量與總收量的差額；②

虛發(fā)點(diǎn)與各實(shí)收點(diǎn)間的單位運(yùn)費(fèi)按如下方法確定：a、缺貨時無損失，可以無條接受件最大限度的缺貨，則虛發(fā)點(diǎn)到這樣的收點(diǎn)的單位運(yùn)費(fèi)為：零；b、缺貨時有一定的損失，在供方給予相應(yīng)的補(bǔ)償后，可以接受最大限度的缺貨，則虛發(fā)點(diǎn)到這樣的收點(diǎn)的單位運(yùn)費(fèi)為：單位補(bǔ)償費(fèi)；c、缺貨時損失巨大，完全不能接受缺貨，或者指令性要求其需求必須滿足，則虛發(fā)點(diǎn)到這樣的收點(diǎn)的單位運(yùn)費(fèi)為：M；③

表上作業(yè)法求解，最優(yōu)方案中，虛發(fā)點(diǎn)向各實(shí)收點(diǎn)發(fā)送的物資量，表示對應(yīng)收點(diǎn)，在總運(yùn)輸費(fèi)用最小時的缺貨量。允許的缺貨量有限時，約束表現(xiàn)為“≥型”，在復(fù)雜問題中討論。例3-5將下面的非平衡運(yùn)輸問題，轉(zhuǎn)換為平衡運(yùn)輸問題。已知三個收點(diǎn)的情況：

B1如果缺貨，每缺1個會造成12的損失，發(fā)貨方答應(yīng)全額補(bǔ)償；B2缺貨時不會造成任何不利影響；B3缺貨損失太大，不允許缺貨。則，問題轉(zhuǎn)化為平衡運(yùn)輸問題后如下表所示：收點(diǎn)發(fā)點(diǎn)B1B2B3發(fā)量A1105645A282735收量35402580100收點(diǎn)發(fā)點(diǎn)B1B2B3發(fā)量A1105645A282735A3120M20收量152020100553.3.2復(fù)雜非平衡運(yùn)輸問題的解法此處的復(fù)雜非平衡運(yùn)輸問題僅指收量約束中有“≥型”約束的問題。例3-6將下面的非平衡運(yùn)輸問題，轉(zhuǎn)換為平衡運(yùn)輸問題。（1）確定無上限需求點(diǎn)的可能最大獲取量在該類運(yùn)輸問題中，往往有些收點(diǎn)只表明了最低需求量，而并無明確的收量上限。此時，為了便于轉(zhuǎn)換為平衡運(yùn)輸問題，需要確定其可能的最大獲取量，用來等效的表示其需求的上限值。某收點(diǎn)的最大可獲取量=總發(fā)量-其它各點(diǎn)需求量下限值之和收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A11056745A2827355A3934530收量15202045需求描述嚴(yán)格為15≥10前提下有償接受缺貨每個補(bǔ)償12無條件接受最大程度的缺貨45為底值上不封頂本例中B4的需求上限可以認(rèn)為是：(45+55+30)-(15+10+0)=105（2）確定最大總需求當(dāng)用最大可獲取量代表無上限需求點(diǎn)的需求上限后，表中每個收點(diǎn)的需求便都具備了上限值，此時，將所有上限值加起來，即為最大總需求。本例中，最大總需求=15+20+20+105=160（3）添加虛擬發(fā)點(diǎn)最大總需求便是用來轉(zhuǎn)換為平衡運(yùn)輸問題的平衡點(diǎn)運(yùn)輸量，次量一般大于總發(fā)量，所以轉(zhuǎn)換時需要添加虛擬發(fā)點(diǎn)，并令其發(fā)量為：虛發(fā)點(diǎn)的發(fā)量=最大總需求-總發(fā)量本例中，虛發(fā)點(diǎn)A4的發(fā)量：a4=160-130=30（4）虛發(fā)點(diǎn)到各實(shí)收點(diǎn)的單位運(yùn)費(fèi)虛發(fā)點(diǎn)到各實(shí)收點(diǎn)的單位運(yùn)費(fèi)，分為以下三種情況：①當(dāng)某個收點(diǎn)的收量為嚴(yán)格的確定數(shù)值時，虛發(fā)點(diǎn)到該類收點(diǎn)的單位運(yùn)費(fèi)為：M，表示不接收來自虛發(fā)點(diǎn)的物資量，從而保障需求實(shí)現(xiàn)。（如B1）②當(dāng)某個收點(diǎn)的收量下限值為零時，虛發(fā)點(diǎn)到這類收點(diǎn)的單位運(yùn)費(fèi)分為兩種情況：當(dāng)缺貨不存在損失賠償時為0；當(dāng)缺貨存在損失賠償時為單位賠償費(fèi)。虛發(fā)點(diǎn)發(fā)往該點(diǎn)的物資量，即為缺貨量。（如B3）③當(dāng)某個收點(diǎn)的收量下限值不為零時，為了便于問題的處理，將該收點(diǎn)按需求量分解為兩個組成部分（在表格里表示為兩個收點(diǎn)）：需求下限部分：用原編號表示，該部分的收量為需求量上限值，虛發(fā)點(diǎn)到該部分的單位運(yùn)費(fèi)為：M；上下限差額部分：用原編號加撇號表示，該部分的收量為需求量上下限的差額，虛發(fā)點(diǎn)到該部分的單位運(yùn)費(fèi)為：0。如本例中，將B2分解為B2和B′2，B2的收量為10，與虛發(fā)點(diǎn)間的單位運(yùn)費(fèi)為M，B′2的收量為10，與虛發(fā)點(diǎn)間的單位運(yùn)費(fèi)為0。（5）利用表上作業(yè)法求解經(jīng)過上述四個步驟的處理，問題已經(jīng)轉(zhuǎn)變?yōu)槠胶膺\(yùn)輸問題，利用表上作業(yè)即可實(shí)現(xiàn)問題的求解。最優(yōu)方案中，虛發(fā)點(diǎn)給各個實(shí)收點(diǎn)的所發(fā)送的物資量，表示各個收點(diǎn)相對與需求上限的不足量（缺貨量）。其中第（4）步可以總結(jié)如下表所示：例3-6最終轉(zhuǎn)換為平衡運(yùn)輸問題的方案表如下：收點(diǎn)發(fā)點(diǎn)B1B2B′2B3B4B′4發(fā)量A1105567745A282273355A393345530A4MM120M030收量151010204560160收點(diǎn)收量實(shí)際發(fā)點(diǎn)到此點(diǎn)運(yùn)價虛設(shè)發(fā)點(diǎn)到此點(diǎn)運(yùn)價

收量同時具有上下界的收點(diǎn)Bj下界值實(shí)際運(yùn)價M

Bj’上下界值之差實(shí)際運(yùn)價0收量只具有上界值的收點(diǎn)Bj上界值實(shí)際運(yùn)價0收量為嚴(yán)格確定值的收點(diǎn)Bj實(shí)際收量實(shí)際運(yùn)價M3.4運(yùn)輸問題應(yīng)用舉例例3-7問題背景：某柴油機(jī)生產(chǎn)廠按合同規(guī)定，須于當(dāng)年的每個季度末分別提供10，15，25，20臺同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如下表所示。又每個季度生產(chǎn)的柴油機(jī)并不一定在當(dāng)季交貨，如果當(dāng)季不交貨，每臺柴油機(jī)每積壓一個季度，需儲存、維護(hù)等費(fèi)用0.15萬元。問題目標(biāo)：要求在完成合同的情況下，作出使該廠全年生產(chǎn)費(fèi)用(包括儲存、維護(hù)費(fèi)用等)最小的最優(yōu)生產(chǎn)與經(jīng)營決策。季度生產(chǎn)能力(臺)單位成本(元)Ⅰ2510.8Ⅱ3511.1Ⅲ3011.0Ⅳ1011.3解：由于每個季度生產(chǎn)出來的柴油機(jī)不一定當(dāng)季交貨，所以令xij為第i個季度生產(chǎn)的，用于第j個季度交貨的柴油機(jī)數(shù)。根據(jù)合同要求，必須滿足：把第i季度生產(chǎn)的柴油機(jī)數(shù)目看作第i個發(fā)點(diǎn)的發(fā)量；把第j季度交貨的柴油機(jī)數(shù)目看作第j個收點(diǎn)的收量；成本加儲存、維護(hù)等費(fèi)用看作單位運(yùn)費(fèi)?？蓸?gòu)造出下面的產(chǎn)銷平衡問題（把一個生產(chǎn)決策問題轉(zhuǎn)為運(yùn)輸問題）：滿足交貨要求則：x11

=10x12+x22

=15x13+x23+x33

=25x14+x24+x34+x44=20滿足生產(chǎn)能力則：x11+x12+x13+x14

≤

25x22+x23+x24

≤

35x33+x34

≤

30x44≤10

銷地產(chǎn)地ⅠⅡⅢⅣD生產(chǎn)量Ⅰ10.810.9511.111.25025ⅡM11.111.2511.4035ⅢMM1111.15030ⅣMMM11.3010需求量1015252030100例3-8問題背景：騰飛電子儀器公司在大連和廣州有兩個分廠生產(chǎn)同一種儀器，大連分廠每月生產(chǎn)450臺,廣州分廠每月生產(chǎn)600臺。該公司在上海和天津有兩個銷售公司，負(fù)責(zé)對南京、濟(jì)南、南昌、青島四個城市的市場進(jìn)行儀器供應(yīng)。另外，因?yàn)榇筮B距離青島較近，公司同意大連分廠