目標(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為了說明目標(biāo)規(guī)劃與線性規(guī)劃在處理問題方法上的區(qū)別，先通過例子來介紹目標(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ī)劃問題，用x1，x2分別表示，產(chǎn)品的產(chǎn)量，其線性規(guī)劃模型表述為： 擁 有 量 原 材 料 (kg) 設(shè) 備 (hr) 2 1 1 2 11 10

2、利 潤 (元 /件 ) 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實際上，工廠在作決策時，需要考慮包括市場因素在內(nèi)等一系列條件。例如:(1)(1)根據(jù)市場信息，產(chǎn)品根據(jù)市場信息，產(chǎn)品的銷售量有下降的趨的銷售量有下降的趨勢，因而希望產(chǎn)品勢，因而希望產(chǎn)品的產(chǎn)量不應(yīng)大于產(chǎn)品的產(chǎn)量不應(yīng)大于產(chǎn)品。(2)(2)當(dāng)超過計劃供應(yīng)原

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

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

5、加入正、負(fù)偏差變量，它們是軟約束。變量，它們是軟約束。8第1節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型 線性規(guī)劃問題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、負(fù)偏差變量后可變換為目標(biāo)約束。也可根據(jù)問題的需要將絕對約束變換為目標(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)先等級)與權(quán)系數(shù)一個規(guī)劃問題常常有若干目標(biāo)。但決策者在要求達(dá)到這些目標(biāo)時，會賦予不同的優(yōu)先因子，并規(guī)定 PkPk+1 k=1,2,，K

6、表示Pk比Pk+1有更大的優(yōu)先權(quán)。即首先保證P1級目標(biāo)的實現(xiàn)，這時可不考慮次級目標(biāo)；而P2級目標(biāo)僅在實現(xiàn)P1級目標(biāo)的基礎(chǔ)上才會考慮；依此類推。若要區(qū)別具有相同優(yōu)先因子的兩個目標(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ù)偏差 變量均盡可能地小，這時，目標(biāo)函數(shù)的形式為 min z=f(d+d)(2) 若要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，若要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，但正偏差變量要盡可能地小，這時目標(biāo)函數(shù)的但正偏差變量要盡可能地小，這時目標(biāo)函數(shù)的形式為形式為 min z=f(d+)(3) 若要求超過目標(biāo)值，即超過量不限，但負(fù)偏差若要求超過目標(biāo)值，即超過量不限，但負(fù)偏差變量要盡可能地小，這時目標(biāo)函數(shù)的形

8、式為變量要盡可能地小，這時目標(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è)備有效臺時，不加班；再次是利潤額不小于56元。求最佳決策方案 。 解：解：按決策者所的要求，分別賦予這三個目標(biāo)優(yōu)先因子P1，P2，P3，得到本問題的數(shù)學(xué)模型為：3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii滿足約束條件：目標(biāo)函數(shù)：13第2節(jié) 解目標(biāo)規(guī)劃的圖解法v對只有兩個決策變量

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

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

11、規(guī)劃模型，并求解黑白和彩色電視機的產(chǎn)量。機的產(chǎn)量。 16第2節(jié) 解目標(biāo)規(guī)劃的圖解法v解解：設(shè)x1，x2分別表示黑白和彩色電視機的產(chǎ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)實現(xiàn)后，的目標(biāo)實現(xiàn)后，x1、x2的的取值范圍為取值范圍為ABCD。當(dāng)考慮當(dāng)考慮P3級目標(biāo)時，因級目標(biāo)時，因d3的權(quán)系數(shù)大于的權(quán)系數(shù)大于d4 ，故先考，故先考慮慮min d3 。這時。這時x1、x2的取值范圍縮小為區(qū)域的取值范圍縮小