《第五章 目標(biāo)規(guī)劃》由會員分享，可在線閱讀，更多相關(guān)《第五章 目標(biāo)規(guī)劃（36頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,運(yùn)籌學(xué)演示課件,第 五 章,1,問題的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型,一、問題的提出,為了具體說明目標(biāo)規(guī)劃與線性規(guī)劃在處理問題方法上的區(qū)別，先通過例子來介紹目標(biāo)規(guī)劃的有關(guān)概念及數(shù)學(xué)模型。,例 某機(jī)器廠生產(chǎn),、,兩種產(chǎn)品，這兩種產(chǎn)品都需要在,A,、,B,、,C,三種不同設(shè)備上加工，三種設(shè)備在計劃期內(nèi)可提供的機(jī)時分別為,12h,、,16h,、,15h,。按工藝資料規(guī)定，生產(chǎn)每件產(chǎn)品,需占用三設(shè)備分別為,2h,、,4h,、,0h,生產(chǎn)每件產(chǎn)品,，需占用各設(shè)備分別為,2h,、,0h,、,5h.,又生產(chǎn)生產(chǎn),、,兩種產(chǎn)品各

2、一件的利潤分別為,2,元與,3,元，問企業(yè)如何安排兩種產(chǎn)品生產(chǎn)數(shù)量使總利潤最大,。,第五章 目標(biāo)規(guī)劃,解：設(shè)兩種產(chǎn)品分別安排為 與,可求出最優(yōu)解,企業(yè)的經(jīng)營目標(biāo)不僅僅是利潤，且作多方面考慮：,（,1,）力求是利潤不低于,15,元；,（,2,）考慮到市場需求，,，,兩種產(chǎn)品的生產(chǎn)量,須保持,12,的比例。,（,3,）,A,為貴重設(shè)備，嚴(yán)格禁止超時使用。,（,4,）設(shè)備,C,可以適當(dāng)加班，但要控制，設(shè)備,B,既,要求充分利用，又盡可能不加班，又在重要性上設(shè),備,B,是設(shè)備,C,的,3,倍。,這樣，在考慮產(chǎn)品生產(chǎn)決策時，不再是單純追求利潤最大，而是同時要考慮多個目標(biāo)，這樣的問題一般的線性規(guī)劃方法已無

3、法解決，需引入一種新的數(shù)學(xué)模型,目標(biāo)規(guī)劃。,線性規(guī)劃模型的局限性,(1),全部約束條件過于剛性，不能違背，否則無解。,與實際脫節(jié)。,（,2,）,只能處理單目標(biāo)的優(yōu)化問題，因此線性規(guī)劃模型認(rèn)為地將一些次要目標(biāo)轉(zhuǎn)為約束。而實際問題中，目標(biāo)和約束可以互相轉(zhuǎn)化，處理時不一定嚴(yán)格區(qū)分,；,（,3,）,線性規(guī)劃中各個約束條件都處于同等重要的地位，但實際問題中，各目標(biāo)的重要性是有差別的；,（,4,）,線性規(guī)劃尋求最優(yōu)解，但很多實際問題中只需找出滿意解就可以了,。,二、目標(biāo)規(guī)劃模型的建立,1.,偏差變量,用來表示實際值與目標(biāo)值之間的差異。,d,+,超出目標(biāo)的差值，稱為,正偏差變量,。,d,-,未達(dá)到目標(biāo)的差值

4、，稱為,負(fù)偏差變量,。,因?qū)嶋H決策值不可能既超過目標(biāo)值又低于目標(biāo)值，故最終結(jié)果中恒有,d,+,d,-,=0,(,即兩者至少有一個為,0),。,目標(biāo)規(guī)劃中，一般有多個目標(biāo)值，每個目標(biāo)值都相應(yīng)有一對偏差變量。,2.,絕對約束和目標(biāo)約束,絕對約束,是指必須嚴(yán)格滿足的等式約束或不等式約束；如線性規(guī)劃問題的所有約束條件，不能滿足這些條件的解稱為非可行解，所以絕對約束是,硬約束,。,目標(biāo)約束,是目標(biāo)規(guī)劃所特有的一種約束，它把要追求的目標(biāo)值作為右端常數(shù)項，在追求此目標(biāo)值時允許發(fā)生正偏差和負(fù)偏差。因此，目標(biāo)約束是由決策變量，正、負(fù)偏差變量和要追求的目標(biāo)值組成的,軟約束,。,目標(biāo)約束不會不滿足，但可能偏差過大,

