運(yùn)籌學(xué) 運(yùn)輸與指派問(wèn)題.ppt

1、第4章 運(yùn)輸問(wèn)題和指派問(wèn)題,運(yùn)輸問(wèn)題和指派問(wèn)題是實(shí)際中碰到的比較常見(jiàn)的一類線性規(guī)劃問(wèn)題，它們?cè)谧兞康娜≈?、約束條件的系數(shù)矩陣等具有一定的特殊性，所以可以找到比單純形法更為簡(jiǎn)便的求解方法。,4.1 運(yùn)輸問(wèn)題模型及表上作業(yè)法求解,單位運(yùn)價(jià)表(cij),產(chǎn)銷平衡表（決策變量xij=0或1),產(chǎn)銷平衡的運(yùn)輸問(wèn)題:,運(yùn)輸問(wèn)題的表上作業(yè)法,表上作業(yè)法是一種簡(jiǎn)便而有效的方法,實(shí)質(zhì)是單純形法. 例4.1某公司下屬有三個(gè)加工廠A1,A2,A3生產(chǎn)化肥,負(fù)責(zé)供應(yīng)B1,B2,B3,B4四個(gè)地區(qū)所需化肥，各廠化肥產(chǎn)量及各地區(qū)所需化肥、各化肥廠到各地區(qū)所的運(yùn)輸距離見(jiàn)下表：,單位 銷地,單位運(yùn)價(jià)表(元),產(chǎn)銷平衡表,銷地

2、,運(yùn)量 產(chǎn)地,給出初始解,給出初始解有西北角法、最小元素法和Vogel法,我們只介紹比較簡(jiǎn)單的最小元素法. 步驟:在產(chǎn)銷平衡的前提下,運(yùn)價(jià)低的優(yōu)先安排調(diào)運(yùn).,3,1,4,6,3,3,最小元素法初始方案,單位運(yùn)價(jià)表,解的最優(yōu)性檢驗(yàn),解的最優(yōu)性檢驗(yàn)主要有閉回路法和位勢(shì)法,我們只介紹位勢(shì)法. 位勢(shì)法: (1)把產(chǎn)銷平衡表中初始方案中有數(shù)字格對(duì)應(yīng)的運(yùn)價(jià)寫到檢驗(yàn)數(shù)表中; (2)對(duì)運(yùn)輸表上的每一行(列)賦予一個(gè)數(shù)值ui(vj),稱為位勢(shì).各格子的位勢(shì)等于行位勢(shì)與列位勢(shì)之和. (3)求出檢驗(yàn)數(shù):ij=cij-(ui+vj),2,-1,3,0,10,-5,9,單位運(yùn)價(jià)表,位勢(shì)法檢驗(yàn)數(shù)計(jì)算表,(3)1,(11)

3、2,(9)1,(8)-1,(7)10,(10)12,運(yùn)輸方案的改進(jìn),當(dāng)所有ij0,即為即優(yōu).當(dāng)ij0時(shí),由閉回路法修改方案. 閉回路法: (1)找到最小的負(fù)檢驗(yàn)數(shù),其對(duì)應(yīng)的變量為入基變量. (2)從入基變量對(duì)應(yīng)的格子出發(fā),遇到有數(shù)字的格子可以轉(zhuǎn)90（也可不轉(zhuǎn)）,直到回到出發(fā)點(diǎn),形成閉回路. (3)根據(jù)供應(yīng)量與需求量總量不變的原則,調(diào)整供需關(guān)系.,0+,3-,4+,1-,因供給非負(fù),所以=1,得新供給方案,運(yùn)輸方案的改進(jìn),單位運(yùn)價(jià)表,0,3,10,-2,3,-5,9,(3) 0,(11)2,(9)2,(2)1,(7)9,(10)12,2,1,3,至此,檢驗(yàn)數(shù)全部大于0, 調(diào)整后的方案為已為最優(yōu)方

4、案. 總運(yùn)費(fèi)=3*5+10*2+1*3+8*1+4*6+5+3 =85,4.2:產(chǎn)銷平衡運(yùn)輸問(wèn)題的Excel求解,1. ExcelORM線性規(guī)劃運(yùn)輸問(wèn)題目標(biāo)min,銷地?cái)?shù)4,產(chǎn)地?cái)?shù)3,生成電子表模型,2.輸入單位運(yùn)價(jià)、產(chǎn)量與銷量,3.設(shè)置規(guī)劃求解參數(shù)對(duì)話框,4.求解,0 0 0,bn+1,Bn+1,4.3 產(chǎn)銷不平衡運(yùn)輸問(wèn)題,產(chǎn)銷平衡:,產(chǎn)量大于銷量,當(dāng)aibj時(shí), 用產(chǎn)銷平衡的數(shù)學(xué)模型,其約束會(huì)產(chǎn)生矛盾.此時(shí)模型應(yīng)改為:,若用表上作業(yè)法求之,可設(shè)一個(gè)假想銷地, 使其銷量為bn+1=ai-bj,ci,n+1=0.,例4.2 按合同供貨的生產(chǎn)計(jì)劃問(wèn)題（P109）,生產(chǎn)能力與生產(chǎn)成本,某廠按合同規(guī)

