案例鋼鐵配礦問(wèn)題教學(xué)用運(yùn)輸

2024/1/27管理運(yùn)籌學(xué)課程組391本章重點(diǎn)第三章運(yùn)輸問(wèn)題

產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的數(shù)學(xué)模型

產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的表上作業(yè)法

本章內(nèi)容運(yùn)輸問(wèn)題的數(shù)學(xué)模型表上作業(yè)法運(yùn)輸問(wèn)題的擴(kuò)展2024/1/27管理運(yùn)籌學(xué)課程組392§1運(yùn)輸問(wèn)題的數(shù)學(xué)模型bn…b2b1需求量Bn…B2B1

需方供方AmA2A1ama2a1供應(yīng)量供需平衡運(yùn)價(jià)2024/1/27管理運(yùn)籌學(xué)課程組393§1運(yùn)輸問(wèn)題的數(shù)學(xué)模型bn…b2b1需求量BnB2B1

需方供方AmA2A1ama2a1供應(yīng)量cmncm2cm1c2nc22c21c1nc12c11…………如何建立供需搭配，使總的運(yùn)輸費(fèi)用最小？供需平衡表2024/1/27管理運(yùn)籌學(xué)課程組394平衡表、運(yùn)價(jià)表和二為一：2024/1/27管理運(yùn)籌學(xué)課程組395數(shù)學(xué)模型設(shè)從Ai到Bj的物資運(yùn)量為xij，產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的數(shù)學(xué)模型。Ai的產(chǎn)品全部供應(yīng)出去Bj的需求全部得到滿足2024/1/27管理運(yùn)籌學(xué)課程組396

例3.1

某公司經(jīng)銷(xiāo)甲產(chǎn)品。它下設(shè)三個(gè)加工廠。每日的產(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噸。已知從各工廠到各銷(xiāo)售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)為表所示。問(wèn)該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷(xiāo)售點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)為最少。解先畫(huà)出這問(wèn)題的產(chǎn)銷(xiāo)平衡表和單位運(yùn)價(jià)表，

B1B2B3B4產(chǎn)量/tA13113107A219284A3741059銷(xiāo)量/t3656銷(xiāo)地運(yùn)費(fèi)產(chǎn)地2024/1/27管理運(yùn)籌學(xué)課程組3971.決策變量xij表示第i產(chǎn)地運(yùn)到第j個(gè)銷(xiāo)地的產(chǎn)品數(shù)量2.目標(biāo)函數(shù)z為總費(fèi)用3.約束條件2024/1/27管理運(yùn)籌學(xué)課程組398運(yùn)輸問(wèn)題有有限最優(yōu)解對(duì)于運(yùn)輸問(wèn)題的模型，若令其變量則上述模型就是運(yùn)輸問(wèn)題模型的一個(gè)可行解，運(yùn)輸問(wèn)題的目標(biāo)函數(shù)有下界，目標(biāo)函數(shù)值不會(huì)趨于負(fù)無(wú)窮大，因此，運(yùn)輸問(wèn)題必存在有限最優(yōu)解。2024/1/27管理運(yùn)籌學(xué)課程組399mn運(yùn)輸問(wèn)題約束條件的系數(shù)矩陣2024/1/27管理運(yùn)籌學(xué)課程組3910約束條件或解可用產(chǎn)銷(xiāo)平衡表表示:2024/1/27管理運(yùn)籌學(xué)課程組3911