5、。,絕對約束,：問題中的目標(biāo),3,，在原料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上考慮，可寫成絕對約束為,假設(shè)問題中甲、乙兩產(chǎn)品的產(chǎn)量分別為,x,1,和,x,2,。,目標(biāo)約束,：問題中的目標(biāo),1,可寫成目標(biāo)約束為,化為標(biāo)準(zhǔn)形式是：,線性目標(biāo)約束的一般形式是：,其中：,3.,優(yōu)先因子和權(quán)系數(shù),目標(biāo)規(guī)劃中，當(dāng)決策者要求實現(xiàn)多個目標(biāo)時，這些目標(biāo)之間是有主次區(qū)別的。,凡要求第一位達(dá)到的目標(biāo)，賦于,優(yōu)先因子,p,1,，,要求第二位達(dá)到的目標(biāo)，賦于優(yōu)先因子,p,2,并規(guī)定,p,k+,1,p,k,，,表示,p,k,比,p,k+,1,有絕對優(yōu)先權(quán)。因此，不同的優(yōu)先因子代表著不同的優(yōu)先等級。,若要區(qū)別具有相同優(yōu)先因子的多個目標(biāo)，

6、可分別賦予它們不同的,權(quán)系數(shù),k,。,越重要的目標(biāo)，其權(quán)系數(shù)的值越大。,在實現(xiàn)多個目標(biāo)時，首先保證,p,1,級目標(biāo)的實現(xiàn)，這時可不考慮其它級目標(biāo)，而,p,2,級目標(biāo)是在保證,p,1,級目標(biāo)值不變的前提下考慮的，以此類推。,4.,目標(biāo)函數(shù),目標(biāo)規(guī)劃的目標(biāo)函數(shù)是由各目標(biāo)約束的正、負(fù)偏差變量及相應(yīng)的優(yōu)先因子、權(quán)系數(shù)構(gòu)成的，其中不含決策變量。因為決策者的愿望總是盡可能縮小偏差，實現(xiàn)目標(biāo)。故總是將目標(biāo)函數(shù)極小化，其基本形式有三種。,對于第,i,個目標(biāo),:,(1),若要求,決策值超過目標(biāo)值,，則相應(yīng)的負(fù)偏差變量要盡可能地小，而對正偏差變量不加限制，目標(biāo)函數(shù)的形式為：,(2),允許,達(dá)不到目標(biāo)值,，就是相應(yīng)

7、的正偏差變量要盡可能地小，目標(biāo)函數(shù)的形式為：,(3),恰好達(dá)到目標(biāo),，則相應(yīng)的正、負(fù)偏差變量都要盡可能地小，目標(biāo)函數(shù)的形式為：,加入優(yōu)先因子和權(quán)系數(shù)后，建立目標(biāo)函數(shù)，其一般形式為：,前述問題的規(guī)劃模型可以寫為：,2,目標(biāo)規(guī)劃的圖解分析法,對于只有兩個決策變量的線性目標(biāo)規(guī)劃的數(shù)學(xué)模型，可以用圖解法來分析求解。傳統(tǒng)的線性規(guī)劃一般只是尋求一個點，在這個點上得到單目標(biāo)的最優(yōu)值，目標(biāo)規(guī)劃一般是尋求一個區(qū)域，這個區(qū)域提供了相互矛盾的目標(biāo)集的折衷方案。,步驟,1,建立直角坐標(biāo)系，令各偏差變量為,0,，作出所有的約束直線。滿足所有絕對約束條件的區(qū)域，用陰影標(biāo)出。,步驟,2,作圖表示差變量增減對約束直線的影響,

8、在所有目標(biāo)約束直線旁標(biāo)上,d,+,，,d,-,，,如圖所示。這表明目標(biāo)約束直線可以沿,d,+,，,d,-,，,所示的方向平移。,步驟,3,根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，逐步分析求解。,根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子次序，首先考慮具有優(yōu)先因子,p,1,的目標(biāo)的實現(xiàn)。目標(biāo)函數(shù)要求實現(xiàn),min,d,1,+,，,從圖中可見，可以滿足,d,1,+,=0,，,這時，只能在三角形,OBC,的區(qū)域上取值；,考察具有優(yōu)先因子,p,2,的目標(biāo)，此時可在線段,ED,上取值；,考察優(yōu)先因子,p,3,的目標(biāo)，這就使取值范圍縮小到線段,GD,上，該線段上所有點的坐標(biāo)，都是問題的解。,多目標(biāo)規(guī)劃問題的另一類表示方法,買糖,問題,

