運(yùn)輸問(wèn)題數(shù)學(xué)建模(共66張PPT)精選

運(yùn)輸(yùnshū)問(wèn)題數(shù)學(xué)建模第一頁(yè)，共66頁(yè)。1．掌握運(yùn)輸問(wèn)題的數(shù)學(xué)模型、系數(shù)矩陣特殊形式2．掌握用西北角法、最小元素法求初始(chūshǐ)基可行解3．掌握回路、位勢(shì)法求解過(guò)程和表上作業(yè)法求解運(yùn)輸問(wèn)題過(guò)程教學(xué)要求：第二頁(yè)，共66頁(yè)。Z0=3×1+6×4+4×3+1×2+3×10+3×5=86(元)u2+v3=c23=2銷地Bj的銷量。(1)由于問(wèn)題中所有產(chǎn)地、中間(zhōngjiān)轉(zhuǎn)運(yùn)站、銷地都可以看作產(chǎn)地，又可看作銷地。注：應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只劃去一行或一列。方案調(diào)整，從當(dāng)前方案出發(fā)尋找更好方案，常采用閉回路法。（1）閉回路(huílù)法u1+v4=c14=10總運(yùn)費(fèi)(yùnfèi)為：f=5×3+2×10+3×1+1×8+6×4+3×5=85。銷量，這樣的運(yùn)輸問(wèn)題稱為產(chǎn)銷(chǎnxiāo)不平衡的運(yùn)輸問(wèn)題。單位(dānwèi)運(yùn)價(jià)表解：這里，總產(chǎn)量為78+45=123；二、表上作業(yè)(zuòyè)法（續(xù)）總運(yùn)費(fèi)(yùnfèi)為：f=5×3+2×10+3×1+1×8+6×4+3×5=85。表上作業(yè)(zuòyè)法中需要說(shuō)明的問(wèn)題一、運(yùn)輸(yùnshū)問(wèn)題及其數(shù)學(xué)模型

在經(jīng)濟(jì)建設(shè)中，經(jīng)常碰到物資調(diào)撥中的運(yùn)輸問(wèn)題。例如煤、鋼材、糧食、木材等物資，在全國(guó)都有若干(ruògān)生產(chǎn)基地，分別將這些物資調(diào)到各消費(fèi)基地去，應(yīng)如何制定調(diào)運(yùn)方案，使總的運(yùn)輸費(fèi)用最少？問(wèn)題(wèntí)的提出:第三頁(yè)，共66頁(yè)。運(yùn)輸問(wèn)題的一般提法是：設(shè)某種物資(wùzī)有m個(gè)產(chǎn)地和n個(gè)銷地。產(chǎn)地Ai的產(chǎn)量為；銷地Bj的銷量。從第i個(gè)產(chǎn)地向第j個(gè)銷地運(yùn)輸每單位物資(wùzī)的運(yùn)價(jià)為Cij。這就是由多個(gè)產(chǎn)地供應(yīng)多個(gè)銷地的單品種物資(wùzī)運(yùn)輸問(wèn)題。問(wèn)如何調(diào)運(yùn)這些物資(wùzī)才能使總運(yùn)費(fèi)達(dá)到最小。1、運(yùn)輸問(wèn)題的一般(yībān)提法第四頁(yè)，共66頁(yè)。單位(dānwèi)運(yùn)價(jià)表第五頁(yè)，共66頁(yè)。（1）。即運(yùn)輸問(wèn)題的總產(chǎn)量等于其總銷量，這樣的運(yùn)輸問(wèn)題稱為產(chǎn)銷(chǎnxiāo)平衡的運(yùn)輸問(wèn)題。（2）。即運(yùn)輸問(wèn)題的總產(chǎn)量不等于總銷量，這樣的運(yùn)輸問(wèn)題稱為產(chǎn)銷(chǎnxiāo)不平衡的運(yùn)輸問(wèn)題。分兩種情況(qíngkuàng)來(lái)討論：第六頁(yè)，共66頁(yè)。若用xij表示從Ai到Bj的運(yùn)量，那么在產(chǎn)銷平衡的條件下，要求(yāoqiú)得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，數(shù)學(xué)模型為：

