運(yùn)輸問題與指派問題(“運(yùn)輸”文檔)共65張

Excel在經(jīng)濟(jì)管理中的運(yùn)用第五講運(yùn)輸問題與指派問題§5.1運(yùn)輸問題(transportationproblem)一、什么是運(yùn)輸問題二、運(yùn)輸問題的分類三、供需平衡運(yùn)輸問題的建模與求解四、供需非平衡運(yùn)輸問題的建模與求解五、運(yùn)輸問題的運(yùn)用一、什么是運(yùn)輸問題在經(jīng)濟(jì)建立中，經(jīng)常碰到大宗物資調(diào)運(yùn)問題，如煤、鋼鐵、木材、糧食等等物資。在全國有假設(shè)干消費(fèi)基地，根據(jù)已有的交通網(wǎng)，應(yīng)如何制定調(diào)運(yùn)方案，將這些物資運(yùn)到各消費(fèi)地點(diǎn)，而總費(fèi)用最小。例：設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地域的農(nóng)用化肥，假定等量的化肥在這些地域運(yùn)用效果一樣。各化肥廠年產(chǎn)量，各地域年需求量及從各化肥廠到各地域運(yùn)送單位化肥的運(yùn)價(jià)如表所示，試求出總的運(yùn)費(fèi)最節(jié)省的化肥調(diào)撥方案。需求地域化肥廠地域1地域2地域3地域4產(chǎn)量〔萬噸〕廠11613221750廠21413191560廠31920231050需求量〔萬噸〕50703010運(yùn)價(jià)：萬元/萬噸1.供應(yīng)節(jié)點(diǎn)：運(yùn)輸?shù)钠瘘c(diǎn)，像消費(fèi)廠商，提供的產(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)。4.運(yùn)輸問題：在滿足供應(yīng)節(jié)點(diǎn)的供應(yīng)量約束和需求節(jié)點(diǎn)的需求量約束的條件下，為了使運(yùn)輸本錢最低，如何安排運(yùn)輸。二、運(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)輸問題。需求地域化肥廠地域1地域2地域3地域4產(chǎn)量〔萬噸〕廠11613221750廠21413191560廠31920231050需求量〔萬噸〕50703010運(yùn)價(jià)：萬元/萬噸需求地域化肥廠地域1地域2地域3地域4產(chǎn)量〔萬噸〕廠11613221750廠21413191580廠31920231050需求量〔萬噸〕50703010運(yùn)價(jià)：萬元/萬噸需求地域化肥廠地域1地域2地域3地域4產(chǎn)量〔萬噸〕廠11613221750廠21413191560廠31920231050需求量〔萬噸〕60703010運(yùn)價(jià)：萬元/萬噸三、供需平衡運(yùn)輸問題的建模與求解知有m個(gè)消費(fèi)地點(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è)表格來表示出來。銷地產(chǎn)地B1B2…Bn產(chǎn)量A1A2…Amc11c12…c1nc21c22…c2n…………cm1cm2…cmna1a2…am銷量b1b2…bn本錢表對(duì)于產(chǎn)銷平衡的運(yùn)輸問題，有下面的關(guān)系式：nm∑bj=∑aij=1i=1銷地產(chǎn)地B1B2…Bn產(chǎn)量A1A2…Amx11x12…x1nx21x22…x2n…………xm1xm2…xmna1a2…am銷量b1b2…bn運(yùn)量分配表用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=1xij≥0

