運(yùn)輸問題與指派問題

Excel在經(jīng)濟(jì)管理中的應(yīng)用第五講運(yùn)輸問題與指派問題運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第1頁(yè)!§5.1運(yùn)輸問題(transportationproblem)一、什么是運(yùn)輸問題二、運(yùn)輸問題的分類三、供需均衡運(yùn)輸問題的建模與求解四、供需非均衡運(yùn)輸問題的建模與求解五、運(yùn)輸問題的應(yīng)用運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第2頁(yè)!一、什么是運(yùn)輸問題在經(jīng)濟(jì)建設(shè)中，經(jīng)常碰到大宗物資調(diào)運(yùn)問題，如煤、鋼鐵、木材、糧食等等物資。在全國(guó)有若干生產(chǎn)基地，根據(jù)已有的交通網(wǎng)，應(yīng)如何制定調(diào)運(yùn)方案，將這些物資運(yùn)到各消費(fèi)地點(diǎn)，而總費(fèi)用最小。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第3頁(yè)!例：設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥，假定等量的化肥在這些地區(qū)使用效果相同。各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運(yùn)送單位化肥的運(yùn)價(jià)如表所示，試求出總的運(yùn)費(fèi)最節(jié)省的化肥調(diào)撥方案。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第4頁(yè)!1.供應(yīng)節(jié)點(diǎn)：運(yùn)輸?shù)钠瘘c(diǎn)，像生產(chǎn)廠商，提供的產(chǎn)品數(shù)量是有限的。2.需求節(jié)點(diǎn)：運(yùn)輸?shù)慕K點(diǎn)或目的地，像銷售地點(diǎn)或用戶所在地，需求量是一個(gè)特定的值。3.假設(shè)：產(chǎn)品不能從一個(gè)供應(yīng)節(jié)點(diǎn)運(yùn)輸?shù)搅硪粋€(gè)供應(yīng)節(jié)點(diǎn)，也不能從一個(gè)需求節(jié)點(diǎn)運(yùn)輸?shù)搅硪粋€(gè)需求節(jié)點(diǎn)，只能從供應(yīng)節(jié)點(diǎn)運(yùn)至需求節(jié)點(diǎn)。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第5頁(yè)!二、運(yùn)輸問題的分類1、供需均衡的運(yùn)輸問題所有供應(yīng)點(diǎn)的供應(yīng)量之和等于所有需求點(diǎn)的需求量之和的運(yùn)輸問題。2、供需非均衡的運(yùn)輸問題所有供應(yīng)點(diǎn)的供應(yīng)量之和不等于所有需求點(diǎn)的需求量之和的運(yùn)輸問題。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第6頁(yè)!需求地區(qū)化肥廠地區(qū)1地區(qū)2地區(qū)3地區(qū)4產(chǎn)量（萬噸）廠11613221750廠21413191580廠31920231050需求量（萬噸）50703010運(yùn)價(jià)：萬元/萬噸運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第7頁(yè)!三、供需均衡運(yùn)輸問題的建模與求解已知有m個(gè)生產(chǎn)地點(diǎn)Ai,i=1,2,…,m，可供應(yīng)某種物資，其供應(yīng)量分別是ai,i=1,2,…,m，有n個(gè)銷地Bj,j=1,2,…,n，其需要量分別為bj，j=1,2,…,n，從Ai到Bj運(yùn)輸單位物資的運(yùn)費(fèi)為cij（單價(jià)）

，可用一個(gè)表格來表示出來。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第8頁(yè)!對(duì)于產(chǎn)銷平衡的運(yùn)輸問題，有下面的關(guān)系式：

n

m∑bj=∑aij=1i=1運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第9頁(yè)!用xij表示從Ai到Bj的運(yùn)量，在產(chǎn)銷平衡的條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，可求解以下數(shù)學(xué)模型：mnMinz=∑∑cijxiji=1j=1s.t.m

∑xij=bj，j=1，2，…，ni=1n

∑xij=ai，i=1，2，…，mj=1

xij≥0