5、定于當(dāng)年每季度未分別提供10、15、25、20臺(tái)同一規(guī)格柴油機(jī)。已知該廠的生產(chǎn)能力與生產(chǎn)成本如下表。若生產(chǎn)出的產(chǎn)品當(dāng)季不交貨，則需儲(chǔ)存、維護(hù)等費(fèi)用1500元。要求在完成合同的情況下，做出全年生產(chǎn)費(fèi)用最小的決策。,分析：由題設(shè)我們可得第i季度生產(chǎn)，第j季度交貨的成本如下表，因此可看成是供大于求的運(yùn)輸問(wèn)題。,交貨季度j,生產(chǎn)季度i,交貨的成本,交貨季度j,生產(chǎn)季度i,設(shè)xij表示第i季度生產(chǎn)，第j季度交貨的柴油機(jī)數(shù)量，則,產(chǎn)銷表,用Excel求解,0 0 0,am+1,Am+1,產(chǎn)銷平衡:,產(chǎn)量小于銷量,當(dāng)aibj時(shí), 用產(chǎn)銷平衡的數(shù)學(xué)模型,其約束會(huì)產(chǎn)生矛盾.此時(shí)模型應(yīng)改為:,若用表上作業(yè)法求之,

6、可設(shè)一個(gè)假想產(chǎn)地, 使其銷量為am+1=bj-ai,cm+1,j=0.,產(chǎn)量小于銷量運(yùn)輸問(wèn)題的Excel求解（P113例4.3),1. ExcelORM線性規(guī)劃運(yùn)輸問(wèn)題目標(biāo)min,銷地?cái)?shù)4,產(chǎn)地?cái)?shù)3,生成電子表模型,用Excel求解,變形運(yùn)輸問(wèn)題的Excel求解（P115例4.4),1. ExcelORM線性規(guī)劃運(yùn)輸問(wèn)題目標(biāo)min,銷地?cái)?shù)4,產(chǎn)地?cái)?shù)3,銷量有彈性，生成電子表模型,用Excel求解,需求有彈性的運(yùn)輸問(wèn)題的Excel求解（P117例4.5),1. ExcelORM線性規(guī)劃運(yùn)輸問(wèn)題目標(biāo)min,銷地?cái)?shù)4,產(chǎn)地?cái)?shù)3,銷量有彈性，生成電子表模型,用Excel求解,例戰(zhàn)備物資的調(diào)運(yùn),但有轉(zhuǎn)運(yùn)

7、問(wèn)題，pij與轉(zhuǎn)運(yùn)方式有關(guān)。,有轉(zhuǎn)運(yùn)的運(yùn)輸問(wèn)題,設(shè)xk（ =0或1）表示第k個(gè)中轉(zhuǎn)站啟用次數(shù)，xik表示從第i個(gè)倉(cāng)庫(kù)運(yùn)到第k個(gè)中轉(zhuǎn)站的物資數(shù)量，ykj表示從第k個(gè)中轉(zhuǎn)站運(yùn)到第j個(gè)單位的物資數(shù)量，則,運(yùn)輸問(wèn)題小結(jié),1.運(yùn)輸問(wèn)題由一個(gè)產(chǎn)銷平衡表和一個(gè)單位運(yùn)價(jià)表構(gòu)成.,2.運(yùn)輸問(wèn)題數(shù)學(xué)模型,產(chǎn)銷平衡,產(chǎn)大于銷,產(chǎn)小于銷,3.表上作業(yè)法:最小元素法給出初始方案、位勢(shì)法求檢驗(yàn)數(shù)、閉回路法調(diào)整方案,5.非地理問(wèn)題轉(zhuǎn)化為運(yùn)輸問(wèn)題,4. 依據(jù)數(shù)學(xué)模型，用Excel求解。,指派問(wèn)題（分派問(wèn)題）（Assignment problem） 若需完成n項(xiàng)任務(wù)，分配給n個(gè)人承擔(dān)。由于每人的專長(zhǎng)、能力不同，各人完成任務(wù)的收

8、益、成本也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，才能使完成n項(xiàng)任務(wù)的總成本最低或總收益最高。這類問(wèn)題統(tǒng)稱為指派問(wèn)題。 指派問(wèn)題的假設(shè) 1. 被指派者的數(shù)量和任務(wù)的數(shù)量是相同的； 2. 每個(gè)人只完成一項(xiàng)任務(wù)； 3. 每項(xiàng)任務(wù)只能由一個(gè)人來(lái)完成； 4.每個(gè)人和每項(xiàng)任務(wù)的組合都會(huì)有一個(gè)相關(guān)成本（收益）； 5.目標(biāo)總成本或總收益值是根據(jù)任務(wù)指派確定。,某單位有n項(xiàng)任務(wù)需要n個(gè)人去完成，每個(gè)人僅能完成一項(xiàng)任務(wù)，每項(xiàng)任務(wù)僅要一人去完成，每個(gè)人完成不同的任務(wù)效率不同（見(jiàn)表4-1），問(wèn)如何安排任務(wù)可使任務(wù)完成效率最高？,設(shè)xij表示安排第i個(gè)人去完成第j項(xiàng)任務(wù)，則,指派問(wèn)題的模型,一般指派問(wèn)題的數(shù)學(xué)模型,

9、它可看作一種特殊的運(yùn)輸問(wèn)題。只是這里要求ai=bj=1,且xij=0,1. 因此其有類似于運(yùn)輸問(wèn)題的變形問(wèn)題，處理技巧也類似。,指派問(wèn)題的Excel求解（P126例4.8),1. ExcelORM線性規(guī)劃分配問(wèn)題目標(biāo)min,任務(wù)數(shù)4,人員數(shù)4,生成電子表模型,用Excel求解,例 2011全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽 B題 交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度,根據(jù)該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個(gè)交巡警服務(wù)平臺(tái)的設(shè)置情況示意圖和相關(guān)的數(shù)據(jù)信息得各交巡警服務(wù)平臺(tái)到各路口的最短距離表。請(qǐng)為各交巡警服務(wù)平臺(tái)分配管轄范圍，使各平臺(tái)管轄范圍內(nèi)的路口數(shù)盡量均衡，同時(shí)使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時(shí)，盡量能在3分鐘內(nèi)有交巡警（警車的時(shí)速為60km/