2、運(yùn)輸(yùnshū)問(wèn)題的數(shù)學(xué)模型其中，ai和bj滿足：稱為(chēnɡwéi)產(chǎn)銷平衡條件。第七頁(yè)，共66頁(yè)。將約束(yuēshù)方程式展開(kāi)可得約束方程式中共(zhōnɡɡònɡ)mn個(gè)變量，m+n個(gè)約束。第八頁(yè)，共66頁(yè)。上述模型是一個(gè)線性規(guī)劃(xiànxìnɡɡuīhuá)問(wèn)題。但是其結(jié)構(gòu)很特殊，特點(diǎn)如下：1.變量(biànliàng)多（mn個(gè)），但結(jié)構(gòu)簡(jiǎn)單。

技術(shù)系數(shù)(xìshù)矩陣該系數(shù)矩陣中每列只有兩個(gè)元素為1，其余的都為零。第九頁(yè)，共66頁(yè)。2.m+n個(gè)約束(yuēshù)中有一個(gè)是多余的（因?yàn)槠溟g含有一個(gè)平衡關(guān)系式）所以R(A)=m+n-1，即解的mn個(gè)變量中基變量為m+n-1個(gè)。第十頁(yè)，共66頁(yè)。二、表上作業(yè)(zuòyè)法運(yùn)輸(yùnshū)問(wèn)題仍然是線性規(guī)劃問(wèn)題，可以用線性規(guī)劃法中的單純形法來(lái)解決。但是：1.運(yùn)輸(yùnshū)問(wèn)題所涉及的變量多，造成單純形表太大；2.若把技術(shù)系數(shù)矩陣A中的0迭代成非0，會(huì)使問(wèn)題更加復(fù)雜。以上兩個(gè)原因使得我們不得不利用運(yùn)輸(yùnshū)問(wèn)題的特點(diǎn)設(shè)計(jì)出它的特殊解法——表上作業(yè)法。第十一頁(yè)，共66頁(yè)。表上作業(yè)法，實(shí)質(zhì)上還是單純形法。其步驟(bùzhòu)如下：1.確定一個(gè)初始可行調(diào)運(yùn)方案?？梢酝ㄟ^(guò)最小元素(yuánsù)法、西北角法、Vogel法來(lái)完成；2.檢驗(yàn)當(dāng)前可行方案是否最優(yōu)，常用的方法有閉回路法和位勢(shì)法，用這兩種方法計(jì)算出檢驗(yàn)數(shù)，從而判別方案是否最優(yōu)；3.方案調(diào)整，從當(dāng)前方案出發(fā)尋找更好方案，常采用閉回路法。二、表上作業(yè)(zuòyè)法（續(xù)）第十二頁(yè)，共66頁(yè)。例某公司(ɡōnɡsī)從三個(gè)產(chǎn)地A1、A2、A3將物品運(yùn)往四個(gè)銷地B1、B2、B3、B4，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表3-4所示問(wèn)應(yīng)如何(rúhé)調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小?第十三頁(yè)，共66頁(yè)。即初始基本可行解的確定，與一般(yībān)線性規(guī)劃問(wèn)題不同，產(chǎn)銷平衡運(yùn)輸問(wèn)題總是存在可行解。1、確定初始(chūshǐ)方案確定初始基本可行(kěxíng)解的方法很多，一般希望方法是既簡(jiǎn)便，又盡可能接近最優(yōu)解。下面介紹兩種方法：最小元素法，西北角法、Vogel法第十四頁(yè)，共66頁(yè)。（1）最小元素(yuánsù)法最小元素法的基本思想是優(yōu)先滿足單位運(yùn)價(jià)最小的供銷業(yè)務(wù)。首先找出運(yùn)價(jià)最小的，并以最大限度滿足其供銷量(xiāoliànɡ)為原則確定供銷業(yè)務(wù)。同樣的方法反復(fù)進(jìn)行直到確定了所有的供銷業(yè)務(wù)，得到一個(gè)完整的調(diào)運(yùn)方案即初始基本可行解為止。第十五頁(yè)，共66頁(yè)。銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A17311310A241928A3974105需求3656201321344653103方案(fāngàn)表運(yùn)價(jià)(yùnjià)表第十六頁(yè)，共66頁(yè)。以此(yǐcǐ)，得到一初始方案：X13=4,X14=3，X21=3，X23=1，X32=6，X34=3（有數(shù)格）X11=X31=X12=X22=X33=X24=0（空格）B1B2B3B4A143A231A363注：（?。┯袛?shù)格是基變量，共m+n-1=3+4-1=6個(gè)。空格是非基變量，共劃去m+n=7條線；（ⅱ）如果填上一個(gè)變量之后(zhīhòu)能同時(shí)劃去兩條線（一行與一列），就須在所劃去的該行或該列填一個(gè)0，此0格當(dāng)有數(shù)格對(duì)待。初始(chūshǐ)方案運(yùn)費(fèi)Z0=3×1+6×4+4×3+1×2+3×10+3×5=86(元)第十七頁(yè)，共66頁(yè)。（2）西北角法西北角法與最小元素法不同，它不是優(yōu)先考慮具有最小單位運(yùn)價(jià)(yùnjià)的供銷業(yè)務(wù)，而是優(yōu)先滿足運(yùn)輸表中西北角（左上角）上空格的供銷需求。第十八頁(yè)，共66頁(yè)。銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A17311310A241928A3974105需求365620342236方案(fāngàn)表運(yùn)價(jià)(yùnjià)表第十九頁(yè)，共66頁(yè)。注：應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只劃去一行或一列。當(dāng)填上一個(gè)數(shù)后行、列同時(shí)飽和時(shí)，也應(yīng)任意(rènyì)劃去一行(列)。在飽和的列（行）沒(méi)被劃去的格內(nèi)標(biāo)一個(gè)0,然后劃去該列（行）。第二十頁(yè)，共66頁(yè)。例某公司(ɡōnɡsī)下屬有生產(chǎn)一種化工產(chǎn)品的三個(gè)產(chǎn)地A1、A2、A3，有四個(gè)銷售點(diǎn)B1、B2、B3、B4銷售這種化工產(chǎn)品。各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每噸產(chǎn)品的運(yùn)費(fèi)（百元）如下表所示。銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A1753859A2402948A3806375需求35405565195問(wèn)應(yīng)如何(rúhé)調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小?第二十一頁(yè)，共66頁(yè)。解：用西北角法求初始(chūshǐ)基本可行解銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A1753859A2402948A3806375需求35405565195方案(fāngàn)表運(yùn)價(jià)(yùnjià)表35400401565第二十二頁(yè)，共66頁(yè)。(3)伏格爾法（次小運(yùn)價(jià)(yùnjià)與最小運(yùn)價(jià)(yùnjià)之差大者先安排）銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A17311310A241928A3974105需求365620方案(fāngàn)表運(yùn)價(jià)(yùnjià)表

