目標(biāo)規(guī)劃-xfj111

《目標(biāo)規(guī)劃-xfj111》由會(huì)員分享，可在線閱讀，更多相關(guān)《目標(biāo)規(guī)劃-xfj111（43頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,第四章 目標(biāo)規(guī)劃,目標(biāo)規(guī)劃的數(shù)學(xué)模型,解目標(biāo)規(guī)劃的圖解法,解目標(biāo)規(guī)劃的單純形法,靈敏度分析,例,1,：某工廠生產(chǎn),，,兩種產(chǎn)品，已,知,知有關(guān)數(shù)據(jù)見(jiàn),下,下表。試求獲,利,利最大生產(chǎn)方,案,案。,擁有量,原材料,Kg,2,1,11,設(shè)備,hr,1,2,10,利潤(rùn) 元,/,件,8,10,目標(biāo)規(guī)劃的數(shù),學(xué),學(xué)模型,問(wèn)題是，在實(shí),際,際生產(chǎn)時(shí)的考,慮,慮如下：,（,1,）根據(jù)市場(chǎng)信,息,息，產(chǎn)品,的銷量有下降,的,的趨勢(shì)，故產(chǎn),品,品,的產(chǎn)量不大于,產(chǎn),產(chǎn)品,的產(chǎn)量；,（,2,）超過(guò)計(jì)劃供,應(yīng),應(yīng)的原材料時(shí),，,

2、，需用高價(jià)采,購(gòu),購(gòu)，這就使得,成,成本增加；,（,3,）應(yīng)盡可能充,分,分利用設(shè)備，,但,但不希望加班,。,。,（,4,）應(yīng)盡可能達(dá),到,到并超過(guò)計(jì)劃,利,利潤(rùn)指標(biāo),56,元。,顯然，這個(gè)決,策,策問(wèn)題有多個(gè)目標(biāo)需要滿足。,應(yīng)該怎樣建立,目,目標(biāo)規(guī)劃的數(shù),學(xué),學(xué)模型？,它和前面所講,的,的線性規(guī)劃的,數(shù),數(shù)學(xué)模型有何,異,異同？,線性規(guī)劃的數(shù),學(xué),學(xué)模型：,用一組未知變,量,量表示要求的,方,方案，這組未,知,知變量稱為決策變量；,存在一定的約束條件，且為線性表,達(dá),達(dá)式；,有一個(gè)目標(biāo)要求（最大化，當(dāng),然,然也可以是最,小,小化），目標(biāo),表,表示為未知變,量,量的線性表達(dá),式,式，稱之為目標(biāo)

3、函數(shù)；,對(duì)決策變量有非負(fù)要求。,目標(biāo)規(guī)劃數(shù)學(xué),模,模型的相關(guān)概,念,念？,用一組未知變,量,量,x,i,表示決策變量,，,，此外，引進(jìn)正、負(fù)偏差變,量,量,d,+,、,d,-,；,存在一定的約,束,束條件，包含絕對(duì)約束和目標(biāo)約束；,各目標(biāo)具有不,同,同的優(yōu)先因子,P,k,或權(quán)系數(shù),w,j,；,目標(biāo)函數(shù)由各,目,目標(biāo)約束的正、負(fù)偏差變,量,量,d,+,、,d,-,和賦予其的優(yōu)先因子及權(quán)系數(shù)構(gòu)造；,對(duì)決策變量和正、負(fù)偏差變,量,量有非負(fù)要求。,用一組未知變,量,量,x,i,表示決策變量,，,，此外，引進(jìn),正,正、負(fù)偏差變,量,量,d,+,、,d,-,；,正偏差量,d,+,表示決策值超,過(guò),過(guò)目標(biāo)值

4、的部,分,分；,負(fù)偏差量,d,-,表示決策值未,達(dá),達(dá)到目標(biāo)值的,部,部分,;,因?yàn)闆Q策值不,可,可能既超過(guò)目,標(biāo),標(biāo)值同時(shí)又未,達(dá),達(dá)到目標(biāo)值，,則,則恒有,d,+,d,-,0,。,存在一定的約,束,束條件，包含,絕,絕對(duì)約束和目,標(biāo),標(biāo)約束；,絕對(duì)約束是指必須嚴(yán)格,滿,滿足的約束條,件,件，如線性規(guī),劃,劃中的約束條,件,件都是絕對(duì)約,束,束；,目標(biāo)約束是目標(biāo)規(guī)劃特,有,有的。目標(biāo)約,束,束的右端是所,要,要追求的目標(biāo),值,值，允許該值,發(fā),發(fā)生正負(fù)偏差,，,，因此在此約,束,束的左端加入正、負(fù)偏差量,d,+,、,d,-,。,各目標(biāo)具有不,同,同的優(yōu)先因子,或,或權(quán)系數(shù)；,決策者對(duì)于不,同

