建模：-運(yùn)輸問題

建模：-運(yùn)輸問題.ppt建模：-運(yùn)輸問題.ppt第3章運(yùn)輸問題第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型第2節(jié)表上作業(yè)法第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法第4節(jié)應(yīng)用舉例第5節(jié)Lingo程序求解運(yùn)輸問題第3章運(yùn)輸問題第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型引例某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地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)用最?。緽1B2B3產(chǎn)量A1646200A2655300銷量150150200運(yùn)費(fèi)表引例某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地B1、B2、引例解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到數(shù)學(xué)模型：引例解：產(chǎn)銷平衡問題：系數(shù)矩陣111000

000111100100

010010

001001m個行約束n個列約束系數(shù)矩陣111第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型系數(shù)矩陣A的特點(diǎn)：1、約束條件左邊所有系數(shù)都是0或1，而且每一列中恰好只有兩個元素是1，其他元素都是0。列向量為：共有m×n個Pij。2、前m個每行有n個1（其余都是0），從第m+1行到第n行，每行有m個1（其余都是0）。第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型系數(shù)矩陣A的特點(diǎn)：共有m×n個P第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型已知有m個生產(chǎn)地點(diǎn)Ai,i=1,2,…，m?？晒?yīng)某種物資，其供應(yīng)量(產(chǎn)量)分別為ai，i=1，2，…，m，有n個銷地Bj，j=1,2,…,n，其需要量分別為bj，j=1,2,…,n，從Ai到Bj運(yùn)輸單位物資的運(yùn)價(單價)為cij，這些數(shù)據(jù)可匯總于產(chǎn)銷平衡表和單位運(yùn)價表中，見表3-1，表3-2。有時可把這兩表合二為一。第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型已知有m個生產(chǎn)地點(diǎn)Ai,i=1,第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型銷地產(chǎn)地12……n產(chǎn)量1c11c12……c1na12c21c22……c2na2………………………………mcm1cm2……cmnam銷量b1b2……bn運(yùn)輸問題的產(chǎn)銷表第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型銷地產(chǎn)地第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型若用xij表示從Ai到Bj的運(yùn)量，那么在產(chǎn)銷平衡的條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，

數(shù)學(xué)模型這就是運(yùn)輸問題的數(shù)學(xué)模型。它包含m×n個變量，(m+n)個約束方程。其系數(shù)矩陣的結(jié)構(gòu)比較松散，且特殊。第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型若用xij表示從Ai到Bj的運(yùn)量第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型系數(shù)矩陣A的特點(diǎn)：1、約束條件左邊所有系數(shù)都是0或1，而且每一列中恰好只有兩個元素是1，其他元素都是0。列向量為：共有m×n個Pij。第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型系數(shù)矩陣A的特點(diǎn)：共有m×n個P第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型2、前m個每行有n個1（其余都是0），從第m+1行到第n行，每行有m個1（其余都是0）。第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型2、前m個每行有n個1（其余都是第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型系數(shù)矩陣中對應(yīng)于變量xij的系數(shù)向量Pij，其分量中除第i個和第m+j個為1以外，其余的都為零。即Pij=(0,…,1,0,…,0,1,0,…,0)T=ei+em+j

對產(chǎn)銷平衡的運(yùn)輸問題，由于有以下關(guān)系式存在：第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型系數(shù)矩陣中對應(yīng)于變量xij的系數(shù)第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型所以，該模型最多只有m+n-1個獨(dú)立約束方程，由于有以上特征，求解運(yùn)輸問題時，可用比較簡便的計算方法，習(xí)慣上稱為表上作業(yè)法。第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型所以，該模型最多只有m+n-1個第2節(jié)表上作業(yè)法表上作業(yè)法是單純形法在求解運(yùn)輸問題時的一種簡化方法，其實質(zhì)是單純形法。但具體計算和術(shù)語有所不同?？蓺w納為：(1)找出初始基可行解。即在(m×n)產(chǎn)銷平衡表上（用西北角法、最小元素法，Vogel法）給出m+n-1個數(shù)字，稱為數(shù)字格。它們就是初始基變量的取值。第2節(jié)表上作業(yè)法表上作業(yè)法是單純形法在求解運(yùn)輸問題時的一第2節(jié)表上作業(yè)法(2)求各非基變量的檢驗數(shù)，即在表上計算空格的檢驗數(shù)，判別是否達(dá)到最優(yōu)解。如已是最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一步。(3)確定換入變量和換出變量，找出新的基可行解。在表上用閉回路法調(diào)整。(4)重復(fù)(2)，(3)直到得到最優(yōu)解為止。第2節(jié)表上作業(yè)法(2)求各非基變量的檢驗數(shù)，即在表上計第2節(jié)表上作業(yè)法給出初始調(diào)運(yùn)方案最優(yōu)性檢驗調(diào)整上述方案停是否相應(yīng)于單純形表的初始基本可行解第2節(jié)表上作業(yè)法給出初始調(diào)運(yùn)方案最優(yōu)性檢驗調(diào)整上述方案停第2節(jié)表上作業(yè)法例1