2513

01160123

212

376512第二十三頁(yè)，共66頁(yè)。2、判斷當(dāng)前(dāngqián)方案是否為最優(yōu)用單純形法解線性規(guī)劃問(wèn)題時(shí)，在迭代過(guò)程中每次求得一個(gè)基本可行解以后，都要檢驗(yàn)它是不是最優(yōu)解，如果不是最優(yōu)解，就要繼續(xù)進(jìn)行迭代，直到求得最優(yōu)解或者判定無(wú)最優(yōu)解。表上作業(yè)法是用以下兩種方法(fāngfǎ)來(lái)處理這個(gè)問(wèn)題的：閉回路法和位勢(shì)法。第二十四頁(yè)，共66頁(yè)。（1）閉回路(huílù)法在單純形法中，為了檢驗(yàn)一個(gè)基本(jīběn)可行解是不是最優(yōu)解，需要求出所有非基變量的檢驗(yàn)數(shù)。在運(yùn)輸問(wèn)題中，每個(gè)空格對(duì)應(yīng)一個(gè)非基變量。因此，我們需要求出每個(gè)空格的檢驗(yàn)數(shù)。由于目標(biāo)要求極小，因此，當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案。

第二十五頁(yè)，共66頁(yè)。B1B2B3B4A143A231A363①對(duì)方案表中每一空格，確定一條由空格出發(fā)的閉回路。閉回路是由水平或垂直線組成的閉合圖形。閉回路上的頂點(diǎn)除了這個(gè)空格外(géwài)，其余均為有數(shù)格。B1B2B3B4A143A231A363可以證明，對(duì)每一個(gè)空格都存在而且惟一存在這樣(zhèyàng)一條封閉回路。第二十六頁(yè)，共66頁(yè)。B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363第二十七頁(yè)，共66頁(yè)。②計(jì)算出空格的檢驗(yàn)數(shù)—等于閉回路上由此空格起奇數(shù)頂點(diǎn)運(yùn)價(jià)與偶數(shù)(ǒushù)頂點(diǎn)運(yùn)價(jià)負(fù)值的代數(shù)和。B1B2B3B4A143A231A36311=3-3+2-1=122=9-2+3–0+5–4=131=7-5+10–3+2–1=1012=11-10+5-4=224=8–10+3–2=-133=10-5+10-3=12第二十八頁(yè)，共66頁(yè)。③當(dāng)所有空格(kōnɡɡé)檢驗(yàn)數(shù) σij≥0則當(dāng)前方案(fāngàn)是最優(yōu)的，若尚有空格檢驗(yàn)數(shù)小于零，表明當(dāng)前方案(fāngàn)尚有待調(diào)整。若所有的空格(kōnɡɡé)檢驗(yàn)數(shù)都大于等于零，表明任何一個(gè)空格(kōnɡɡé)處調(diào)運(yùn)1單位都會(huì)引起總成本的上升，這表明當(dāng)前方案不能再改進(jìn)，即定為最優(yōu)方案。σij

