運輸問題與指派問題第5ppt課件

1、OROR課件課件 回 顧v但是：但是：v在決策的實踐中，有些問題約束條件在決策的實踐中，有些問題約束條件存在一定的特殊性，按常規(guī)辦法有可能存在一定的特殊性，按常規(guī)辦法有可能出現(xiàn)嚴(yán)重退化而導(dǎo)致問題無法順利求解。出現(xiàn)嚴(yán)重退化而導(dǎo)致問題無法順利求解。如：運輸問題、指派問題等。如：運輸問題、指派問題等。從約束條件入手OROR課件課件運 籌 帷 幄 之 中決 勝 千 里 之 外OROR課件課件運輸問題與指派問題 運輸問題和指派問題是一種特殊的LP問題，要求了解兩問題的基本特征；掌握兩問題的求解算法原理及計算過程；學(xué)會對它們的特殊形式的處理。本章的要求TP & APOROR課件課件運輸問題與指派問

2、題重點重點本章重點與難點難點難點TP & AP運輸與指派問題模型及其特征算法原理特殊問題的處理兩算法的思想及其實現(xiàn)OROR課件課件運輸問題與指派問題運輸問題運輸問題主要內(nèi)容指派問題指派問題TP & AP運輸問題及其數(shù)學(xué)模型求解方法表上作業(yè)法特殊運輸問題的求解指派問題及其數(shù)學(xué)模型求解方法匈牙利法特殊指派問題的求解OROR課件課件運輸問題運輸問題及其數(shù)學(xué)模型運輸問題及其數(shù)學(xué)模型TP & AP 設(shè)某種物資有m個產(chǎn)地：A1,A2,Am；產(chǎn)量分別為：a1,a2,am個單位；n個銷地：B1,B2,Bn；銷量分別為：b1,b2,bn個單位；假設(shè)產(chǎn)銷總量是平衡的，即單位運價：Ai Bj

3、：cij問：如何調(diào)運這種物資才能使總的運費最??？njjmiiba11OROR課件課件運輸問題單位運價表與平衡表合表）單位運價表與平衡表合表）TP & AP產(chǎn) 地 B1 B2 Bn 產(chǎn) 量 A1 A2 . Am . C11 C21 cm 1 C12 C21 cm 2 C1n C2n cm n a1 a2 am 銷 量 b1 b2 bn 銷 地 單位運價產(chǎn)銷量平衡）OROR課件課件運輸問題模型模型TP & AP設(shè)：xij為AiBj的運量 )(0,2, 1,2, 1,111111njjmiiijjmiijinjijminjijijbaxbxaxxcnjmiMinS OROR課件課件運

4、輸問題表上作業(yè)法表上作業(yè)法TP & AP【簡例】已知有關(guān)資料如下表算法的提出：觀測模型的特征產(chǎn) 地 B 1 B 2 B 3 產(chǎn) 量 A 1 A 2 1 4 2 5 3 6 20 30 銷 量 10 25 15 銷 地 要求建立總運費最小的模型。OROR課件課件運輸問題模型模型TP & APnjmiMinSxxxxxxxxxxxxxxxxxxxij, 2 , 1;, 2 , 1, 0152510302033132212211123222113121123222113121165432 100100010010001001111000000111A 約束條件個數(shù)為 m+n，但只有m

5、+n-1 個是線性無關(guān)元素只有0和1，每列只有兩個1OROR課件課件表上作業(yè)法算法思想算法思想TP & AP 與單純形法一樣，最優(yōu)解在基本可行解中產(chǎn)生。但基于模型的特征，初始基本可行解是通過分析單位運價表，首先滿足局部最優(yōu)，然后通過調(diào)整迭代使整體達到最優(yōu)。平衡表OROR課件課件表上作業(yè)法 步驟算法步驟及要點算法步驟及要點TP & AP初始調(diào)運方案檢驗數(shù)ij0 ?YN調(diào)整：找到新的調(diào)運方案特征：解變量基變量個特征：解變量基變量個數(shù)為數(shù)為 m+n-1；以解變量為頂；以解變量為頂點不構(gòu)成折現(xiàn)閉回路。點不構(gòu)成折現(xiàn)閉回路。方法：最小元素法、差值法方法：最小元素法、差值法方法：閉回路法、位

6、勢法方法：閉回路法OROR課件課件表上作業(yè)法初始方案折現(xiàn)閉回路：折現(xiàn)閉回路：TP & AP產(chǎn) 地 B 1 B 2 B 3 B 4 A 1 X 11 X 12 X 13 X 14 A 2 X 21 X 22 X 23 X 24 A 3 X 31 X 32 X 33 X 34 銷 地 頂點: x11,x12,x32,x31頂點：x12,x13,x33,x34,x24,x22v定理：以m+n-1個變量構(gòu)成的基本可行解的充要條件是它不含折現(xiàn)閉回路。OROR課件課件表上作業(yè)法初始方案最小元素法最小元素法TP & AP產(chǎn) 地 B 1 B 2 B 3 B 4 產(chǎn) 量 A 1 2 9 1 0

7、7 9 A 2 1 3 4 2 5 A 3 8 4 2 5 7 銷 量 3 8 4 6 銷 地 基本思想：“就近供應(yīng)或稱“就廉供應(yīng)”3 42 345Z=139543247422100OROR課件課件表上作業(yè)法初始方案差值法差值法伏格爾伏格爾Vogel) 法法TP & AP產(chǎn) 地 B 1 B 2 B 3 B 4 產(chǎn) 量 行 差 值 A 1 2 9 1 0 7 9 5 A 2 1 3 4 2 5 1 A 3 8 4 2 5 7 2 銷 量 3 8 4 6 列 差 值 1 1 2 3 銷 地 基本思想：在考慮最大差值的基礎(chǔ)上，就近供應(yīng)差值行、列）次小元素最小元素Z=2395432471258

