運輸問題與指派問題

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

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

n

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

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

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

xij≥0

運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第10頁!例5.2.1海華設備廠均衡運輸問題海華設備廠下設三個位于不同地點的分廠A、B、C，該三個分廠生產(chǎn)同一種設備，設每月的生產(chǎn)能力分別為20臺、30臺和40臺。海華設備廠有四個固定用戶，該四個用戶下月的設備需求量分別為20臺、15臺、23臺和32臺。設各分廠的生產(chǎn)成本相同，從各分廠至各用戶的單位設備運輸成本如表4.2.1所示，運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第11頁!而且各分廠本月末的設備庫存量為零。問該廠應如何安排下月的生產(chǎn)與運輸，才能在滿足四個用戶需求的前提下，使總運輸成本最低。運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第12頁!總供應量=20+30+40=90（臺），總需求量=20+15+23+32=90（臺），供應量之和等于需求量之和，供需均衡。決策變量是下月各分廠為各用戶生產(chǎn)與運輸?shù)脑O備數(shù)量?？稍O：分廠A下月為四個用戶生產(chǎn)和運輸?shù)脑O備數(shù)量分別為A1，A2，A3，A4（臺）；運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第13頁!約束條件有兩部分，部分是需求約束，各用戶從各分廠收到的設備總數(shù)不得少于它們的需求量：A1+B1+C1=20A2+B2+C2=15A3+B3+C3=23A4+B4+C4=32運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第14頁!線性規(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運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第15頁!四、供需非均衡運輸問題的建模與求解1、當供給大于需求時，即n

m∑bj

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

…Bn產(chǎn)量A1A2

…Amx11x12…x1nx21x22…

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

m∑bj

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

…Bn產(chǎn)量A1A2

…Amx11x12…x1nx21x22…

x2n…xm1xm2…xmna1a2…am銷量b1b2…bn運量分配表運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第19頁!例5.2.1海華設備廠非均衡運輸問題若例4.2.1中的三個分廠經(jīng)技術(shù)改造，每月的生產(chǎn)能力均增加了5臺，即分別從20臺、30臺、40臺增加為25臺、35臺、45臺，其他條件不變?yōu)閼撊绾伟才畔略碌纳a(chǎn)與運輸，才能在滿足四個用戶的前提下使總運輸成本最低。運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第20頁!總供應量=25+35+45=105（臺），總需求量=20+15+23+32=90（臺），供應量之和大于需求量之和，供需不均衡。需求節(jié)點收到的產(chǎn)品總數(shù)等于其總需求量，而各供應節(jié)點發(fā)出的產(chǎn)品總數(shù)則小于其供應能力。模型變?yōu)椋哼\輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第21頁!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運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第22頁!北方飛機制造公司問題的生產(chǎn)進度安排數(shù)據(jù)月份計劃安裝量最大產(chǎn)量單位生產(chǎn)成本（百萬美元）單位存儲成本(百萬美元)正常時間加班時間正常時間加班時間11020101.081.100.01521530151.111.120.01532525101.101.110.0154205101.131.15運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第23頁!例產(chǎn)品分配計劃求佳產(chǎn)品公司決定使用三個有生產(chǎn)余力的工廠進行四種新產(chǎn)品的生產(chǎn)制造。就哪個工廠生產(chǎn)哪種產(chǎn)品做決策,使總成本達到最小。運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第24頁!

單位利潤

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

…Bn分配的任務A1A2

…Anc11c12…c1nc21c22…

c2n…cn1cn2…cnn11…1要完成的任務1

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

n

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

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

ni=1n

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

nj=1

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

指派問題的變形

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

…Bn產(chǎn)量A1A2

…Amc11c12…c1nc21c22…

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

…Bn產(chǎn)量A1A2

…Amx11x12…x1nx21x22…

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

+130C3+40C4

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

≥0運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第45頁!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運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第46頁!銷地產(chǎn)地B1B2

…Bn產(chǎn)量A1A2

…Amc11c12…c1nc21c22…

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

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

∑xij≤

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

…Bn產(chǎn)量A1A2

…Amc11c12…c1nc21c22…

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

∑xij≤

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

∑xij=aii=1，2，…，mj=1xij≥0運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第50頁!ABC4321704080607010011050807013040解：可用一個網(wǎng)絡圖來描述25354520152332運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第51頁!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運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第52頁!五、運輸問題的應用例:北方飛機制造公司為全世界的航空公司生產(chǎn)各種商務飛機。制造過程的最后一步是生產(chǎn)噴氣發(fā)動機并把它們安裝到已經(jīng)完成的飛機框架之中去。按照公司的一些訂單合同，不久公司要交付使用相當多數(shù)量的飛機。所以有必要現(xiàn)在為未來四個月這些飛機噴氣發(fā)動機的生產(chǎn)制定計劃。運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第53頁!生產(chǎn)管理人員需要制定出一個每月生產(chǎn)多少發(fā)動機的計劃,使制造和存儲的總成本達到最小。運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第54頁!公司的產(chǎn)品數(shù)據(jù)單位成本可用能力產(chǎn)品1234工廠1$41$27$28$247524029--237533730272145要求產(chǎn)量20303040運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第55頁!目標決定向每位顧客銷售多少單位的產(chǎn)品以及為實現(xiàn)最大利潤。運輸問題與指派問題共65頁，您現(xiàn)在瀏覽的是第56頁!一、什么是指派問題有n項任務，恰好有n個人可承擔