具有確切的經(jīng)濟(jì)意義，它表示由Ai往Bj增運(yùn)1單位時(shí)，引起的總運(yùn)輸成本的變化數(shù)。B1B2B3B4A143A231A363

閉回路法的主要缺點(diǎn)是：當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路以及計(jì)算都會(huì)產(chǎn)生困難。第二十九頁(yè)，共66頁(yè)。（2）位勢(shì)法（對(duì)偶(duìǒu)變量法）對(duì)于一個(gè)調(diào)運(yùn)方案的每列賦予一個(gè)值，稱為列位(lièwèi)勢(shì)，記，對(duì)于每行賦予一個(gè)值，稱為行位勢(shì)，記為則檢驗(yàn)(jiǎnyàn)數(shù)為：ij=cij-ui-vji=1,…,m;j=1,…,n它們的值由下列方程組決定：其中，cij

是所有基變量（數(shù)字格）xij

的運(yùn)價(jià)系數(shù)。第三十頁(yè)，共66頁(yè)。銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A17311310A241928A3974105需求3656201321344653103方案(fāngàn)表運(yùn)價(jià)(yùnjià)表u1+v3=c13=3u2+v1=c21=1u3+v2=c32=4u1u2u3v1v3v2v4u1+v4=c14=10u2+v3=c23=2u3+v4=c34=5第三十一頁(yè)，共66頁(yè)。令u1=5則有v4=5

v3=-2u2=4

u3=0v2=4v1=-311=c11–u1-v1=3–5–(-3)=1

12=c12–u1–v2=11–5–4=222=c22–u2–v2=9–4–4=1

24=c24–u2–v4=8–4–5=-1

