目標(biāo)規(guī)劃教學(xué)教案講義

1、第三章 目標(biāo)規(guī)劃第一節(jié) 目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃法是求一組變量的值，在一組資源約束和目標(biāo)約束條件下，實(shí)現(xiàn)管理目標(biāo)與實(shí)際目標(biāo)之間的偏差最小的一種方法。應(yīng)用目標(biāo)規(guī)劃法解決多種目標(biāo)決策問(wèn)題時(shí)，首先要建立目標(biāo)規(guī)劃模型。目標(biāo)規(guī)劃模型由變量、約束和目標(biāo)函數(shù)組成。為具體說(shuō)明目標(biāo)規(guī)劃與線(xiàn)性規(guī)劃在處理問(wèn)題方法上的區(qū)別，先通過(guò)例子介紹目標(biāo)規(guī)劃的有關(guān)概念及數(shù)學(xué)模型。一、舉例例 1 某廠(chǎng)生產(chǎn)、兩種產(chǎn)品，已知計(jì)劃期有關(guān)數(shù)據(jù)如下，求獲利最大的生產(chǎn)方案。 生產(chǎn)有關(guān)數(shù)據(jù)表 擁有量 原材料 （公斤） 2 1 11 設(shè)備臺(tái)時(shí)（小時(shí)） 利潤(rùn) （元/件） 1 8 2 10 10用線(xiàn)性規(guī)劃方法求解：設(shè)、兩種產(chǎn)品產(chǎn)量分別為x1，x2

2、可得 z=62元，x=（4，3）t但實(shí)際決策時(shí)，有可能考慮市場(chǎng)等其它方面因素，例如按重要性排序的下列目標(biāo)：據(jù)市場(chǎng)信息，產(chǎn)品銷(xiāo)售量下降，要求產(chǎn)品產(chǎn)量低于產(chǎn)品產(chǎn)量；盡可能充分利用現(xiàn)有設(shè)備，但不希望加班；達(dá)到并超過(guò)計(jì)劃利潤(rùn)指標(biāo)56元。這樣考慮生產(chǎn)計(jì)劃問(wèn)題即為多目標(biāo)規(guī)劃問(wèn)題。下面結(jié)合上述例題介紹有關(guān)建立目標(biāo)規(guī)劃數(shù)學(xué)模型的基本概念。二、目標(biāo)規(guī)劃基本概念1. 設(shè)x1，x2為決策變量，并引入正、負(fù)偏差變量d+、d正偏差變量d+表示決策值超過(guò)目標(biāo)值的部分；負(fù)偏差變量d表示決策值未達(dá)到目標(biāo)值的部分，d+，d0。決策值不可能既超過(guò)又未達(dá)到目標(biāo)值，因此恒有d+d0。2.絕對(duì)約束和目標(biāo)約束絕對(duì)約束指必須嚴(yán)格滿(mǎn)足的“，

3、” 約束，稱(chēng)為硬約束，例如線(xiàn)性規(guī)劃中的約束，不滿(mǎn)足它們的約束稱(chēng)為非可行解；目標(biāo)約束是目標(biāo)規(guī)劃所特有的，它把約束的右端常數(shù)項(xiàng)看作追求的目標(biāo)值，允許出現(xiàn)正、負(fù)偏差，用“d+、d”表示，稱(chēng)為軟約束。約束的一般形式為：式中第個(gè)目標(biāo)約束的目標(biāo)值；目標(biāo)約束中決策變量的參數(shù)；以目標(biāo)值為標(biāo)準(zhǔn)而設(shè)置的偏差變量。線(xiàn)性規(guī)劃問(wèn)題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、負(fù)偏差變量后可變?yōu)槟繕?biāo)約束；同樣，線(xiàn)性規(guī)劃問(wèn)題的絕對(duì)約束，加入正、負(fù)偏差變量后也可變?yōu)槟繕?biāo)約束。例如，例1中線(xiàn)性規(guī)劃問(wèn)題的目標(biāo)函數(shù)：z = 8 x1 + 10x2 ，可變換為目標(biāo)規(guī)劃問(wèn)題中的目標(biāo)約束：8 x1 + 10x2 =56 + d+d ；而同樣，線(xiàn)性規(guī)

4、劃問(wèn)題的絕對(duì)約束：2x1 + x2 11，可變換為目標(biāo)規(guī)劃問(wèn)題中的目標(biāo)約束：2x1 + x2 = 11d 。建立約束需注意的問(wèn)題時(shí)：（1）對(duì)于絕對(duì)約束，則為資源限制值，上式中不加。（2）非負(fù)約束是指偏差變量非負(fù)，至于決策變量是否要求非負(fù)，依具體問(wèn)題要求決定。（3）在目標(biāo)規(guī)劃約束中，凡已列入目標(biāo)約束的資源約束，不應(yīng)再列入資源約束。（4）如果有明顯的目標(biāo)要求，可在中只選一個(gè)。3.優(yōu)先級(jí)與權(quán)系數(shù)要解決的規(guī)劃問(wèn)題往往有多個(gè)目標(biāo)，而決策者對(duì)于要達(dá)到的目標(biāo)是有主次之分的。要求首先達(dá)到的目標(biāo)賦予優(yōu)先級(jí)p1，稍次者賦予p2 ，。這里規(guī)定：不同級(jí)目標(biāo)重要性差異懸殊，pk pk+1，即先保證上一級(jí)目標(biāo)實(shí)現(xiàn)的基礎(chǔ)上