9、設(shè),商店有甲、乙、丙三種糖果，單價分別為,4,元,/kg,，,2.80,元,/kg,和,2.40,元,/kg,。,今要籌辦一次節(jié)日茶話會，要求用于買糖的錢數(shù)不超過,20,元，糖的總量不少于,6kg,，,甲、乙兩種糖的總和不少于,3kg,，,問應(yīng)如何確定最好的買糖方案。,解,：設(shè)購買甲,乙,丙三種糖果的斤數(shù)分別為,x,1,x,2,x,3,用于買糖所花的錢數(shù)為,y,1,，,所買糖的總斤數(shù)為,y,2,。,我們希望,y,1,取最小值，,y,2,取最大值。,約束條件可以寫為：,這是含有兩個目標(biāo)的線性規(guī)劃問題，這里可以將求,y,2,的最大值轉(zhuǎn)化為求（,-,y,2,）,的最小值，這時目標(biāo)函數(shù)可以寫為：,其中

10、：,3,用單純形法求解目標(biāo)規(guī)劃,目標(biāo)規(guī)劃的數(shù)學(xué)模型與線性規(guī)劃的數(shù)學(xué)模型基本相同，因此利用單純形法求解步驟也基本相同，但是需要尤其注意它們之間的區(qū)別。,線性規(guī)劃的單純形法求解過程：,1.,建立初始單純形表，計算出所有變量的檢驗數(shù)。,2.,在非基變量檢驗數(shù)中找到最大的正數(shù),j,，,它所對應(yīng)的變量,x,j,作為換入基的變量。,3.,對于所有,a,ij,0,計算,b,i,/,a,ij,，,其中最小的元素,所對應(yīng)的基變量,x,i,作為換出基的變量。,4.,建立新單純形表，重復(fù)上述步驟,2,、,3,，直到所有檢驗數(shù)都小于等于零。,由于目標(biāo)規(guī)劃的目標(biāo)函數(shù)都是求極小化問題，而線性規(guī)劃問題的標(biāo)準(zhǔn)型中目標(biāo)函數(shù)都是

11、求極大化問題，因此在用單純形法求解時要注意一些重要的的差別。,用,單純形法求解下述目標(biāo)規(guī)劃問題,：,第一步：,列出初始單純形表，并計算檢驗數(shù)。,將表格中最后一行檢驗數(shù)按優(yōu)先級改寫為：,（這是與線性規(guī)劃單純形法的,第一個差別,）,對,兩行檢驗數(shù)需分別進(jìn)行處理。,第二步：,確定換入基的變量。,在負(fù)檢驗數(shù)中，選擇最小的一個,j,所對應(yīng)的變量,x,j,作為換入基的變量。在這個問題中第一優(yōu)先級,P,1,所的檢驗數(shù)中,1,是最小的，因此,x,1,為換入基的變量。,這是與線性規(guī)劃單純形法的,第二個差別,，在線性規(guī)劃中是將大于零的檢驗數(shù)中較大的一個對應(yīng)的變量換入基。這是僅僅因為目標(biāo)函數(shù)取值有極大和極小的差別，

12、對于目標(biāo)函數(shù)取極小的線性規(guī)劃問題也可以同樣進(jìn)行處理。,第三步：,確定換出基的變量。,對于所有,a,ij,0,計算,b,i,/,a,ij,其中最小的元素,所對應(yīng)的基變量,x,i,作為換出基的變量。（這與線性規(guī)劃相同,）,在,這個問題中,min,b,i,/,a,ij,=10,，,因此,d,1,-,為換出變量。,換入、換出基的變量確定過程如下表：,第四步：,用換入變量替換換出變量，進(jìn)行單純形法迭代運(yùn)算，直至優(yōu)先級,P,1,所對應(yīng)的檢驗數(shù)全為非負(fù)。,本例,中，第一優(yōu)先級計算后得：,由于優(yōu)先級,P,2,的,檢驗數(shù)仍然有負(fù)值，因此可以繼續(xù)優(yōu)化，重復(fù)上述步驟,24,。,確定換入、換出變量：,第一點說明：,目