某公司經(jīng)銷甲產(chǎn)品。它下設(shè)三個加工廠。每日的產(chǎn)量分別是：A1為7噸，A2為4噸，A3為9噸。該公司把這些產(chǎn)品分別運(yùn)往四個銷售點(diǎn)。各銷售點(diǎn)每日銷量為：B1為3噸，B2為6噸，B3為5噸，B4為6噸。已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價為表3-3所示。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)為最少。第2節(jié)表上作業(yè)法例1某公司經(jīng)銷甲產(chǎn)品。它下設(shè)三個加第2節(jié)表上作業(yè)法解

先作出這問題的產(chǎn)銷平衡表和單位運(yùn)價表，見表3-3，表3-4表3-3單位運(yùn)價表第2節(jié)表上作業(yè)法解先作出這問題的產(chǎn)銷平衡表和單位運(yùn)價第2節(jié)表上作業(yè)法表3-4產(chǎn)銷平衡表第2節(jié)表上作業(yè)法表3-4產(chǎn)銷平衡表第2節(jié)表上作業(yè)法用線性規(guī)劃法處理此問題。設(shè)由產(chǎn)地i到銷地j的運(yùn)量為xij，模型為：minz=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij≥0(i=1,2,3;j=1,2,3,4)運(yùn)輸問題一般用表上作業(yè)法求解，需建立表格模型：第2節(jié)表上作業(yè)法用線性規(guī)劃法處理此問題。設(shè)由產(chǎn)地i到銷地第2節(jié)表上作業(yè)法第2節(jié)表上作業(yè)法2.1確定初始基可行解這與一般線性規(guī)劃問題不同。產(chǎn)銷平衡的運(yùn)輸問題總是存在可行解。因有必存在xij≥0，i=1，…，m，j=1，…，n這就是可行解。又因0≤xij≤min(aj，bj)故運(yùn)輸問題必存在最優(yōu)解。2.1確定初始基可行解這與一般線性規(guī)劃問題不同。必存在x2.1確定初始基可行解確定初始基可行解的方法很多，有西北角法，最小元素法和伏格爾(Vogel)法。一般希望的方法是既簡便，又盡可能接近最優(yōu)解。下面介紹伏格爾(Vogel)法：2.1確定初始基可行解確定初始基可行解的方法很多，1.伏格爾法伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有一個差額。差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時，運(yùn)費(fèi)增加越多。因而對差額最大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)。1.伏格爾法伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運(yùn)費(fèi)伏格爾法的步驟1.計算每行、列兩個最小運(yùn)價的差；2.找出最大差所在的行或列；3.找出該行或列的最小運(yùn)價，確定供求關(guān)系，最大量的供應(yīng)；4.劃掉已滿足要求的行或(和)列，如果需要同時劃去行和列，必須要在該行或列的任意位置填個“0”；5.在剩余的運(yùn)價表中重復(fù)1~4步，直到得到初始基可行解。伏格爾法的步驟1.計算每行、列兩個最小運(yùn)價的差；銷地產(chǎn)地B1B2B3B4產(chǎn)量行差①②③③219284116A374105912銷量3656列差①2513②212③④63√3331√√52√122銷地B1B2B3B4產(chǎn)量行差①②③③地產(chǎn)地B1B2B3B4產(chǎn)量A1527A2314A3639銷量3656運(yùn)量表（vogel法）銷地B1B2B3B4產(chǎn)量A1527A2311.伏格爾法伏格爾法的步驟是：第一步：在表3-3中分別計算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行，見表3-10。1.伏格爾法伏格爾法的步驟是：1.伏格爾法第二步：從行或列差額中選出最大者，選擇它所在行或列中的最小元素。在表3-10中B2列是最大差額所在列。B2列中最小元素為4，可確定A3的產(chǎn)品先供應(yīng)B2的需要。得表3-111.伏格爾法第二步：從行或列差額中選出最大者，選擇它所在行1.伏格爾法同時將運(yùn)價表中的B2列數(shù)字劃去。