31=c31–u3-v1=7–0–(-3)=1033=c33–u3–v3=10–0–(-2)=12再求非基變量(biànliàng)（空格）檢驗(yàn)數(shù)：u1+v3=c13=3u2+v1=c21=1u3+v2=c32=4u1+v4=c14=10u2+v3=c23=2u3+v4=c34=5第三十二頁(yè)，共66頁(yè)。（1）在有數(shù)格上填上相應(yīng)(xiāngyīng)的運(yùn)價(jià)銷產(chǎn)B1B2B3B4A143A231A363方案(fāngàn)表運(yùn)價(jià)(yùnjià)表銷產(chǎn)B1B2B3B4A1310A212A345u1u2u3v1v3v2v4位勢(shì)法在表上進(jìn)行：第三十三頁(yè)，共66頁(yè)。(2)設(shè)u1=0，然后根據(jù)cij=ui+vj（有數(shù)格），依次(yīcì)求得ui和vj的值，并填在相應(yīng)的位置銷產(chǎn)B1B2B3B4A1310A212A345u1u2u3v1v3v2v4239100-1-5計(jì)算(ui+vj)表，把(ui+vj)位勢(shì)和值填在表中相應(yīng)位置(wèizhi)上，并將有數(shù)格位置(wèizhi)上的值ui+vj加上括號(hào)以示區(qū)別。（）（）（）（）（）（）2989-3-2(ui+vj)表第三十四頁(yè)，共66頁(yè)。銷產(chǎn)B1B2B3B4A1311310A21928A374105運(yùn)價(jià)(yùnjià)表銷產(chǎn)B1B2B3B4A129(3)(10)A2(1)8(2)9A3-3(4)-2(5)u1u2u3v1v3v2v4239100-1-5檢驗(yàn)(jiǎnyàn)數(shù)表銷產(chǎn)B1B2B3B4A1A2A3（3）計(jì)算檢驗(yàn)(jiǎnyàn)數(shù)表ij=cij–(ui+vj)(ui+vj)表121-11012第三十五頁(yè)，共66頁(yè)。3、調(diào)整(tiáozhěng)方案若在檢驗(yàn)數(shù)上有某空格的檢驗(yàn)數(shù)為負(fù)，則可改進(jìn)(gǎijìn)方案，降低成本。調(diào)整的方法是從具有負(fù)檢驗(yàn)數(shù)的空格出發(fā)(有多個(gè)負(fù)檢驗(yàn)數(shù)時(shí)，選擇絕對(duì)值大的一個(gè))，沿它的閉回路進(jìn)行調(diào)整，即在保持方案可行的條件下，盡量增加空格上的運(yùn)量。第三十六頁(yè)，共66頁(yè)。從σijθ,偶數(shù)頂點(diǎn)(dǐngdiǎn)的運(yùn)量減少θ(這才能保證新的平衡)，其中調(diào)整量θ為該空格閉回路中偶數(shù)頂點(diǎn)(dǐngdiǎn)的最小值。B1B2B3B4A143A231A363注：若閉回路的偶數(shù)頂點(diǎn)中同時(shí)有兩個(gè)格以上運(yùn)量為θ，則調(diào)整后其中一個(gè)變空格，其余(qíyú)填0。（保證基變量個(gè)數(shù)不變）（p48）B1B2B3B4A152A231A36324=-1，作x24的閉回路(huílù)，調(diào)整數(shù)=1，調(diào)整得第三十七頁(yè)，共66頁(yè)。再用閉回路(huílù)法或位勢(shì)法求各空格的檢驗(yàn)數(shù)，B1B2B3B4A152A231A363x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余(qíyú)的xij=0總運(yùn)費(fèi)(yùnfèi)為：f=5×3+2×10+3×1+1×8+6×4+3×5=85。銷產(chǎn)B1B2B3B4A102A221A3912表中的所有檢驗(yàn)數(shù)都非負(fù)，故上表中的解為最優(yōu)解。檢驗(yàn)數(shù)表方案表第三十八頁(yè)，共66頁(yè)。表上作業(yè)(zuòyè)法中需要說(shuō)明的問(wèn)題（1）無(wú)窮多最優(yōu)解當(dāng)?shù)?diédài)到運(yùn)輸問(wèn)題的最優(yōu)解時(shí)，如果有某非基變量的檢驗(yàn)數(shù)等于零，則說(shuō)明該運(yùn)輸問(wèn)題有多重（無(wú)窮多）最優(yōu)解。上面的例題是多解情況銷產(chǎn)B1B2B3B4A102A221A3912B1B2B3B4A152A231A363檢驗(yàn)(jiǎnyàn)數(shù)表方案表B1B2B3B4A1250A213A363調(diào)整方案表第三十九頁(yè)，共66頁(yè)。（2）退化當(dāng)運(yùn)輸問(wèn)題某部分產(chǎn)地的產(chǎn)量和，與某一部分銷地的銷量和相等時(shí)，在迭代過(guò)程中有可能在某個(gè)格填入一個(gè)運(yùn)量時(shí)需同時(shí)劃去運(yùn)輸表的一行和一列(yīliè)，這時(shí)就出現(xiàn)了退化。在運(yùn)輸問(wèn)題中，退化解是時(shí)常發(fā)生的。為了使表上作業(yè)法的迭代工作進(jìn)行下去，退化時(shí)應(yīng)在同時(shí)劃去的一行或一列(yīliè)中的某個(gè)格中填入數(shù)字0，表示這個(gè)格中的變量是取值為0的基變量，使迭代過(guò)程中基可行解的分量恰好為（m+n-1）個(gè)。表上作業(yè)(zuòyè)法中需要說(shuō)明的問(wèn)題第四十頁(yè)，共66頁(yè)。三、產(chǎn)銷(chǎnxiāo)不平衡的運(yùn)輸問(wèn)題前面我們討論的運(yùn)輸問(wèn)題，都是產(chǎn)銷平衡的問(wèn)題，即滿足在實(shí)際問(wèn)題中，產(chǎn)銷往往是不平衡的，遇到這種情況，我們可以經(jīng)過(guò)簡(jiǎn)單的處理(chǔlǐ)，使其轉(zhuǎn)化為產(chǎn)銷平衡問(wèn)題，然后再按前面的方法來(lái)求解。第四十一頁(yè)，共66頁(yè)。1、產(chǎn)量(chǎnliàng)大于銷量對(duì)于(duìyú)產(chǎn)大于銷問(wèn)題，可得到下列運(yùn)輸問(wèn)題的模型：第四十二頁(yè)，共66頁(yè)?？稍黾右粋€(gè)假想的銷地，其銷量為：某個(gè)產(chǎn)地Ai運(yùn)到這個(gè)假想銷地Bn+1的物資量xi,n+1，實(shí)際上就意味著將這些物資在原產(chǎn)地貯存，其相應(yīng)的運(yùn)價(jià)，轉(zhuǎn)化為產(chǎn)銷平衡(pínghéng)的問(wèn)題，其數(shù)學(xué)模型為：第四十三頁(yè)，共66頁(yè)。例3-3某公司(ɡōnɡsī)從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？銷產(chǎn)B1B2B3產(chǎn)量A113151278A211292245需求533625