5、,同的目標(biāo)要求,，,，有主次輕重,之,之分。要求第,一,一位達(dá)到的目,標(biāo),標(biāo)賦予優(yōu)先因,子,子,P,1,，次位的目標(biāo),賦,賦予優(yōu)先因子,P,2,，依次類推，,并,并規(guī)定,P,k,P,k+1,。,若要區(qū)別具有,相,相同優(yōu)先因子,的,的兩個(gè)目標(biāo)的,差,差別，可分別,賦,賦予它們不同,的,的權(quán)系數(shù),w,j,。,注：目標(biāo)的主,次,次輕重之分由,決,決策者確定。,目標(biāo)函數(shù)由各,目,目標(biāo)約束的正,負(fù),負(fù)偏差量和各,目,目標(biāo)相應(yīng)的優(yōu),先,先因子及權(quán)系,數(shù),數(shù)構(gòu)造。,當(dāng)某一目標(biāo)值,確,確定后，決策,者,者的要求是盡,可,可能地縮小與,目,目標(biāo)值的偏離,。,。因此目標(biāo)規(guī),劃,劃的目標(biāo)函數(shù),形,形式為,minz=

6、f(d,+,d,-,),，其基本形式,有,有三種：,1,）要求恰好達(dá),到,到目標(biāo)值，即,正,正負(fù)偏差都要,盡,盡可能的小，,這,這時(shí)要求,minz=f(d,+,+d,-,),2,）要求不超過(guò),目,目標(biāo)值，也就,是,是允許達(dá)不到,目,目標(biāo)值，而正,偏,偏差量要盡可,能,能的小，即,minz=f(d,+,),3,）要求不低于,目,目標(biāo)值，也就,是,是允許超過(guò)目,標(biāo),標(biāo)值，而負(fù)偏,差,差量要盡可能,的,的小，即,minz=f(d,-,),例,2,對(duì)于例,1,中需要考慮的,多,多個(gè)目標(biāo)，試,給,給出合適的目,標(biāo),標(biāo)規(guī)劃數(shù)學(xué)模,型,型。,解：,1,）設(shè)定決策,變,變量,x,i,;,2,）確定所需,考,考

7、慮的各個(gè),目,目標(biāo)的優(yōu)先,級(jí),級(jí)及權(quán)系數(shù),。,。,假定決策者,在,在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上考慮：首先是產(chǎn)品,的產(chǎn)量不低于產(chǎn),品,品,的產(chǎn)量（,P,1,級(jí)）；其次是充分利用設(shè)備,有,有效臺(tái)時(shí)，不加,班,班（,P,2,級(jí)）；再次是利潤(rùn)不小于,56,元（,P,3,級(jí)）。,原材料供應(yīng)受嚴(yán)格限制絕對(duì)約束,首先是產(chǎn)品,的產(chǎn)量不低于產(chǎn),品,品,的產(chǎn)量?jī)?yōu)先級(jí)為,P,1,的目標(biāo)約束,其次是充分利用設(shè)備,有,有效臺(tái)時(shí)，不加,班,班優(yōu)先級(jí)為,P,2,的目標(biāo)約束,再次是利潤(rùn)不小于,56,元優(yōu)先級(jí)為,P,3,的目標(biāo)約束,3,）將各個(gè)目標(biāo)寫,入,入目標(biāo)規(guī)劃的約,束,束條件，包括絕,對(duì),對(duì)約束和目標(biāo)約,束,束。,4,

