目標(biāo)規(guī)劃數(shù)學(xué)模型與圖解法

1、1第第5章章 線性目標(biāo)規(guī)劃線性目標(biāo)規(guī)劃n第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型n第2節(jié) 解目標(biāo)規(guī)劃的圖解法n第3節(jié) 解目標(biāo)規(guī)劃的單純形法n第4節(jié) 應(yīng)用舉例2第第1 1節(jié)節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的數(shù)學(xué)模型v為了說(shuō)明目標(biāo)規(guī)劃與線性規(guī)劃在處理問(wèn)題方法上的區(qū)別，先通過(guò)例子來(lái)介紹目標(biāo)規(guī)劃的有關(guān)概念及數(shù)學(xué)模型。3第第1 1節(jié)節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的數(shù)學(xué)模型v例1 某工廠生產(chǎn)，兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)見下表。試求獲利最大的生產(chǎn)方案。v解：這是求獲利最大的單目標(biāo)的規(guī)劃問(wèn)題，用x1，x2分別表示，產(chǎn)品的產(chǎn)量，其線性規(guī)劃模型表述為： 擁 有 量 原 材 料 (kg) 設(shè) 備 (hr) 2 1 1 2 11 10

2、利 潤(rùn) (元 /件 ) 8 10 0,102112108max21212121xxxxxxxxz滿足約束條件：目標(biāo)函數(shù)：4第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型v用圖解法求得最優(yōu)決策方案為：x1*=4, x2*=3, z*=62(元)。(4,3)0,102112108max21212121xxxxxxxxz滿足約束條件：目標(biāo)函數(shù)：5第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型v實(shí)際上，工廠在作決策時(shí)，需要考慮包括市場(chǎng)因素在內(nèi)等一系列條件。例如:(1)(1)根據(jù)市場(chǎng)信息，產(chǎn)品根據(jù)市場(chǎng)信息，產(chǎn)品的銷售量有下降的趨的銷售量有下降的趨勢(shì)，因而希望產(chǎn)品勢(shì)，因而希望產(chǎn)品的產(chǎn)量不應(yīng)大于產(chǎn)品的產(chǎn)量不應(yīng)大于產(chǎn)品。(2)(2)當(dāng)超過(guò)計(jì)劃供應(yīng)原

3、材料時(shí)，需用高價(jià)采購(gòu)，當(dāng)超過(guò)計(jì)劃供應(yīng)原材料時(shí)，需用高價(jià)采購(gòu)，會(huì)使成本大幅度增加。會(huì)使成本大幅度增加。(3)(3)應(yīng)盡可能充分利用設(shè)備臺(tái)時(shí)，但不希望加班。應(yīng)盡可能充分利用設(shè)備臺(tái)時(shí)，但不希望加班。(4)(4)應(yīng)盡可能達(dá)到并超過(guò)計(jì)劃利潤(rùn)指標(biāo)：應(yīng)盡可能達(dá)到并超過(guò)計(jì)劃利潤(rùn)指標(biāo)：5656元。元。6第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型v這樣的產(chǎn)品決策問(wèn)題便構(gòu)成了一個(gè)多目標(biāo)決策問(wèn)題，目標(biāo)規(guī)劃方法正是解這類決策問(wèn)題的方法之一。下面引入與目標(biāo)規(guī)劃模型有關(guān)的概念。v1.正、負(fù)偏差變量d+，dv設(shè)x1，x2為決策變量，正偏差變量d表示決策值超過(guò)目標(biāo)值的部分；負(fù)偏差變量d表示決策值未達(dá)到目標(biāo)值的部分。因決策值不可能既超過(guò)目標(biāo)值同

4、時(shí)又未達(dá)到目標(biāo)值，即恒有 d+d = 0。7第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型v2.絕對(duì)約束和目標(biāo)約束絕對(duì)約束是指必須嚴(yán)格滿足的等式約束和不等式絕對(duì)約束是指必須嚴(yán)格滿足的等式約束和不等式約束，如線性規(guī)劃問(wèn)題的所有約束條件，不能滿約束，如線性規(guī)劃問(wèn)題的所有約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是足這些約束條件的解稱為非可行解，所以它們是硬約束。硬約束。目標(biāo)約束是目標(biāo)規(guī)劃特有的，目標(biāo)約束是目標(biāo)規(guī)劃特有的，可把約束右端項(xiàng)看可把約束右端項(xiàng)看作要追求的目標(biāo)值作要追求的目標(biāo)值。在達(dá)到此目標(biāo)值時(shí)允許發(fā)生。在達(dá)到此目標(biāo)值時(shí)允許發(fā)生正或負(fù)偏差。因此在這些約束中加入正、負(fù)偏差正或負(fù)偏差。因此在這些約束中