123114單位(dānwèi)運(yùn)價(jià)表第四十四頁(yè)，共66頁(yè)。解：這里，總產(chǎn)量為78+45=123；總銷量為53+36+25=114。產(chǎn)銷不平衡，增加一個(gè)虛設(shè)(xūshè)的銷地，得到下表銷產(chǎn)B1B2B3B4產(chǎn)量B1B2B3B4A1781315120A2451129220需求5236259123銷產(chǎn)B1B2B3產(chǎn)量A113151278A211292245需求533625

123114第四十五頁(yè)，共66頁(yè)。2、產(chǎn)量(chǎnliàng)小于銷量對(duì)于(duìyú)產(chǎn)小于銷問(wèn)題可增加一個(gè)假想的產(chǎn)地，其產(chǎn)量為：其相應(yīng)的運(yùn)費(fèi)為上述(shàngshù)不平衡問(wèn)題就轉(zhuǎn)化為平衡的問(wèn)題，第四十六頁(yè)，共66頁(yè)。例3-4某公司從兩個(gè)產(chǎn)地(chǎndì)A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地(chǎndì)的產(chǎn)量、各銷地的銷量和各產(chǎn)地(chǎndì)運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？銷產(chǎn)B1B2B3產(chǎn)量A113151278A211292245需求533665

