第二節(jié)目標(biāo)規(guī)劃的圖解法

由于目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上建立，并彌補(bǔ)了部分不足．所以兩種規(guī)劃模型結(jié)構(gòu)沒有本質(zhì)區(qū)別，解法也非常類似．形式上的區(qū)別主要在于：①線性規(guī)劃只能處理一個(gè)目標(biāo)，而目標(biāo)規(guī)劃能統(tǒng)籌兼顧地處理多個(gè)目標(biāo)關(guān)系，以求得切合實(shí)際需求的解；②線性規(guī)劃是求滿足所有約束條件的最優(yōu)解，而目標(biāo)規(guī)劃是要在多個(gè)目標(biāo)或約束條件下找到盡量好的滿意解；③線性規(guī)劃的約束條件是不分主次地同等對(duì)待，而目標(biāo)規(guī)劃可根據(jù)實(shí)際需要給予輕重緩急的考慮．1ppt課件第二節(jié)目標(biāo)規(guī)劃的圖解法由于目標(biāo)規(guī)劃

關(guān)于最優(yōu)解：線性規(guī)劃是在可行解域內(nèi)尋找某一點(diǎn)，使單個(gè)目標(biāo)達(dá)到最優(yōu)值（最大值或最小值）．而目標(biāo)規(guī)劃是在可行域內(nèi)，首先尋找到一個(gè)使P1級(jí)目標(biāo)均滿足的區(qū)域R1，然后再在R1中尋找一個(gè)使P2級(jí)目標(biāo)均滿足或盡最大可能滿足的區(qū)域R2（R1），再在R2中尋找一個(gè)滿足P3的各目標(biāo)的區(qū)域R3（R2R1），…,如此下去，直到尋找到一個(gè)區(qū)域Rk(Rk-1…R1)，滿足Pk級(jí)的各目標(biāo)，這個(gè)Rk即為所求的解域，如果某一個(gè)Ri(1ik)已退化為一點(diǎn)，則計(jì)算終止，這一點(diǎn)即為滿意解，它只能滿足P1,…，Pi級(jí)目標(biāo)，而無法進(jìn)一步改進(jìn)，當(dāng)然，此時(shí)或許有低于Pi級(jí)目標(biāo)被滿足，這純屬巧合．2ppt課件關(guān)于最優(yōu)解：線性規(guī)劃是在可行解域內(nèi)尋找某一點(diǎn)，使目標(biāo)規(guī)劃圖解法的具體演算過程與線性規(guī)劃圖解法類似．第1步：根據(jù)決策變量（當(dāng)然不能多于2個(gè)）繪畫所有（軟、硬）約束條件的直線圖形，偏差變量以移動(dòng)（平移）直線的方法加以考慮．第5步：重復(fù)第3、4步過程，直到解區(qū)域Ri減少到一點(diǎn)或滿足了所有k個(gè)級(jí)別的目標(biāo)為止，此時(shí)，Rk即為這個(gè)目標(biāo)規(guī)劃的最優(yōu)解區(qū)域，其中的任何一點(diǎn)均為目標(biāo)規(guī)劃的滿意解．第2步：對(duì)P1級(jí)的各目標(biāo)，確定解區(qū)域R1．第3步：對(duì)下一個(gè)優(yōu)先級(jí)別Pi級(jí)各目標(biāo)，確定它的最優(yōu)解空間Ri，但必須是RiRi-1(i=2,3,…)．

第4步：在這個(gè)過程中，如果某解區(qū)域Ri減小到一點(diǎn)，則可結(jié)束這個(gè)過程，因?yàn)榇藭r(shí)沒有進(jìn)一步改進(jìn)的可能．3ppt課件目標(biāo)規(guī)劃圖解法的具體演算過程與線性規(guī)劃圖解法類似．第1步：例5

求解下面目標(biāo)規(guī)劃:解