5、再考慮下一級(jí)目標(biāo)，低級(jí)目標(biāo)的多大收獲也不能彌補(bǔ)高級(jí)目標(biāo)的微小損失。若要區(qū)別具有相同優(yōu)先級(jí)的目標(biāo)的差別，可賦予不同的權(quán)系數(shù)wj 。4.目標(biāo)函數(shù)目標(biāo)規(guī)劃問(wèn)題的目標(biāo)函數(shù)是由各目標(biāo)約束不同的正、負(fù)偏差變量d+、d，優(yōu)先級(jí)pk與權(quán)系數(shù)wj所構(gòu)成的。與線(xiàn)性規(guī)劃不同的是目標(biāo)函數(shù)中不含決策變量xj 。當(dāng)各目標(biāo)值確定之后，決策者希望的是盡可能縮小對(duì)目標(biāo)值的偏離。因此，目標(biāo)規(guī)劃問(wèn)題的目標(biāo)函數(shù)只能是：min z = f (d+，d)。其基本形式有下列三種：要求恰好達(dá)到目標(biāo)值，即正、負(fù)偏差變量都應(yīng)盡可能的小，這時(shí)目標(biāo)函數(shù)的形式： min z = f (d+ + d)要求不超過(guò)目標(biāo)值，即正偏差變量應(yīng)盡可能的小，這時(shí)目標(biāo)

6、函數(shù)的形式： min z = f (d+ )要求超過(guò)目標(biāo)值，即負(fù)偏差變量應(yīng)盡可能的小，這時(shí)目標(biāo)函數(shù)的形式： min z = f ( d)由此可見(jiàn)，目標(biāo)規(guī)劃比線(xiàn)性規(guī)劃體現(xiàn)了新的靈活思想，約束和目標(biāo)都不看作是絕對(duì)的。決策者根據(jù)要求賦予各目標(biāo)不同的優(yōu)先級(jí)、權(quán)系數(shù)，構(gòu)造目標(biāo)函數(shù)。下面舉例說(shuō)明。例2 某構(gòu)件公司商品混凝土車(chē)間生產(chǎn)能力為20t/h，每天工作8h，現(xiàn)有2個(gè)施工現(xiàn)場(chǎng)分別需要商品混凝土a為150t，商品混凝土b為100t，兩種混凝土的構(gòu)成、單位利潤(rùn)及企業(yè)所擁有的原材料見(jiàn)下表所示，現(xiàn)管理部門(mén)提出：原材料消耗、擁有量r單位利潤(rùn)表ab擁有資源量水泥/t0.350.2550t砂/t0.550.65130

7、t單位利潤(rùn)/元10080（1）充分利用生產(chǎn)能力；（2）加班不超過(guò)2h；（3）產(chǎn)量盡量滿(mǎn)足兩工地需求；（4）力爭(zhēng)實(shí)現(xiàn)利潤(rùn)2萬(wàn)元/天試建立目標(biāo)規(guī)劃模型擬定一個(gè)滿(mǎn)意的生產(chǎn)計(jì)劃。解：1.確定變量設(shè)分別為兩種混凝土的產(chǎn)量。2.約束條件（1）目標(biāo)約束：級(jí)：要求生產(chǎn)能力充分利用，即要求剩余工時(shí)越小越好。 其中要求級(jí)：要求可以加班，但每日不超過(guò)2h，即日產(chǎn)量不超過(guò)200t。 其中要求級(jí)：兩個(gè)工地需求盡量滿(mǎn)足，但不能超過(guò)需求。 其中要求 其中要求因需求量不能超過(guò)其需求，故=0級(jí)：目標(biāo)利潤(rùn)超過(guò)2萬(wàn)元。 其中要求（2）資源約束水泥需求不超過(guò)現(xiàn)有資源： 砂需求不超過(guò)現(xiàn)有資源：（3）非負(fù)約束3.目標(biāo)函數(shù)依目標(biāo)約束中的要

8、求，第三層目標(biāo)中有兩個(gè)子目標(biāo)，其權(quán)數(shù)可依其利潤(rùn)多少的比例確定，即100:80，故w1=5，w2=4。故目標(biāo)函數(shù)為整理得該問(wèn)題的目標(biāo)規(guī)劃模型為：目標(biāo)：約束條件：例 3 例1的決策者在原材料供應(yīng)受?chē)?yán)格限制的基礎(chǔ)上考慮：產(chǎn)品產(chǎn)量低于產(chǎn)品產(chǎn)量；其次，盡可能充分利用現(xiàn)有設(shè)備，但不希望加班；再次，達(dá)到并超過(guò)計(jì)劃利潤(rùn)指標(biāo)56元，求決策方案。解 按決策者的要求，分別賦予三個(gè)目標(biāo)不同的優(yōu)先級(jí)p1，p2，p3。然后建立目標(biāo)規(guī)劃模型如下：min z = p1d1+ + p2(d2+d2) + p3d32x1 + x2 11 x1x2 + d1 d1+ = 0 x1 +2x2 + d2 d2+ = 108x1 +10