123154單位(dānwèi)運(yùn)價(jià)表第四十七頁(yè)，共66頁(yè)。解:這里，總產(chǎn)量小于總銷量，產(chǎn)銷不平衡，增加一個(gè)(yīɡè)虛設(shè)的產(chǎn)地，得到下表銷產(chǎn)B1B2B3產(chǎn)量B1B2B3A178131512A245112922A331000需求533665

154銷產(chǎn)B1B2B3產(chǎn)量A113151278A211292245需求533665

123154第四十八頁(yè)，共66頁(yè)。四、應(yīng)用(yìngyòng)舉例在變量個(gè)數(shù)相等的情況下，表上作業(yè)法的計(jì)算遠(yuǎn)比單純形法簡(jiǎn)單。解決實(shí)際問(wèn)題時(shí)，人們常常(chángcháng)盡可能把某些線性規(guī)劃的問(wèn)題化為運(yùn)輸問(wèn)題的數(shù)學(xué)模型。下面為幾個(gè)典型的例子。第四十九頁(yè)，共66頁(yè)。例3-5有A1、A2、A3三個(gè)生產(chǎn)某種物資的產(chǎn)地，五個(gè)地區(qū)B1、B2、B3、B4、B5對(duì)這種物資有需求?，F(xiàn)要將這種物資從三個(gè)產(chǎn)地運(yùn)往五個(gè)需求地區(qū)，各產(chǎn)地的產(chǎn)量、各需求地區(qū)的需要量和各產(chǎn)地運(yùn)往各地區(qū)每單位(dānwèi)物資的運(yùn)費(fèi)如下表所示，其中B2地區(qū)的115個(gè)單位(dānwèi)必須滿足。問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。夸N地產(chǎn)地B1B2B3B4B5產(chǎn)量A1101520204050A22040153030100A33035405525130需求25115603070280300運(yùn)輸費(fèi)用(fèiyong)及產(chǎn)量、需求量表第五十頁(yè)，共66頁(yè)。解：由于產(chǎn)量小于需求量，因此設(shè)一虛設(shè)(xūshè)產(chǎn)地A4,它的產(chǎn)量為需求量與產(chǎn)量的差20，與這一項(xiàng)有關(guān)的運(yùn)輸費(fèi)用一般為零。因?yàn)锽2地區(qū)的115個(gè)單位必須滿足，即不能有物資從A4運(yùn)往B2地區(qū)，于是取相應(yīng)的費(fèi)用為M（M是一個(gè)充分大的正數(shù)），以保證在求最小運(yùn)輸費(fèi)用的前提下，該變量的值為零。銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A1101520204050A22040153030100A33035405525130需求25115603070280300第五十一頁(yè)，共66頁(yè)?？梢越⑷缦庐a(chǎn)銷平衡的運(yùn)輸(yùnshū)費(fèi)用表銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A1101520204050A22040153030100A33035405525130A40M00020需求25115603070第五十二頁(yè)，共66頁(yè)。例3-6某研究院有B1、B2、B3三個(gè)區(qū)。每年取暖分別需要用煤3500噸、1100噸、2400噸，這些煤都要由A1、A2兩處煤礦負(fù)責(zé)供應(yīng)，價(jià)格、質(zhì)量均相同。A1、A2煤礦的供應(yīng)能力分別為1500噸、4000噸，運(yùn)價(jià)（元/噸）如下表。由于需求大于供給，經(jīng)院研究決定(juédìng)B1區(qū)供應(yīng)量可減少0—900噸，B2區(qū)必須滿足需求量，B3區(qū)供應(yīng)量不少于1600噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。銷地產(chǎn)地B1B2B3產(chǎn)量A11751952081500A21601822154000需求量350011002400第五十三頁(yè)，共66頁(yè)。由于B1區(qū)供應(yīng)量可減少(jiǎnshǎo)0—900噸，B3區(qū)供應(yīng)量不少于1600噸，可以把B1區(qū)和B3區(qū)分別設(shè)為兩個(gè)區(qū)：一個(gè)為必須滿足需求量的區(qū)域，另一個(gè)為可以調(diào)整供應(yīng)量的區(qū)域。原問(wèn)題化為五個(gè)需求區(qū)域B1、B1’、B2、B3、B3’的問(wèn)題，同時(shí)增加一個(gè)虛設(shè)的產(chǎn)地A3。在運(yùn)輸費(fèi)方面,必須滿足需求量的相應(yīng)變量，運(yùn)費(fèi)的取值為M，可調(diào)整需求量的相應(yīng)變量，運(yùn)費(fèi)的取值為0，作出產(chǎn)銷(chǎnxiāo)平衡的運(yùn)價(jià)表解：這是需求量大于生產(chǎn)量的運(yùn)輸(yùnshū)問(wèn)題第五十四頁(yè)，共66頁(yè)。銷地產(chǎn)地B1B1*B2B3B3*產(chǎn)量A11751751952082081500A21601601822152154000A2M0MM01500需求量260090011001600800第五十五頁(yè)，共66頁(yè)。例3-7某公司(ɡōnɡsī)生產(chǎn)某種規(guī)格的設(shè)備，由于生產(chǎn)與季節(jié)有關(guān)系，生產(chǎn)能力與成本有差異，如下表所示。某種規(guī)格(guīgé)設(shè)備各季節(jié)的生產(chǎn)能力與成本第一季度第二季度第三季度第四季度生產(chǎn)能力(臺(tái))500700600200成本(萬(wàn)元/臺(tái)）9.810.510.310.6該廠年初(niánchū)簽訂的合同規(guī)定：當(dāng)年一、二、三、四每個(gè)季度末分別需要提供200、300、500、400臺(tái)這種規(guī)格的設(shè)備。如果生產(chǎn)出來(lái)的設(shè)備當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用為萬(wàn)元。試求在完成合同的前提下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。第五十六頁(yè)，共66頁(yè)。解：設(shè)xij為第i季度生產(chǎn)的第j季度交貨的設(shè)備數(shù)目(shùmù)，則問(wèn)題的線性規(guī)劃模型為：cij=第i季度每臺(tái)的生產(chǎn)成本(j-i)（儲(chǔ)存(chǔcún)、維護(hù)等費(fèi)用）。計(jì)算可得：

c11=9.8,c12=9.95,c13=10.1,c14=10.25,c22=10.5,c23=10.65,c24=10.8,c33=10.3,c34=10.45,c44=10.6。第五十七頁(yè)，共66頁(yè)。于是得到(dédào)目標(biāo)函數(shù)：

x11x12x13x14+x22x23x24x33+x34x44x11=200x12+x22=300x13+x23+x33=500x14+x24+x34+x44=400

交貨(jiāohuò)：生產(chǎn)(shēngchǎn)：x11+x12+x13+x14≤500x22+x23+x24≤700x33+x34≤600x44≤200xij

0i=1,2,3,4ji第五十八頁(yè)，共66頁(yè)。由于產(chǎn)大于銷，虛構(gòu)一個(gè)(yīɡè)銷地，可構(gòu)造下列產(chǎn)銷平衡問(wèn)題:各季節(jié)(jìjié)的生產(chǎn)、交貨費(fèi)用表交貨生產(chǎn)第一季度第二季度第三季度第四季度虛設(shè)交貨生產(chǎn)能力第一