5、加入正、負(fù)偏差變量，它們是軟約束。變量，它們是軟約束。8第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型 線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、負(fù)偏差變量后可變換為目標(biāo)約束。也可根據(jù)問(wèn)題的需要將絕對(duì)約束變換為目標(biāo)約束，如可將例1的 目標(biāo)函數(shù)目標(biāo)函數(shù) z=8x1+10 x 變換為目標(biāo)約束變換為目標(biāo)約束 8x1+10 x2+d1d1+=56 約束條件約束條件 2x1+x211變換為目標(biāo)約束變換為目標(biāo)約束 2x1+x2+d2d2+=119第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型v3.優(yōu)先因子(優(yōu)先等級(jí))與權(quán)系數(shù)一個(gè)規(guī)劃問(wèn)題常常有若干目標(biāo)。但決策者在要求達(dá)到這些目標(biāo)時(shí)，會(huì)賦予不同的優(yōu)先因子，并規(guī)定 PkPk+1 k=1,2,，K

6、表示Pk比Pk+1有更大的優(yōu)先權(quán)。即首先保證P1級(jí)目標(biāo)的實(shí)現(xiàn)，這時(shí)可不考慮次級(jí)目標(biāo)；而P2級(jí)目標(biāo)僅在實(shí)現(xiàn)P1級(jí)目標(biāo)的基礎(chǔ)上才會(huì)考慮；依此類推。若要區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，可分別賦予它們不同的權(quán)系數(shù)wj，這些都由決策者按具體情況而定。 10第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型v4.目標(biāo)規(guī)劃的目標(biāo)函數(shù)目標(biāo)規(guī)劃的目標(biāo)函數(shù)目標(biāo)規(guī)劃的目標(biāo)函數(shù)(準(zhǔn)則函數(shù)準(zhǔn)則函數(shù))是按各目標(biāo)約是按各目標(biāo)約束的正、負(fù)偏差變量和賦予的優(yōu)先因子及權(quán)束的正、負(fù)偏差變量和賦予的優(yōu)先因子及權(quán)系數(shù)而構(gòu)造的。當(dāng)每一目標(biāo)值確定后，決策系數(shù)而構(gòu)造的。當(dāng)每一目標(biāo)值確定后，決策者的要求是盡可能縮小和目標(biāo)值的偏差。因者的要求是盡可能縮小和目標(biāo)值

7、的偏差。因此目標(biāo)規(guī)劃的目標(biāo)函數(shù)的形式通常是此目標(biāo)規(guī)劃的目標(biāo)函數(shù)的形式通常是 min z=f(d+,d)11第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型 其具體形式大致有三種： (1) 若要求恰好達(dá)到目標(biāo)值，則應(yīng)要求正、負(fù)偏差 變量均盡可能地小，這時(shí)，目標(biāo)函數(shù)的形式為 min z=f(d+d)(2) 若要求不超過(guò)目標(biāo)值，即允許達(dá)不到目標(biāo)值，若要求不超過(guò)目標(biāo)值，即允許達(dá)不到目標(biāo)值，但正偏差變量要盡可能地小，這時(shí)目標(biāo)函數(shù)的但正偏差變量要盡可能地小，這時(shí)目標(biāo)函數(shù)的形式為形式為 min z=f(d+)(3) 若要求超過(guò)目標(biāo)值，即超過(guò)量不限，但負(fù)偏差若要求超過(guò)目標(biāo)值，即超過(guò)量不限，但負(fù)偏差變量要盡可能地小，這時(shí)目標(biāo)函數(shù)的形