9、x2 + d3d3+ = 56x1，x2，di，di+ 0， i = 1，2，3目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式： 建立目標(biāo)規(guī)劃數(shù)學(xué)模型時(shí)，需要確定目標(biāo)值，優(yōu)先級(jí)，權(quán)系數(shù)等，它們都具有一定的主觀性，模糊性，通常采用專(zhuān)家評(píng)定法給予量化。第二節(jié) 目標(biāo)規(guī)劃的圖解法對(duì)于只有兩個(gè)決策變量的目標(biāo)規(guī)劃數(shù)學(xué)模型，可采用圖解法分析求解，這對(duì)于了解目標(biāo)規(guī)劃一般問(wèn)題的解題思路也很有幫助。下面用例2加以說(shuō)明。類(lèi)似于線(xiàn)性規(guī)劃，先在平面直角坐標(biāo)系第一象限繪出各約束條件。絕對(duì)約束的作圖與線(xiàn)性規(guī)劃相同，對(duì)于目標(biāo)約束，先繪出di+，di= 0對(duì)應(yīng)的直線(xiàn)，然后在直線(xiàn)旁相應(yīng)側(cè)標(biāo)注di+，di，如圖3-1所示。根據(jù)目標(biāo)函數(shù)中的優(yōu)先級(jí)對(duì)下圖

10、進(jìn)行分析，即可找到滿(mǎn)意解（由于目標(biāo)規(guī)劃問(wèn)題常出現(xiàn)非可行解，因此稱(chēng)目標(biāo)規(guī)劃問(wèn)題的最優(yōu)解為滿(mǎn)意解）。 x2 b11d1 d1+d2d2+a0 5.57 d3+ 10 x1fed3 dcg 圖3-1例2的目標(biāo)規(guī)劃的圖解由圖可見(jiàn)，首先考慮絕對(duì)約束：2x1 + x2 11，解的可行域?yàn)槿切?0ab，然后按優(yōu)先級(jí)p1，目標(biāo)函數(shù)中要求min d1+，解域縮減至0bc內(nèi)；再按優(yōu)先級(jí)p2，目標(biāo)函數(shù)中要求min (d2+d2)，解域縮減至線(xiàn)段ed上；最后按優(yōu)先級(jí)p3，目標(biāo)函數(shù)中要求min d3，因此最終滿(mǎn)意解域?yàn)榫€(xiàn)段gd?？汕蟮孟鄳?yīng)坐標(biāo)：g（2，4），d（10/3，10/3）。gd的凸線(xiàn)性組合都是該目標(biāo)規(guī) 劃的

11、解。目標(biāo)規(guī)劃問(wèn)題求解時(shí)，把絕對(duì)約束作為最高優(yōu)先級(jí)（但不必賦p1）例中能依次滿(mǎn)足d1+=0，d2+d2=0 d3=0，因此z*=0。但大多數(shù)情況下并非如此，還可能出現(xiàn)矛盾，這可以通過(guò)下面的例子加以說(shuō)明。例 3 某電子設(shè)備廠(chǎng)裝配a、b兩種型號(hào)同類(lèi)產(chǎn)品，每裝配一臺(tái)需占用裝配線(xiàn)1小時(shí)。每周裝配線(xiàn)開(kāi)動(dòng)40小時(shí)，預(yù)計(jì)每周銷(xiāo)售：a產(chǎn)品24臺(tái)，每臺(tái)可獲利80元；b產(chǎn)品30臺(tái)，每臺(tái)可獲利40元。該廠(chǎng)確定的目標(biāo)為：第一目標(biāo)：充分利用裝配線(xiàn)每周開(kāi)動(dòng)40小時(shí)；第二目標(biāo)：允許裝配線(xiàn)加班，但加班時(shí)間每周不超過(guò)10小時(shí)；第三目標(biāo)：裝配數(shù)量盡量滿(mǎn)足市場(chǎng)需求。要求建立上述問(wèn)題的數(shù)學(xué)模型并求解。解 設(shè)x1，x2分別為產(chǎn)品a、b的計(jì)劃產(chǎn)量。對(duì)于第三目標(biāo)，由于每臺(tái)a產(chǎn)品利潤(rùn)是b產(chǎn)品的2倍，因此取其權(quán)系數(shù)分別為2，1。建立目標(biāo)規(guī)劃模型：min z = p1d1+ p2d2+ + p3(2d3+d4)x1 + x2 + d1 d1+ = 40x1+ x2 + d2 d2+ = 50x1 + d3 d3+ = 24x2 + d4 d4+ = 30x1，x2，di，di+ 0， i = 1，2，3，4ed2+d1+dbgfhx2d3d3+d4+d4-d1-d2-0 24 a c x1 圖3-2 例3的目標(biāo)規(guī)劃的圖解由圖3-2可見(jiàn)，在考慮了第一目