在這個(gè)數(shù)學(xué)模型中，包含有m×n個(gè)變量，有〔m+n〕個(gè)約束方程，約束條件中變量的系數(shù)比較特殊，不是1就是0。例5.2.1海華設(shè)備廠平衡運(yùn)輸問題海華設(shè)備廠下設(shè)三個(gè)位于不同地點(diǎn)的分廠A、B、C，該三個(gè)分廠消費(fèi)同一種設(shè)備，設(shè)每月的消費(fèi)才干分別為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è)各分廠的消費(fèi)本錢一樣，從各分廠至各用戶的單位設(shè)備運(yùn)輸本錢如表4.2.1所示，表5.2.1海華設(shè)備廠運(yùn)輸本錢表分廠稱號(hào)運(yùn)輸本錢〔元/臺(tái)〕月消費(fèi)才干〔臺(tái)〕用戶1用戶2用戶3用戶4分廠A7040806020分廠B701001105030分廠C80701304040下月設(shè)備需求量〔臺(tái)〕2015233290而且各分廠本月末的設(shè)備庫存量為零。問該廠應(yīng)如何安排下月的消費(fèi)與運(yùn)輸，才干在滿足四個(gè)用戶需求的前提下，使總運(yùn)輸本錢最低。解：可用一個(gè)網(wǎng)絡(luò)圖來描畫ABC432170408060701001105080701304020304020152332總供應(yīng)量=20+30+40=90〔臺(tái)〕，總需求量=20+15+23+32=90〔臺(tái)〕，供應(yīng)量之和等于需求量之和，供需平衡。決策變量是下月各分廠為各用戶消費(fèi)與運(yùn)輸?shù)脑O(shè)備數(shù)量?？稍O(shè)：分廠A下月為四個(gè)用戶消費(fèi)和運(yùn)輸?shù)脑O(shè)備數(shù)量分別為A1，A2，A3，A4〔臺(tái)〕；分廠B下月為四個(gè)用戶消費(fèi)和運(yùn)輸?shù)脑O(shè)備數(shù)量分別為B1，B2，B3，B4〔臺(tái)〕；分廠C下月為四個(gè)用戶消費(fèi)和運(yùn)輸?shù)脑O(shè)備數(shù)量分別為C1，C2，C3，C4〔臺(tái)〕。目的函數(shù)是總運(yùn)輸本錢最小化，總運(yùn)輸本錢=70A1+40A2+80A360A4+70B1+100B2+110B3+50B4+80C1+70C2+130C3+40C4約束條件有兩部分，第一部分是需求約束，各用戶從各分廠收到的設(shè)備總數(shù)不得少于它們的需求量：A1+B1+C1=20A2+B2+C2=15A3+B3+C3=23A4+B4+C4=32第二部分是消費(fèi)才干約束，各分廠消費(fèi)和運(yùn)輸?shù)脑O(shè)備總數(shù)不得超越其消費(fèi)才干：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線性規(guī)劃模型為：Min70A1+40A2+80A360A4+70B1+100B2+110B3+50B4+80C1+70C2+130C3+40C4s.t.A1+B1+C1=20A2+B2+C2=15A3+B3+C3=23A4+B4+C4=32A1+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)輸問題的建模與求解1、當(dāng)供應(yīng)大于需求時(shí)，即nm∑bj≤∑aij=1i=1銷地產(chǎn)地B1B2…Bn產(chǎn)量A1A2…Amc11c12…c1nc21c22…c2n…………cm1cm2…cmna1a2…am銷量b1b2…bn本錢表銷地產(chǎn)地B1B2…Bn產(chǎn)量A1A2…Amx11x12…x1nx21x22…x2n…………xm1xm2…xmna1a2…am銷量b1b2…bn運(yùn)量分配表用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≥02、當(dāng)供應(yīng)小于需求時(shí)，即nm∑bj≥∑aij=1i=1銷地產(chǎn)地B1B2…Bn產(chǎn)量A1A2…Amc11c12…c1nc21c22…c2n…cm1cm2…cmna1a2…am銷量b1b2…bn本錢表A1，A2，A3，A4，B1，B2，B3，B4，Minz=∑∑cijxijb1b2…bn銷地b1b2…bn在經(jīng)濟(jì)建立中，經(jīng)常碰到大宗物資調(diào)運(yùn)問題，如煤、鋼鐵、木材、糧食等等物資。1$55$42$46$538,000∑bj≥∑aib1b2…bnx21x22…x2nb1b2…bn問應(yīng)如何分配義務(wù)，才干使得完成四種零件加工義務(wù)的總時(shí)間最短。j=1i=1∑xij≤bj，j=1，2，…，nC1+C2+C3+C4=40Excel在經(jīng)濟(jì)管理中的運(yùn)用銷地產(chǎn)地B1B2…Bn產(chǎn)量A1A2…Amx11x12…x1nx21x22…x2n…xm1xm2…xmna1a2…am銷量b1b2…bn運(yùn)量分配表用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例5.2.1海華設(shè)備廠非平衡運(yùn)輸問題假設(shè)例4.2.1中的三個(gè)分廠經(jīng)技術(shù)改造，每月的消費(fèi)才干均添加了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)該如何安排下月的消費(fèi)與運(yùn)輸，才干在滿足四個(gè)用戶的前提下使總運(yùn)輸本錢最低。ABC4321704080607010011050807013040解：可用一個(gè)網(wǎng)絡(luò)圖來描畫25354520152332總供應(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)椋篗in70A1+40A2+80A360A4+70B1+100B2+110B3+50B4+80C1+70C2+130C3+40C4s.t.A1+B1+C1=20A2+B2+C2=15A3+B3+C3=23A4+B4+C4=32A1+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)輸問題的運(yùn)用例:北方飛機(jī)制造公司為全世界的航空公司消費(fèi)各種商務(wù)飛機(jī)。制造過程的最后一步是消費(fèi)噴氣發(fā)動(dòng)機(jī)并把它們安裝到曾經(jīng)完成的飛機(jī)框架之中去。按照公司的一些訂單合同，不久公司要交付運(yùn)用相當(dāng)多數(shù)量的飛機(jī)。所以有必要如今為未來四個(gè)月這些飛機(jī)噴氣發(fā)動(dòng)機(jī)的消費(fèi)制定方案。北方飛機(jī)制造公司問題的消費(fèi)進(jìn)度安排數(shù)據(jù)月份方案安裝量最大產(chǎn)量單位消費(fèi)本錢〔百萬美圓〕單位存儲(chǔ)本錢(百萬美圓)正常時(shí)間加班時(shí)間正常時(shí)間加班時(shí)間11020101.081.100.01521530151.111.120.01532525101.101.110.0154205101.131.15消費(fèi)管理人員需求制定出一個(gè)每月消費(fèi)多少發(fā)動(dòng)機(jī)的方案,使制造和存儲(chǔ)的總本錢到達(dá)最小。例產(chǎn)品分配方案求佳產(chǎn)品公司決議運(yùn)用三個(gè)有消費(fèi)余力的工廠進(jìn)展四種新產(chǎn)品的消費(fèi)制造。就哪個(gè)工廠消費(fèi)哪種產(chǎn)品做決策,使總本錢到達(dá)最小。公司的產(chǎn)品數(shù)據(jù)單位本錢可用才干產(chǎn)品1234工廠1$41$27$28$247524029--237533730272145要求產(chǎn)量20303040