8、式為變量要盡可能地小，這時(shí)目標(biāo)函數(shù)的形式為 min z=f(d)12第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型v例例2 例1的決策者在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上考慮：首先是產(chǎn)品的產(chǎn)量不低于產(chǎn)品的產(chǎn)量；其次是充分利用設(shè)備有效臺(tái)時(shí)，不加班；再次是利潤(rùn)額不小于56元。求最佳決策方案 。 解：解：按決策者所的要求，分別賦予這三個(gè)目標(biāo)優(yōu)先因子P1，P2，P3，得到本問(wèn)題的數(shù)學(xué)模型為：3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii滿足約束條件：目標(biāo)函數(shù)：13第2節(jié) 解目標(biāo)規(guī)劃的圖解法v對(duì)只有兩個(gè)決策變量

9、的目標(biāo)規(guī)劃問(wèn)題，可以用圖解法來(lái)求解，以例2說(shuō)明之（圖5-1）。3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii14第2節(jié) 解目標(biāo)規(guī)劃的圖解法v注意：求解目標(biāo)規(guī)劃問(wèn)題時(shí)，把絕對(duì)約束作為最高優(yōu)先級(jí)考慮。在本例中，能依先后次序都滿足d1+=0，d2+d2=0，d3=0，因而z*=0。但在大多數(shù)問(wèn)題中并非如此，會(huì)出現(xiàn)某些約束得不到滿足，故將目標(biāo)規(guī)劃問(wèn)題的最優(yōu)解稱為滿意解。 15第2節(jié) 解目標(biāo)規(guī)劃的圖解法v例例3 3 某電視機(jī)廠裝配黑白和彩色兩種電視機(jī)，每裝配一臺(tái)電視機(jī)需占用裝配線1小時(shí)，

10、裝配線每周計(jì)劃開動(dòng)40小時(shí)。預(yù)計(jì)市場(chǎng)每周彩色電視機(jī)的銷量是24臺(tái)，每臺(tái)可獲利80元；黑白電視機(jī)的銷量是30臺(tái)，每臺(tái)可獲利40元。該廠確定的目標(biāo)為：第一優(yōu)先級(jí)：充分利用裝配線每周計(jì)劃開動(dòng)第一優(yōu)先級(jí)：充分利用裝配線每周計(jì)劃開動(dòng)4040小時(shí)；小時(shí)；第二優(yōu)先級(jí)：允許裝配線加班；但加班時(shí)間每周盡量不第二優(yōu)先級(jí)：允許裝配線加班；但加班時(shí)間每周盡量不超過(guò)超過(guò)1010小時(shí)；小時(shí)；第三優(yōu)先級(jí)：裝配電視機(jī)的數(shù)量盡量滿足市場(chǎng)需要。因第三優(yōu)先級(jí)：裝配電視機(jī)的數(shù)量盡量滿足市場(chǎng)需要。因彩色電視機(jī)的利潤(rùn)高，取其權(quán)系數(shù)為彩色電視機(jī)的利潤(rùn)高，取其權(quán)系數(shù)為2 2。試建立本問(wèn)題的目標(biāo)規(guī)劃模型，并求解黑白和彩色電視試建立本問(wèn)題的目標(biāo)

11、規(guī)劃模型，并求解黑白和彩色電視機(jī)的產(chǎn)量。機(jī)的產(chǎn)量。 16第2節(jié) 解目標(biāo)規(guī)劃的圖解法v解解：設(shè)x1，x2分別表示黑白和彩色電視機(jī)的產(chǎn)量，本問(wèn)題的目標(biāo)規(guī)劃模型為：4 , 3 , 2 , 1, 0,30245040)2(min21442331222111214332211iddxxddxddxddxxddxxddPdPdPzii滿足約束條件：目標(biāo)函數(shù)：17第2節(jié) 解目標(biāo)規(guī)劃的圖解法v用圖解法求解，見圖5.2。18第2節(jié) 解目標(biāo)規(guī)劃的圖解法v從圖5.2可看出：在考慮具有優(yōu)先因子在考慮具有優(yōu)先因子P1、P2的目標(biāo)實(shí)現(xiàn)后，的目標(biāo)實(shí)現(xiàn)后，x1、x2的的取值范圍為取值范圍為ABCD。當(dāng)考慮當(dāng)考慮P3級(jí)目標(biāo)時(shí)，因級(jí)目標(biāo)時(shí)，因d3的權(quán)系數(shù)大于的權(quán)系數(shù)大于d4 ，故先考，故先考慮慮min d3 。這時(shí)。這時(shí)x1、x2的取值范圍縮小為區(qū)域的取值范圍縮小