將約束方程以直線形式畫在圖上，這里只使用決策變量（即），偏差變量在畫直線時(shí)被去掉，直線畫好后，在該直線上標(biāo)出目標(biāo)函數(shù)中與該直線相關(guān)的偏差變量增大時(shí)直線的平移方向（用垂直于直線的箭頭來反映）．如圖3-2．4ppt課件例5求解下面目標(biāo)規(guī)劃:解將約束方程以直線形式畫在圖l1l2l3l4oABCDEFx1x2R3圖3-2圖解法示意圖再考慮P2級(jí)目標(biāo)，要求目標(biāo)越小越好，因而解空間R2為△OCD區(qū)域按優(yōu)先級(jí)高低，首先考慮P1級(jí)目標(biāo)，要求目標(biāo)越小越好，就在絕約束的可行解域△OAB中進(jìn)一步縮小為△OAC，記作R1R1R2最后考慮P3級(jí)，此時(shí)要求目標(biāo)越小越好，由圖3-2可知R3為四邊形CDEF區(qū)域，5ppt課件l1l2l3l4oABCDEFx1x2R3圖3-2圖解法

這個(gè)區(qū)域內(nèi)的任一點(diǎn)均是該問題的滿意解，可使目標(biāo)函數(shù)

由于C、D、E、F坐標(biāo)分別為(6,3)、(9,0)、(8，0)、(4.8,2.4)，故滿意解可表示為：其中：

這種滿足所有目標(biāo)要求的情況，即：，在實(shí)際中并不多見，很多目標(biāo)規(guī)劃問題只能滿足前面幾級(jí)目標(biāo)要求．6ppt課件這個(gè)區(qū)域內(nèi)的任一點(diǎn)均是該問題的滿意解，可使目標(biāo)函數(shù)例6

用圖解法求解下面目標(biāo)規(guī)劃問題：解

作圖3-3：7ppt課件例6用圖解法求解下面目標(biāo)規(guī)劃問題：解作圖3-3：7pl1x1x2ol2l3R1(10,0)

圖3-3圖解法示意圖AB考慮P2級(jí)目標(biāo)，由于直線l2與R1不相交，所以在R1內(nèi)無法使因此在不退化P1級(jí)目標(biāo)時(shí)，不可能使P2級(jí)目標(biāo)完全滿足．這樣R2就縮為一點(diǎn)，因?yàn)樵赗1中，使達(dá)到最小的為A點(diǎn)，所以：x*=(10,0),8ppt課件l1x1x2ol2l3R1(10,0)圖3-3由于R2僅含有一個(gè)點(diǎn)，所以對(duì)P3級(jí)目標(biāo)，我們已經(jīng)無法進(jìn)一步的選擇與考慮，可求得，即目標(biāo)函數(shù)為：

此例中，之所以產(chǎn)生解域R2退縮為一個(gè)點(diǎn)，從而無法使P2，P3級(jí)目標(biāo)達(dá)成，是因?yàn)镻2級(jí)目標(biāo)的期望值定得過高．如果將它的目標(biāo)值從26降到14，則可考慮到P3級(jí)目標(biāo)，見圖3-4．9ppt課件由于R2僅含有一個(gè)點(diǎn)，所以對(duì)P3級(jí)目標(biāo)，我們已經(jīng)無法進(jìn)一步的

滿足P1、P2級(jí)目標(biāo)的可行解域?yàn)镽2，R1l1x1x2ol2l3(10,0)R2R3使P1,P2,P3級(jí)目標(biāo)完全滿足，這時(shí)問題的滿意解不唯一．一般地，目標(biāo)要求確定得越低，可供選擇的解越多，目標(biāo)定得太高，滿意解的選擇余地也越小，甚至一些低級(jí)別的目標(biāo)無法實(shí)現(xiàn)．進(jìn)一步考察P3級(jí)目

標(biāo)可得最優(yōu)解區(qū)域R3，對(duì)該區(qū)域中任意一點(diǎn)，均同時(shí)能圖3-410ppt課件滿足P1、P2級(jí)目標(biāo)的可行解域?yàn)镽2，R1l1x1x2o例6

求解下面目標(biāo)規(guī)劃:11ppt課件例6求解下面目標(biāo)規(guī)劃:11ppt課件用圖解法求解，見圖4.2。

12ppt課件用圖解法求解，見圖4.2。