單位利潤

顧客:1234消費(fèi)才干工廠1$55$42$46$538,0002371832485,0003295951357,000最少購買力7000300020000最大購買力7000900060008000例產(chǎn)品銷售方案目的決議向每位顧客銷售多少單位的產(chǎn)品以及為實(shí)現(xiàn)最大利潤。三、指派問題在電子表格中的建模與求解j=1c21c22…c2nx11x12…x1nC1+C2+C3+C4=40需求量之和的運(yùn)輸問題。xm1xm2…xmnC1+C2+C3+C4=40B1B2…Bn海華設(shè)備廠下設(shè)三個(gè)位于不同地點(diǎn)的分廠A、B、C，該三個(gè)分廠消費(fèi)同一種設(shè)備，設(shè)每月的消費(fèi)才干分別為20臺(tái)、30臺(tái)和40臺(tái)。按照公司的一些訂單合同，不久公司要交付運(yùn)用相當(dāng)多數(shù)量的飛機(jī)。3295951357,000A1，A2，A3，A4，B1，B2，B3，B4，§5.2指派問題(assignmentproblem)一、什么是指派問題二、指派問題的普通數(shù)學(xué)模型三、指派問題在電子表格中的建模與求解一、什么是指派問題有n項(xiàng)義務(wù)，恰好有n個(gè)人可承當(dāng)這些義務(wù)，要求每項(xiàng)義務(wù)必需且只能有一個(gè)承當(dāng)者完成，每個(gè)承當(dāng)者必需且只能承當(dāng)一項(xiàng)義務(wù)，每個(gè)人的專長不同，各人完成義務(wù)所費(fèi)的時(shí)間不同，效率也不同，于是產(chǎn)生派哪個(gè)人去完成哪項(xiàng)義務(wù)，使得完成n項(xiàng)義務(wù)的總效率最高，或者是所需的時(shí)間最短？這類問題稱為指派問題或分派問題。例：有一份中文闡明書，需譯成英、日、德、俄四種文字，分別記作E、J、G、R，現(xiàn)有甲、乙、丙、丁四人。他們將中文闡明書翻譯成不同語種的闡明書所需時(shí)間如表所示，問應(yīng)指派何人去完成何任務(wù)，使所需總時(shí)間最少？義務(wù)人員EJGR甲215134乙1041415丙9141613丁78119單位：小時(shí)又如：有n項(xiàng)加工義務(wù)，怎樣指派到n臺(tái)機(jī)床上分別完成的問題，有n條航線，怎樣指定n艘船去航行的問題等等都是指派問題。二、指派問題的數(shù)學(xué)模型設(shè)決策變量為xij，其值只能取1或0，并令Xij=1當(dāng)指派第i人去完成第j項(xiàng)義務(wù)0當(dāng)不指派第i人去完成第j項(xiàng)義務(wù)設(shè)cij為系數(shù)矩陣中的任一元素，那么它的普通數(shù)學(xué)模型為：義務(wù)人員B1B2…Bn分配的義務(wù)A1A2…Anc11c12…c1nc21c22…c2n…cn1cn2…cnn11…1要完成的義務(wù)11…1義務(wù)人員B1B2…Bn分配的義務(wù)A1A2…Anx11x12…x1nx21x22…x2n…xn1xn2…xnn11…1要完成的義務(wù)11…1nnMin