第3章 運輸規(guī)劃

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

收量同時具有上下界的收點Bj下界值實際運價M

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

=10x12+x22

=15x13+x23+x33

=25x14+x24+x34+x44=20滿足生產能力則：x11+x12+x13+x14

≤

25x22+x23+x24

≤

35x33+x34

≤

30x44≤10

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