如表3-12所示。1.伏格爾法同時將運(yùn)價表中的B2列數(shù)字劃去。

如表3-121.伏格爾法第三步：對表3-12中未劃去的元素再分別計算出各行、各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行。重復(fù)第一、二步。直到給出初始解為止。用此法給出例1的初始解列于表3-13。1.伏格爾法第三步：對表3-12中未劃去的元素再分別計算出1.伏格爾法由以上可見：伏格爾法同最小元素法除在確定供求關(guān)系的原則上不同外，其余步驟相同。伏格爾法給出的初始解比用最小元素法給出的初始解更接近最優(yōu)解。本例用伏格爾法給出的初始解就是最優(yōu)解。1.伏格爾法由以上可見：2-2最優(yōu)解的判別2-2最優(yōu)解的判別判別的方法是計算空格(非基變量)的檢驗數(shù)cij-CBB-1Pij，i,j∈N。因運(yùn)輸問題的目標(biāo)函數(shù)是要求實現(xiàn)最小化，故當(dāng)所有的cij-CBB-1Pij≥0時，為最優(yōu)解。2-2最優(yōu)解的判別2-2最優(yōu)解的判別2-2最優(yōu)解的判別σij≥0（因為目標(biāo)函數(shù)要求最小化）表格中有調(diào)運(yùn)量的地方為基變量，空格處為非基變量?；兞康臋z驗數(shù)σij＝0，非基變量的檢驗數(shù)σij≥0。σij<0表示運(yùn)費(fèi)減少，σij>0表示運(yùn)費(fèi)增加。有兩種檢驗方法：位勢法和閉合回路法。2-2最優(yōu)解的判別σij≥0（因為目標(biāo)函數(shù)要求最小化）1.閉回路法1.閉回路法1.閉回路法1.閉回路法1.閉回路法在給出調(diào)運(yùn)方案的計算表上，如表3-13，從每一空格出發(fā)找一條閉回路。它是以某空格為起點(diǎn)。用水平或垂直線向前劃，當(dāng)碰到一數(shù)字格時可以轉(zhuǎn)90°后，繼續(xù)前進(jìn)，直到回到起始空格為止。閉回路如圖3-1的(a),(b),(c)等所示。1.閉回路法在給出調(diào)運(yùn)方案的計算表上，如表3-13，從每一空1.閉回路法從每一空格出發(fā)一定存在和可以找到唯一的閉回路。因(m+n-1)個數(shù)字格(基變量)對應(yīng)的系數(shù)向量是一個基。任一空格(非基變量)對應(yīng)的系數(shù)向量是這個基的線性組合。1.閉回路法從每一空格出發(fā)一定存在和可以找到唯一的閉回路。1.閉回路法閉回路法計算檢驗數(shù)的經(jīng)濟(jì)解釋為：在已給出初始解的表3-9中，

可從任一空格出發(fā)，如(A1，B1)，

若讓A1的產(chǎn)品調(diào)運(yùn)1噸給B1。為了保持產(chǎn)銷平衡，就要依次作調(diào)整：

在(A1，B3)處減少1噸，(A2，B3)處增加1噸，(A2，B1)處減少1噸，即構(gòu)成了以(A1，B1)空格為起點(diǎn)，其他為數(shù)字格的閉回路。1.閉回路法閉回路法計算檢驗數(shù)的經(jīng)濟(jì)解釋為：1.閉回路法如表3-14中的虛線所示。在這表中閉回路各頂點(diǎn)所在格的右上角數(shù)字是單位運(yùn)價。B1B2B3B4產(chǎn)量A17A2

4A39銷量36563113101927410583416331.閉回路法如表3-14中的虛線所示。在這表中閉回路各頂點(diǎn)所B1B2B3B4產(chǎn)量A17A24A39銷量3656313463（＋1）（＋1）（－1）（－1）①②③③

計算如下：空格處（A1

B1）＝