8、83 25 2854 13 15OROR課件課件表上作業(yè)法最優(yōu)性檢驗閉回路法閉回路法TP & AP 基本原理：以任一非基變量為頂點，其它頂點為基變量，所構(gòu)成的閉回路是唯一的。偶數(shù)頂點奇數(shù)頂點ccijijij 產(chǎn) 地 B 1 B 2 B 3 B 4 產(chǎn) 量 A 1 2 9 1 0 7 9 A 2 1 3 4 2 5 A 3 8 4 2 5 7 銷 量 3 8 4 6 銷 地 3 42 345471323OROR課件課件表上作業(yè)法最優(yōu)性檢驗TP & AP位勢法位勢法 基本原理：由于找閉回路帶來的麻煩，根據(jù)對偶理論，設(shè)兩組變量對偶變量ui和vj，及基變量的檢驗數(shù)等于0，建立一組參數(shù)方

9、程：), 2 , 1;, 2 , 1(njmicvuijji )(vucjiijij OROR課件課件表上作業(yè)法最優(yōu)性檢驗TP & AP產(chǎn) 地 B 1 B 2 B 3 B 4 產(chǎn) 量 A 1 2 9 1 0 7 9 A 2 1 3 4 2 5 A 3 8 4 2 5 7 銷 量 3 8 4 6 銷 地 3 42 345vjui242179333332232442211214411221cvucvucvucvucvucvu 76557903132421vvuuvvu 0-5-56977-47-1323OROR課件課件表上作業(yè)法方案調(diào)整TP & AP產(chǎn) 地 B 1 B 2 B 3

10、B 4 產(chǎn) 量 A 1 2 9 1 0 7 9 A 2 1 3 4 2 5 A 3 8 4 2 5 7 銷 量 3 8 4 6 銷 地 3 42 345-47-1313閉回路法閉回路法基本思想：確定換入、換出變量。在閉回基本思想：確定換入、換出變量。在閉回路上采用路上采用“奇加偶減調(diào)整運量奇加偶減調(diào)整運量xij，閉，閉回路以外回路以外xij不變。不變。315?OROR課件課件表上作業(yè)法方案調(diào)整TP & AP產(chǎn) 地 B 1 B 2 B 3 B 4 產(chǎn) 量 A 1 2 9 1 0 7 9 A 2 1 3 4 2 5 A 3 8 4 2 5 7 銷 量 3 8 4 6 銷 地 45 3153

11、 vjui0297-5-57411-1323560產(chǎn) 地 B 1 B 2 B 3 B 4 產(chǎn) 量 A 1 2 9 1 0 7 9 A 2 1 3 4 2 5 A 3 8 4 2 5 7 銷 量 3 8 4 6 銷 地 40 363 5vjui027-58-464101432S=83OROR課件課件運輸問題TP & AP特殊運輸問題及其求解特殊運輸問題及其求解目標(biāo)取極大MaxZ）：用ij 0 進行最優(yōu)性檢驗。供過于求產(chǎn)銷）：加虛銷點，且加虛銷點，且Ci虛虛0 ，銷量為產(chǎn)銷之差，銷量為產(chǎn)銷之差 【例】【例】供不應(yīng)求銷產(chǎn)）：加虛產(chǎn)點，且加虛產(chǎn)點，且C虛虛j = 0 ，產(chǎn)量為銷產(chǎn)之差，產(chǎn)量為銷

12、產(chǎn)之差 【例】【例】 OROR課件課件特殊運輸問題及求解TP & AP產(chǎn) 地 B 1 B 2 B 3 產(chǎn) 量 A 1 2 9 1 0 9 A 2 1 3 4 5 A 3 8 4 2 7 銷 量 3 8 4 銷 地 產(chǎn) 地 B 1 B 2 B 3 B 虛 產(chǎn) 量 A 1 2 9 1 0 0 9 A 2 1 3 4 0 5 A 3 8 4 2 0 7 銷 量 3 8 4 6 銷 地 2115OROR課件課件特殊運輸問題及求解TP & AP產(chǎn) 地 B 1 B 2 B 3 產(chǎn) 量 A 1 2 9 10 9 A 2 1 3 4 5 A 3 8 4 2 7 銷 量 3 8 14 銷 地 產(chǎn)

13、 地 B 1 B 2 B 3 產(chǎn) 量 A 1 2 9 1 0 9 A 2 1 3 4 5 A 3 8 4 2 7 A 虛 0 0 0 4 銷 量 3 8 4 銷 地 2125OROR課件課件指派問題TP & AP問題的提出問題的提出 設(shè)有n個人，需要分派他們?nèi)プ鰊件工作。要求一個人做一件事，一件事只能由一個人完成；由于每人的專長不同，各人做任一種工作的效率可能不同，因而創(chuàng)造的價值也不同。問如何安排，才能使創(chuàng)造的總價值最大？OROR課件課件指派問題TP & AP數(shù)學(xué)模型數(shù)學(xué)模型【例】現(xiàn)有4輛裝載不同貨物的待卸車，派班員要分派給4個裝卸班組，每個班組卸一輛車。由于各個班組的技術(shù)專長