運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第10頁(yè)!例5.2.1海華設(shè)備廠均衡運(yùn)輸問題海華設(shè)備廠下設(shè)三個(gè)位于不同地點(diǎn)的分廠A、B、C，該三個(gè)分廠生產(chǎn)同一種設(shè)備，設(shè)每月的生產(chǎn)能力分別為20臺(tái)、30臺(tái)和40臺(tái)。海華設(shè)備廠有四個(gè)固定用戶，該四個(gè)用戶下月的設(shè)備需求量分別為20臺(tái)、15臺(tái)、23臺(tái)和32臺(tái)。設(shè)各分廠的生產(chǎn)成本相同，從各分廠至各用戶的單位設(shè)備運(yùn)輸成本如表4.2.1所示，運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第11頁(yè)!而且各分廠本月末的設(shè)備庫(kù)存量為零。問該廠應(yīng)如何安排下月的生產(chǎn)與運(yùn)輸，才能在滿足四個(gè)用戶需求的前提下，使總運(yùn)輸成本最低。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第12頁(yè)!總供應(yīng)量=20+30+40=90（臺(tái)），總需求量=20+15+23+32=90（臺(tái)），供應(yīng)量之和等于需求量之和，供需均衡。決策變量是下月各分廠為各用戶生產(chǎn)與運(yùn)輸?shù)脑O(shè)備數(shù)量。可設(shè)：分廠A下月為四個(gè)用戶生產(chǎn)和運(yùn)輸?shù)脑O(shè)備數(shù)量分別為A1，A2，A3，A4（臺(tái)）；運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第13頁(yè)!約束條件有兩部分，部分是需求約束，各用戶從各分廠收到的設(shè)備總數(shù)不得少于它們的需求量：A1+B1+C1=20A2+B2+C2=15A3+B3+C3=23A4+B4+C4=32運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第14頁(yè)!線性規(guī)劃模型為：Min70A1+40A2+80A360A4+70B1+100B2+110B3+50B4+80C1+70C2+130C3+40C4

s.t.A1+B1+C1=20A2+B2+C2=15A3+B3+C3=23A4+B4+C4=32運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第15頁(yè)!四、供需非均衡運(yùn)輸問題的建模與求解1、當(dāng)供給大于需求時(shí)，即n

m∑bj

≤∑aij=1i=1運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第16頁(yè)!銷地產(chǎn)地B1B2

…Bn產(chǎn)量A1A2

…Amx11x12…x1nx21x22…

x2n…………xm1xm2…xmna1a2…am銷量b1b2…bn運(yùn)量分配表運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第17頁(yè)!2、當(dāng)供給小于需求時(shí)，即n

m∑bj

≥∑aij=1i=1運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第18頁(yè)!銷地產(chǎn)地B1B2

…Bn產(chǎn)量A1A2

…Amx11x12…x1nx21x22…