ui?vj無(wú)約束（i=1,2,…,m;j=1,2,…,n)uivj設(shè)ui,vj為對(duì)偶變量，對(duì)偶問(wèn)題模型為m個(gè)n個(gè)2024/1/27管理運(yùn)籌學(xué)課程組3912約束條件系數(shù)矩陣的元素等于0或1約束條件系數(shù)矩陣的每一列有兩個(gè)非零元素，這對(duì)應(yīng)于每一個(gè)變量在前m個(gè)約束方程中出現(xiàn)一次，在后n個(gè)約束方程中也出現(xiàn)一次。對(duì)產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題，除上述兩個(gè)特點(diǎn)外，還有以下特點(diǎn):所有約束條件都是等式約束；各產(chǎn)地產(chǎn)量之和等于各銷(xiāo)地銷(xiāo)量之和。運(yùn)輸問(wèn)題的特點(diǎn)2024/1/27管理運(yùn)籌學(xué)課程組3913根據(jù)運(yùn)輸問(wèn)題的數(shù)學(xué)模型求出的運(yùn)輸問(wèn)題的解，代表著一個(gè)運(yùn)輸方案，其中每一個(gè)變量的值表示由調(diào)運(yùn)數(shù)量為物品給。前已指出運(yùn)輸問(wèn)題是一種線性規(guī)劃問(wèn)題，可設(shè)想用迭代法進(jìn)行求解，即先找出它的某一個(gè)基可行解，再進(jìn)行解的最優(yōu)性檢驗(yàn)，若它不是最優(yōu)解，就進(jìn)行迭代調(diào)整，以得到一個(gè)新的更好的解，繼續(xù)檢驗(yàn)和調(diào)整改進(jìn)，直至得到最優(yōu)解為止。運(yùn)輸問(wèn)題的解2024/1/27管理運(yùn)籌學(xué)課程組3914為了能按上述思路求解運(yùn)輸問(wèn)題，要求每步得到的解都必須是基可行解，這意味著：(l)解必須滿足模型中的所有約束條件；(2)基變量對(duì)應(yīng)的約束方程組的系數(shù)列向量線性無(wú)關(guān)；(3)解中非零變量的個(gè)數(shù)不能大于個(gè)，原因是運(yùn)輸問(wèn)題中雖有個(gè)結(jié)構(gòu)約束條件，但由于總產(chǎn)量等于總銷(xiāo)量，故只有個(gè)約束條件是線性獨(dú)立的；(4)為使迭代順利進(jìn)行，基變量的個(gè)數(shù)在迭代過(guò)程中保持為個(gè)。2024/1/27管理運(yùn)籌學(xué)課程組3915§2表上作業(yè)法計(jì)算步驟：(1)找出初始調(diào)運(yùn)方案。即在(m×n)產(chǎn)銷(xiāo)平衡表上給出m+n-1個(gè)數(shù)字格。(最小元素法或差值法）(2)求檢驗(yàn)數(shù)。（閉回路法或位勢(shì)法）判別是否達(dá)到最優(yōu)解。如已是最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)到下一步。(3)對(duì)方案進(jìn)行改善，找出新的調(diào)運(yùn)方案。（表上閉回路法調(diào)整）確定m+n-1個(gè)基變量

(4)重復(fù)（2）、（3），直到求得最優(yōu)調(diào)運(yùn)方案?？崭?024/1/27管理運(yùn)籌學(xué)課程組3916

例運(yùn)輸問(wèn)題供需平衡表和運(yùn)價(jià)表如下，求最優(yōu)調(diào)運(yùn)方案。

供需B1B2B3B4供應(yīng)量（T）A13113107A219284A3741059需求量（T）36562024/1/27管理運(yùn)籌學(xué)課程組3917基本思想：應(yīng)優(yōu)先考慮單位運(yùn)價(jià)最小(或運(yùn)距最短)的供銷(xiāo)業(yè)務(wù)，最大限度地滿足其供銷(xiāo)量。即對(duì)所有i和j找出，的物品量由Ai0供應(yīng)給Bj0.若xi0j0

＝ai0，則產(chǎn)地Ai0的可供物品已用完，以后不再繼續(xù)考慮這個(gè)產(chǎn)地，且Bj0的需求量由bj0減少為bj0-ai0;如果xi0j0

＝bj0

，則銷(xiāo)地Bj0的需求已全部得到滿足，以后不再考慮這個(gè)銷(xiāo)地，且Ai0的可供量由ai0減少為aj0-bi0

。然后，在余下的供、銷(xiāo)點(diǎn)的供銷(xiāo)關(guān)系中，繼續(xù)按上述方法安排調(diào)運(yùn)，直至安排完所有供銷(xiāo)任務(wù)，得到一個(gè)完整的調(diào)運(yùn)方案(完整的解)為止。這樣就得到了運(yùn)輸問(wèn)題的一個(gè)初始基可行解(初始調(diào)運(yùn)方案)。1最小元素法2024/1/27管理運(yùn)籌學(xué)課程組3918314