12ppt課件從圖4.2中看到在考慮具有P1、P2的目標(biāo)實(shí)現(xiàn)后，x1、x2的取值范圍為ABCD?？紤]P3的目標(biāo)要求時(shí)，因d3—的權(quán)系數(shù)大于d4—，故先考慮mind3—；這時(shí)x1、x2的取值范圍縮小為ABEF區(qū)域。然后考慮d4—。在ABEF中無法滿足d4—=0，因此只能在ABEF中取一點(diǎn)，使d4—盡可能小，這就是E點(diǎn)。故E點(diǎn)為滿意解。其坐標(biāo)為(24，26)，13ppt課件從圖4.2中看到在考慮具有P1、P2的目標(biāo)實(shí)現(xiàn)后，x1、x2

注意：在目標(biāo)規(guī)劃中，考慮低級(jí)別目標(biāo)時(shí)，不能破壞已經(jīng)滿足的高級(jí)別目標(biāo)，這是基本原則．但它并不是說，當(dāng)某一高級(jí)別目標(biāo)不可能滿足時(shí)，其后的低級(jí)別目標(biāo)就一定不能滿足．而是在有些目標(biāo)規(guī)劃中，當(dāng)某一優(yōu)先級(jí)的目標(biāo)不能滿足時(shí)，其后的某些低級(jí)別目標(biāo)仍可能被滿足．#14ppt課件注意：在目標(biāo)規(guī)劃中，考慮低級(jí)別目標(biāo)時(shí)，不能破壞例3.5用圖解法求解目標(biāo)規(guī)劃

S,t(利潤(rùn))(裝配)(檢驗(yàn))15ppt課件例3.5用圖解法求解目標(biāo)規(guī)劃S,t(利潤(rùn))(裝配X2X1102030400102030405060AB①②FE③CGHIDP1級(jí)目標(biāo)：線段AB：P1＋P2級(jí)目標(biāo)：線段HI：故I

點(diǎn)為最優(yōu)解。P1＋P2+P3級(jí)目標(biāo)：H點(diǎn)：(25,15)I點(diǎn)：(37.5,7.5)I16ppt課件X2X1102030400102030405060AB①②Fx1x2l1l2OCBAl3Dl41、l1與l2形成的可行域OABC2、先滿足P1，OD線段E3、再滿足P2，ED線段（滿意解）E(500/11,500/11),D(360/7,360/7),150501005010015017ppt課件x1x2l1l2OCBAl3Dl41、l1與l2形成的可行域小結(jié)第一節(jié)目標(biāo)規(guī)劃的基本概念與數(shù)學(xué)模型一、問題的提出二、目標(biāo)規(guī)劃的基本概念

1.決策變量與偏差變量

２.目標(biāo)約束與絕對(duì)約束３.目標(biāo)規(guī)劃的目標(biāo)函數(shù)(達(dá)成函數(shù))４.優(yōu)先因子與權(quán)系數(shù)三、目標(biāo)規(guī)劃的數(shù)學(xué)模型建立目標(biāo)規(guī)劃模型的步驟第二節(jié)目標(biāo)規(guī)劃的圖解法#18ppt課件小結(jié)第一節(jié)目標(biāo)規(guī)劃的基本概念與數(shù)學(xué)模型一、問題的第二節(jié)目標(biāo)規(guī)劃的圖解法

由于目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上建立，并彌補(bǔ)了部分不足．所以兩種規(guī)劃模型結(jié)構(gòu)沒有本質(zhì)區(qū)別，解法也非常類似．形式上的區(qū)別主要在于：①線性規(guī)劃只能處理一個(gè)目標(biāo)，而目標(biāo)規(guī)劃能統(tǒng)籌兼顧地處理多個(gè)目標(biāo)關(guān)系，以求得切合實(shí)際需求的解；②線性規(guī)劃是求滿足所有約束條件的最優(yōu)解，而目標(biāo)規(guī)劃是要在多個(gè)目標(biāo)或約束條件下找到盡量好的滿意解；③線性規(guī)劃的約束條件是不分主次地同等對(duì)待，而目標(biāo)規(guī)劃可根據(jù)實(shí)際需要給予輕重緩急的考慮．19ppt課件第二節(jié)目標(biāo)規(guī)劃的圖解法由于目標(biāo)規(guī)劃

關(guān)于最優(yōu)解：線性規(guī)劃是在可行解域內(nèi)尋找某一點(diǎn)，使單個(gè)目標(biāo)達(dá)到最優(yōu)值（最大值或最小值）．而目標(biāo)規(guī)劃是在可行域內(nèi)，首先尋找到一個(gè)使P1級(jí)目標(biāo)均滿足的區(qū)域R1，然后再在R1中尋找一個(gè)使P2級(jí)目標(biāo)均滿足或盡最大可能滿足的區(qū)域R2（R1），再在R2中尋找一個(gè)滿足P3的各目標(biāo)的區(qū)域R3（R2R1），…,如此下去，直到尋找到一個(gè)區(qū)域Rk(Rk-1…R1)，滿足Pk級(jí)的各目標(biāo)，這個(gè)Rk即為所求的解域，如果某一個(gè)Ri(1ik)已退化為一點(diǎn)，則計(jì)算終止，這一點(diǎn)即為滿意解，它只能滿足P1,…，Pi級(jí)目標(biāo)，而無法進(jìn)一步改進(jìn)，當(dāng)然，此時(shí)或許有低于Pi級(jí)目標(biāo)被滿足，這純屬巧合．20ppt課件關(guān)于最優(yōu)解：線性規(guī)劃是在可行解域內(nèi)尋找某一點(diǎn)，使目標(biāo)規(guī)劃圖解法的具體演算過程與線性規(guī)劃圖解法類似．第1步：根據(jù)決策變量（當(dāng)然不能多于2個(gè)）繪畫所有（軟、硬）約束條件的直線圖形，偏差變量以移動(dòng)（平移）直線的方法加以考慮．第5步：重復(fù)第3、4步過程，直到解區(qū)域Ri減少到一點(diǎn)或滿足了所有k個(gè)級(jí)別的目標(biāo)為止，此時(shí)，Rk即為這個(gè)目標(biāo)規(guī)劃的最優(yōu)解區(qū)域，其中的任何一點(diǎn)均為目標(biāo)規(guī)劃的滿意解．第2步：對(duì)P1級(jí)的各目標(biāo)，確定解區(qū)域R1．第3步：對(duì)下一個(gè)優(yōu)先級(jí)別Pi級(jí)各目標(biāo)，確定它的最優(yōu)解空間Ri，但必須是RiRi-1(i=2,3,…)．

第4步：在這個(gè)過程中，如果某解區(qū)域Ri減小到一點(diǎn)，則可結(jié)束這個(gè)過程，因?yàn)榇藭r(shí)沒有進(jìn)一步改進(jìn)的可能．21ppt課件目標(biāo)規(guī)劃圖解法的具體演算過程與線性規(guī)劃圖解法類似．第1步：例5