x2n…xm1xm2…xmna1a2…am銷量b1b2…bn運(yùn)量分配表運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第19頁(yè)!例5.2.1海華設(shè)備廠非均衡運(yùn)輸問題若例4.2.1中的三個(gè)分廠經(jīng)技術(shù)改造，每月的生產(chǎn)能力均增加了5臺(tái)，即分別從20臺(tái)、30臺(tái)、40臺(tái)增加為25臺(tái)、35臺(tái)、45臺(tái)，其他條件不變?yōu)閼?yīng)該如何安排下月的生產(chǎn)與運(yùn)輸，才能在滿足四個(gè)用戶的前提下使總運(yùn)輸成本最低。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第20頁(yè)!總供應(yīng)量=25+35+45=105（臺(tái)），總需求量=20+15+23+32=90（臺(tái)），供應(yīng)量之和大于需求量之和，供需不均衡。需求節(jié)點(diǎn)收到的產(chǎn)品總數(shù)等于其總需求量，而各供應(yīng)節(jié)點(diǎn)發(fā)出的產(chǎn)品總數(shù)則小于其供應(yīng)能力。模型變?yōu)椋哼\(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第21頁(yè)!A1+A2+A3+A4

≤25B1+B2+B3+B4

≤35C1+C2+C3+C4

≤45A1，A2，A3，A4，B1，B2，B3，B4，C1，C2，C3，C4

≥0運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第22頁(yè)!北方飛機(jī)制造公司問題的生產(chǎn)進(jìn)度安排數(shù)據(jù)月份計(jì)劃安裝量最大產(chǎn)量單位生產(chǎn)成本（百萬美元）單位存儲(chǔ)成本(百萬美元)正常時(shí)間加班時(shí)間正常時(shí)間加班時(shí)間11020101.081.100.01521530151.111.120.01532525101.101.110.0154205101.131.15運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第23頁(yè)!例產(chǎn)品分配計(jì)劃求佳產(chǎn)品公司決定使用三個(gè)有生產(chǎn)余力的工廠進(jìn)行四種新產(chǎn)品的生產(chǎn)制造。就哪個(gè)工廠生產(chǎn)哪種產(chǎn)品做決策,使總成本達(dá)到最小。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第24頁(yè)!

單位利潤(rùn)

顧客:1234生產(chǎn)能力工廠1$55$42$46$538,0002371832485,0003295951357,000最少購(gòu)買力7000300020000最大購(gòu)買力7000900060008000例產(chǎn)品銷售計(jì)劃運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第25頁(yè)!§5.2指派問題(assignmentproblem)一、什么是指派問題二、指派問題的一般數(shù)學(xué)模型三、指派問題在電子表格中的建模與求解運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第26頁(yè)!例：有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作E、J、G、R，現(xiàn)有甲、乙、丙、丁四人。他們將中文說明書翻譯成不同語種的說明書所需時(shí)間如表所示，問應(yīng)指派何人去完成何工作，使所需總時(shí)間最少？運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第27頁(yè)!又如：有n項(xiàng)加工任務(wù)，怎樣指派到n臺(tái)機(jī)床上分別完成的問題，有n條航線，怎樣指定n艘船去航行的問題等等都是指派問題。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第28頁(yè)!任務(wù)人員B1B2

…Bn分配的任務(wù)A1A2

…Anc11c12…c1nc21c22…

c2n…cn1cn2…cnn11…1要完成的任務(wù)1

1…1運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第29頁(yè)!

n

nMinz=∑∑cijxiji=1j=1s.t.n

∑xij=1，j=1，2，…，

ni=1n

∑xij=1，i=1，2，…，

nj=1

Xij=1或0一般的模型為：運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第30頁(yè)!例：有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作E、J、G、R，現(xiàn)有甲、乙、丙、丁四人。他們將中文說明書翻譯成不同語種的說明書所需時(shí)間如表所示，問應(yīng)指派何人去完成何工作，使所需總時(shí)間最少？運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第31頁(yè)!有一些被指派者并不能進(jìn)行某一些的任務(wù)。任務(wù)比被指派者多。被指派者比要完成的任務(wù)多。

指派問題的變形

運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第32頁(yè)!例5.2.1金工車間任務(wù)指派問題某金工車間要加工四種零件，現(xiàn)有五臺(tái)機(jī)器可以使用，表4.3.1給出了各臺(tái)機(jī)器加工各種零件所需的時(shí)間。若每臺(tái)機(jī)器最多只能承擔(dān)一種零件。問應(yīng)如何分配任務(wù)，才能使得完成四種零件加工任務(wù)的總時(shí)間最短。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第33頁(yè)!例：分配甲、乙、丙、丁四人去完成五項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)時(shí)間如表所示，由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中有一個(gè)人可見完成兩項(xiàng)任務(wù)，其余三人每人完成一項(xiàng)。試確定總花費(fèi)時(shí)間為最少的指派方案。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第34頁(yè)!需求地區(qū)化肥廠地區(qū)1地區(qū)2地區(qū)3地區(qū)4產(chǎn)量（萬噸）廠11613221750廠21413191560廠31920231050需求量（萬噸）50703010運(yùn)價(jià)：萬元/萬噸運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第35頁(yè)!4.運(yùn)輸問題：在滿足供應(yīng)節(jié)點(diǎn)的供應(yīng)量約束和需求節(jié)點(diǎn)的需求量約束的條件下，為了使運(yùn)輸成本最低，如何安排運(yùn)輸。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第36頁(yè)!需求地區(qū)化肥廠地區(qū)1地區(qū)2地區(qū)3地區(qū)4產(chǎn)量（萬噸）廠11613221750廠21413191560廠31920231050需求量（萬噸）50703010運(yùn)價(jià)：萬元/萬噸運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第37頁(yè)!需求地區(qū)化肥廠地區(qū)1地區(qū)2地區(qū)3地區(qū)4產(chǎn)量（萬噸）廠11613221750廠21413191560廠31920231050需求量（萬噸）60703010運(yùn)價(jià)：萬元/萬噸運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第38頁(yè)!銷地產(chǎn)地B1B2

…Bn產(chǎn)量A1A2

…Amc11c12…c1nc21c22…

c2n…………cm1cm2…cmna1a2…am銷量b1b2…bn成本表運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第39頁(yè)!銷地產(chǎn)地B1B2

…Bn產(chǎn)量A1A2

…Amx11x12…x1nx21x22…