633Z=4×3+3×10+3×1+1×2+6×4+3×5=86該方案總運(yùn)費(fèi)：2024/1/27管理運(yùn)籌學(xué)課程組3919例3.2某部門(mén)有3個(gè)生產(chǎn)同類(lèi)產(chǎn)品的工廠(產(chǎn)地)，生產(chǎn)的產(chǎn)品由4個(gè)銷(xiāo)售點(diǎn)(銷(xiāo)地)出售，各工廠的生產(chǎn)量、各銷(xiāo)售點(diǎn)的銷(xiāo)售量(單位為噸)以及各工廠到各銷(xiāo)售點(diǎn)的單位運(yùn)價(jià)(元／噸)示于表中。問(wèn):要求產(chǎn)品如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最小?2024/1/27管理運(yùn)籌學(xué)課程組3920解:由于總產(chǎn)量和總銷(xiāo)量均為48，故知這是一個(gè)產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題。最小費(fèi)用法的初始分配方案如下表所示

總運(yùn)費(fèi)(目標(biāo)函數(shù)值)z=10×4十6×ll十8×2十2×3十14×5十8×6＝246

這個(gè)解滿足所有約束條件，其非零變量的個(gè)數(shù)為6(等于m+n-1=3+4-1=6)不難驗(yàn)證，這6個(gè)非零變量(基變量)對(duì)應(yīng)的約束條件系數(shù)列向量線性無(wú)關(guān)。

2024/1/27管理運(yùn)籌學(xué)課程組3921基本思想：首先計(jì)算運(yùn)輸表中每一行和每一列的次小單位運(yùn)價(jià)和最小單位運(yùn)價(jià)之間的差值，并分別稱(chēng)之為行罰數(shù)和列罰數(shù)。將算出的行罰數(shù)填入位于運(yùn)輸表右側(cè)行罰數(shù)欄的左邊第一列的相應(yīng)格子中，列罰數(shù)填入位于運(yùn)輸表下邊列罰數(shù)欄的第一行的相應(yīng)格子中，見(jiàn)下表。在這些罰數(shù)中，確定最大者，對(duì)應(yīng)的運(yùn)輸格優(yōu)先填入盡可能大的運(yùn)量，同最小元素法一樣，劃去相應(yīng)的行或列。在尚未劃去的各行和各列中如上重新計(jì)算各行罰數(shù)和列罰數(shù)，并分別填入行罰數(shù)欄，用上述方法繼續(xù)作下去，依次算出每次迭代的行罰數(shù)和列罰數(shù)，根據(jù)其最大罰數(shù)值的位置在運(yùn)輸表中的適當(dāng)格中填入一個(gè)盡可能大的運(yùn)輸量，并劃去對(duì)應(yīng)的一行或一列。用這種方法可以得到一個(gè)初始基可行解。2.伏格爾法2024/1/27管理運(yùn)籌學(xué)課程組3922.

分別計(jì)算各行、各列次小、最小運(yùn)價(jià)的差額，優(yōu)先在最大差額處進(jìn)行供需搭配。步驟：10計(jì)算未劃去行、列的差額；20

找出最大差額對(duì)應(yīng)的最小元素cij進(jìn)行供需分配；30

在未被劃去的行、列重新計(jì)算差額。2024/1/27管理運(yùn)籌學(xué)課程組3923

銷(xiāo)產(chǎn)B1B2B3B4供量A17A24A39銷(xiāo)量

3656

6B1B2B3B4行差額A13113100A219281A3741051列差額25132024/1/27管理運(yùn)籌學(xué)課程組3924

銷(xiāo)產(chǎn)B1B2B3B4供量A17A24A3

9銷(xiāo)量

3656

6B1B2B3B4行差額A13113100A219281A3741052列差額21332024/1/27管理運(yùn)籌學(xué)課程組3925

銷(xiāo)產(chǎn)B1B2B3B4供量A17A24A3

9銷(xiāo)量

3656

6B1B2B3B4行差額A13113100A219281A374105列差額212332024/1/27管理運(yùn)籌學(xué)課程組3926

銷(xiāo)產(chǎn)B1B2B3B4供量A17A24A3

39銷(xiāo)量

3656

6B1B2B3B4差額A13113107A219286A374105差額12

