版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、2.6 2.6 運(yùn)輸問題及其解法運(yùn)輸問題及其解法 引例:某公司經(jīng)銷甲產(chǎn)品,它下設(shè)三個(gè)加工廠,每日的引例:某公司經(jīng)銷甲產(chǎn)品,它下設(shè)三個(gè)加工廠,每日的產(chǎn)量分別為:產(chǎn)量分別為:A1-40噸,噸,A2-40噸,噸,A3-90噸。該公司把這些噸。該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn),各銷售點(diǎn)每日銷量為:產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn),各銷售點(diǎn)每日銷量為:B1-30噸噸,B2-40噸,噸,B3-60噸,噸,B4-20噸噸, B5-20噸。已知從各工廠到各噸。已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)為下表所示。問該公司應(yīng)如何調(diào)運(yùn)銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)為下表所示。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品,在滿足各銷售點(diǎn)需求量的前提下,使總
2、運(yùn)費(fèi)為最少產(chǎn)品,在滿足各銷售點(diǎn)需求量的前提下,使總運(yùn)費(fèi)為最少 銷地 產(chǎn)地B1B2B3B4B5產(chǎn)量(萬噸)A171086440A259712640A336581190銷量(萬噸)30406020201解:這是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題,解:這是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題, 設(shè)設(shè)Xij表示從表示從Ai調(diào)運(yùn)產(chǎn)調(diào)運(yùn)產(chǎn)品到品到Bj的數(shù)量(噸),其數(shù)學(xué)模型是:的數(shù)量(噸),其數(shù)學(xué)模型是: 0X20XXX20XXX60XXX40XXX30XXX90XXXXX40XXXXX40XXXXX. t . sXCzminij352515342414332313322212222111353433323125242322211
3、51413121131i51jijij2一、產(chǎn)銷平衡的運(yùn)輸問題及其解法一、產(chǎn)銷平衡的運(yùn)輸問題及其解法1.產(chǎn)銷平衡的運(yùn)輸問題的數(shù)學(xué)模型及其特點(diǎn)產(chǎn)銷平衡的運(yùn)輸問題的數(shù)學(xué)模型及其特點(diǎn) :minjijijXCZ11min )n,.,1j,m,.,1i (0X)m,.,2, 1i (aX)n,.,2, 1j(bXijn1jiijm1ijij特點(diǎn):(1)其系數(shù)矩陣的結(jié)構(gòu)疏松,且每一列向量Pij=(0,1,1,0)T=ei+em+j 可以證明,r(A)=m+n1。即有m+n1個(gè)獨(dú)立方程。于是,該LP問題有且僅有m+n1個(gè)基變量。 3(2) (產(chǎn)銷平衡條件) minjjiba11(3)因?yàn)?, 故必有可行解和
4、最優(yōu)解。 minjijijXCMinZ110 由于上述特點(diǎn),若按單純形法求解必須增加人工變量由于上述特點(diǎn),若按單純形法求解必須增加人工變量,致使計(jì)算量大大增加,故用特殊解法,致使計(jì)算量大大增加,故用特殊解法表上作業(yè)法。表上作業(yè)法。2.表上作業(yè)法表上作業(yè)法 表上作業(yè)法實(shí)質(zhì)上還是單純形法,但具體計(jì)算和術(shù)語上表上作業(yè)法實(shí)質(zhì)上還是單純形法,但具體計(jì)算和術(shù)語上有所不同。其計(jì)算步驟和方法,我們通過對引例的求解過有所不同。其計(jì)算步驟和方法,我們通過對引例的求解過程說明之。程說明之。(1)用最小元素法確定初始方案(即初始基可行解)用最小元素法確定初始方案(即初始基可行解) 切記在產(chǎn)銷平衡表上必須且只能填寫切記
5、在產(chǎn)銷平衡表上必須且只能填寫m+n1個(gè)數(shù)字格個(gè)數(shù)字格 4例18(P37)設(shè)某產(chǎn)品從產(chǎn)地A1,A2,A3運(yùn)往銷地B1,B2,B3,B4,B5,運(yùn)量和單位運(yùn)價(jià)如下表所示,問如何調(diào)運(yùn)才能使總的運(yùn)費(fèi)最少? 銷地 運(yùn)價(jià)產(chǎn)地B1B2B3B4B5產(chǎn)量(萬噸)A171086440A259712640A336581190銷量(萬噸)3040602020解:用最小元素法或伏格爾法求得其初始調(diào)運(yùn)方案如下:解:用最小元素法或伏格爾法求得其初始調(diào)運(yùn)方案如下:5 銷地 運(yùn)價(jià)產(chǎn)地B1B2B3B4B5產(chǎn)量(萬噸)A171086440A259712640A336581190銷量(萬噸)304060202030406020200
6、0接接下來我們就要判別這個(gè)調(diào)運(yùn)方案是否是最優(yōu)調(diào)運(yùn)方案?下來我們就要判別這個(gè)調(diào)運(yùn)方案是否是最優(yōu)調(diào)運(yùn)方案? 判別的方法同線性規(guī)劃一樣,首先求出空格的檢驗(yàn)數(shù),判別的方法同線性規(guī)劃一樣,首先求出空格的檢驗(yàn)數(shù),由于是最小化問題,所以當(dāng)所有空格的檢驗(yàn)數(shù)均小于由于是最小化問題,所以當(dāng)所有空格的檢驗(yàn)數(shù)均小于0時(shí)得時(shí)得到的解為最優(yōu)解。到的解為最優(yōu)解。 求運(yùn)輸問題的空格的檢驗(yàn)數(shù)的方法有閉回路法和位勢求運(yùn)輸問題的空格的檢驗(yàn)數(shù)的方法有閉回路法和位勢法。法。6(2)用閉回路法或位勢法求空格的檢驗(yàn)數(shù))用閉回路法或位勢法求空格的檢驗(yàn)數(shù)1) 用閉回路法求檢驗(yàn)數(shù):用閉回路法求檢驗(yàn)數(shù): 首先,每一個(gè)空格有且僅有一個(gè)閉回路,而圈格
7、無閉回首先,每一個(gè)空格有且僅有一個(gè)閉回路,而圈格無閉回路。路。 閉回路閉回路是以空格為起點(diǎn),沿同一行或同一列前進(jìn),遇上是以空格為起點(diǎn),沿同一行或同一列前進(jìn),遇上圈格可轉(zhuǎn)圈格可轉(zhuǎn)90度繼續(xù)前進(jìn),按此方法進(jìn)行下去,直到回到始度繼續(xù)前進(jìn),按此方法進(jìn)行下去,直到回到始點(diǎn)的一個(gè)封閉折線。點(diǎn)的一個(gè)封閉折線。 以始點(diǎn)為第以始點(diǎn)為第0個(gè)點(diǎn),依次給閉回路上的每一個(gè)頂點(diǎn)編號個(gè)點(diǎn),依次給閉回路上的每一個(gè)頂點(diǎn)編號。其中奇序數(shù)對應(yīng)的為奇頂點(diǎn),偶數(shù)對應(yīng)的為偶頂點(diǎn)。其中奇序數(shù)對應(yīng)的為奇頂點(diǎn),偶數(shù)對應(yīng)的為偶頂點(diǎn)。 其次,其次,每一個(gè)空格的檢驗(yàn)數(shù)每一個(gè)空格的檢驗(yàn)數(shù)=奇頂點(diǎn)運(yùn)費(fèi)之和奇頂點(diǎn)運(yùn)費(fèi)之和 偶頂點(diǎn)偶頂點(diǎn)運(yùn)費(fèi)之和。運(yùn)費(fèi)之和。
8、7 2)用位勢法求出空格的檢驗(yàn)數(shù)并進(jìn)行最優(yōu)解的判別用位勢法求出空格的檢驗(yàn)數(shù)并進(jìn)行最優(yōu)解的判別設(shè)設(shè)u1,u2,um; v1,v2,vn是對應(yīng)運(yùn)輸問題是對應(yīng)運(yùn)輸問題m+n個(gè)約束條件的個(gè)約束條件的對偶變量,對偶變量,B為含有人工變量的初始可行基,由為含有人工變量的初始可行基,由LP問題的問題的對偶理論知:對偶理論知:CBB-1=(u1,u2,um; v1,v2,vn) 而每個(gè)決策變量而每個(gè)決策變量Xij相應(yīng)的系數(shù)向量相應(yīng)的系數(shù)向量Pij=ei+em+j,所以所以CBB-1Pij=ui+vj, 于是,檢驗(yàn)數(shù)于是,檢驗(yàn)數(shù)ij=CBB-1PijCij =(ui+vj)Cij又各基變量的檢驗(yàn)數(shù)為又各基變量的
9、檢驗(yàn)數(shù)為0,故對每個(gè)基變量所在的圈格的檢,故對每個(gè)基變量所在的圈格的檢驗(yàn)數(shù)有驗(yàn)數(shù)有 即有方程組:即有方程組:isjsjsisjijijijiCvuCvuCvu:22221111共m+n個(gè)未知數(shù) s=m+n1個(gè)方程 Cvuijji)(08 顯然上述方程有解,且由于含有一個(gè)自由變量,因此,令 任 一 未 知 數(shù) 為 0 , 就 可 求 出 上 述 方 程 組 的 解(ui1,ui2,uim,vj1,vj2,vjn)稱為位勢解。如用位勢法求引例初始基可行解的檢驗(yàn)數(shù): 銷地 運(yùn)價(jià)產(chǎn)地B1B2B3B4B5vjA17108646A259712612A336581110ui-7-3-50-2-8-7-704
10、12-33040602020009 第一步:將運(yùn)價(jià)表中增加vj和ui列。 第二步:利用圈格分別算出ui和vj,即令u1=0,然后按ui+vj=Cij (i,jJB),相繼確定ui,vj的值。 第三步:按ij= (ui+vj)Cij (i,jJN)算出表中各空格(即非基變量)的檢驗(yàn)數(shù): 由于運(yùn)輸問題的目標(biāo)函數(shù)是求最小化,故判別最優(yōu)解故判別最優(yōu)解的準(zhǔn)則是所有的非基變量的檢驗(yàn)數(shù):的準(zhǔn)則是所有的非基變量的檢驗(yàn)數(shù):ij=CBB-1PijCij0 因?yàn)?5 =+4, 32 =+1, 34 =+2均為正數(shù),所以目前尚未得到最優(yōu)解(其實(shí)只要有一個(gè)正檢驗(yàn)數(shù),所對應(yīng)的方案就不是最優(yōu)方案),尚須改進(jìn)。 方案的調(diào)整(
11、即換基迭代)是在閉回路上進(jìn)行方案的調(diào)整(即換基迭代)是在閉回路上進(jìn)行10 3)在調(diào)運(yùn)平衡表上用閉回路法進(jìn)行調(diào)整,得到新的基可)在調(diào)運(yùn)平衡表上用閉回路法進(jìn)行調(diào)整,得到新的基可行解(新的調(diào)運(yùn)方案)行解(新的調(diào)運(yùn)方案) i) 確定進(jìn)基變量:自上而下,自左向右第一個(gè)正檢驗(yàn)數(shù)相應(yīng)的非基變量(空格)為進(jìn)基變量。 ii) 作閉回路:以進(jìn)基變量空格為出發(fā)點(diǎn),用水平或垂直線向前劃,當(dāng)碰到某一恰當(dāng)數(shù)格轉(zhuǎn)90后,繼續(xù)前進(jìn),直至回到起始空格止。 iii) 確定調(diào)整量=min奇頂點(diǎn)的調(diào)運(yùn)量(即閉回路上奇頂點(diǎn)運(yùn)量的最小值為調(diào)整量) iv) 在閉回路上進(jìn)行調(diào)整:對閉回路上每個(gè)奇頂點(diǎn)的調(diào)運(yùn)對閉回路上每個(gè)奇頂點(diǎn)的調(diào)運(yùn)量量 ,對
12、閉回路上每個(gè)偶頂點(diǎn)(含起始格)的調(diào)運(yùn)量對閉回路上每個(gè)偶頂點(diǎn)(含起始格)的調(diào)運(yùn)量+ 。調(diào)整后,將閉回路中為0的一個(gè)數(shù)格作為空格(即出基變量)。閉回路外的各調(diào)運(yùn)量不變。這樣便得到新的調(diào)運(yùn)方案(新基可行解)11 銷地 運(yùn)價(jià)產(chǎn)地B1B2B3B4B5產(chǎn)量(萬噸)A171086 +04 -040A259712-06 +040A336581190銷量(萬噸)304060202020 B1B2B3B4B5產(chǎn)量(萬噸)A171086440A259712640A336581190銷量(萬噸)3040602020200040306020306040020200124)表上作業(yè)法須注意的問題:)表上作業(yè)法須注意的問題
13、: i) 在最終調(diào)運(yùn)表中,若有某個(gè)空格(非基變量)的檢驗(yàn)數(shù)為0時(shí),則表明該運(yùn)輸問題有多重調(diào)運(yùn)方案; ii) 在確定初始方案時(shí),若某一行的產(chǎn)量與某一列的需求量同時(shí)滿足,這時(shí)也只能劃去一行或一列(絕對不能同時(shí)把行、列劃去,否則就不滿足圈格=m+n1個(gè)的要求,即基變量的個(gè)數(shù)永遠(yuǎn)要保持為m+n1個(gè)); iii) 在用閉回路法調(diào)整時(shí),當(dāng)閉回路上奇頂點(diǎn)有幾個(gè)相同的最小值時(shí),調(diào)整后只能有一個(gè)空格,其余均要保留數(shù)“0”,以保證圈格=m+n1個(gè)的需要。 iv) 用最小元素法所得到的初始方案可以不唯一。13二、產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法1.數(shù)學(xué)模型:數(shù)學(xué)模型: minjjiijXCZ11min),.,2 ,
14、 1,.,2 , 1(0),.,2 , 1(),.,2 , 1(11njmiXnjbXmiaXijmijijnjiijminjjiijXC11min),.,2 , 1,.,2 , 1(0),.,2 , 1(),.,2 , 1(11njmiXnjbXmiaXijmijijnjiijnjjmiiba11產(chǎn)大于銷njjmiiba11銷大于產(chǎn)14然后再用產(chǎn)銷平衡的運(yùn)輸問題的解法進(jìn)行解之。 2.解法思路:解法思路: 將不平衡運(yùn)輸問題轉(zhuǎn)化為平衡運(yùn)輸問題。即當(dāng) 時(shí),考慮在平衡表中增加一虛擬列,表示增加一個(gè)銷貨點(diǎn)(j=n+1)如倉庫,其銷貨量為 ,且各運(yùn)價(jià)Cin+1=0;當(dāng) 時(shí),考慮在平衡表中增加一虛擬行,表
15、示增加一個(gè)新產(chǎn)地,且各運(yùn)價(jià)Cm+1j=0。 njjmiiba11njjmiiba11njjmiiba1115例題19(P45) 三個(gè)電視機(jī)廠供應(yīng)四個(gè)地區(qū)某種型號的電視機(jī),其運(yùn)價(jià)表如下,試求總運(yùn)費(fèi)最少的調(diào)運(yùn)方案?例18 下表是一個(gè)運(yùn)輸問題的單位運(yùn)價(jià)表。 B1B2B3B4產(chǎn)量(萬噸)A11035650A221131270A3781870銷量(萬噸)20304060 比較總產(chǎn)量和總銷量可知,這是一個(gè)非平衡運(yùn)輸問題(屬于產(chǎn)大于銷的情況),為化為平衡運(yùn)輸問題,需虛設(shè)一個(gè)銷點(diǎn)B5,其運(yùn)價(jià)為0,其銷量為40。B50004016 銷地廠家B1B2B3B4產(chǎn)量(萬臺)A16312610A2439 12A3910
16、131010最低需求61405最高需求10146不不限限(12) 銷地廠家B1B1B2B3B4B4產(chǎn)量(萬臺)A1663126610A24439 MM12A3991013101010A4M0M0M1010銷量6414657化為產(chǎn)銷平衡的運(yùn)輸問題有:17三、轉(zhuǎn)運(yùn)問題及其解法三、轉(zhuǎn)運(yùn)問題及其解法1.所謂轉(zhuǎn)運(yùn)問題是在以下背景產(chǎn)生的: (1)每個(gè)工廠生產(chǎn)的產(chǎn)品不直接運(yùn)到銷地,可以幾個(gè)產(chǎn)地集中一起運(yùn)。 (2)運(yùn)往各銷地的物資可先運(yùn)給其中的幾個(gè)銷地,再轉(zhuǎn)運(yùn)給其它銷地。 (3)除產(chǎn)、銷地之外,還可以有幾個(gè)中間轉(zhuǎn)運(yùn)站,在產(chǎn)地之間,銷地之間或產(chǎn)銷地之間轉(zhuǎn)運(yùn)。 凡類似上述情況下的調(diào)運(yùn)物資并使總運(yùn)費(fèi)最小的問題統(tǒng)稱為
17、轉(zhuǎn)運(yùn)問題。2.求解“轉(zhuǎn)運(yùn)問題”的思路是把問題中所有的產(chǎn)地、中轉(zhuǎn)站和銷地都既看作產(chǎn)地,又都看作銷地,把“轉(zhuǎn)運(yùn)問題”變成擴(kuò)大后的產(chǎn)銷平衡的運(yùn)輸問題處理。183.求解“轉(zhuǎn)運(yùn)問題”的方法步驟: (1)建立擴(kuò)大的產(chǎn)銷平衡運(yùn)輸問題單位運(yùn)價(jià)表。其中 1)對兩地不能直接運(yùn)輸?shù)膯挝贿\(yùn)價(jià)定為M(很大的正數(shù)) 3)對產(chǎn)量列的各數(shù)據(jù)可按下式計(jì)算并填入: Ai的產(chǎn)量=ai+,Tj產(chǎn)量=,Bj的產(chǎn)量= 4)對銷量行的各數(shù)據(jù)可按下式計(jì)算并填入: Aj的產(chǎn)量=,Tj銷量=,Bj的銷量=+bj (2)用表上作業(yè)法進(jìn)行求解m1in1jji,maxba2)對所有中轉(zhuǎn)站Tj的產(chǎn)量和銷量定為相等,設(shè)定為19例26(P61)已知甲、乙兩
18、處分別有100噸和85噸同種物質(zhì)外運(yùn),A、B、C三處各需物質(zhì)55,60,70(噸),物質(zhì)可以直接運(yùn)到目的地,也可以經(jīng)某些中轉(zhuǎn)點(diǎn)轉(zhuǎn)運(yùn),已知各處之間的距離如下表所示,試確定一個(gè)最優(yōu)的調(diào)運(yùn)方案。 從 到甲乙甲乙010120從 到ABC甲乙101514121218從 到ABCABC0108140121140從 到甲乙ABC產(chǎn)量甲乙ABC010MMM120MMM1015010814121401212181140285270185185185銷量185185240245255再用表上作業(yè)法進(jìn)行求解。202.7 2.7 線性目標(biāo)規(guī)劃及其解法線性目標(biāo)規(guī)劃及其解法 前面的線性規(guī)劃問題都是處理單個(gè)目標(biāo)的情況,但是
19、在現(xiàn)實(shí)世界中有許多問題具有多個(gè)目標(biāo),這些目標(biāo)的重要性各不相同,往往有不同的量綱,有的目標(biāo)相互依賴,例如決策者既希望實(shí)現(xiàn)利潤最大,又希望實(shí)現(xiàn)產(chǎn)值最大;有的相互抵觸,如決策者既希望充分利用資源,又不希望超越資源限量。而決策者希望在某些限制條件下,依次實(shí)現(xiàn)這些目標(biāo)。這就是目標(biāo)規(guī)劃所要解決的問題。當(dāng)所有的目標(biāo)函數(shù)和約束條件都是線性時(shí),我們稱其為線性目標(biāo)規(guī)劃問題。在這里我們主要討論線性目標(biāo)規(guī)劃問題。1、目標(biāo)規(guī)劃模型的建立 21引例: 對于生產(chǎn)計(jì)劃問題: 甲 乙 資源限額 材料 2 3 24 工時(shí) 3 2 26 單位利潤 4 3 現(xiàn)在工廠領(lǐng)導(dǎo)要考慮市場等一系列其他因素,提出如下目標(biāo):(1)根據(jù)市場信息,甲
20、產(chǎn)品的銷量有下降的趨勢,而乙產(chǎn)品的銷量有上升的趨勢,故考慮乙產(chǎn)品的產(chǎn)量應(yīng)大于甲產(chǎn)品的產(chǎn)量。(2)盡可能充分利用工時(shí),不希望加班。(3)應(yīng)盡可能達(dá)到并超過計(jì)劃利潤30元?,F(xiàn)在的問題是:在原材料不能超計(jì)劃使用的前提下,如何安排生產(chǎn)才能使上述目標(biāo)依次實(shí)現(xiàn)?22解:(1)決策變量:仍設(shè)每天生產(chǎn)甲、乙兩種產(chǎn)品各為x1和x2 偏差變量:對于每一目標(biāo),我們引進(jìn)正、負(fù)偏差變量。 如對于目標(biāo)1,設(shè)d1-表示乙產(chǎn)品的產(chǎn)量低于甲產(chǎn)品產(chǎn)量的數(shù),d1+表示乙產(chǎn)品的產(chǎn)量高于甲產(chǎn)品產(chǎn)量的數(shù)。稱它們分別為產(chǎn)量比較的負(fù)偏差變量和正偏差變量。則對于目標(biāo)1,可將它表示為等式約束的形式 -x1+x2+ d1- d1+ =0 (目標(biāo)約
21、束) 同樣設(shè)d2-和d2+分別表示安排生產(chǎn)時(shí),低于可利用工時(shí)和高于可利用工時(shí),即加班工時(shí)的偏差變量,則對目標(biāo)2,有 -3x1+2x2+ d2-d2+ =26 對于目標(biāo)3,設(shè)d3-和d3+分別表示安排生產(chǎn)時(shí),低于計(jì)劃利潤30元和高于計(jì)劃利潤30元的偏差變量,有: 23 4x1+3x2+ d3-d3+ =30 (2)約束條件:有資源約束和目標(biāo)約束 資源約束:2x1+3x224 目標(biāo)約束:為上述各目標(biāo)中得出的約束 (3)目標(biāo)函數(shù):三個(gè)目標(biāo)依次為: minZ1=d1- ,minZ2=d2+d2- ,minZ3=d3- 因而該問題的數(shù)學(xué)模型可表述如下: minZ1=d1- ,minZ2=d2+d2-,m
22、inZ3=d3- 2x1+3x224 st -x1+x2+ d1- d1+ =0 -3x1+2x2+ d2-d2+ =26 4x1+3x2+ d3-d3+ =30 24 例20(提級加新問題) 某公司的員工工資有四級,根據(jù)公司的業(yè)務(wù)發(fā)展情況,準(zhǔn)備招收部分新員工,并將部分員工的工資提升一級。該公司的員工工資及提級前后的編制表如下,其中提級后編制是計(jì)劃編制,允許有變化,其中1級員工中有8%要退休。公司領(lǐng)導(dǎo)的目標(biāo)如下:(1)提級后在職員工的工資總額不超過550千元;(2)各級員工不要超過定編人數(shù);(3)為調(diào)動積極性,各級員工的升級面不少于現(xiàn)有人數(shù)的18%;(4)總提級面不大于20%,但盡可能多提;(
23、5)4級不足編制人數(shù)可錄用新工人。 25問:應(yīng)如何擬定一具滿意的方案,才能接近上述目標(biāo)? 級別1234工資(千元)8643現(xiàn)有員工數(shù)10204030編制員工數(shù)10225230解:(1)決策變量:設(shè)x1,x2,x3,x4分別表示提升到1,2,3級和新錄用的員工數(shù)。 偏差變量:為各目標(biāo)的正、負(fù)偏差變量。 (2)約束條件:1) 提級后在職員工的工資總額不超過550千元;8(10-108%+x1)+6(20-x1+x2)+4(40-x2+x3)+3(30-x3+x4)+d1-d1+=550 26 2)各級員工不要超過定編人數(shù)1級有: 10-10 8%+x1+d2-d2+=10 2級有: 20-x1+
24、x2+d3-d3+=22 3級有: 40-x2+ x3+d4-d4+=52 4級有: 30-x3+ x4+d5-d5+=303)各級員工的升級面不少于現(xiàn)有人數(shù)的18%對2級有: x1+d6-d6+=22 18%對3級有: x2+d7-d7+=40 18% 對4級有: x3+d8-d8+=30 18% 4)總提級面人數(shù)不大于20%,但盡可能多提 x1+ x2+ x3+d9-d9+=100 20% 27(3)目標(biāo)函數(shù): minZ1=d1+minZ2=d2+d3+ d4+ d5+minZ3=d6-+ d7-+ d8-minZ4=d9+ d9-目標(biāo)規(guī)劃的一般模型見書本P48 二、目標(biāo)規(guī)劃的解法二、目標(biāo)
25、規(guī)劃的解法 由于目標(biāo)規(guī)劃有多個(gè)目標(biāo),各個(gè)目標(biāo)又有相對不同的重要性,求解時(shí)是首先滿足重要性權(quán)數(shù)大的目標(biāo),再滿足重要性權(quán)數(shù)次大的目標(biāo),所以并不能保證所有的目標(biāo)都能達(dá)到,所求的解也不一定是最優(yōu)解,而只能求出滿意解。 28求解目標(biāo)規(guī)劃有圖解法和單純形法,在這里我們主要介紹單純形法。 求解目標(biāo)規(guī)劃的單純形法與線性規(guī)劃的單純形法原理基本一致,只是此時(shí)檢驗(yàn)數(shù)行不再是一行,而是變化為一個(gè)檢驗(yàn)數(shù)矩陣。 例1 例20 用單純形法求解如下線性目標(biāo)規(guī)劃模型 minZ1=d1-,minZ2=d2+d2-,minZ3=d3- 2x1+3x224 加入松馳變量化為標(biāo)準(zhǔn)形 2x1+3x2+ x3=24 st -x1+x2+
26、d1- d1+ =0 -3x1+2x2+ d2-d2+ =26 4x1+3x2+ d3-d3+ =30 解:取x3,d1-,d2-,d3-為基變量,建立初始單純形表 29-1-2-1123-13402630Z1Z2Z3000-100-100-10000010010010010003 1 232-1342402630 x3d1-d2-d3-d3+d2+d1+d3-d2-d1-x3x2x1bXB迭代的步驟完全與線性規(guī)劃的單純形法一樣。滿意解的判定:檢驗(yàn)數(shù)矩陣的每一列從上至下第一個(gè)非零元為負(fù)數(shù),則解為滿意解。迭代的最優(yōu)表如下: 30-2-1-1-11-1020Z1Z2Z3100000-106/5-2
27、/5-13/5-10000010-6/52/51-3/57/51/5-11/50100000118/524/5224/5d3+x2d2-x1d3+d2+d1+d3-d2-d1-x3x2x1bXB因而滿意解為:x1=24/5,x2=24/5,d2-=2,d3+=18/5 其中第一、三目標(biāo)已達(dá)到最優(yōu),第二個(gè)目標(biāo)未達(dá)最優(yōu)。目標(biāo)利潤 Z=4x1+3x2=168/5312.8 2.8 評價(jià)相對有效性的評價(jià)相對有效性的DEA模型模型 DEA模型(也稱數(shù)據(jù)包絡(luò)分析)最早由美國運(yùn)籌學(xué)家 A.Charnes等人于1978年提出,在中國最早由中國人民大學(xué)的魏權(quán)齡教授于1985向國內(nèi)介紹。 DEA是對其決策單元(同
28、類型的企業(yè)或部門)的投入規(guī)模、技術(shù)有效性作出評價(jià),即對各同類型的企業(yè)投入一定數(shù)量的資金、勞動力等資源后,其產(chǎn)出的效益(經(jīng)濟(jì)效益和社會效益)作一個(gè)相對有效性評價(jià)。 例如:區(qū)域可持續(xù)發(fā)展的DEA評價(jià)、企業(yè)營銷效果的DEA評價(jià)、企業(yè)競爭能力的DEA評價(jià)等。為了說明DEA模型的建模思路,我們看下面的例子:32 例1: 某公司有甲、乙、丙三個(gè)企業(yè),為評價(jià)這幾個(gè)企業(yè)的生產(chǎn)效率,收集到反映其投入(固定資產(chǎn)年凈值x1、流動資金x2、職工人數(shù)x3)和產(chǎn)出(總產(chǎn)值y1、利稅總額y2)的有關(guān)數(shù)據(jù)如下表 企業(yè)指標(biāo)甲乙丙x1(萬元)41527x2 (萬元)1545x3 (萬元)825y1 (萬元)602224y2 (萬
29、元)1268 由于投入指標(biāo)和產(chǎn)出指標(biāo)都不止一個(gè),故通常采用加權(quán)的辦法來綜合投入指標(biāo)值和產(chǎn)出指標(biāo)值。 33對于第一個(gè)企業(yè),產(chǎn)出綜合值為對于第一個(gè)企業(yè),產(chǎn)出綜合值為60u1+12u2,投入綜合值投入綜合值4v1+15v2+8v3,其中其中u1 u2 v1 v2 v3分別為產(chǎn)出與投入的權(quán)重系分別為產(chǎn)出與投入的權(quán)重系數(shù)。數(shù)。我們定義第一個(gè)企業(yè)的生產(chǎn)效率為:我們定義第一個(gè)企業(yè)的生產(chǎn)效率為:總產(chǎn)出與總投入的比總產(chǎn)出與總投入的比即即vvvuuh32121181541260類似,可知第二、第三個(gè)企業(yè)的生產(chǎn)效率分別為:類似,可知第二、第三個(gè)企業(yè)的生產(chǎn)效率分別為:vvvuuh3212122415622vvvuuh
30、452782432121334我們限定所有的我們限定所有的hj值不超過值不超過1,即,即 ,這意味著,這意味著,若第若第k個(gè)企業(yè)個(gè)企業(yè)hk=1,則該企業(yè)相對于其他企業(yè)來說生產(chǎn)率最則該企業(yè)相對于其他企業(yè)來說生產(chǎn)率最高,或者說這一生產(chǎn)系統(tǒng)是相對有效的,若高,或者說這一生產(chǎn)系統(tǒng)是相對有效的,若hk1,那么該那么該企業(yè)相對于其他企業(yè)來說,生產(chǎn)效率還有待于提高,或者企業(yè)相對于其他企業(yè)來說,生產(chǎn)效率還有待于提高,或者說這一生產(chǎn)系統(tǒng)還不是有效的。說這一生產(chǎn)系統(tǒng)還不是有效的。1maxhj即即vvvuuh32121181541260max12415622321212vvvuuh14527824321213vvv
31、uuh因此,建立第一個(gè)企業(yè)的生產(chǎn)效率最高的優(yōu)化模型如下:因此,建立第一個(gè)企業(yè)的生產(chǎn)效率最高的優(yōu)化模型如下:這是一個(gè)分式規(guī)劃,需要這是一個(gè)分式規(guī)劃,需要將它化為線性規(guī)劃才能求將它化為線性規(guī)劃才能求解。解。35設(shè)設(shè)vvvt3218154vtwutiiii,則此則此分式規(guī)劃可化為如下的分式規(guī)劃可化為如下的線性規(guī)劃線性規(guī)劃1w8w15w4w4w5w27824w2w4w15622w8w15w41260. t . s1260hmax321321213212132121211其其對偶對偶問題為問題為128612602422608428155415427154. t . sVmin32132132132132
32、1Dvvvuuh32121181541260max12415622321212vvvuuh14527824321213vvvuuh1v8v15v4u12u60h32121136 設(shè)vi為第i個(gè)指標(biāo)xi的權(quán)重,ur為第r個(gè)產(chǎn)出yr指標(biāo)的權(quán)重,則第j個(gè)企業(yè)投入的綜合值為 ,產(chǎn)出的綜合值為 其生產(chǎn)效率定義為: 于是問題實(shí)際上是確定一組最佳的權(quán)變量v1,v2,v3和u1,u2,使第j個(gè)企業(yè)的效率值hj最大。這個(gè)最大的效率評價(jià)值是該企業(yè)相對于其他企業(yè)來說不可能更高的相對效率評價(jià)值。 xvij31iiyurj21rr31iiji21rrjrjxvyuh 我們限定所有的hj值(j=1,2,3)不超過1,即m
33、axhj1。這意味著,若第k個(gè)企業(yè)hk=1,則該企業(yè)相對于其他企業(yè)來說生產(chǎn)率最高,或者說這一系統(tǒng)是相對而言有效的;若hk1,那么該企業(yè)相對于其他企業(yè)來說,生產(chǎn)率還有待于提高,或者說這一生產(chǎn)系統(tǒng)還不是有效的。 37 根據(jù)上述分析,可以建立確定任何一個(gè)企業(yè)(如第3 個(gè)企業(yè)即丙企業(yè))的相對生產(chǎn)率最優(yōu)化模型如下: 3 , 2 , 1i , 0, 2 , 1r , 03 , 2 , 1j , 1. t . sHmaxvuhhirj31、評價(jià)決策單元技術(shù)和規(guī)模綜合效率的、評價(jià)決策單元技術(shù)和規(guī)模綜合效率的C2R模型模型 設(shè)有n個(gè)同類型的企業(yè)(也稱決策單元),對于每個(gè)企業(yè)都有m種類型的“輸入”(表示該單元對“
34、資源”的消耗)以及p種類型的“輸出”(表示該單元在消耗了“資源”之后的產(chǎn)出)。 這n個(gè)企業(yè)及其輸入-輸出關(guān)系如下: 38:y1ny2n:ypny1jy2j:ypj:y12y22:yp2y11y21:yp1u1u2:up12:p輸出x1nx2n:xmnx1jx2j:xmj:x12x22:xm2x11x21:xm1v1v2:vm12:m輸入nj21 部門指標(biāo) 權(quán)數(shù)每個(gè)決策單元的效率評價(jià)指數(shù)為: m1iijip1rrjrjxvyuhj=1,2,n39而第j0個(gè)決策單元的相對效率優(yōu)化評價(jià)模型為: 上述模型中xij,yrj為已知數(shù)(可由歷史資料或預(yù)測數(shù)據(jù)得到),vi,ur為變量。模型的含義是以權(quán)系數(shù)vi
35、,ur為變量,以所有決策單元的效率指標(biāo)hj為約束,以第j0個(gè)決策單元的效率指數(shù)為目標(biāo)。即評價(jià)第j0個(gè)決策單元的生產(chǎn)效率是否有效,是相對于其他所有決策單元而言的。 m1i0ijip1r0rjr0jxvyuhmax s.t. vi,ur0, i=1,2,m; r=1,2,p n,.,2 , 1j , 1m1iijip1rrjrxvyu(1)40 這是一個(gè)分式規(guī)劃模型,我們必須將它化為線性規(guī)劃模型才能求解。為此,令 m1i0ijixv1tvwiiturrt則模型(1)轉(zhuǎn)化為: p,.,2 , 1r;m,.2 , 1i, 0,1n,.,2 , 1j, 0. t . swxwxwyyhmaxir0ijm
36、1iip1rm1iijirjrp1r0rjr0 j(2)41其對偶問題為: 無約束,0p,.,2, 1r ,m,.,2, 1i ,. t . sminjn1j0rrjjn1j0iijjDyyxxv(3)寫成向量形式有:, 0, 0, 0jn1j0jj0jn1jjssysyxsxs.t.無約束(4) min42設(shè)問題(4)的最優(yōu)解為*,s*-,s*+,*,則有如下結(jié)論: (1)若*=1,則DMUj0為弱DEA有效(總體)。(2)若*=1,且s*-=0,s*+=0,則DMUj0為DEA有效(總體)(3)令 0=*x0- s*-, 0=y0- s*+,則為在有效前沿面上的投影,相對于原來的n個(gè)DMU
37、是有效(總體)的。 x y x y (4)若存在j*(j=1,2,m),使 =1成立,則DMUj0為規(guī)模效益不變;若不存在j*(j=1,2,m),使 =1成立,則 1 DMUj0為規(guī)模效益遞減。 n1j*jn1j*jn1j*jn1j*jn1j*j43評價(jià)第j0決策單元DMU純技術(shù)效率C2GS2模型為: min 0, 0ssysyxsxn1j0jj0jn1jj1n1j*j0js.t.j=1,2,n無約束(5) 該模型計(jì)算出的DMU效率是純技術(shù)效率,反映DMU的純技術(shù)效率狀況,稱為純技術(shù)效率。設(shè)問題(2)的最優(yōu)解為*,s*-,s*+,*,則有如下對結(jié)論: 44(1)若*=1,則DMUj0為弱DEA
38、有效(純技術(shù))。(2)若*=1,且s*-=0,s*+=0,則DMUj0為DEA有效(純技術(shù))。評價(jià)第j0決策單元DMU純規(guī)模效率模型為: *s(6) 根據(jù)DEA的理論,總體效率*、純技術(shù)效率*、純規(guī)模效率s*三個(gè)參數(shù)之間存在(6)式所述的關(guān)系,由(6)可直接計(jì)算DMU的純規(guī)模效率。 45P63例例28 以以1997年全部獨(dú)立核算企業(yè)為對象年全部獨(dú)立核算企業(yè)為對象,對安徽、江西對安徽、江西、湖南和湖北四省進(jìn)行生產(chǎn)水平的比較。投入要素取固定、湖南和湖北四省進(jìn)行生產(chǎn)水平的比較。投入要素取固定資產(chǎn)凈值年平均余額資產(chǎn)凈值年平均余額(億元億元),流動資金年平均余額及從業(yè)人流動資金年平均余額及從業(yè)人員員(萬
39、人萬人),產(chǎn)出要素取總產(chǎn)值產(chǎn)出要素取總產(chǎn)值(億元億元)和利稅總額和利稅總額(億元億元).安徽安徽江西江西湖南湖南湖北湖北固定資產(chǎn)固定資產(chǎn)932.66583.08936.841306.56流動資金流動資金980.45581.64849.311444.30從業(yè)人員從業(yè)人員401.8294.2443.20461.00利稅總額利稅總額179.2949.76144.20181.41總產(chǎn)值總產(chǎn)值2196.09930.221659.042662.21全全要素相對生產(chǎn)率要素相對生產(chǎn)率(即即DEA評價(jià)值評價(jià)值)1.0000.71400.92851.000排序排序1321461. 建立評價(jià)湖南省的建立評價(jià)湖南省的
40、DEA模型如下模型如下 無約束無約束, 004.1659s21.266204.165922.93009.219620.144s410.18120.144760.4929.17920.443s000.46120.44320.24980.40131.849s40.144431.84964.58145.98084.936s56.130684.93608.58366.932. t . sVminj2432114321343212432114321D求解求解結(jié)果為結(jié)果為:24.107s, 0s,17.88s, 0s,71.119s, 0,8043. 0,9285. 0213214321 調(diào)整方案為調(diào)整方
41、案為:輸入調(diào)整前輸入調(diào)整前輸入調(diào)整后輸入調(diào)整后輸出調(diào)整前輸出調(diào)整前輸出調(diào)整后輸出調(diào)整后936.84936.84*0.9285-119.71=750.15144.20144.20849.31849.31*0.9285=788.581659.041659.04+107.24=1766.28443.20443.2*0.9285-88.17=323.3447第二章 整數(shù)線性規(guī)劃問題及其解法 在上一章討論的LP問題中,對決策變量只限于不能取負(fù)值的連續(xù)型數(shù)值,即可以是正分?jǐn)?shù)或正小數(shù)。然而在許多經(jīng)濟(jì)管理的實(shí)際問題中,決策變量只有非負(fù)整數(shù)才有實(shí)際意義。對求整數(shù)最優(yōu)解的問題,稱為整數(shù)規(guī)劃(Integer Pro
42、gramming)(簡記為IP)。又稱約束條件和函數(shù)均為線性的IP為整數(shù)線性規(guī)劃(Integer Linear Programming)(簡記為ILP)。根據(jù)變量取整數(shù)的情況根據(jù)變量取整數(shù)的情況,將整數(shù)規(guī)劃分為將整數(shù)規(guī)劃分為:(1)純整數(shù)規(guī)劃,所有變量都取整數(shù))純整數(shù)規(guī)劃,所有變量都取整數(shù).(2)混合整數(shù)規(guī)劃,一部分變量取整數(shù))混合整數(shù)規(guī)劃,一部分變量取整數(shù),一部分變量取實(shí)數(shù)一部分變量取實(shí)數(shù)(3)0-1整數(shù)規(guī)劃整數(shù)規(guī)劃 ,所有變量均取所有變量均取0或或1求解整數(shù)規(guī)劃常用的算法有分枝定界法、割平面法求解整數(shù)規(guī)劃常用的算法有分枝定界法、割平面法,求解求解0-1的還有隱枚舉法、匈牙利法。的還有隱枚舉
43、法、匈牙利法。48一、整數(shù)線性規(guī)劃模型的建立一、整數(shù)線性規(guī)劃模型的建立例題例題2 P72 某單位有某單位有5個(gè)擬選擇的投資項(xiàng)目,其所需投資個(gè)擬選擇的投資項(xiàng)目,其所需投資額與期望收益如下表。由于各項(xiàng)目之間有一定聯(lián)系,額與期望收益如下表。由于各項(xiàng)目之間有一定聯(lián)系,A、C、E之間必須選擇一項(xiàng)且僅需選擇一項(xiàng);之間必須選擇一項(xiàng)且僅需選擇一項(xiàng);B和和D之間需選之間需選擇也僅需選擇一項(xiàng);又由于擇也僅需選擇一項(xiàng);又由于C和和D兩項(xiàng)目密切相關(guān),兩項(xiàng)目密切相關(guān),C的實(shí)的實(shí)施必須以施必須以D的實(shí)施為前提條件,該單位共籌集資金的實(shí)施為前提條件,該單位共籌集資金15萬元萬元,問應(yīng)該選擇哪些項(xiàng)目投資,使期望收益最大?,問
44、應(yīng)該選擇哪些項(xiàng)目投資,使期望收益最大?項(xiàng)目所需投資額(萬元)期望收益(萬元)A610B48C27D46E5949解:決策變量:設(shè))5 , 4 , 3 , 2 , 1j (j1j0 xj被選中表示項(xiàng)目不被選中表示項(xiàng)目目標(biāo)函數(shù):期望收益最大xxxxx54321967810zmax約束條件:投資額限制條件 6x1+4x2+2x3+4x4+5x515項(xiàng)目A、C、E之間必須且只需選擇一項(xiàng):x1+x3+x5=1項(xiàng)目C的實(shí)施要以項(xiàng)目D的實(shí)施為前提條件: x3 x4項(xiàng)目B、D之間必須且只需選擇一項(xiàng):x2+x4=1歸納起來,其數(shù)學(xué)模型為:10111554246967810zmaxxxxxxxxxxxxxxxxx
45、xxj43423215432154321或50由此,ILP問題數(shù)學(xué)模型的一般形式為:求一組變量X1,X2,Xn,使 n1jjjXCMaxZ數(shù)且皆為整數(shù)或部分為整, 0Xj)m, 2 , 1i (bXat . sn1jiijij此例還表明,利用0-1變量處理一類“可供選擇條件”的問題非常簡明方便。下面再進(jìn)一步分別說明對0-1變量的應(yīng)用。假定現(xiàn)有m種資源對可供選擇的n個(gè)項(xiàng)目進(jìn)行投資的數(shù)學(xué)模型為:求一組決策變量X1,X2,Xn,使 njjjXCZ1max), 2 , 1(10), 2 , 1(1njXmibXajnjijij或(3.1)(3.2)(3.3)511.對可供項(xiàng)目的選擇 (1)如果在可供選
46、擇的前k(kn)個(gè)項(xiàng)目中,必須且只能選擇一項(xiàng),則在(3.2)中加入新的約束條件:kjjX11(2)如果可供選擇的k(kn)個(gè)項(xiàng)目是相互排斥的,則在(3.2)中加入新的約束條件:kjjX11同時(shí)它還表示在第k個(gè)項(xiàng)目中至多只能選擇一項(xiàng)投資。 (3)如果在可供選擇的k(kn)個(gè)項(xiàng)目中,至少應(yīng)選擇一項(xiàng)投資,則在(3.2)中加入新的約束條件:kjjX1152(4)如果項(xiàng)目j的投資必須以項(xiàng)目i的投資為前提,則可在(3.2)中加入新的約束條件: XjXi (5)如果項(xiàng)目i與項(xiàng)目j要么同時(shí)被選中,要么同時(shí)不被選中,則在(3.2)中加入新的約束條件:Xj=Xi (ij) 2.對可供資源的選擇 (1)如果對第r種
47、資源br與第t種資源bt的投資是相互排斥的,即只允許對資源br與bt中的一種進(jìn)行投資,則可將(3.2)的第r個(gè)和第t個(gè)約束條件改寫為: 53 njrjrjyMbXa1njtjtjMybXa1)1 ( 其中y為新引進(jìn)的0-1變量,M為充分大正數(shù)。易見,當(dāng)y=0時(shí),式就是原來的第r個(gè)約束條件,具有約束作用。此時(shí)對式而言,無論Xj為何值都成立,毫無約束作用,這就使問題僅允許第r種資源進(jìn)行投資。當(dāng)y=1時(shí),式對Xj起了約束作用,而式成了多余的條件。到底是滿足還是,則視問題在求出最優(yōu)解后,y為0還是1而定。54(2)如果問題是要求在前m個(gè)約束條件中至少滿足k(1k0,則令則令xj=1-yj3)如果約束條
48、件是如果約束條件是“ ”形,則可兩邊乘形,則可兩邊乘-1,改為,改為“ ”形形;4)若某個(gè)約束條件為)若某個(gè)約束條件為“=”形,則化為兩個(gè)形,則化為兩個(gè)“ ”的不等的不等式式,如如n1jijijn1jijijn1jijijbxabxabxa可化成63(3)隱枚舉法的基本思想 見P83例1、用隱枚舉法求解下列0-1規(guī)劃)5.,2, 1j(100242645723. t . s4352zmaxxxxxxxxxxxxxxxxxj543215432154321或解:令x1=1-y1,x3=1-y3,x5=1-y5,x2=y2,x4=y4化為規(guī)范形得:64)5.,2, 1j(105242845723.
49、t . s435211zmaxyyyyyyyyyyyyyyyyj543215432154321或其求解過程如下圖所示:y4=0y5=101234567810911121314Z=11y3=1y3=0y4=1y5=1y5=0y2=1y2=0y4=0y4=1y5=0y1=0y1=1可行解z=3可行解z=1可行解z=2不可行子域不可行子域可行解z=6可行解z=2不可行子域由此可知,最優(yōu)解為x3=x4=x5=1,x1=x2=0,maxz=665三三. . 指派問題及其解法指派問題及其解法 任務(wù) 人員 E J G R 甲 3 14 10 5 乙 10 4 12 10 丙 9 14 15 13 丁 7 8
50、 11 9 解:設(shè)Xij表示第i人從事第j項(xiàng)工作,且 01jiX因此,該問題的數(shù)學(xué)模型為當(dāng)指派第i人去完成第j項(xiàng)工作否則 引例:假設(shè)有4個(gè)人去完成4項(xiàng)任務(wù),每個(gè)人由于技術(shù)、專長不同,完成任務(wù)的時(shí)間如下表,且規(guī)定每人只能做一項(xiàng)工作,每項(xiàng)工作只能由一人完成,問應(yīng)如何分配任務(wù)使總費(fèi)用最?。?6MinZ=3X11+14X12+10X13+5X14+10X21+4X22+12X23+10X24 +9X31+14X32+15X33+13X34+7X41+8X42+11X43+9X44 111144342414433323134232221241312111XXXXXXXXXXXXXXXX表示第j項(xiàng)工作只指
51、派1人完成 111144434241343332312423222114131211XXXXXXXXXXXXXXXX表示第i人被指派完成一項(xiàng)工作 Xij=0或1(i,j=1,2,3,4) 67 諸如此類,有n項(xiàng)任務(wù),恰好有n個(gè)人可承擔(dān)這些任務(wù),但由于每人的技術(shù)專長不同,完成任務(wù)的效率(所費(fèi)時(shí)間不同,為使完成n項(xiàng)任務(wù)的總效率最高(即所需總時(shí)間最少),應(yīng)如何指派(分派)人員的問題統(tǒng)稱為指派(分派)問題。一、指派問題的數(shù)學(xué)模型及其特點(diǎn)一、指派問題的數(shù)學(xué)模型及其特點(diǎn)1.數(shù)學(xué)模型: ninjijijijCXCMinZ11)0(),.,2, 1(10),.,2, 1(1),.,2, 1(111nijXni
52、XnjXijnjijniij或682.特點(diǎn) (1)給定一個(gè)指派問題時(shí),必須給出效率矩陣(系數(shù)矩陣)C=(Cij)nxn,且Cij0,因此必有最優(yōu)解( )。 ninjijijXCMinZ110(2)指派問題是一種特殊的平衡運(yùn)輸問題,由于模型結(jié)構(gòu)的特殊性(看作每個(gè)產(chǎn)地的產(chǎn)量均為1,每個(gè)銷地的銷量均為1),故可用更為簡便的匈牙利算法進(jìn)行求解。二、指派問題的解法二、指派問題的解法匈牙利法匈牙利法 匈牙利法是求解指派問題的一種好算法,它只能求解目標(biāo)函數(shù)為最小化的情況,它由匈牙利數(shù)學(xué)家柯尼格(D.Konig)提出,因此而得名。69 1.匈牙利法的基本思想是:對同一項(xiàng)工作(任務(wù))j來說,同時(shí)提高或降低每人相
53、同的效率(常數(shù)ti),不影響其最優(yōu)指派;同樣,對同一個(gè)人i來說,完成各項(xiàng)工作的效率都提高或降低相同的效率(常數(shù)di),也不影響其最優(yōu)指派,因此可得到新的效率矩陣(bij)nxn,其中 bij=Cij+ti+dj (對所有的i,j)則新的目標(biāo)函數(shù)為ninjijijXbZ11ninjijjiijXdtC11)( ninjninjniijjnjijiijijXdXtXC111111)()()(11ninjjidtZ其中ninjjidt11為常數(shù)70 這說明Z與Z同時(shí)達(dá)到最小值。因而最優(yōu)解相同。故指派問題有以下性質(zhì): 若從效率矩陣(Cij)nxn的一行(列)各元素中分別減去該行(列)的最小元素,得到的
54、新效率矩陣(bij)nxn不改變原指派問題的最優(yōu)解。 2.匈牙利法的計(jì)算步驟見P88-89三、關(guān)于求最大化的指派問題71 對于求最大化的指派問題(即求 ),可采用構(gòu)造新的效率矩陣(MCij)nxn,其中M=maxCij,(顯然MCij0),將其轉(zhuǎn)化為 ninjijijXCMaxZ11ninjijijXCMZMin11)( 求所得到的最優(yōu)解就是原問題的最優(yōu)解。事實(shí)上 由于nM為常數(shù),因此,使Z取得最小的最優(yōu)解就是使Z取得最大的最優(yōu)解。 ijninjijninjijninjijijXCXMXCMZ111111)(ZnMXCnMijninjij11724.以上討論的指派問題是效率矩陣的行數(shù)等于列數(shù),
55、即m+n的情況。當(dāng)mn時(shí),則可用增加虛設(shè)的零元數(shù)行(列)使效率矩陣變成方陣后,再用匈牙利法求解。 5.指派問題必有最優(yōu)解,但可以不唯一。 n-m行000000,2111211mnmmnCCCCCC當(dāng)mn時(shí)73第四章第四章 動態(tài)規(guī)劃動態(tài)規(guī)劃(Dynamic Programming) 動態(tài)規(guī)劃是動態(tài)規(guī)劃是1951年由美國數(shù)學(xué)家貝爾曼(年由美國數(shù)學(xué)家貝爾曼(Richard Bellman)提出,它是解決一類多階段決策問題的優(yōu)化方法,提出,它是解決一類多階段決策問題的優(yōu)化方法,也是考察問題的一種途徑,而不是一種算法(如也是考察問題的一種途徑,而不是一種算法(如LP單純形法單純形法)。因此它不象)。因此
56、它不象LP那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則,而必須對具體問題進(jìn)行具體分析處理。的一組規(guī)則,而必須對具體問題進(jìn)行具體分析處理。 動態(tài)規(guī)劃方法是現(xiàn)代企業(yè)管理中的一種重要決策方法。如動態(tài)規(guī)劃方法是現(xiàn)代企業(yè)管理中的一種重要決策方法。如果一個(gè)問題可將其過程劃分為若干個(gè)相互聯(lián)系的階段問題,果一個(gè)問題可將其過程劃分為若干個(gè)相互聯(lián)系的階段問題,且它的每一階段都需進(jìn)行決策,則這類問題均可用動態(tài)規(guī)劃且它的每一階段都需進(jìn)行決策,則這類問題均可用動態(tài)規(guī)劃方法進(jìn)行求解。方法進(jìn)行求解。 根據(jù)多階段決策過程的時(shí)序和決策過程的演變,動態(tài)規(guī)劃根據(jù)多階段決策過程的時(shí)序和決策過程的
57、演變,動態(tài)規(guī)劃方法有以下四種類型:離散確定型、離散隨機(jī)型、連續(xù)確定方法有以下四種類型:離散確定型、離散隨機(jī)型、連續(xù)確定型和連續(xù)隨機(jī)型型和連續(xù)隨機(jī)型。返回741動態(tài)規(guī)劃的基本概念和最優(yōu)化原理一、引例(最短路問題)一、引例(最短路問題) 假如上圖是一個(gè)線路網(wǎng)絡(luò),兩點(diǎn)之間連線上的數(shù)字表示假如上圖是一個(gè)線路網(wǎng)絡(luò),兩點(diǎn)之間連線上的數(shù)字表示兩點(diǎn)間的距離(或費(fèi)用),我們的問題是要將貨物從兩點(diǎn)間的距離(或費(fèi)用),我們的問題是要將貨物從A地運(yùn)地運(yùn)往往E地,中間通過地,中間通過B、C、D三個(gè)區(qū)域,在區(qū)域內(nèi)有多條路徑三個(gè)區(qū)域,在區(qū)域內(nèi)有多條路徑可走,現(xiàn)求一條由可走,現(xiàn)求一條由A到到E的線路,使總距離最短(或總費(fèi)用的
58、線路,使總距離最短(或總費(fèi)用最?。W钚。?。AB1B2B3C1C2C3D1D2E2437463242653463333475 將該問題劃分為將該問題劃分為4個(gè)階段的決策問題,即第一階段為從個(gè)階段的決策問題,即第一階段為從A到到Bj(j=1,2,3),),有三種決策方案可供選擇;第二階段有三種決策方案可供選擇;第二階段為從為從Bj到到Cj(j=1,2,3),),也有三種方案可供選擇;第三階也有三種方案可供選擇;第三階段為從段為從Cj到到Dj(j=1,2),有兩種方案可供選擇;第四階段為有兩種方案可供選擇;第四階段為從從Dj到到E,只有一種方案選擇。如果用完全枚舉法,則可只有一種方案選擇。如果用完
59、全枚舉法,則可供選擇的路線有供選擇的路線有3321=18(條),將其一一比較才(條),將其一一比較才可找出最短路線:可找出最短路線:AB1C2D3E 其長度為其長度為12。 顯然,這種方法是不經(jīng)濟(jì)的,特別是當(dāng)階段數(shù)很多,各顯然,這種方法是不經(jīng)濟(jì)的,特別是當(dāng)階段數(shù)很多,各階段可供的選擇也很多時(shí),這種解法甚至在計(jì)算機(jī)上完成階段可供的選擇也很多時(shí),這種解法甚至在計(jì)算機(jī)上完成也是不現(xiàn)實(shí)的。也是不現(xiàn)實(shí)的。 由于我們考慮的是從全局上解決求由于我們考慮的是從全局上解決求A到到E的最短路問題的最短路問題,而不是就某一階段解決最短路線,因此可考慮從最后一,而不是就某一階段解決最短路線,因此可考慮從最后一階段開始
60、計(jì)算,由后向前逐步推至階段開始計(jì)算,由后向前逐步推至A點(diǎn):點(diǎn):76第四階段,由第四階段,由D1到到E只有一條路線,其長度只有一條路線,其長度f4(D1)=3,同理同理f4(D2)=4。 第三階段,由第三階段,由Cj到到Di分別均有兩種選擇,即分別均有兩種選擇,即64433minDfDCDfDCminCf2421141113,決策點(diǎn)為D1643*33minDfDCDfDCminCf2423141333,決策點(diǎn)為D17*4336minDfDCDfDCminCf2422141223,決策點(diǎn)為D277第二階段,由Bj到Cj分別均有三種選擇,即: 11667467minCfCBCfCBCfCBminBf
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年家長與學(xué)校共同打造學(xué)生成長檔案合同3篇
- 醫(yī)療設(shè)備售后服務(wù)與客戶關(guān)系維護(hù)
- 在線辦公時(shí)代下的農(nóng)產(chǎn)品直銷新模式-以網(wǎng)絡(luò)直播為例
- 醫(yī)療倫理與患者溝通的藝術(shù)
- 2025中國鐵塔貴州分公司招聘32人高頻重點(diǎn)提升(共500題)附帶答案詳解
- 2025中國石化貴州貴陽石油分公司加油站營業(yè)員招聘45人高頻重點(diǎn)提升(共500題)附帶答案詳解
- 2025中國電信集團(tuán)限公司春季校園招聘高頻重點(diǎn)提升(共500題)附帶答案詳解
- 2025中國大唐集團(tuán)限公司福建分公司校招高頻重點(diǎn)提升(共500題)附帶答案詳解
- 2025中國農(nóng)業(yè)科學(xué)院農(nóng)產(chǎn)品加工研究所谷物加工與品質(zhì)調(diào)控創(chuàng)新團(tuán)隊(duì)博士后公開招聘3人高頻重點(diǎn)提升(共500題)附帶答案詳解
- 2025東方電氣招聘452人歷年高頻重點(diǎn)提升(共500題)附帶答案詳解
- 深基坑事故案例
- 誡勉談話檢討書3篇
- 行車時(shí)遇突發(fā)故障的應(yīng)急辦法演示
- 倉儲管理員高級工題庫及參考答案
- XX公司學(xué)歷、職稱、技能工資補(bǔ)貼規(guī)定
- 川省成都市2022屆高二上學(xué)期期末考試:英語
- 消防安全操作規(guī)程
- 廣東省江門市2022-2023學(xué)年高一上學(xué)期期末調(diào)研考試物理試題(一)
- 蘇州市蘇教版五年級下冊數(shù)學(xué)第三單元第12課《因數(shù)和倍數(shù)整理練習(xí)(第2課時(shí))》課件
- GB/T 19929-2014土方機(jī)械履帶式機(jī)器制動系統(tǒng)的性能要求和試驗(yàn)方法
- GB 2714-2015食品安全國家標(biāo)準(zhǔn)醬腌菜
評論
0/150
提交評論