8、）確定各個(gè)目標(biāo),約,約束對(duì)于各自正,負(fù),負(fù)偏差量的的要,求,求。,首先,是產(chǎn)品,的產(chǎn)量不低于產(chǎn)品,的產(chǎn)量，也就是要求,x,1,-x,2,不超過(guò)目標(biāo)值,0,，即 盡量小。,其次,是充分利用設(shè)備有效臺(tái)時(shí)，不加班，也就是要求,x,1,+2x,2,最好恰好為,10,，即 盡量小。,再次,是利潤(rùn)不小于,56,元，也就是要求,8x,1,+10 x,2,不小于目標(biāo)值,56,，即 盡量小。,5,）用各目標(biāo)約束,的,的優(yōu)先因子及權(quán),系,系數(shù)與其自身偏,差,差量要求的乘積的加和構(gòu)造目標(biāo)函數(shù)。,6,）給出各決策變,量,量和偏差變量的,非,非負(fù)要求,將上述步驟加以,整,整理，得例,2,的數(shù)學(xué)模型為：,目標(biāo)規(guī)劃的一般,

9、數(shù),數(shù)學(xué)模型：,目標(biāo)規(guī)劃,vs,線性規(guī)劃,1,）線性規(guī)劃只有,一,一個(gè)目標(biāo)。而目,標(biāo),標(biāo)規(guī)劃具有多個(gè),目,目標(biāo)，并有不同,的,的優(yōu)先級(jí)，低優(yōu),先,先級(jí)目標(biāo)必須服,從,從高優(yōu)先級(jí)目標(biāo),的,的實(shí)現(xiàn)。,2,）線性規(guī)劃尋求,單,單一目標(biāo)的最優(yōu),值,值。而目標(biāo)規(guī)劃,尋,尋求所有目標(biāo)與,預(yù),預(yù)計(jì)成果的最小,差,差距，差距越小,，,，目標(biāo)實(shí)現(xiàn)的可,能,能性越大。,3,）線性規(guī)劃只接,受,受最優(yōu)解，而目,標(biāo),標(biāo)規(guī)劃接受滿意,解,解，即如果某些,低,低優(yōu)先級(jí)的約束,得,得不到滿足，將,目,目標(biāo)規(guī)劃問(wèn)題的,解,解稱為滿意解。,2.,解目標(biāo)規(guī)劃的圖,解,解法,求解思路：,（,1,）在平面直角系,的,的第一象限，做,

10、出,出滿足絕對(duì)約束,條,條件的可行域。,（,2,）令 ，做出相應(yīng)的目標(biāo)約束線，并確定正負(fù)偏差量的方向。,（,3,）根據(jù)目標(biāo)函數(shù),中,中各目標(biāo)偏差量,的,的優(yōu)先等級(jí)依次,分,分析求解。,例：用圖解法求,解,解例,2,F,G,J,E,D,C,O,B,A,x,1,x,2,d,1,-,d,1,+,d,2,+,d,2,-,d,3,-,d,3,+,例,3,解,:,假設(shè),x,1,x,2,分別表示彩色和黑白電視機(jī)的產(chǎn)量：,F,E,G,J,D,C,O,B,A,x,1,x,2,d,1,-,d,1,+,d,2,+,d,2,-,d,3,-,d,3,+,d,4,+,d,4,-,H,3,解目標(biāo)規(guī)劃的單,純,純形法,例：用

11、單純形法,求,求解書上例,2,的目標(biāo)規(guī)劃,數(shù)學(xué)模型,1.,將該目標(biāo)規(guī)劃中,的,的第四個(gè)約束（,絕,絕對(duì)約束）修正,為,為標(biāo)準(zhǔn)化形式。,2.,按標(biāo)準(zhǔn)化模型列,出,出單純形表，將,檢,檢驗(yàn)數(shù)行按優(yōu)先,因,因子的個(gè)數(shù)排成,K,行，見(jiàn)下表。（確定初始解）,11/1,10/2,56/10,c,B,d,1,-,x,1,b,x,B,x,2,x,s,d,2,-,d,1,+,d,3,-,d,2,+,d,3,+,c,j,P,3,P,2,P,1,P,2,11 21 1,0 1-11 -1,10121-1,568101-1,x,s,d,1,-,d,2,-,d,3,-,00,P,2,P,3,c,j,-z,j,P,1,P