35122024/1/27管理運(yùn)籌學(xué)課程組3927以3.2為例，用伏格爾法給出初始調(diào)運(yùn)方案的過(guò)程如下表第一步：在上表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行第二步：從行或列差額中選出最大者，選擇它所在行或列的最小元素。在上表中B2列差額最大為5。在該列最小元素位置填上產(chǎn)銷(xiāo)量的最小值14，然后將運(yùn)價(jià)表中的B2列數(shù)字劃去；運(yùn)價(jià)表中劃去B2列數(shù)字后重新計(jì)算行或列差額，形成第二列和行的罰數(shù)，進(jìn)入下一步，如表所示第三步：對(duì)表中未劃去的元素再分別計(jì)算出各行、各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行，重復(fù)第一、二步，直到給出初始解為止伏爾加法與最小元素法除在確定供求關(guān)系原則上不同外，其余步驟相同，伏爾加法給出的初始解比用最小元素法給出的初始解更接近最優(yōu)解。目標(biāo)函數(shù)值z(mì)=12×4十8×2十2×9十14×5十8×6＝2442024/1/27管理運(yùn)籌學(xué)課程組3928用伏爾加法給出例3.1的初始解如下表此初始解即為最優(yōu)解，總費(fèi)用為z=5*3+2*10+3*1+1*8+6*4+3*5=85(元)

一般說(shuō)來(lái)，沃格爾法得出的初始解的質(zhì)量最好，常用來(lái)作為運(yùn)輸問(wèn)題最優(yōu)解的近似解，最小元素法解的目標(biāo)函數(shù)值比較大。

2024/1/27管理運(yùn)籌學(xué)課程組3929最優(yōu)解的判別（檢驗(yàn)數(shù)的求法）①閉回路法要判別運(yùn)輸問(wèn)題的某個(gè)解是否為最優(yōu)解，可仿照一般單純形法，檢驗(yàn)這個(gè)解的各非基變量（對(duì)應(yīng)于運(yùn)輸表中的空格）的檢驗(yàn)數(shù)，若有某空格的檢驗(yàn)數(shù)為負(fù)，說(shuō)明將其變成基變量將使運(yùn)輸費(fèi)用減少，故當(dāng)前這個(gè)解不是最優(yōu)解。若所有空格的檢驗(yàn)數(shù)全為非負(fù)，則不管怎樣變換，解均不能使運(yùn)輸費(fèi)用降低，即目標(biāo)函數(shù)值已無(wú)法改進(jìn)，這個(gè)解就是最優(yōu)解。

2024/1/27管理運(yùn)籌學(xué)課程組3930

閉回路：從空格出發(fā)順時(shí)針(或逆時(shí)針)畫(huà)水(或垂直)直線，遇到填有運(yùn)量的方格可轉(zhuǎn)90°，然后繼續(xù)前進(jìn)，直到到達(dá)出發(fā)的空格所形成的閉合回路。調(diào)運(yùn)方案的任意空格存在唯一閉回路。

銷(xiāo)產(chǎn)B1B2B3B4供量A1527A2314A36

39銷(xiāo)量

36562024/1/27管理運(yùn)籌學(xué)課程組3931

閉回路：從空格出發(fā)順時(shí)針(或逆時(shí)針)畫(huà)水平(或垂直)直線，遇到填有運(yùn)量的方格可轉(zhuǎn)90°，然后繼續(xù)前進(jìn)，直到到達(dá)出發(fā)的空格所形成的閉合回路。調(diào)運(yùn)方案的任意空格存在唯一閉回路。

銷(xiāo)產(chǎn)B1B2B3B4供量A1527A2314A36

39銷(xiāo)量

36562024/1/27管理運(yùn)籌學(xué)課程組3932314

633最小元素法+-+-

x11為換入變量，x11增加1，運(yùn)費(fèi)的變化為3-1+2-3=1。這個(gè)變化就是x11的檢驗(yàn)數(shù)，故

11=12024/1/27管理運(yùn)籌學(xué)課程組3933

從每一空格出發(fā)一定存在和可以找到唯一的閉回路。因(m+n-1)個(gè)數(shù)字格(基變量)對(duì)應(yīng)的系數(shù)向量是一個(gè)基.任一空格(非基變量)對(duì)應(yīng)的系數(shù)向量是這個(gè)基的線形組合.如Pij，（i，j∈N