14、不同，各個班組卸不同車輛所需時間小時如下表。問派班員應(yīng)如何分配卸車任務(wù)，才能使卸車所花的總時間最少？ P 1 P 2 P 3 P 4 A B C D 4 2 4 3 3 3 3 2 4 6 5 6 1 5 4 5 待卸車裝卸組cijOROR課件課件指派問題數(shù)學(xué)模型TP & AP P 1 P 2 P 3 P 4 A B C D 4 2 4 3 3 3 3 2 4 6 5 6 1 5 4 5 待卸車裝卸組否則01jixij bjai1111111110, 2, 1, 1, 2, 1,11111min或xxxxcZijniijnjijninjijijnjni OROR課件課件指派問題TP &

15、amp; AP10, 2, 1, 1, 2, 1,11111min或xxxxcZijniijnjijninjijijnjni 匈牙利算法匈牙利算法算法的提出：觀測模型的特征特殊的運輸問題OROR課件課件匈牙利算法TP & AP算法原理算法原理cijnn不同行列減去最小元素 bijnn？OROR課件課件匈牙利算法TP & AP設(shè)：i，j 分別是系數(shù)矩陣cij 行和列減去的最小元素。那么 bij=cij- i - j 0jjiiijijijjiijjijijiijijijijijjiijijijijxcxxxcxcxb 因為bij0，xij0 則上式為bij所對應(yīng)的最優(yōu)目標(biāo)值0。c

16、ij所對應(yīng)的最優(yōu)目標(biāo)值為行、列減去的最小元素之和。OROR課件課件匈牙利算法TP & AP算法步驟算法步驟YN行列減去該行列的最小元素【例1】bij中存在不同行、不同列的0元素bij= (0)時，xij=1; 否則，xij=0變換系數(shù)矩陣【例2】OROR課件課件匈牙利算法TP & AP 562345345632143444cij -1-2-3-23401120134100323 -23201100132100123 bij44 (0)(0)(0)(0) 001001000001100044xij Z=1+2+5+2=1+2+3+2+2=10【例1】OROR課件課件匈牙利算法TP

17、 & AP 5432564577858791044cij -7-5-4-2-1 bij44 【例2】2210020112300023 (0)3210120122301023(0)(0)-1-111100020201200024(0)(0)(0)(0)1100020201200024(0)(0)(0)(0)或：關(guān)鍵：能覆蓋所有關(guān)鍵：能覆蓋所有0元素的最少直線數(shù)？元素的最少直線數(shù)？如何畫如何畫 ？OROR課件課件匈牙利算法TP & AP Z=20【例2】 000100101000010044xij 或：OROR課件課件匈牙利算法TP & AP【例2】畫法：畫法：在沒有0的行打號對打號的行上的