12、,2,P,3,-1,-8,-2,-10,1,2,1,3.,由高優(yōu),先,先級(jí)開(kāi),始,始檢查,每,每行檢,驗(yàn),驗(yàn)數(shù)是,否,否存在,負(fù),負(fù)數(shù)，,且,且對(duì)應(yīng),前,前幾行,的,的系數(shù),為,為,0,。若存,在,在，取,最,最小者,對(duì),對(duì)應(yīng)的,變,變量為,換,換入變,量,量進(jìn)基,，,，然后,用,用最小,比,比原則,確,確定出,基,基變量,，,，得到,主,主元素,；,；若不,存,存在，,計(jì),計(jì)算結(jié),束,束。（判斷,是,是否滿,意,意）,11/1,10/2,56/10,c,B,d,1,-,x,1,b,x,B,x,2,x,s,d,2,-,d,1,+,d,3,-,d,2,+,d,3,+,c,j,P,3,P,2,P,

13、1,P,2,11211,01-11-1,10121-1,568101-1,x,s,d,1,-,d,2,-,d,3,-,00,P,2,P,3,c,j,-z,j,P,1,P,2,P,3,-1,-8,-2,-10,1,2,1,4.,確定主,元,元素后,，,，按照,單,單純形,法,法進(jìn)行,基,基變換,運(yùn),運(yùn)算，,得,得到關(guān),于,于新基,的,的計(jì)算,表,表（換基,迭,迭代）。然后,重,重新計(jì),算,算檢驗(yàn),數(shù),數(shù),(,第,2,步,),，并判,斷,斷是否,最,最優(yōu),(,第三步,),。,4,10/3,10,6/3,c,B,d,1,-,x,1,b,x,B,x,2,x,s,d,2,-,d,1,+,d,3,-,d,

14、2,+,d,3,+,c,j,P,3,P,2,P,1,P,2,63/21-1/2 1/2,53/21-1-1/2 1/2,51/211/2-1/2,63,551,1,x,s,d,1,-,x,2,d,3,-,00 0,P,3,c,j,-z,j,P,1,P,2,P,3,-3,1,1,5,1,-3,1,-5,5.,繼續(xù)進(jìn),行,行基變換,運(yùn),運(yùn)算，得到,關(guān),關(guān)于新,基,基的計(jì),算,算表，,然,然后計(jì),算,算檢驗(yàn),數(shù),數(shù)，判,斷,斷是否,滿,滿意。,11/1,10/2,56/10,c,B,d,1,-,x,1,b,x,B,x,2,x,s,d,2,-,d,1,+,d,3,-,d,2,+,d,3,+,c,j,P

15、,3,P,2,P,1,P,2,312-2-1/21/2,21-13-3-1/21/2,414/3-4/3-1/61/6,21-5/35/31/3-1/3,x,s,d,1,-,x,2,x,1,00,0,0,c,j,-z,j,P,1,P,2,P,3,1,1,1,1,所,有,有,非,非,基,基,變,變,量,量,的,的,檢,檢,驗(yàn),驗(yàn),數(shù),數(shù),均,均,=0,已,達(dá),達(dá),到,到,滿,滿,意,意,。,。,6.,由,于,于,非,非,基,基,變,變,量,量,d,3,+,的,檢,檢,驗(yàn),驗(yàn),數(shù),數(shù),為,為,0,，,表,表,明,明,存,存,在,在,多,多,重,重,解,解,。,。,在,在,上,上,表,表,的,的,基

16、,基,礎(chǔ),礎(chǔ),上,上,以,以,d,3,+,作,為,為,換,換,入,入,變,變,量,量,，,，,繼,繼,續(xù),續(xù),迭,迭,代,代,。,。,6,4,24,c,B,d,1,-,x,1,b,x,B,x,2,x,s,d,2,-,d,1,+,d,3,-,d,2,+,d,3,+,c,j,P,3,P,2,P,1,P,2,312 -2 -1/21/2,21-13-3-1/21/2,414/3-4/3-1/6 1/6,2 1-5/35/31/3-1/3,x,s,d,1,-,x,2,x,1,00,0,0,c,j,-z,j,P,1,P,2,P,3,1,1,1,1,C,j,p,1,p,2,p,2,p,3,C,B,X,B,b,x,1,x,2,x,S,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,x,S,1,1,-1,1,-1,1,d,3,-,4,2,-2,6,-6,-1,1,x,2,10/3,1,-1/3,1/3,1/3,-1/3,x,1,10/3,1,2/3,-2/3,1/3,-1/3,c,j,-z,j,p,1,1,p,2,1,1,p,3,1,第一個(gè)滿,意,意解為：,x,1,=2,x,2