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

3.1運(yùn)輸問(wèn)題概述第3章運(yùn)輸規(guī)劃一般來(lái)說(shuō)，運(yùn)輸問(wèn)題是指：某種物資由m個(gè)發(fā)送點(diǎn)（發(fā)點(diǎn)）運(yùn)往n個(gè)接收點(diǎn)（收點(diǎn)），已知各個(gè)發(fā)點(diǎn)的最大供給量（發(fā)量）、各個(gè)收點(diǎn)的需求量（收量），以及各發(fā)點(diǎn)向各收點(diǎn)的單位運(yùn)價(jià)，如下表所示，在各收點(diǎn)收量達(dá)到滿(mǎn)足的條件下，求總運(yùn)費(fèi)最低的運(yùn)輸方案的問(wèn)題。3.1.1運(yùn)輸問(wè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)輸問(wèn)題的類(lèi)型根據(jù)實(shí)踐應(yīng)用中的具體情況，運(yùn)輸問(wèn)題一般可以分為以下幾種類(lèi)型。（1）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

=10x12+x22

=15x13+x23+x33

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

≤

25x22+x23+x24

≤

35x33+x34

≤

30x44≤10

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