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

建模：-運(yùn)輸問(wèn)題.ppt建模：-運(yùn)輸問(wèn)題.ppt第3章運(yùn)輸問(wèn)題第1節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型第2節(jié)表上作業(yè)法第3節(jié)產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題及其求解方法第4節(jié)應(yīng)用舉例第5節(jié)Lingo程序求解運(yùn)輸問(wèn)題第3章運(yùn)輸問(wèn)題第1節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型引例某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷(xiāo)地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷(xiāo)地的銷(xiāo)量和各產(chǎn)地運(yùn)往各銷(xiāo)地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？B1B2B3產(chǎn)量A1646200A2655300銷(xiāo)量150150200運(yùn)費(fèi)表引例某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷(xiāo)地B1、B2、引例解：產(chǎn)銷(xiāo)平衡問(wèn)題：總產(chǎn)量=總銷(xiāo)量設(shè)xij為從產(chǎn)地Ai運(yùn)往銷(xiāo)地Bj的運(yùn)輸量，得到數(shù)學(xué)模型：引例解：產(chǎn)銷(xiāo)平衡問(wèn)題：系數(shù)矩陣111000

000111100100

010010

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

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

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

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

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

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

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

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

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

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

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

計(jì)算如下：空格處（A1

B1）＝

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

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

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

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

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

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

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

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

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

2.位勢(shì)法因非基變量的檢驗(yàn)數(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)計(jì)算檢驗(yàn)數(shù)，并以σij≥0檢驗(yàn)，或用(ui+vj)

－cij

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

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

改進(jìn)的方法-閉回路調(diào)整法B1B2B3B4產(chǎn)量A17A24A39銷(xiāo)量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ī)劃來(lái)確定換出變量相同)。然后按閉回路上的正、負(fù)號(hào)，加入和減去此值，得到調(diào)整方案，如表3-20所示。2.3改進(jìn)的方法-閉回路調(diào)整法(2，4)格的調(diào)入量θ是選擇B1B2B3B4產(chǎn)量A1527A2314A3639銷(xiāo)量36566563銷(xiāo)量9A34A27A1產(chǎn)量B4B3B2B1313463（＋1）（＋1）（－1）（－1）B1B2B3B4產(chǎn)量A1527A2314A3639銷(xiāo)量365B1B2B3B4A10200A20210A390120經(jīng)檢驗(yàn)所有σij≥0得到最優(yōu)解，最小運(yùn)費(fèi)為85元。v4v3v2v1u354A3u281A2u1103A1B4B3B2B110393－55－24－2A3－28171A2010393A1B4B3B2B1(ui+vj)cijB1B2B3B4A10200A20210A390120經(jīng)檢驗(yàn)2.4

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

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

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

表上作業(yè)法計(jì)算中的問(wèn)題可在表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)解，見(jiàn)表3-22。B1B2B3B4產(chǎn)量A1527A2314A3639銷(xiāo)量3656+2+2-2-22.4表上作業(yè)法計(jì)算中的問(wèn)題可在表3-20中以(1，1)2.4

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

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

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

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

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

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

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

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

第4節(jié)應(yīng)用舉例例3某廠(chǎng)按合同規(guī)定須于當(dāng)年每個(gè)季第4節(jié)應(yīng)用舉例表3-29第4節(jié)應(yīng)用舉例表3-29第4節(jié)應(yīng)用舉例解由于每個(gè)季度生產(chǎn)出來(lái)的柴油機(jī)不一定當(dāng)季交貨，所以設(shè)xij為第i季度生產(chǎn)的用于第j季度交貨的柴油機(jī)數(shù)。根據(jù)合同要求，必須滿(mǎn)足第4節(jié)應(yīng)用舉例解由于每個(gè)季度生產(chǎn)出來(lái)的柴油機(jī)不第4節(jié)應(yīng)用舉例又每季度生產(chǎn)的用于當(dāng)季和以后各季交貨的柴油機(jī)數(shù)不可能超過(guò)該季度的生產(chǎn)能力，故又有：第4節(jié)應(yīng)用舉例又每季度生產(chǎn)的用于當(dāng)季和以后各季交貨第4節(jié)應(yīng)用舉例第i季度生產(chǎn)的用于j季度交貨的每臺(tái)柴油機(jī)的實(shí)際成本cij應(yīng)該是該季度單位成本加上儲(chǔ)存、維護(hù)等費(fèi)用。cij的具體數(shù)值見(jiàn)表3-30第4節(jié)應(yīng)用舉例第i季度生產(chǎn)的用于j季度交貨的每臺(tái)柴第4節(jié)應(yīng)用舉例設(shè)用ai表示該廠(chǎng)第i季度的生產(chǎn)能力，bj表示第i季度的合同供應(yīng)量，則問(wèn)題可寫(xiě)成：目標(biāo)函數(shù)：滿(mǎn)足第4節(jié)應(yīng)用舉例設(shè)用ai表示該廠(chǎng)第i季度的生產(chǎn)能力，第4節(jié)應(yīng)用舉例顯然，這是一個(gè)產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題模型。注意到這個(gè)問(wèn)題中當(dāng)i＞j時(shí)，xij=0，所以應(yīng)令對(duì)應(yīng)的cij=M，再加上一個(gè)假想的需求D，就可以把這個(gè)問(wèn)題變成產(chǎn)銷(xiāo)平衡的運(yùn)輸模型，并寫(xiě)出產(chǎn)銷(xiāo)平衡表和單位運(yùn)價(jià)表(合在一起，見(jiàn)表3-31)。第4節(jié)應(yīng)用舉例顯然，這是一個(gè)產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題模型第4節(jié)應(yīng)用舉例表3-31第4節(jié)應(yīng)用舉例表3-31第4節(jié)應(yīng)用舉例經(jīng)用表上作業(yè)法求解，可得多個(gè)最優(yōu)方案，表3-32中列出最優(yōu)方案之一。即第Ⅰ季度生產(chǎn)25臺(tái)，10臺(tái)當(dāng)季交貨，15臺(tái)Ⅱ季度交貨；Ⅱ季度生產(chǎn)5臺(tái)，用于Ⅲ季度交貨；Ⅲ季度生產(chǎn)30臺(tái)，其中20臺(tái)于當(dāng)季交貨，10臺(tái)于Ⅳ季度交貨。Ⅳ季度生產(chǎn)10臺(tái)，于當(dāng)季交貨。按此方案生產(chǎn)，該廠(chǎng)總的生產(chǎn)(包括儲(chǔ)存、維護(hù))的費(fèi)用為773萬(wàn)元。第4節(jié)應(yīng)用舉例經(jīng)用表上作業(yè)法求解，可得多個(gè)最優(yōu)方案第4節(jié)應(yīng)用舉例第4節(jié)應(yīng)用舉例5、用Lingo解運(yùn)輸問(wèn)題例1.設(shè)有三個(gè)產(chǎn)地的產(chǎn)品要銷(xiāo)往四個(gè)銷(xiāo)地，各產(chǎn)地的產(chǎn)量、各銷(xiāo)地的銷(xiāo)量及各產(chǎn)地運(yùn)往各銷(xiāo)地的單位運(yùn)費(fèi)如下表，問(wèn)如何調(diào)運(yùn)使得總的運(yùn)費(fèi)最少。B1B2B3B4產(chǎn)量A1626730A2495325A3881521銷(xiāo)量151722125、用Lingo解運(yùn)輸問(wèn)題例1.設(shè)有三個(gè)產(chǎn)地的產(chǎn)品要銷(xiāo)往四解：編寫(xiě)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