13、標(biāo)函數(shù)按優(yōu)先級順序進(jìn)行優(yōu)化，當(dāng),P,1,行,所有檢驗數(shù)非負(fù)時，說明第一級已經(jīng)優(yōu)化，可以轉(zhuǎn)入下一級，考察,P,2,行,檢驗數(shù)，依此類推。,第二點說明：,從,考察,P,2,行,檢驗數(shù)開始，注意應(yīng)包括更高級別的優(yōu)先因子在內(nèi)。如上述問題的進(jìn)一步單純形表如下：,對應(yīng)的檢驗數(shù)為,P,1,+(3/2),P,2,0,對應(yīng)的檢驗數(shù)為,P,1,P,2,0,對應(yīng)的檢驗數(shù)為,P,1,2,P,2,0,因此上述三種情況都不能選為換入基的變量，這其實與線性規(guī)劃相同。,判別迭代計算停止的準(zhǔn)則：,(1),檢驗數(shù),P,1,P,2,P,k,行的,所有值均為非負(fù)；,(2),若,P,1,P,2,P,i,行的所有檢驗數(shù)為非負(fù)，而,P,i

14、,+1,行存在負(fù)檢驗數(shù)，但在負(fù)檢驗數(shù)所在列的上面行中有正檢驗數(shù)（不一定是相鄰行，只要在起上方即可）。,4,求解目標(biāo)規(guī)劃的層次算法,求解目標(biāo)規(guī)劃是從高優(yōu)先級到低優(yōu)先級逐層優(yōu)化的，求解目標(biāo)規(guī)劃的層次算法就是根據(jù)這樣的思想構(gòu)造的。,層次算法步驟：,第一步：,對目標(biāo)函數(shù)中的,P,1,層次進(jìn)行優(yōu)化，建立第一層次的線性規(guī)劃模型,LP,1,并求解。,LP,1,的目標(biāo)函數(shù)為,LP,1,的約束條件含原目標(biāo)規(guī)劃的所有約束。,第二步：,對,P,2,層次進(jìn)行優(yōu)化。,由于下一層次的優(yōu)化應(yīng)在前面各層次優(yōu)化的基礎(chǔ)上進(jìn)行，若第一層次目標(biāo)函數(shù)最優(yōu)值為,z,1,*,，,則構(gòu)建的,P,2,層次的線性規(guī)劃模型,LP,2,，其目標(biāo)函數(shù)

15、為,約束條件除含有原目標(biāo)規(guī)劃的所有約束條件之外，由于這一步優(yōu)化是在前一步優(yōu)化的基礎(chǔ)上進(jìn)行的，所以前一步優(yōu)化的結(jié)果應(yīng)成為一個新的約束條件，即約束條件增加了一個式子：,小于等于使得上一步的最優(yōu)值在計算后不會發(fā)生改變,第三步：,依此類推得到第,P,s,(,s,2),層次進(jìn)行優(yōu)化時建立的線性規(guī)劃模型,LP,s,為：,當(dāng),進(jìn)行到,s,=,K,時，對,P,k,層次建立的線性規(guī)劃模型,LP,k,的最優(yōu)解即為目標(biāo)規(guī)劃問題的滿意解。,K,是某一步。,例,.,用層次算法求解下述目標(biāo)規(guī)劃。,解：,第一層次的優(yōu)化模型,LP,1,為：,利用線性規(guī)劃的單純形法對其求解，得：,因為,z,1,*,=0,，,因此在第二層次的優(yōu)化模型中加上約束條件,=0(,因為 最小就只能是,0,，因此不用寫小于號,).,求解后所得最優(yōu)值與最優(yōu)解與,LP,1,相同，即,z,2,*,=0,。,由于,z,2,*,=0,，故對,第三層次進(jìn)行優(yōu)化的時候，在,LP,2,的基礎(chǔ)上加上約束 ，得,LP,3,：,求解,LP,3,得：,到,此時，所有各層次的優(yōu)化都已經(jīng)完成，而最后一個層次的最優(yōu)值,z,3,*,=29.0,，因此并沒有取得最優(yōu)解，這個值只是該目標(biāo)規(guī)劃問題的滿意解，這個解與用圖解法求出的解相同，就是圖中,F,點。,工序,每周生產(chǎn)時間最好恰好為,150h,工序,生產(chǎn)時間可適當(dāng)超過其能力。試建立這個問題的,數(shù)學(xué)模型。,