求解下面目標(biāo)規(guī)劃:解

將約束方程以直線形式畫在圖上，這里只使用決策變量（即），偏差變量在畫直線時(shí)被去掉，直線畫好后，在該直線上標(biāo)出目標(biāo)函數(shù)中與該直線相關(guān)的偏差變量增大時(shí)直線的平移方向（用垂直于直線的箭頭來反映）．如圖3-2．22ppt課件例5求解下面目標(biāo)規(guī)劃:解將約束方程以直線形式畫在圖l1l2l3l4oABCDEFx1x2R3圖3-2圖解法示意圖再考慮P2級(jí)目標(biāo)，要求目標(biāo)越小越好，因而解空間R2為△OCD區(qū)域按優(yōu)先級(jí)高低，首先考慮P1級(jí)目標(biāo)，要求目標(biāo)越小越好，就在絕約束的可行解域△OAB中進(jìn)一步縮小為△OAC，記作R1R1R2最后考慮P3級(jí)，此時(shí)要求目標(biāo)越小越好，由圖3-2可知R3為四邊形CDEF區(qū)域，23ppt課件l1l2l3l4oABCDEFx1x2R3圖3-2圖解法

這個(gè)區(qū)域內(nèi)的任一點(diǎn)均是該問題的滿意解，可使目標(biāo)函數(shù)

由于C、D、E、F坐標(biāo)分別為(6,3)、(9,0)、(8，0)、(4.8,2.4)，故滿意解可表示為：其中：