x2n…………xm1xm2…xmna1a2…am銷量b1b2…bn運(yùn)量分配表運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第40頁(yè)!在這個(gè)數(shù)學(xué)模型中，包含有m×n個(gè)變量，有（m+n）個(gè)約束方程，約束條件中變量的系數(shù)比較特殊，不是1就是0。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第41頁(yè)!表5.2.1海華設(shè)備廠運(yùn)輸成本表分廠名稱運(yùn)輸成本（元/臺(tái)）月生產(chǎn)能力（臺(tái)）用戶1用戶2用戶3用戶4分廠A7040806020分廠B701001105030分廠C80701304040下月設(shè)備需求量（臺(tái)）2015233290運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第42頁(yè)!解：可用一個(gè)網(wǎng)絡(luò)圖來描述ABC432170408060701001105080701304020304020152332運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第43頁(yè)!分廠B下月為四個(gè)用戶生產(chǎn)和運(yùn)輸?shù)脑O(shè)備數(shù)量分別為B1，B2，B3，B4（臺(tái)）；分廠C下月為四個(gè)用戶生產(chǎn)和運(yùn)輸?shù)脑O(shè)備數(shù)量分別為C1，C2，C3，C4（臺(tái)）。目標(biāo)函數(shù)是總運(yùn)輸成本最小化，總運(yùn)輸成本=70A1+40A2+80A360A4+70B1+100B2+110B3+50B4+80C1+70C2

+130C3+40C4

運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第44頁(yè)!第二部分是生產(chǎn)能力約束，各分廠生產(chǎn)和運(yùn)輸?shù)脑O(shè)備總數(shù)不得超過其生產(chǎn)能力：A1+A2+A3+A4=20B1+B2+B3+B4=30C1+C2+C3+C4=40最后，還有非負(fù)約束：A1，A2，A3，A4，B1，B2，B3，B4，C1，C2，C3，C4

≥0運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第45頁(yè)!A1+A2+A3+A4=20B1+B2+B3+B4=30C1+C2+C3+C4=40A1，A2，A3，A4，B1，B2，B3，B4，C1，C2，C3，C4

≥0運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第46頁(yè)!銷地產(chǎn)地B1B2

…Bn產(chǎn)量A1A2

…Amc11c12…c1nc21c22…

c2n…………cm1cm2…cmna1a2…am銷量b1b2…bn成本表運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第47頁(yè)!用xij表示從Ai到Bj的運(yùn)量，在產(chǎn)銷非平衡的條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，可求解以下數(shù)學(xué)模型：mnMinz=∑∑cijxiji=1j=1s.t.m

∑xij=bj，j=1，2，…，ni=1n

∑xij≤

aii=1，2，…，mj=1xij≥0運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第48頁(yè)!銷地產(chǎn)地B1B2

…Bn產(chǎn)量A1A2

…Amc11c12…c1nc21c22…

c2n…cm1cm2…cmna1a2…am銷量b1b2…bn成本表運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第49頁(yè)!用xij表示從Ai到Bj的運(yùn)量，在產(chǎn)銷非平衡的條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，可求解以下數(shù)學(xué)模型：mnMinz=∑∑cijxiji=1j=1s.t.m

∑xij≤

bj，j=1，2，…，ni=1n

∑xij=aii=1，2，…，mj=1xij≥0運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第50頁(yè)!ABC4321704080607010011050807013040解：可用一個(gè)網(wǎng)絡(luò)圖來描述25354520152332運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第51頁(yè)!Min70A1+40A2+80A360A4+70B1+100B2+110B3+50B4+80C1+70C2+130C3+40C4

s.t.A1+B1+C1=20A2+B2+C2=15A3+B3+C3=23A4+B4+C4=32運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第52頁(yè)!五、運(yùn)輸問題的應(yīng)用例:北方飛機(jī)制造公司為全世界的航空公司生產(chǎn)各種商務(wù)飛機(jī)。制造過程的最后一步是生產(chǎn)噴氣發(fā)動(dòng)機(jī)并把它們安裝到已經(jīng)完成的飛機(jī)框架之中去。按照公司的一些訂單合同，不久公司要交付使用相當(dāng)多數(shù)量的飛機(jī)。所以有必要現(xiàn)在為未來四個(gè)月這些飛機(jī)噴氣發(fā)動(dòng)機(jī)的生產(chǎn)制定計(jì)劃。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第53頁(yè)!生產(chǎn)管理人員需要制定出一個(gè)每月生產(chǎn)多少發(fā)動(dòng)機(jī)的計(jì)劃,使制造和存儲(chǔ)的總成本達(dá)到最小。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第54頁(yè)!公司的產(chǎn)品數(shù)據(jù)單位成本可用能力產(chǎn)品1234工廠1$41$27$28$247524029--237533730272145要求產(chǎn)量20303040運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第55頁(yè)!目標(biāo)決定向每位顧客銷售多少單位的產(chǎn)品以及為實(shí)現(xiàn)最大利潤(rùn)。運(yùn)輸問題與指派問題共65頁(yè)，您現(xiàn)在瀏覽的是第56頁(yè)!一、什么是指派問題有n項(xiàng)任務(wù)，恰好有n個(gè)人可承擔(dān)