(1×3)＋｛(－1)×3｝＋(1×2)＋｛(－1)×1｝＝1

此數(shù)即為該空格處的檢驗數(shù)。1⑦⑾④⑨⑩⑩⑧⑤B1B2B3B4產(chǎn)量A17A24A39銷量3656313461.閉回路法可見這個調(diào)整方案使運(yùn)費(fèi)增加

(+1)×3+(-1)×3+(+1)×2+(-1)×１=1(元)

這表明若這樣調(diào)整運(yùn)量將增加運(yùn)費(fèi)。將“1”這個數(shù)填入(A1，B1)格，這就是檢驗數(shù)。按以上所述，可找出所有空格的檢驗數(shù)，

見表3-15。1.閉回路法可見這個調(diào)整方案使運(yùn)費(fèi)增加

(+1)×3+(-1B1B2B3B4產(chǎn)量A17A24A39銷量365631363124①②③③⑦⑾④⑨⑩⑩⑧⑤B1B2B3B4產(chǎn)量A17A24A39銷量365631363B1B2B3B4產(chǎn)量A17A24A39銷量36563136312-14①②③③⑦⑾④⑨⑩⑩⑧⑤B1B2B3B4產(chǎn)量A17A24A39銷量365631363B1B2B3B4產(chǎn)量A17A24A39銷量365631363121-14①②③③⑦⑾④⑨⑩⑩⑧⑤B1B2B3B4產(chǎn)量A17A24A39銷量365631363B1B2B3B4產(chǎn)量A17A24A39銷量365631363121-1124①②③③⑦⑾④⑨⑩⑩⑧⑤B1B2B3B4產(chǎn)量A17A24A39銷量365631363B1B2B3B4產(chǎn)量A17A24A39銷量365631363121-112104①②③③⑦⑾④⑨⑩⑩⑧⑤B1B2B3B4產(chǎn)量A17A24A39銷量3656313631.閉回路法按以上所述，找出所有空格的檢驗數(shù)，

見表3-15。B1B2B3B4產(chǎn)量A17A24A39銷量365600000121-112100檢驗數(shù)表1.閉回路法按以上所述，找出所有空格的檢驗數(shù)，

見表3-151.閉回路法當(dāng)檢驗數(shù)還存在負(fù)數(shù)時，說明原方案不是最優(yōu)解，要繼續(xù)改進(jìn)。σij<0表示運(yùn)費(fèi)減少，σij>0表示運(yùn)費(fèi)增加。1.閉回路法當(dāng)檢驗數(shù)還存在負(fù)數(shù)時，說明原方案不是最優(yōu)解，要繼2.位勢法用閉回路法求檢驗數(shù)時，需給每一空格找一條閉回路。當(dāng)產(chǎn)銷點(diǎn)很多時，這種計算很繁瑣。下面介紹較為簡便的方法——位勢法。設(shè)u1，u2，…，um;v1，v2，…，vn是對應(yīng)運(yùn)輸問題的m+n個約束條件的對偶變量。B是含有一個人工變量xa的(m+n)×(m+n)初始基矩陣。人工變量xa在目標(biāo)函數(shù)中的系數(shù)ca=0，從線性規(guī)劃的對偶理論可知。2.位勢法用閉回路法求檢驗數(shù)時，需給每一空格找一條閉回路2.位勢法2.位勢法2.位勢法由單純形法得知所有基變量的檢驗數(shù)等于0。即

因為CBB-1Pij=ui+vj,于是檢驗數(shù)2.位勢法由單純形法得知所有基變量的檢驗數(shù)等于0。即因2.位勢法因非基變量的檢驗數(shù)這就可以從已知的ui，vj值中求得。這些計算可在表格中進(jìn)行。

2.位勢法因非基變量的檢驗數(shù)這就可以從已知的ui，vj值B1B2B3B4A1310u1A212u2A345u3v1v2v3v4B1B2B3B4A1293100A21829－1A3－34－25－529310u2+v1=1

u2+v3=2

u3+v2=4u1+v4=10

u1+v3=3u3+v4=5令：u1＝0u1＝0v1＝2u2＝－1v2＝9u3＝－5v3＝3v4＝10(ui+vj)B1B2B3B4A1310u1A212u2A345u3v1v

按σij=cij－(ui+vj)計算檢驗數(shù)，并以σij≥0檢驗，或用(ui+vj)

－cij

≤0檢驗。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A3－34-25(ui+vj)－B1B2B3B4A11200A2010－1A3100120＝表中還有負(fù)數(shù)，說明還未得到最優(yōu)解，應(yīng)繼續(xù)調(diào)整。σij按σij=cij－(ui+vj)計算檢驗數(shù)，B1B2B2.3

改進(jìn)的方法-閉回路調(diào)整法當(dāng)在表中空格處出現(xiàn)負(fù)檢驗數(shù)時，表明未得最優(yōu)解。若有兩個和兩個以上的負(fù)檢驗數(shù)時，一般選其中最小的負(fù)檢驗數(shù)，以它對應(yīng)的空格為調(diào)入格。即以它對應(yīng)的非基變量為換入變量。由表3-18得(2，4)為調(diào)入格。以此格為出發(fā)點(diǎn)，作一閉回路，如表3-19所示。2.3改進(jìn)的方法-閉回路調(diào)整法當(dāng)在表中空格處出現(xiàn)負(fù)檢驗數(shù)時2.3

改進(jìn)的方法-閉回路調(diào)整法B1B2B3B4產(chǎn)量A17A24A39銷量3656313463（＋1）（＋1）（－1）（－1）2.3改進(jìn)的方法-閉回路調(diào)整法B1B2B3B4產(chǎn)量A17A2.3

改進(jìn)的方法-閉回路調(diào)整法(2，4)格的調(diào)入量θ是選擇閉回路上具有(-1)的數(shù)字格中的最小者。即θ=min(1,3)=1(其原理與單純形法中按θ規(guī)劃來確定換出變量相同)。然后按閉回路上的正、負(fù)號，加入和減去此值，得到調(diào)整方案，如表3-20所示。2.3改進(jìn)的方法-閉回路調(diào)整法(2，4)格的調(diào)入量θ是選擇B1B2B3B4產(chǎn)量A1527A2314A3639銷量36566563銷量9A34A27A1產(chǎn)量B4B3B2B1313463（＋1）（＋1）（－1）（－1）B1B2B3B4產(chǎn)量A1527A2314A3639銷量365B1B2B3B4A10200A20210A390120經(jīng)檢驗所有σij≥0得到最優(yōu)解，最小運(yùn)費(fèi)為85元。v4v3v2v1u354A3u281A2u1103A1B4B3B2B110393－55－24－2A3－28171A2010393A1B4B3B2B1(ui+vj)cijB1B2B3B4A10200A20210A390120經(jīng)檢驗2.4

表上作業(yè)法計算中的問題1.無窮多最優(yōu)解2.退化2.4表上作業(yè)法計算中的問題1.無窮多最優(yōu)解2.4

表上作業(yè)法計算中的問題1.無窮多最優(yōu)解在本章2.1節(jié)中提到，產(chǎn)銷平衡的運(yùn)輸問題必定存在最優(yōu)解。那么有唯一最優(yōu)解還是無窮多最優(yōu)解?判別依據(jù)與第1章3.3節(jié)講述的相同。即某個非基變量(空格)的檢驗數(shù)為0時，該問題有無窮多最優(yōu)解。表3-21空格(1，1)的檢驗數(shù)是0，表明例1有無窮多最優(yōu)解。2.4表上作業(yè)法計算中的問題1.無窮多最優(yōu)解2.4

表上作業(yè)法計算中的問題B1B2B3B4A10200A20210A390120空格(1，1)的檢驗數(shù)是0，表明有無窮多最優(yōu)解。2.4表上作業(yè)法計算中的問題B1B2B3B4A102002.4

表上作業(yè)法計算中的問題可在表3-20中以(1，1)為調(diào)入格，作閉回路(1，1)+--(1，4)---(2，4)+--(2，1)---(1，1)+。確定θ=min(2,3)=2。經(jīng)調(diào)整后得到另一最優(yōu)解，見表3-22。B1B2B3B4產(chǎn)量A1527A2314A3639銷量3656+2+2-2-22.4表上作業(yè)法計算中的問題可在表3-20中以(1，1)2.4

表上作業(yè)法計算中的問題表3-222.4表上作業(yè)法計算中的問題表3-222.4

表上作業(yè)法計算中的問題2.退化

用表上作業(yè)法求解運(yùn)輸問題當(dāng)出現(xiàn)退化時，在相應(yīng)的格中一定要填一個0，以表示此格為數(shù)字格。有以下兩種情況：2.4表上作業(yè)法計算中的問題2.退化

用表上作業(yè)法求解2.4

表上作業(yè)法計算中的問題(1)當(dāng)確定初始解的各供需關(guān)系時，若出現(xiàn)Ai處的余量等于Bj處的需量。需在單位運(yùn)價表上相應(yīng)地要劃去一行和一列。為了使在產(chǎn)銷平衡表上有(m+n-1)個數(shù)字格。這時需要添一個“0”。2.4表上作業(yè)法計算中的問題(1)當(dāng)確定初始解的各供需2.4

表上作業(yè)法計算中的問題(2)在用閉回路法調(diào)整時，在閉回路上出現(xiàn)兩個和兩個以上的具有(-1)標(biāo)記的相等的最小值。這時只能選擇其中一個作為調(diào)入格。經(jīng)調(diào)整后，得到退化解。另一個數(shù)字格必須填入一個0，表明它是基變量。當(dāng)出現(xiàn)退化解后，并作改進(jìn)調(diào)整時，可能在某閉回路上有標(biāo)記為(-1)的取值為0的數(shù)字格，這時應(yīng)取調(diào)整量θ=0。2.4表上作業(yè)法計算中的問題(2)在用閉回路法調(diào)整時，第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法但是實際問題中產(chǎn)銷往往是不平衡的。就需要把產(chǎn)銷不平衡的問題化成產(chǎn)銷平衡的問題。當(dāng)產(chǎn)大于銷，就要考慮多余的物資在哪一個產(chǎn)地就地儲存的問題。這就需要增加一個假想的銷地j=n+1(實際上是儲存)該銷地總需要量為產(chǎn)量銷量在單位運(yùn)價表中從各產(chǎn)地到假想銷地的單位運(yùn)價為0，這就轉(zhuǎn)化成一個產(chǎn)銷平衡的運(yùn)輸問題第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法但是實際問題中產(chǎn)第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法當(dāng)銷大于產(chǎn)時，可以在產(chǎn)銷平衡表中增加一個假想的產(chǎn)地i=m+1，該地產(chǎn)量為在單位運(yùn)價表上令從該假想產(chǎn)地到各銷地的運(yùn)價為0，就可以轉(zhuǎn)化為一個產(chǎn)銷平衡的運(yùn)輸問題。

第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法當(dāng)銷大于產(chǎn)時，可銷地產(chǎn)地B1B2B3B4產(chǎn)量A17A25A37銷量2346銷地產(chǎn)地B1B2B3B4A121134A210359A37812表3-33產(chǎn)銷平衡表表3-34單位運(yùn)價表例2：求下面問題最優(yōu)調(diào)運(yùn)方案銷地B1B2B3B4產(chǎn)量A17A舉例銷地產(chǎn)地B1B2B3B4產(chǎn)量A1211347A2103595A378127銷量2346舉例銷地B1B2B3B4產(chǎn)量A1舉例解：首先化為產(chǎn)銷平衡的運(yùn)輸問題。假設(shè)一個庫存地B5，產(chǎn)銷平衡表如表3-35，其中b5=19-15=4銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A12113407A21035905A3781207銷量23464舉例解：首先化為產(chǎn)銷平衡的運(yùn)輸問題。假設(shè)一個庫存地B5，產(chǎn)銷

B1B2B3B4B5產(chǎn)量A12113407A21035905A3781207銷量23464432533323222最小元素法B1B2B3B4B5產(chǎn)量A121舉例由Vogel法求初始調(diào)運(yùn)方案銷地產(chǎn)地B1B2B3B4B5產(chǎn)量行差①②③③A121134072331A21035905335A37812071111銷量23464列差①55220②220③23222245333舉例由Vogel法求初始調(diào)運(yùn)方案銷地B1B2B表3-37Vogel法得運(yùn)量表銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A12327A2325A3437銷量23464表3-37Vogel法得運(yùn)量表用位勢法求表3-37是否為最優(yōu)調(diào)運(yùn)方案。其位勢表與檢驗數(shù)表如表3-38和3-39表3-38位勢表銷地產(chǎn)地B1B2B3B4B5uiA1240A230A312vjV1=2v2=3V3=3V4=4V5=0u1=0u2=0u3=-2用位勢法求表3-37是否為最優(yōu)調(diào)運(yùn)方案。σij=cij－(ui+vj)=0u1+v1=2u1+v4=4u1+v5=0u2+v2=3u2+v5=0u3+v3=1u3+v4=2令：u1＝0σij=cij－(ui+vj)=0u1+v1=2表3-39銷地產(chǎn)地B1B2B3B4B5A108000A280250A377002所有檢驗數(shù)都大于等于0，所以是最優(yōu)方案。最優(yōu)值fmin=2×2+4×3+3×3+4×1+2×3=35表3-39銷地B1B2B3B4B舉例例2設(shè)有三個化肥廠(A，B，C)供應(yīng)四個地區(qū)(Ⅰ，Ⅱ，Ⅲ，Ⅳ)的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同。各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運(yùn)送單位化肥的運(yùn)價如表3-25所示。試求出總的運(yùn)費(fèi)最節(jié)省的化肥調(diào)撥方案。舉例例2設(shè)有三個化肥廠(A，B，C)供應(yīng)四個地區(qū)(Ⅰ，Ⅱ第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法需求地化肥廠B1B2B3B4產(chǎn)量（萬噸）A11613221750A21413191560A3192023——50最低需求（萬噸）3070010最高需求（萬噸）507030不限表3-25第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法解分析：已知總產(chǎn)量為160噸，最低需求為110萬噸（30+70+10=110），最高需求為無限。B4地區(qū)最多分配60萬噸（160-30-70=60）最高需求為210萬噸（50+70+30+60），大于產(chǎn)量。為了求得平衡，在產(chǎn)銷平衡表中增加一個假想的化肥廠D，其年產(chǎn)量為50萬噸（210-160）。第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法解第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法對凡是需求分兩種情況的地區(qū)，實際可按照兩個地區(qū)看待。如地區(qū)Ⅰ，其中30萬噸是最低需求，故不能由假想化肥廠D供給，令相應(yīng)運(yùn)價為M(任意大正數(shù))，另一部分20萬噸滿足或不滿足均可以，因此可以由假想化肥廠D供給，按前面講的，令相應(yīng)運(yùn)價為0。這樣可以寫出這個問題的產(chǎn)銷平衡表(表3-26)和單位運(yùn)價表(表3-27)。第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法對凡是需求分兩種第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法產(chǎn)銷平衡表(表3-26),第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法產(chǎn)銷平衡表(表3第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法單位運(yùn)價表(表3-27)由于各地區(qū)的需要量包含兩部分，最低需求不能由假想化肥廠供給，其余部分可以，并令運(yùn)價為0。第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法單位運(yùn)價表(表3舉例表3-43最優(yōu)分配表需求地化肥廠B1B’1B2B3B4B’4產(chǎn)量A116161322171750A214141319151560A319192023MM50DM0M0M050銷量（萬噸）302070301050214019215310030203100203022022◆5020557M-15M-15105030202030200舉例表3-43最優(yōu)分配表舉例最優(yōu)方案如表3-28所示舉例最優(yōu)方案如表3-28所示第4節(jié)應(yīng)用舉例由于在變量個數(shù)相等的情況下，表上作業(yè)法的計算遠(yuǎn)比單純形法簡單得多。所以在解決實際問題時，人們常常盡可能把某些線性規(guī)劃的問題化為運(yùn)輸問題的數(shù)學(xué)模型。下面介紹幾個典型的例子。第4節(jié)應(yīng)用舉例由于在變量個數(shù)相等的情況下，表上作業(yè)第4節(jié)應(yīng)用舉例例3某廠按合同規(guī)定須于當(dāng)年每個季度末分別提供10，15，25，20臺同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如表3-29所示。又如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨的，每臺每積壓一個季度需儲存、維護(hù)等費(fèi)用0.15萬元。要求在完成合同的情況下，作出使該廠全年生產(chǎn)(包括儲存、維護(hù))費(fèi)用最小的決策

第4節(jié)應(yīng)用舉例例3某廠按合同規(guī)定須于當(dāng)年每個季第4節(jié)應(yīng)用舉例表3-29第4節(jié)應(yīng)用舉例表3-29第4節(jié)應(yīng)用舉例解由于每個季度生產(chǎn)出來的柴油機(jī)不一定當(dāng)季交貨，所以設(shè)xij為第i季度生產(chǎn)的用于第j季度交貨的柴油機(jī)數(shù)。根據(jù)合同要求，必須滿足第4節(jié)應(yīng)用舉例解由于每個季度生產(chǎn)出來的柴油機(jī)不第4節(jié)應(yīng)用舉例又每季度生產(chǎn)的用于當(dāng)季和以后各季交貨的柴油機(jī)數(shù)不可能超過該季度的生產(chǎn)能力，故又有：第4節(jié)應(yīng)用舉例又每季度生產(chǎn)的用于當(dāng)季和以后各季交貨第4節(jié)應(yīng)用舉例第i季度生產(chǎn)的用于j季度交貨的每臺柴油機(jī)的實際成本cij應(yīng)該是該季度單位成本加上儲存、維護(hù)等費(fèi)用。cij的具體數(shù)值見表3-30第4節(jié)應(yīng)用舉例第i季度生產(chǎn)的用于j季度交貨的每臺柴第4節(jié)應(yīng)用舉例設(shè)用ai表示該廠第i季度的生產(chǎn)能力，bj表示第i季度的合同供應(yīng)量，則問題可寫成：目標(biāo)函數(shù)：滿足第4節(jié)應(yīng)用舉例設(shè)用ai表示該廠第i季度的生產(chǎn)能力，第4節(jié)應(yīng)用舉例顯然，這是一個產(chǎn)大于銷的運(yùn)輸問題模型。注意到這個問題中當(dāng)i＞j時，xij=0，所以應(yīng)令對應(yīng)的cij=M，再加上一個假想的需求D，就可以把這個問題變成產(chǎn)銷平衡的運(yùn)輸模型，并寫出產(chǎn)銷平衡表和單位運(yùn)價表(合在一起，見表3-31)。第4節(jié)應(yīng)用舉例顯然，這是一個產(chǎn)大于銷的運(yùn)輸問題模型第4節(jié)應(yīng)用舉例表3-31第4節(jié)應(yīng)用舉例表3-31第4節(jié)應(yīng)用舉例經(jīng)用表上作業(yè)法求解，可得多個最優(yōu)方案，表3-32中列出最優(yōu)方案之一。即第Ⅰ季度生產(chǎn)25臺，10臺當(dāng)季交貨，15臺Ⅱ季度交貨；Ⅱ季度生產(chǎn)5臺，用于Ⅲ季度交貨；Ⅲ季度生產(chǎn)30臺，其中20臺于當(dāng)季交貨，10臺于Ⅳ季度交貨。Ⅳ季度生產(chǎn)10臺，于當(dāng)季交貨。按此方案生產(chǎn)，該廠總的生產(chǎn)(包括儲存、維護(hù))的費(fèi)用為773萬元。第4節(jié)應(yīng)用舉例經(jīng)用表上作業(yè)法求解，可得多個最優(yōu)方案第4節(jié)應(yīng)用舉例第4節(jié)應(yīng)用舉例5、用Lingo解運(yùn)輸問題例1.設(shè)有三個產(chǎn)地的產(chǎn)品要銷往四個銷地，各產(chǎn)地的產(chǎn)量、各銷地的銷量及各產(chǎn)地運(yùn)往各銷地的單位運(yùn)費(fèi)如下表，問如何調(diào)運(yùn)使得總的運(yùn)費(fèi)最少。B1B2B3B4產(chǎn)量A1626730A2495325A3881521銷量151722125、用Lingo解運(yùn)輸問題例1.設(shè)有三個產(chǎn)地的產(chǎn)品要銷往四解：編寫Lingo程序(命名exam1.lg4)：min=6*x11+2*x12+6*x13+7*x14+4*x21+9*x22+5*x23+3*x23+3*x24+8*x31+8*x32+x33+5*x34;x11+x12+x13+x14<=30;x21+x22+x23+x24<=25;x31+x32+x33+x34<=21;x11+x21+x31>=15;x12+x22+x32>=17;x13+x23+x33>=22;x14+x24+x34>=12;求解結(jié)果如下：Globaloptimalsolutionfound.Objectivevalue:161.0000Totalsolveriterations:6VariableValueReducedCostX112.0000000.000000X1217.000000.000000X131.0000000.000000X2113.000000.000000X2412.000000.000000X3321.000000.000000RowSlac