）可表示為而這些向量構(gòu)成了閉回路?？崭瘢╥，j）對(duì)應(yīng)非基變量xij，其檢驗(yàn)數(shù)（閉回路上奇數(shù)次頂點(diǎn)的運(yùn)價(jià)之和）-（閉回路上偶數(shù)次頂點(diǎn)的運(yùn)價(jià)之和）2024/1/27管理運(yùn)籌學(xué)課程組3934閉回路法計(jì)算檢驗(yàn)數(shù)的經(jīng)濟(jì)解釋為：在已給出初始解的表3-8中，可從任一空格出發(fā)，如（A1，B1），若讓A1的產(chǎn)品調(diào)運(yùn)1噸給B1。為了保持產(chǎn)品平衡，就要依次作調(diào)整：在（A1，B3）處減少1噸，（A2，B3）處增加1噸，（A1，B3）處減少1噸，即構(gòu)成了以（A1，B1）空格為起點(diǎn)，其它為數(shù)字格的閉回路，如表3-8中折線所示。在這表中閉回路各頂點(diǎn)所在格的右上角數(shù)字是單位運(yùn)價(jià)。檢驗(yàn)數(shù)通?？捎玫葦?shù)字表示，正的檢驗(yàn)數(shù)可簡(jiǎn)記為-5+2024/1/27管理運(yùn)籌學(xué)課程組3935

基變量的檢驗(yàn)數(shù)為零(

基變量xij)，

ij=cij-(ui+vj),ui,vj自由變量②.位勢(shì)法

標(biāo)準(zhǔn)型運(yùn)輸問(wèn)題的對(duì)偶問(wèn)題是：

XBXNXS0CN-CBB-1N-CBB-1-YS1-YS2-Y檢驗(yàn)數(shù)

得m+n-1個(gè)方程，令某個(gè)ui

(或vj)=0，可解出m+n個(gè)ui

和vj；由此得非基變量的檢驗(yàn)數(shù)。對(duì)偶變量值等于原問(wèn)題的檢驗(yàn)數(shù)松弛變量2024/1/27管理運(yùn)籌學(xué)課程組393601122024/1/27管理運(yùn)籌學(xué)課程組393701128-37位勢(shì)表2989-3-2檢驗(yàn)數(shù)2024/1/27管理運(yùn)籌學(xué)課程組393801128-37檢驗(yàn)數(shù)表121-11012

24=-1＜0，當(dāng)前方案不是最優(yōu)方案。2024/1/27管理運(yùn)籌學(xué)課程組3939閉回路調(diào)整法改進(jìn)方案pqijj,i)(min

=<0xpq為換入變量

從(p,q)空格開(kāi)始畫(huà)閉回路，其它轉(zhuǎn)角點(diǎn)都是填有運(yùn)量的方格，并從(p,q)空格開(kāi)始給閉回路上的點(diǎn)按+1，-1，+1，-1編號(hào)，-1格的最小運(yùn)量為調(diào)整量。換出變量運(yùn)量表3-102024/1/27管理運(yùn)籌學(xué)課程組3940

新的調(diào)運(yùn)方案為：2024/1/27管理運(yùn)籌學(xué)課程組3941得到的一個(gè)解2024/1/27管理運(yùn)籌學(xué)課程組3942

需供B1B2B3B4uiA10210A2218A39125Vj

-7-1-70713491110231085對(duì)應(yīng)上述解的非基變量檢驗(yàn)數(shù)2024/1/27管理運(yùn)籌學(xué)課程組3943表上作業(yè)法中的問(wèn)題（1）無(wú)窮多最優(yōu)解在前面提到，產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題必定存在最優(yōu)解。那么有唯一最優(yōu)解還是無(wú)窮多最優(yōu)解？依線性規(guī)劃單純性最優(yōu)解判別標(biāo)準(zhǔn)，即某個(gè)非基變量（空格）的檢驗(yàn)數(shù)為０時(shí)，該問(wèn)題有無(wú)窮多最優(yōu)解。表3-10空格（1，1）的檢驗(yàn)數(shù)是０，表明例3.1有無(wú)窮多最優(yōu)解?？稍诒?-12中以（1，1）為調(diào)入格，作閉回路（1，1）+－(1，4)-－(2，4)+－(2，1)-－(1，1)+。確定