這種滿足所有目標(biāo)要求的情況，即：，在實(shí)際中并不多見，很多目標(biāo)規(guī)劃問題只能滿足前面幾級(jí)目標(biāo)要求．24ppt課件這個(gè)區(qū)域內(nèi)的任一點(diǎn)均是該問題的滿意解，可使目標(biāo)函數(shù)例6

用圖解法求解下面目標(biāo)規(guī)劃問題：解

作圖3-3：25ppt課件例6用圖解法求解下面目標(biāo)規(guī)劃問題：解作圖3-3：7pl1x1x2ol2l3R1(10,0)

圖3-3圖解法示意圖AB考慮P2級(jí)目標(biāo)，由于直線l2與R1不相交，所以在R1內(nèi)無法使因此在不退化P1級(jí)目標(biāo)時(shí)，不可能使P2級(jí)目標(biāo)完全滿足．這樣R2就縮為一點(diǎn)，因?yàn)樵赗1中，使達(dá)到最小的為A點(diǎn)，所以：x*=(10,0),26ppt課件l1x1x2ol2l3R1(10,0)圖3-3由于R2僅含有一個(gè)點(diǎn)，所以對(duì)P3級(jí)目標(biāo)，我們已經(jīng)無法進(jìn)一步的選擇與考慮，可求得，即目標(biāo)函數(shù)為：

此例中，之所以產(chǎn)生解域R2退縮為一個(gè)點(diǎn)，從而無法使P2，P3級(jí)目標(biāo)達(dá)成，是因?yàn)镻2級(jí)目標(biāo)的期望值定得過高．如果將它的目標(biāo)值從26降到14，則可考慮到P3級(jí)目標(biāo)，見圖3-4．27ppt課件由于R2僅含有一個(gè)點(diǎn)，所以對(duì)P3級(jí)目標(biāo)，我們已經(jīng)無法進(jìn)一步的

滿足P1、P2級(jí)目標(biāo)的可行解域?yàn)镽2，R1l1x1x2ol2l3(10,0)R2R3使P1,P2,P3級(jí)目標(biāo)完全滿足，這時(shí)問題的滿意解不唯一．一般地，目標(biāo)要求確定得越低，可供選擇的解越多，目標(biāo)定得太高，滿意解的選擇余地也越小，甚至一些低級(jí)別的目標(biāo)無法實(shí)現(xiàn)．進(jìn)一步考察P3級(jí)目

標(biāo)可得最優(yōu)解區(qū)域R3，對(duì)該區(qū)域中任意一點(diǎn)，均同時(shí)能圖3-428ppt課件滿足P1、P2級(jí)目標(biāo)的可行解域?yàn)镽2，R1l1x1x2o例6

求解下面目標(biāo)規(guī)劃:29ppt課件例6求解下面目標(biāo)規(guī)劃:11ppt課件用圖解法求解，見圖4.2。

30ppt課件用圖解法求解，見圖4.2。

12ppt課件從圖4.2中看到在考慮具有P1、P2的目標(biāo)實(shí)現(xiàn)后，x1、x2的取值范圍為ABCD。考慮P3的目標(biāo)要求時(shí)，因d3—的權(quán)系數(shù)大于d4—，故先考慮mind3—；這時(shí)x1、x2的取值范圍縮小為ABEF區(qū)域。然后考慮d4—。在ABEF中無法滿足d4—=0，因此只能在ABEF中取一點(diǎn)，使d4—盡可能小，這就是E點(diǎn)。故E點(diǎn)為滿意解。其坐標(biāo)為(24，26)，31ppt課件從圖4.2中看到在考慮具有P1、P2的目標(biāo)實(shí)現(xiàn)后，x1、x2

注意：在目標(biāo)規(guī)劃中，考慮低級(jí)別目標(biāo)時(shí)，不能破壞已經(jīng)滿足的高級(jí)別目標(biāo)，這是基本原則．但它并不是說，當(dāng)某一高級(jí)別目標(biāo)不可能滿足時(shí)，其后的低級(jí)別目標(biāo)就一定不能滿足．而是在有些目標(biāo)規(guī)劃中，當(dāng)某一優(yōu)先級(jí)的目標(biāo)不能滿足時(shí)，其后的某些低級(jí)別目標(biāo)仍可