




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、1多目標(biāo)規(guī)劃模型多目標(biāo)規(guī)劃模型 在現(xiàn)實(shí)生活中在現(xiàn)實(shí)生活中,決策的目標(biāo)往往有多個(gè)決策的目標(biāo)往往有多個(gè),例如例如,對企業(yè)產(chǎn)品的生產(chǎn)管對企業(yè)產(chǎn)品的生產(chǎn)管理理,既希望達(dá)到高利潤既希望達(dá)到高利潤,又希望優(yōu)質(zhì)和低消耗又希望優(yōu)質(zhì)和低消耗,還希望減少對環(huán)境的污還希望減少對環(huán)境的污染等染等.這就是一個(gè)多目標(biāo)決策的問題這就是一個(gè)多目標(biāo)決策的問題.又如選購一個(gè)好的計(jì)算機(jī)系統(tǒng)又如選購一個(gè)好的計(jì)算機(jī)系統(tǒng),似乎只有一個(gè)目標(biāo)似乎只有一個(gè)目標(biāo),但由于要從多方面去反映但由于要從多方面去反映,要用多個(gè)不同的準(zhǔn)則要用多個(gè)不同的準(zhǔn)則來衡量來衡量,比如比如,性能要好性能要好,維護(hù)要容易維護(hù)要容易,費(fèi)用要省費(fèi)用要省.這些準(zhǔn)則自然構(gòu)成了多
2、這些準(zhǔn)則自然構(gòu)成了多個(gè)目標(biāo)個(gè)目標(biāo),故也是一個(gè)多目標(biāo)決策問題故也是一個(gè)多目標(biāo)決策問題.矛盾性、不可公度性。矛盾性、不可公度性。一般來說一般來說,多目標(biāo)決策問題有兩類多目標(biāo)決策問題有兩類.一類是多目標(biāo)規(guī)劃問題一類是多目標(biāo)規(guī)劃問題,其對其對象是在管理決策過程中求解使多個(gè)目標(biāo)象是在管理決策過程中求解使多個(gè)目標(biāo)都達(dá)到都達(dá)到滿意結(jié)果的最優(yōu)方案滿意結(jié)果的最優(yōu)方案.另一類是多目標(biāo)優(yōu)選問題另一類是多目標(biāo)優(yōu)選問題,其對象是在管理決策過程中根據(jù)多個(gè)目標(biāo)其對象是在管理決策過程中根據(jù)多個(gè)目標(biāo)或多個(gè)準(zhǔn)則衡量和得出各種備選方案的或多個(gè)準(zhǔn)則衡量和得出各種備選方案的優(yōu)先等級與排序優(yōu)先等級與排序. 多目標(biāo)決策由于考慮的目標(biāo)多多目
3、標(biāo)決策由于考慮的目標(biāo)多,有些目標(biāo)之間又有些目標(biāo)之間又彼此有矛盾彼此有矛盾,這就使多目標(biāo)問題成為一個(gè)復(fù)雜而困難這就使多目標(biāo)問題成為一個(gè)復(fù)雜而困難的問題的問題.但由于客觀實(shí)際的需要但由于客觀實(shí)際的需要,多目標(biāo)決策問題越來多目標(biāo)決策問題越來越受到重視越受到重視,因而出現(xiàn)了許多解決此決策問題的方法因而出現(xiàn)了許多解決此決策問題的方法.一般來說一般來說,其基本途徑是其基本途徑是,把求解多目標(biāo)問題把求解多目標(biāo)問題轉(zhuǎn)化為求轉(zhuǎn)化為求解單目標(biāo)問題解單目標(biāo)問題.其主要步驟是其主要步驟是,先轉(zhuǎn)化為單目標(biāo)問題先轉(zhuǎn)化為單目標(biāo)問題,然后利用單目標(biāo)模型的方法然后利用單目標(biāo)模型的方法,求出單目標(biāo)模型的最優(yōu)求出單目標(biāo)模型的最優(yōu)解
4、解,以此作為多目標(biāo)問題的解以此作為多目標(biāo)問題的解. 化多目標(biāo)問題為單目標(biāo)問題的方法大致可分為兩化多目標(biāo)問題為單目標(biāo)問題的方法大致可分為兩類類,一類是轉(zhuǎn)化為一個(gè)單目標(biāo)問題一類是轉(zhuǎn)化為一個(gè)單目標(biāo)問題,另一類是轉(zhuǎn)化為多另一類是轉(zhuǎn)化為多個(gè)單目標(biāo)問題個(gè)單目標(biāo)問題,關(guān)鍵是如何轉(zhuǎn)化關(guān)鍵是如何轉(zhuǎn)化. 下面下面,我們介紹幾種主要的轉(zhuǎn)化方法我們介紹幾種主要的轉(zhuǎn)化方法:主要目標(biāo)法、主要目標(biāo)法、線性加權(quán)和法、字典序法、步驟法。線性加權(quán)和法、字典序法、步驟法。f1f21234567810.1多目標(biāo)決策問題的特征多目標(biāo)決策問題的特征 在解決單目標(biāo)問題時(shí),我們的任務(wù)是選擇一個(gè)或一組變在解決單目標(biāo)問題時(shí),我們的任務(wù)是選擇一個(gè)
5、或一組變量量X,使目標(biāo)函數(shù)使目標(biāo)函數(shù)f(X)取得最大(或最?。?。對于任意兩方案取得最大(或最?。?。對于任意兩方案所對應(yīng)的解,只要比較它們相應(yīng)的目標(biāo)值,就可以判斷誰優(yōu)所對應(yīng)的解,只要比較它們相應(yīng)的目標(biāo)值,就可以判斷誰優(yōu)誰劣。但在多目標(biāo)情況下,問題卻不那么單純了。例如,有誰劣。但在多目標(biāo)情況下,問題卻不那么單純了。例如,有兩個(gè)目標(biāo)兩個(gè)目標(biāo)f1(X),f2(X),希望它們都越大越好。下圖列出在這兩希望它們都越大越好。下圖列出在這兩個(gè)目標(biāo)下共有個(gè)目標(biāo)下共有8個(gè)解的方案。其中方案個(gè)解的方案。其中方案1,2,3,4稱為劣解,稱為劣解,因?yàn)樗鼈冊趦蓚€(gè)目標(biāo)值上都比方案因?yàn)樗鼈冊趦蓚€(gè)目標(biāo)值上都比方案5差,是可以
6、淘汰的解。而差,是可以淘汰的解。而方案方案5,6,7,8是非劣解(或稱為有效解,滿意解),因?yàn)槭欠橇咏猓ɑ蚍Q為有效解,滿意解),因?yàn)檫@些解都不能輕易被淘汰掉,它們中間的一個(gè)與其余任何一這些解都不能輕易被淘汰掉,它們中間的一個(gè)與其余任何一個(gè)相比,總有一個(gè)指標(biāo)更優(yōu)越,而另一個(gè)指標(biāo)卻更差。個(gè)相比,總有一個(gè)指標(biāo)更優(yōu)越,而另一個(gè)指標(biāo)卻更差。一、解的特點(diǎn)一、解的特點(diǎn)二、模型結(jié)構(gòu)二、模型結(jié)構(gòu) 多目標(biāo)決策問題包含有三大要素:目標(biāo)、方案和決策者。多目標(biāo)決策問題包含有三大要素:目標(biāo)、方案和決策者。在多目標(biāo)決策問題中,目標(biāo)有多層次的含義。從最高層次在多目標(biāo)決策問題中,目標(biāo)有多層次的含義。從最高層次來看,目標(biāo)代表了問
7、題要達(dá)到的總目標(biāo)。如確定最滿意的來看,目標(biāo)代表了問題要達(dá)到的總目標(biāo)。如確定最滿意的投資項(xiàng)目、選擇最滿意的食品。從較低層次來看,目標(biāo)可投資項(xiàng)目、選擇最滿意的食品。從較低層次來看,目標(biāo)可看成是體現(xiàn)總目標(biāo)得以實(shí)現(xiàn)的各個(gè)具體的目標(biāo),如投資項(xiàng)看成是體現(xiàn)總目標(biāo)得以實(shí)現(xiàn)的各個(gè)具體的目標(biāo),如投資項(xiàng)目的盈利要大、成本要低、風(fēng)險(xiǎn)要?。荒繕?biāo)也可看成衡量目的盈利要大、成本要低、風(fēng)險(xiǎn)要?。荒繕?biāo)也可看成衡量總目標(biāo)得以實(shí)現(xiàn)的各個(gè)準(zhǔn)則,如食品的味道要好,質(zhì)量要總目標(biāo)得以實(shí)現(xiàn)的各個(gè)準(zhǔn)則,如食品的味道要好,質(zhì)量要好,花費(fèi)要少。好,花費(fèi)要少。 多目標(biāo)決策問題中的方案即為決策變量,也稱為多目多目標(biāo)決策問題中的方案即為決策變量,也稱為
8、多目標(biāo)問題的解。備選方案即決策問題的可行解。在多目標(biāo)決標(biāo)問題的解。備選方案即決策問題的可行解。在多目標(biāo)決策中,有些問題的方案是有限的,有些問題策中,有些問題的方案是有限的,有些問題 的方案是無限的方案是無限的。方案有其特征或特性,稱之為屬性。的。方案有其特征或特性,稱之為屬性。1、多目標(biāo)規(guī)劃問題的模型結(jié)構(gòu)0)(0)(. .)(),.,(),()(21XhXgtsXfXfXfXoptFjiTp),.,(21nxxxX 為決策變量如對于求極大(max)型,其各種解定義如下:絕對最優(yōu)解:若對于任意的X,都有F(X*)F(X)有效解:若不存在X,使得F(X*) F(X)弱有效解:若不存在X,使得F(X
9、*)F(X)2、多目標(biāo)優(yōu)選問題的模型結(jié)構(gòu) 可用效用函數(shù)來表示。設(shè)方案的效用是目標(biāo)屬性的函數(shù):),.,()(21pfffUxU并設(shè))(jiijxfa 且各個(gè)方案的效用函數(shù)分別為),.,()(21pjjjjaaaUxU則多目標(biāo)優(yōu)選模型的結(jié)構(gòu)可表示如下:0)(0)(. .)(),.,(),()(21XhXgtsXUXUXUXordUjiTp10.2 多目標(biāo)規(guī)劃問題的求解多目標(biāo)規(guī)劃問題的求解1、主要目標(biāo)法、主要目標(biāo)法 在有些多目標(biāo)決策問題中,各種目標(biāo)的重要性程度往往不一樣。其中一個(gè)重要性程度最高和最為關(guān)鍵的目標(biāo),稱之為主要目標(biāo)法。其余的目標(biāo)則稱為非主要目標(biāo)。0)(0)(. .)(),.,(),()(2
10、1XhXgtsXfXfXfXoptFjiTp例如,在上述多目標(biāo)問題中,假定f1(X)為主要目標(biāo),其余p-1個(gè)為非主要目標(biāo)。這時(shí),希望主要目標(biāo)達(dá)到極大值,并要求其余的目標(biāo)滿足一定的條件,即1,.,2 , 1,)(,.,2 , 1, 0)(,.,2 , 1, 0)(. .)(max1pkXfmjXhniXgtsXfkkji例題例題1 某工廠在一個(gè)計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品,各產(chǎn)品某工廠在一個(gè)計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品,各產(chǎn)品都要消耗都要消耗A,B,C三種不同的資源。每件產(chǎn)品對資源的單位三種不同的資源。每件產(chǎn)品對資源的單位消耗、各種資源的限量以及各產(chǎn)品的單位價(jià)格、單位利潤和消耗、各種資源的限量以及各
11、產(chǎn)品的單位價(jià)格、單位利潤和所造成的單位污染如下表。假定產(chǎn)品能全部銷售出去,問每所造成的單位污染如下表。假定產(chǎn)品能全部銷售出去,問每期怎樣安排生產(chǎn),才能使利潤和產(chǎn)值都最大,且造成的污染期怎樣安排生產(chǎn),才能使利潤和產(chǎn)值都最大,且造成的污染最???最???解:問題的多目標(biāo)模型如下0,300103200542404923)(max(600400)(max12070)(max21212121213212211xxxxxxxxxxXfxxXfxxXf對于上述模型的三個(gè)目標(biāo),工廠確定利潤最大為主要目標(biāo)。另兩個(gè)目標(biāo)則通過預(yù)測預(yù)先給定的希望達(dá)到的目標(biāo)值轉(zhuǎn)化為約束條件。經(jīng)研究,工廠認(rèn)為總產(chǎn)值至少應(yīng)達(dá)到20000個(gè)單位
12、,而污染控制在90個(gè)單位以下,即9023)(20000600400)(213212xxXfxxXf由主要目標(biāo)法化為單目標(biāo)問題0,300103200542404990232000060040012070)(max212121212121211xxxxxxxxxxxxxxXf用單純形法求得其最優(yōu)解為90)(,20750)(,4025)(,25.26, 5 .1232121xfxfxfxx2、線性加權(quán)和目標(biāo)規(guī)劃、線性加權(quán)和目標(biāo)規(guī)劃0)(0)(. .)(),.,(),()(21XhXgtsXfXfXfXoptFjiTp在上述目標(biāo)規(guī)劃中,假定f1(X),f2(X),fp(X)具有相同的量綱,按照一定的規(guī)
13、則分別給fi賦予相同的權(quán)系數(shù)i,作線性加權(quán)和評價(jià)函數(shù)piiiXfXU1)()(則多目標(biāo)問題化為如下的單目標(biāo)問題0)(0)(. .)()(max1XhXgtsXfXUjipiii例如,某公司計(jì)劃購進(jìn)一批新卡車,可供選擇的卡車有如例如,某公司計(jì)劃購進(jìn)一批新卡車,可供選擇的卡車有如下下4種類型:種類型:A1,A2,A3,A4?,F(xiàn)考慮現(xiàn)考慮6個(gè)方案屬性:維個(gè)方案屬性:維修期限修期限f1,每每100升汽油所跑的里數(shù)升汽油所跑的里數(shù)f2,最大載重噸數(shù)最大載重噸數(shù)f3,價(jià)價(jià)格(萬元)格(萬元)f4,可靠性可靠性f5,靈敏性靈敏性f6。這這4種型號的卡車分別種型號的卡車分別關(guān)于目標(biāo)屬性的指標(biāo)值關(guān)于目標(biāo)屬性的指
14、標(biāo)值fij如下表所示。如下表所示。首先對不同度量單位和不同數(shù)量級的指標(biāo)值進(jìn)行標(biāo)準(zhǔn)化處理。首先對不同度量單位和不同數(shù)量級的指標(biāo)值進(jìn)行標(biāo)準(zhǔn)化處理。先將定性指標(biāo)定量化:先將定性指標(biāo)定量化:可靠性和靈敏性都屬于效益型指標(biāo),其打分如下按以下公式作無量綱的標(biāo)準(zhǔn)化處理1*)*(99jjjijijffffa其中:ijijijijffffminmax*變換后的指標(biāo)值矩陣為:設(shè)權(quán)系數(shù)向量為W=(0.2,0.1,0.1,0.1,0.2,0.3),則925.57)(max*27.40)(925.57)(6 .40)(34)(36144613361226111XUUUaXUaXUaXUaXUjjjjjjjjjjjj故最
15、優(yōu)方案為選購A3型卡車3、分層序列法:、分層序列法:1.基本步驟:把(VP)中的p個(gè)目標(biāo) 按其重要程度排序。依次求單目標(biāo)規(guī)劃的最優(yōu)解。2. 過程:無妨設(shè)其次序?yàn)?先求解 得最優(yōu)值 ,記再解 得最優(yōu)值 ,依次進(jìn)行,直到 得最優(yōu)值則 是在分層序列意義下的最優(yōu)解集合。)(,),(1xfxfppfff,21SxtsxfP. .)(min)(11*1fSfxfxS*111)(122. .)(min)(SxtsxfP*2f1*222)(SfxfxS1. .)(min)(pppSxtsxfP*pf1*)(ppppSfxfxS3. 性質(zhì): ,即在分層序列意義下的最優(yōu)解是有效解。證明:反證。設(shè) ,但 ,則必存在
16、 使 即至少有一個(gè)j0 ,使 , 由于 ,即 , 矛盾。得證。4. 進(jìn)一步討論: 上述方法過程中,當(dāng)某個(gè)問題(Pj)的解唯一時(shí),則問題 的求解無意義,因?yàn)榻舛际俏ㄒ坏摹?實(shí)際求解時(shí),有較寬容意義下的分層序列法: 取 為預(yù)先給定的寬容值,整個(gè)解法同原方法類似,只是取各約束集合時(shí),分別取為:pjPP,10, 011ppjSfxfxSjjjj, 3 , 2,)(1*)(min)(0000*xffxfjSxjjj0jSx)()(00 xfyfjj1, 1),()(0jjxfyfjj)()(xFyFSy *paSxpSx *papSS 4、步驟法(、步驟法(STEM法)法) 這是一種交互方法,其求解過程
17、通過分析者與決策者之間的對話逐步進(jìn)行,故稱步驟法。 步驟法的基本思想是,首先需要求出原多目標(biāo)問題的一組理想解(f1*,f2*,fp*)。實(shí)際上,這些解fi*(i=1,2,p)無法同時(shí)達(dá)到,但可以當(dāng)作一組理想的最優(yōu)值。以理想解作為一個(gè)標(biāo)準(zhǔn),可以估計(jì)有效解,然后通過對話,不斷修改目標(biāo)值,并把降低要求的目標(biāo)作為新的約束條件加入原來的約束條件中去重新計(jì)算,直到?jīng)Q策者得到滿意的解。 步驟法算法如下:第一步:分別求解以下p個(gè)單目標(biāo)問題的最優(yōu)解0)(0)(. .)(max1XhXgtsxcXfjinjjiji得到最優(yōu)解 ,其相應(yīng)的目標(biāo)值 即為理想值,此最優(yōu)解處別的目標(biāo)所取的值用 表示,即 ,把上述計(jì)算結(jié)果列
18、入下表).,2 , 1(*piXi).,2 , 1(*pifikizpkikXfzikki,.,2 , 1,),(*21*21*11211*121pipppppiiiiipipifzzzXzfzzXzzzfXffffX在表中,確定每一列的最小值并記第i列的最小值為fip(i=1,2,p)第二步:求解0,.,2 , 1,)(*(minSXpiXffiii其中:piiii1這里0*,*0*,*2/1122/112injijpiipiinjijipiiifcffffcfff(1)第三步:將上述模型(1)的解X0與相應(yīng)的目標(biāo)值f1(X0), f2(X0), ,fp(X0) 交給決策者去判斷。決策者把這
19、些目標(biāo)值與理想值進(jìn)行比較后,如果認(rèn)為其中某些目標(biāo)值太壞,另一些目標(biāo)值可以不要那么太好,可以把比較好的目標(biāo)值中的某一個(gè)修改得差一些,以使水平太壞的目標(biāo)得到改善。 當(dāng)決策者減少了第j個(gè)目標(biāo)的值 之后,約束條件S應(yīng)該改為S*jfpijiXfXfkjfXfXfSSiijjj,.,2 , 1,),()(,.,2 , 1,)()(*00在進(jìn)行下一次迭代時(shí),對應(yīng)于降低了要求的那些目標(biāo)fj(j=1,2,k)的權(quán)系數(shù)i應(yīng)該設(shè)為0。這種迭代繼續(xù)下去,直到?jīng)Q策者滿意為止。例題:例題:某公司考慮生產(chǎn)兩種光電太陽能電池:產(chǎn)品甲和產(chǎn)品乙。這種生產(chǎn)過程會(huì)在空氣中引起放射性污染。因此,公司經(jīng)理有兩個(gè)目標(biāo):極大化利潤與極小化總
20、的放射性污染。已知在一個(gè)生產(chǎn)周期內(nèi),每單位甲產(chǎn)品的收益是1元,每單位乙產(chǎn)品的收益是3元。而放射性污染的數(shù)量,每單位甲產(chǎn)品是1.5個(gè)單位,每單位乙產(chǎn)品是1個(gè)單位.由于機(jī)器能力(小時(shí))、裝配能力(人時(shí))和可用的原材料(單位)的限制,約束條件是)(725)(42 . 02 . 0)(825. 05 . 0212121原材料裝配能力機(jī)器能力xxxxxx目標(biāo)有兩個(gè):一是利潤最大,二是污染最小.該問題的多目標(biāo)規(guī)劃模型如下:)(725)(42 . 02 . 0)(825. 05 . 05 . 1)(,3)()(),()(max21212121221121原材料裝配能力機(jī)器能力xxxxxxxxXfxxXfXf
21、XfXFT解:首先,分別求解兩個(gè)單目標(biāo)問題的最優(yōu)解,由它們得到的目標(biāo)函數(shù)值組成理想解.)(725)(42 . 02 . 0)(825. 05 . 03)(max212121211原材料裝配能力機(jī)器能力xxxxxxxxXf)(725)(42 . 02 . 0)(825. 05 . 05 . 1)(max212121212原材料裝配能力機(jī)器能力xxxxxxxxXf46*)13, 7(1*1fX0*)0 , 0(1*2fX由此,構(gòu)造支付表由此計(jì)算兩個(gè)目標(biāo)與理想值偏離的權(quán)重637. 0,363. 0,555. 0,316. 02121解下列線性規(guī)劃問題:0,7254)2 . 02 . 08)25. 0
22、5 . 0)230(637. 0)346(363. 0min212121212121xxxxxxxxxxxx由此求得,064. 7,192.21,064. 7, 02121ffxx分析者把計(jì)算結(jié)果交給決策者,決策者將目標(biāo)值與理想值(21.192,-7.064)與理想值(46,0)比較,如果認(rèn)為f2是滿意的,但利潤太低,并認(rèn)為污染可接受到10個(gè)單位.于是,約束集修改成0,192.213105 . 17254)2 . 02 . 08)25. 05 . 0212121212121xxxxxxxxxxxx進(jìn)行下一輪迭代.首先設(shè)2=0,并計(jì)算得1=1.將模型修改為0,7254)2 . 02 . 08)2
23、5. 05 . 0192.21310)5 . 1346min21212121212121xxxxxxxxxxxxxx由此求得:10,3010, 02121ffxx決策者把這一結(jié)果與前一輪的解及理想值作比較,認(rèn)為兩個(gè)目標(biāo)值都比較滿意,則迭代結(jié)束. 目標(biāo)規(guī)劃模型目標(biāo)規(guī)劃模型 線性規(guī)劃問題都是處理單個(gè)目標(biāo)的情況,但是在現(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ī)劃所要解決的問題
24、。當(dāng)所有的目標(biāo)函數(shù)和約束條件都是線性時(shí),我們稱其為線性目標(biāo)規(guī)劃問題。在這里我們主要討論線性目標(biāo)規(guī)劃問題。一、目標(biāo)規(guī)劃模型的建立一、目標(biāo)規(guī)劃模型的建立 引例引例1: 對于生產(chǎn)計(jì)劃問題: 甲 乙 資源限額 材料 2 3 24 工時(shí) 3 2 26 單位利潤 4 3 現(xiàn)在工廠領(lǐng)導(dǎo)要考慮市場等一系列其他因素,提出如下目標(biāo):(1)根據(jù)市場信息,甲產(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)?解:(1)決策
25、變量:仍設(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)約束) 同樣設(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元的偏差變量,有: 4x1+
26、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-,minZ3=d3- 2x1+3x224 st -x1+x2+ d1- d1+ =0 3x1+2x2+ d2-d2+ =26 4x1+3x2+ d3-d3+ =30 案例案例2(提級加新問題)(提級加新問題) 某公司的員工工資有四級,根據(jù)公司的業(yè)務(wù)發(fā)展情況,準(zhǔn)備招收部分新員工,并
27、將部分員工的工資提升一級。該公司的員工工資及提級前后的編制表如下,其中提級后編制是計(jì)劃編制,允許有變化,其中1級員工中有8%要退休。公司領(lǐng)導(dǎo)的目標(biāo)如下:(1)提級后在職員工的工資總額不超過550千元;(2)各級員工不要超過定編人數(shù);(3)為調(diào)動(dòng)積極性,各級員工的升級面不少于現(xiàn)有人數(shù)的18%;(4)總提級面不大于20%,但盡可能多提;(5)4級不足編制人數(shù)可錄用新工人。 問:應(yīng)如何擬定一具滿意的方案,才能接近上述目標(biāo)? 解:(1)決策變量:設(shè)x1,x2,x3,x4分別表示提升到1,2,3級和新錄用的員工數(shù)。 偏差變量:為各目標(biāo)的正、負(fù)偏差變量。 (2)約束條件:1) 提級后在職員工的工資總額不超
28、過550千元;8(10-108%+x1)+6(20-x1+x2)+4(40-x2+x3)+3(30-x3+x4)+d1-d1+=550 2)各級員工不要超過定編人數(shù)1級有: 10-10 8%+x1+d2-d2+=10 2級有: 20-x1+ 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+=20 18%對3級有: x2+d7-d7+=40 18% 對4級有: x3+d8-d8+=30 18% 4)總提級面人數(shù)不大于20%,但盡可能多提 x1+ x2
29、+ x3+d9-d9+=100 20% (3)目標(biāo)函數(shù):minZ1=d1+minZ2=d2+d3+ d4+ d5+minZ3=d6-+ d7-+ d8-minZ4=d9+ d9-案例案例3 有三個(gè)產(chǎn)地向四個(gè)銷地供應(yīng)物資。產(chǎn)地有三個(gè)產(chǎn)地向四個(gè)銷地供應(yīng)物資。產(chǎn)地Ai(i=1,2,3)的供應(yīng)量的供應(yīng)量ai、銷地銷地Bj(j=1,2,3,4)的需要量的需要量bj、各產(chǎn)銷地之間各產(chǎn)銷地之間的單位物資運(yùn)費(fèi)的單位物資運(yùn)費(fèi)Cij如表如表2所示。表中,所示。表中,ai和和bj的單位為噸的單位為噸,Cij的單位為元的單位為元/噸。編制調(diào)運(yùn)方案時(shí)要求按照相應(yīng)的優(yōu)噸。編制調(diào)運(yùn)方案時(shí)要求按照相應(yīng)的優(yōu)先級依次考慮下列七個(gè)
30、目標(biāo):先級依次考慮下列七個(gè)目標(biāo):P1:B4是重點(diǎn)保證單位,其需要量應(yīng)盡可能全部滿足;是重點(diǎn)保證單位,其需要量應(yīng)盡可能全部滿足;P2:A3向向B1提供的物資不少于提供的物資不少于100噸;噸;P3:每個(gè)銷地得到的物資數(shù)量不少于其需要量的每個(gè)銷地得到的物資數(shù)量不少于其需要量的80%; P4:實(shí)際的總運(yùn)費(fèi)不超過當(dāng)不考慮實(shí)際的總運(yùn)費(fèi)不超過當(dāng)不考慮P1至至P6各目標(biāo)時(shí)的最小各目標(biāo)時(shí)的最小總運(yùn)費(fèi)的總運(yùn)費(fèi)的110%,這里的最小總費(fèi)用利用第三大題中第,這里的最小總費(fèi)用利用第三大題中第2小題小題求出的結(jié)果;求出的結(jié)果;P5:因路況原因,盡量避免安排因路況原因,盡量避免安排A2的物資運(yùn)往的物資運(yùn)往B4;P6:對對
31、B1和和B3的供應(yīng)率要盡可能相同;的供應(yīng)率要盡可能相同;P7:力求使總運(yùn)費(fèi)最省。力求使總運(yùn)費(fèi)最省。試建立該問題的運(yùn)籌學(xué)模型。試建立該問題的運(yùn)籌學(xué)模型。 解:用表上作業(yè)法可求得不考慮解:用表上作業(yè)法可求得不考慮P1至至P6各目標(biāo)時(shí)的最小運(yùn)各目標(biāo)時(shí)的最小運(yùn)費(fèi)調(diào)運(yùn)方案,相應(yīng)的最小運(yùn)費(fèi)為費(fèi)調(diào)運(yùn)方案,相應(yīng)的最小運(yùn)費(fèi)為2950元元(1)決策變量:設(shè))決策變量:設(shè)Ai運(yùn)往運(yùn)往Bj的物資為的物資為xij噸噸(2)約束條件:)約束條件: 3141998833231331211177243141665533231344322212333121112231113424143433323124232221141312
32、1129500)(450200)(0324536080160100250400200300ijijijijijijddxcddxxxxxxddxddxcddxxxddxxxddxxxddxddxxxxxxxxxxxxxxx產(chǎn)量約束產(chǎn)量約束B4銷量要滿足銷量要滿足銷量銷量80%的限制的限制供應(yīng)率盡可能相同供應(yīng)率盡可能相同二、目標(biāo)規(guī)劃的解法二、目標(biāo)規(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)解,而只能求出滿意解。 (3)目標(biāo)函數(shù))目標(biāo)函數(shù)dZddZdZdZd
33、ddZdZdZ97886756454332211minminminminminminmin 求解目標(biāo)規(guī)劃的仍用單純形法,但是與線性規(guī)劃的單純求解目標(biāo)規(guī)劃的仍用單純形法,但是與線性規(guī)劃的單純形法不同的是,此時(shí)檢驗(yàn)數(shù)行不再是一行,而是變化為一形法不同的是,此時(shí)檢驗(yàn)數(shù)行不再是一行,而是變化為一個(gè)檢驗(yàn)數(shù)矩陣。個(gè)檢驗(yàn)數(shù)矩陣。 例例4 用單純形法求解如下線性目標(biāo)規(guī)劃模型 minZ1=d1-,minZ2=d2+d2-,minZ3=d3- 2x1+3x224 加入松馳變量化為標(biāo)準(zhǔn)形 2x1+3x2+ x3=24 st -x1+x2+ d1- d1+ =0 3x1+2x2+ d2-d2+ =26 4x1+3x2
34、+ d3-d3+ =30 解 (1)取x3,d1-,d2-,d3-為基變量,建立初始單純形表 -1-2-1123-13402630Z1Z2Z3000-100-100-10000010010010010003 1 232-1342402630 x3d1-d2-d3-d3+d2+d1+d3-d2-d1-x3x2x1bXB迭代的步驟完全與線性規(guī)劃的單純形法一樣。(2)滿意解的判定:檢驗(yàn)數(shù)矩陣的每一列從上至下第一個(gè)非零元為負(fù)數(shù),則解為滿意解。迭代的最優(yōu)表如下: -2-1-1-11-1020Z1Z2Z3100000-106/5-2/5-13/5-10000010-6/52/51-3/57/51/5-11
35、/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/541層次分析法層次分析法一、層次分析法的基本原理一、層次分析法的基本原理 層次分析法,又稱AHP(Analytic Hirrarchy Process)方法,是美國運(yùn)籌學(xué)家薩蒂(T.Saaty)提出的一種多目標(biāo)、多準(zhǔn)則的決策分析方法。該方法被廣泛應(yīng)用于工程、經(jīng)濟(jì)、軍事、政治、外交等領(lǐng)域,解決了諸如系統(tǒng)評價(jià)、資源分配
36、、價(jià)格預(yù)測、項(xiàng)目選擇等許多重要問題,是一種定量分析與定性分析相結(jié)合的有效方法。用層次分析法作決策分析,首先要把問題層次化。根據(jù)問題的性質(zhì)和要達(dá)到的總目標(biāo),將問題分解為不同的組成因素,并按照因素間的相互影響以及隸屬關(guān)系按不同層次聚集組合,形成一個(gè)多層次的分析結(jié)構(gòu)模型。最終把系統(tǒng)分析歸結(jié)為最低層(如決策方案)相對于最高層(總目標(biāo))的相對重要性權(quán)值的確定或相對優(yōu)劣次序的排序問題,從而為決策方案的選擇提供依據(jù)。 層次分析法大體分為六個(gè)步驟層次分析法大體分為六個(gè)步驟1)明確問題:為了運(yùn)用AHP進(jìn)行系統(tǒng)分析,首先要對問題有明確的認(rèn)識,弄清問題范圍、所包含的因素及其相互關(guān)系、解決問題的目的、是否具有AHP所
37、描述的特征。2)建立層次結(jié)構(gòu)模型:將問題中所包含的因素劃分為不同層次。例如,對于決策問題,通??梢詣澐譃橄旅鎺讉€(gè)層次:最高層:表示解決問題的目的,稱為目標(biāo)層。中間層:表示采取某種措施或政策實(shí)現(xiàn)預(yù)定目標(biāo)的涉及的中間環(huán)節(jié),一般又分為策略層、準(zhǔn)則層等。最低層:表示解決問題的措施或方案,稱為措施層或方案層。如下圖所示。決策目標(biāo)準(zhǔn)則1準(zhǔn)則1準(zhǔn)則m子準(zhǔn)則1子準(zhǔn)則2子準(zhǔn)則k方案1方案2方案n目標(biāo)層目標(biāo)層準(zhǔn)則層準(zhǔn)則層子準(zhǔn)則層子準(zhǔn)則層方案層方案層3)構(gòu)造判斷矩陣針對上一層某元素,對每一層次各個(gè)元素的相對重要性進(jìn)行兩兩比較,并給出判斷。這些判斷用數(shù)值表示出來,寫成矩陣形式,即所謂的判斷矩陣。nnnnnnnnkbb
38、bBbbbBbbbBBBA2122221211211121B其中bij表示對于Ak而言,Bi對Bj的相對重要性,通常bij取1,2,9及它們的倒數(shù),其含義為:它們之間的數(shù)2,4,6,8及各數(shù)的倒數(shù)有相應(yīng)的類似意義。顯然,對判斷矩陣有).,2 , 1,( , 1,1njibbbiijiij因此,對于n階判斷矩陣,我們僅需對n(n-1)/2個(gè)元素給出數(shù)值。4)層次單排序及其一致性檢驗(yàn) 所謂層次單排序,即把同一層次相應(yīng)元素對于上一層次某元素相對重要性的排序權(quán)值求出來。其方法是計(jì)算判斷矩陣A的滿足等式 的最大特征值 和對應(yīng)的特征向量W,這個(gè)特征向量就是單排序權(quán)值。WAWmaxmax 可以證明,對于n階
39、判斷矩陣,其最大特征根 為單根,且 , 所對應(yīng)的特征向量均由正數(shù)組成。特別地,當(dāng)判斷矩陣具有完全一致性時(shí),有 ,這里,所謂完全一致性是指對于判斷矩陣來說,存在maxnmaxmaxnmax),.,2 , 1,(nkjibbbjkikij為檢驗(yàn)判斷矩陣的一致性,需要計(jì)算一致性指標(biāo)1maxnnCI此外,還需要判斷矩陣的平均隨機(jī)一致性指標(biāo)RI。對于1至9階矩陣,RI的值如下表。 在這里,對于1,2階判斷矩陣,RI只是形式上的,因?yàn)?,2階判斷矩陣總具有完全一致性,當(dāng)階數(shù)大于2時(shí),判斷矩陣的一致性指標(biāo)CI與同階平均隨機(jī)一致性指標(biāo)RI之比稱謂隨機(jī)一致性比率,記為CR,CR=CI/RI0.10時(shí),即認(rèn)為判斷
40、矩陣具有滿意的一致性,否則就需要調(diào)整判斷矩陣,使其具有滿意的一致性。5)層次總排序 計(jì)算同一層次所有元素對于最高層相對重要性的排序權(quán)值,稱為層次總排序。這一過程是最高層次到最低層次逐層進(jìn)行的。若上一層次A包含m個(gè)元素A1,A2,Am,其層次總排序權(quán)值分別為a1,a2,am,下一層次B包含n個(gè)元素B1,B2,Bn,它們對于元素Aj的層次單排序權(quán)值分別為b1j,b2j,bnj(當(dāng)Bk與Aj無關(guān)系時(shí),bkj=0),此時(shí),層次總排序權(quán)值為mAAA21maaa21nBB21Bnwww21nmnnmmbbbbbbbbb212222111211nibawmjijji,.,2 , 1,16)層次總排序的一致性
41、檢驗(yàn)。 這一步也是從高到低逐層進(jìn)行的。如果B層次某些元素對于Aj單排序的一致性指標(biāo)為CIj,相應(yīng)的平均隨機(jī)一致性指標(biāo)為RIj,則B層次總排序隨機(jī)一致性比率為mjjjmjjjRIaCIaCR11類似地,當(dāng)CR0.10時(shí),認(rèn)為層次總排序結(jié)果具有滿意的一致性,否則需要重新調(diào)整判斷矩陣的元素取值。10.5 層次分析法的計(jì)算問題層次分析法的計(jì)算問題 層次分析法計(jì)算的根本問題是如何計(jì)算判斷矩陣的最大特征根其對應(yīng)的特征向量.一般來說,計(jì)算判斷矩陣最大特征根及其對應(yīng)特征向量,并不需要追求較高的精確定度.這是因?yàn)榕袛嗑仃嚤旧硐喈?dāng)?shù)恼`差范圍.應(yīng)用層次分析法給出的層次中各種元素優(yōu)先排序權(quán)值從本質(zhì)上來說是表達(dá)某種定性
42、的概念.因此,從實(shí)用性來看,往往希望使用較為簡單的近似算法.下面介紹二種稱之為方根法和和積法的近似算法. 1、方根法的步驟如下:(1)計(jì)算判斷矩陣B每一行元素的乘積Mi.nibMnjiji,.,2 , 1,1(2)計(jì)算Mi的n次方根ViniiMV (3)對向量V=(V1,V2,Vn)T規(guī)一化,即njjiiVVW1則W=(W1,W2,Wn)T.即為所求的特征向量(4)計(jì)算判斷矩陣的最大特征根maxniiinWBW1max)(式中(BW)i表示向量BW的第i個(gè)分量.容易證明:當(dāng)正互反矩陣 為一致性矩陣時(shí),方根法可得到精確的最大特征值與相應(yīng)的特征向量。nnijaA)(證明:設(shè) 為一致性矩陣, 為其最大特征值, 為相應(yīng)的特征向量,且是歸一化的。nnijaA)(maxTnuuuu),.,(21由于jiijuuan ,max令njiusnnjj, 2 , 1,/11suaMinnjjii/11顯然,歸一化后, 于是用公式Tnuuuw),(21niiiwAwn1)(1求得的最大特征值為n例題例題6 某廠準(zhǔn)備購買一臺計(jì)算機(jī),希望功能強(qiáng),價(jià)格低,維護(hù)容易.
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025至2030中國甲醇燃料汽車行業(yè)發(fā)展分析及市場競爭格局與發(fā)展前景預(yù)測報(bào)告
- 2025至2030中國瑜伽夾克和連帽衫行業(yè)市場深度研究及發(fā)展前景投資可行性分析報(bào)告
- 2025至2030中國玻璃工藝品行業(yè)深度研究及發(fā)展前景投資評估分析
- 2025至2030中國環(huán)境試驗(yàn)行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢及投資規(guī)劃深度研究報(bào)告
- 初中學(xué)業(yè)水平考試實(shí)驗(yàn)室設(shè)備標(biāo)準(zhǔn)化與統(tǒng)一化研究
- 推動(dòng)素質(zhì)教育教育機(jī)器人的重要作用與應(yīng)用前景
- 招聘培訓(xùn)課件軟件
- 美術(shù)培訓(xùn)主題課件名稱
- 高效會(huì)議管理培訓(xùn)課件
- 多媒體教學(xué)技術(shù)在課堂教學(xué)中的實(shí)踐
- DGJ08-81-2015 現(xiàn)有建筑抗震鑒定與加固規(guī)程
- 2025年中小學(xué)暑假安全教育主題家長會(huì) 課件
- 近視管理白皮書(2025)專家共識-
- 2025年佛山市南海區(qū)圖書館招聘題庫帶答案分析
- GB/T 31586.1-2015防護(hù)涂料體系對鋼結(jié)構(gòu)的防腐蝕保護(hù)涂層附著力/內(nèi)聚力(破壞強(qiáng)度)的評定和驗(yàn)收準(zhǔn)則第1部分:拉開法試驗(yàn)
- 北京市部分地區(qū)2021-2022學(xué)年高一上學(xué)期期末語文試題分類匯編:文學(xué)類文本閱讀專題(含答案)
- 科爾沁蒙古族草原上的婚禮
- 管道壓力試驗(yàn)事故案例
- 筆記本電腦借用申請單
- SYB游戲模塊PPT課件
- 中國古代文化常識測試題
評論
0/150
提交評論