1、第五章 目標(biāo)規(guī)劃,2011年4月,Goal Programming,本章主要內(nèi)容： 一、問題提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型 二、目標(biāo)規(guī)劃的解法,一、問題提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型,線性規(guī)劃：在一組線性約束下一個(gè)線性函數(shù)的極值問題。,線性規(guī)劃的局限性 只能解決一組線性約束條件下，某一目標(biāo)而且只能是一個(gè)目標(biāo)的最大或最小值的問題。,實(shí)際決策中，衡量方案優(yōu)劣常常需要考慮多個(gè)目標(biāo),比如 1）.生產(chǎn)計(jì)劃決策中，通常要考慮產(chǎn)值、利潤(rùn)、滿足市場(chǎng)需求、降低消耗、提高質(zhì)量、提高勞動(dòng)生產(chǎn)率等； 2）.生產(chǎn)布局決策中，除了要考慮運(yùn)輸費(fèi)用、投資、原料供應(yīng)、產(chǎn)品需求量等經(jīng)濟(jì)指標(biāo)外，還要考慮到污染和其它社會(huì)因素等。 這些目標(biāo)中，有

2、主要的，也有次要的；有最大的，也有最小的；有定量的，也有定性的；有互相補(bǔ)充的，也有互相對(duì)立的，LP則無(wú)能為力。,目標(biāo)規(guī)劃（Goal Programming） 在線性規(guī)劃的基礎(chǔ)上發(fā)展起來(lái)的解決多目標(biāo)規(guī)劃問題的最有效的方法之一。 美國(guó)經(jīng)濟(jì)學(xué)家查恩斯(A.Charnes)和庫(kù)柏(W.W.Cooper)在1961年出版的管理模型及線性規(guī)劃的工業(yè)應(yīng)用一書中，首先提出的。 1976年伊格尼齊奧發(fā)表了目標(biāo)規(guī)劃及其擴(kuò)展一書，系統(tǒng)歸納總結(jié)了目標(biāo)規(guī)劃的理論和方法。,例1.某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，這些產(chǎn)品分別要在A、B、C、D四種不同的設(shè)備上加工。各產(chǎn)品占用資源數(shù)量，資源擁有量及產(chǎn)品利潤(rùn)見下表。問如何安排生產(chǎn)

3、，才能獲得最大的總利潤(rùn)？,3,2,利潤(rùn)（百元/件）,12,4,0,D,16,0,4,C,8,2,1,B,12,2,2,A,設(shè)備工作臺(tái)時(shí),乙,甲,消耗 產(chǎn)品 設(shè)備,解：設(shè) x1， x2 分別表示甲乙產(chǎn)品的產(chǎn)量，則相應(yīng)的線性規(guī)劃模型為：,它的最優(yōu)解為: x1 =4, x2 =2, z =14,假設(shè)企業(yè)的經(jīng)營(yíng)目標(biāo)不僅僅是利潤(rùn)，而是要考慮多個(gè)方面的目標(biāo):,（1）企業(yè)利潤(rùn)不低于12（百元）。 （2）力爭(zhēng)使甲乙兩種產(chǎn)品的比例大致為1：1。 （3）設(shè)備B必要時(shí)可以加班，但不希望加班；設(shè)備A既要充分利用，又盡可能不加班。,是否可以用線性規(guī)劃解決上述多目標(biāo)的問題？,為了解決上述多目標(biāo)的規(guī)劃問題，就需要使用目標(biāo)規(guī)

4、劃的方法。,線性規(guī)劃模型存在以下幾方面的局限性:,1.LP只能處理單目標(biāo)優(yōu)化問題。因此，線性規(guī)劃模型中人為地將一些次要目標(biāo)轉(zhuǎn)化為約束。（在實(shí)際中，目標(biāo)和約束可以相互轉(zhuǎn)化） 2.LP要求問題的解必須滿足全部約束條件，但實(shí)際中并非所有約束都必須嚴(yán)格滿足。 3.LP中各個(gè)約束（實(shí)際上也可以看作目標(biāo)）都處于同等重要地位，但實(shí)際問題中各個(gè)目標(biāo)既有層次上的差別，又有權(quán)重上的區(qū)分。 4.LP尋求最優(yōu)解，但很多問題只要找到滿意解即可。,目標(biāo)規(guī)劃解決上述LP建模中的局限性的方法： 對(duì)每個(gè)目標(biāo)函數(shù)確定一個(gè)希望達(dá)到的期望值(目標(biāo)值或理想值)；由于各種條件的限制，這些目標(biāo)值往往不可能全部都達(dá)到； 對(duì)每一個(gè)目標(biāo)函數(shù)引入

5、正的或負(fù)的偏差變量，分別表示超過或未達(dá)到目標(biāo)值的情況； 對(duì)所有的目標(biāo)函數(shù)建立約束方程，并入原來(lái)的約束條件中，組成新的約束條件； 引入目標(biāo)的優(yōu)先等級(jí)和加權(quán)系數(shù)；建立使組合偏差最小的目標(biāo)函數(shù)。,1.確定目標(biāo)函數(shù)的期望值 每一個(gè)目標(biāo)函數(shù)希望達(dá)到的期望值(或目標(biāo)值、理想值)。 根據(jù)歷史資料、市場(chǎng)需求或上級(jí)部門的布置等來(lái)確定。,2.設(shè)置偏差變量，用來(lái)表明實(shí)際值同目標(biāo)值之間的差異。,超出目標(biāo)的差值，稱正偏差變量； -未達(dá)到目標(biāo)的差值，稱負(fù)偏差變量。 與兩者必有一個(gè)為零 （1）-0，0 表示實(shí)際值超出規(guī)定目標(biāo)值； （2）-0，0 表示實(shí)際值未達(dá)到目標(biāo)值； （3）-=0，0 表示實(shí)際值同規(guī)定目標(biāo)值恰好一致。,

6、3.統(tǒng)一處理目標(biāo)和約束,系統(tǒng)約束(硬約束)：對(duì)資源使用上有嚴(yán)格限制的約束，用嚴(yán)格的等式或不等式表示（同線性規(guī)劃中的約束）。 如：4x1 16 (設(shè)備C的使用時(shí)間) 4x2 12 (設(shè)備D的使用時(shí)間),目標(biāo)約束（軟約束）：引入正、負(fù)偏差變量后，對(duì)各個(gè)目標(biāo)建立的目標(biāo)約束方程。,原來(lái)的目標(biāo)函數(shù)變成了約束條件的一部分，即目標(biāo)約束(軟約束),設(shè)備A既要充分利用，又盡可能不加班,可以寫成 mind3- +d3+ 2x1+2x2+ d3- d3=12 (設(shè)備A) 設(shè)備B允許加班，只是不希望加班或少加班，可以寫成 mind4 x1+2x2+ d4- - d4=8 (設(shè)備B),原來(lái)的目標(biāo)函數(shù)，在目標(biāo)規(guī)劃中只是成

7、了問題要達(dá)到的目標(biāo)之一 ,“目標(biāo)利潤(rùn)不低于12（百元 ）”, 可以表示成 mind1- 2x1 +3x2 + d1- - d1=12,要求甲、乙兩種產(chǎn)品的比例盡可能接近11，可以表示成 mind2- + d2 x1-x2 +d2- - d2 = 0,4.目標(biāo)函數(shù)、目標(biāo)的優(yōu)先級(jí)和權(quán)系數(shù),（1）在目標(biāo)規(guī)劃中，如果兩個(gè)不同目標(biāo)的重要程度相差懸殊，為達(dá)到某一目標(biāo)可犧牲其他目標(biāo)，稱這些目標(biāo)是屬于不同層次的優(yōu)先級(jí)。優(yōu)先級(jí)層次的高低可通過優(yōu)先因子P1，P2表示。 并規(guī)定P k P k+1 ，即不同優(yōu)先級(jí)之間的差別無(wú)法用數(shù)字大小衡量。 （2）對(duì)屬于同一層次優(yōu)先級(jí)的不同目標(biāo)，其重要程度的差別可以通過設(shè)置權(quán)系數(shù)來(lái)

8、表達(dá)。權(quán)系數(shù)越大，表示目標(biāo)越重要。,目標(biāo)規(guī)劃中的目標(biāo)函數(shù)是各個(gè)實(shí)際值與目標(biāo)值之間的最小差距。,本例中，假設(shè)： P1 ：企業(yè)利潤(rùn)目標(biāo)； P2 ：甲、乙產(chǎn)品的產(chǎn)量盡可能達(dá)到11的要求； P3 ：設(shè)備A、B盡量不超負(fù)荷工作，在第三優(yōu)先級(jí)中，設(shè)備A的重要性是設(shè)備B的三倍。,本例中，假設(shè)： P1 ：企業(yè)利潤(rùn)目標(biāo)； P2 ：甲、乙產(chǎn)品的產(chǎn)量盡可能達(dá)到11的要求； P3 ：設(shè)備A、B盡量不超負(fù)荷工作，在第三優(yōu)先級(jí)中，設(shè)備A的重要性是設(shè)備B的三倍。,目標(biāo)約束：f(x) + d- d = f0 ; 1.要求性能指標(biāo)f(x) 盡量達(dá)到目標(biāo)值f0 （即不足f0不好，超出f0也不好） min(d-+ d) = f0

9、2.要求性能指標(biāo)f(x)的值不少于目標(biāo)值f0 (即允許超過f0，但盡可能不要少于f0） min（d-） f0 3.要求性能指標(biāo) f(x) 的值不超過目標(biāo)值 f0 (即允許少于f0，但盡可能不要超過f0） min（d） f0,小結(jié),課堂練習(xí)1： 某工廠計(jì)劃生產(chǎn)A、B兩種產(chǎn)品，每噸產(chǎn)品的耗電量指標(biāo)、原材料消耗、單位產(chǎn)品利潤(rùn)及資源限量如表所示。 廠長(zhǎng)首先考慮要充分利用供電部門分配的電量限額66， 然后考慮利潤(rùn)不低于100元； 其次據(jù)市場(chǎng)調(diào)查結(jié)果，希望B產(chǎn)品的產(chǎn)量不低于A產(chǎn)品的產(chǎn)量， 問應(yīng)如何安排產(chǎn)品A、B的產(chǎn)量。,20,10,單位產(chǎn)品利潤(rùn),8,1,2,原材料,66,12,10,電力,資源限量,B,A

10、,消耗 產(chǎn)品 資源,解：設(shè)x1 、x2分別表示A、B兩種產(chǎn)品的產(chǎn)量，則目標(biāo)規(guī)劃模型如下：,課堂練習(xí)2： 某電視機(jī)廠裝配黑白和彩色兩種電視機(jī)，每裝配一臺(tái)電視機(jī)需要占用裝配線1小時(shí)，裝配線每周計(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)的40小時(shí)； 第二優(yōu)先級(jí)：允許裝配線加班，但加班的時(shí)間盡量不超過10小時(shí)； 第三優(yōu)先級(jí)：裝配電視機(jī)的數(shù)量盡量滿足市場(chǎng)需要。因彩色電視機(jī)利潤(rùn)高，取其權(quán)為2。 試確定該廠為達(dá)到以上目標(biāo)的最優(yōu)生產(chǎn)計(jì)劃。（建立數(shù)學(xué)模型）,解：設(shè) x1, x2

11、分別表示彩色和黑白電視機(jī)的產(chǎn)量。該問題的目標(biāo)規(guī)劃模型為：,作業(yè)：,P145. 第 5.8題,二、目標(biāo)規(guī)劃的解法,（一）目標(biāo)規(guī)劃的圖解法 （二）目標(biāo)規(guī)劃的單純形解法,(一)、目標(biāo)規(guī)劃的圖解法,只含有兩個(gè)決策變量(不考慮偏差變量)的目標(biāo)規(guī)劃模型 線性規(guī)劃是在可行域中尋找一點(diǎn)，使單個(gè)目標(biāo)極大或極??； 目標(biāo)規(guī)劃則是尋找一個(gè)區(qū)域，這個(gè)區(qū)域提供了相互矛盾的目標(biāo)集的 折衷方案。 目標(biāo)規(guī)劃的圖解法的思路,首先是在可行域內(nèi)尋找一個(gè)使P1級(jí)各目標(biāo)均滿足的區(qū)域R1； 然后再在R1中尋找一個(gè)使P2級(jí)各目標(biāo)均滿足的區(qū)域R2(R2 R1)； 接著再在R2中尋找一個(gè)滿足P3級(jí)各目標(biāo)的區(qū)域R3(R3 R2 R1)； 如此繼續(xù)

12、，直到尋找到一個(gè)區(qū)域RK(RK RK-1 R3 R2 R1)，滿足PK級(jí)各目標(biāo)，這時(shí)RK即為這個(gè)目標(biāo)規(guī)劃的最優(yōu)解空間，其中的任一點(diǎn)均為這個(gè)目標(biāo)規(guī)劃的滿意解。,目標(biāo)規(guī)劃的圖解法的步驟 第一步：按照系統(tǒng)約束畫出可行域， 第二步：不考慮正負(fù)偏差變量，畫出目標(biāo)約束的邊界線， 第三步：按優(yōu)先級(jí)別和權(quán)重依次分析各級(jí)目標(biāo)。,選擇F點(diǎn)作為滿意解 即x1=3,x2=3,企業(yè)的利潤(rùn)是15百元。,F,G,H,x1,x2,(1),(2),(3),(4),(5),(6),例2 用圖解法求解目標(biāo)規(guī)劃,課堂練習(xí)： 用圖解法求解目標(biāo)規(guī)劃,x1,x2,(1),(2),(3),(4),由于E點(diǎn)使得d4-取值最小，故E點(diǎn)為滿意解

13、(24,26),E,(二)、求解目標(biāo)規(guī)劃的單純形法,目標(biāo)規(guī)劃與線性規(guī)劃的數(shù)學(xué)模型的結(jié)構(gòu)相似 可用前述單純形算法求解目標(biāo)規(guī)劃模型：,由于檢驗(yàn)數(shù)一般是各優(yōu)先等級(jí)因子的代數(shù)和，為方便可以將檢驗(yàn)數(shù)行根據(jù)優(yōu)先因子分成K行，判斷檢驗(yàn)數(shù)的正負(fù)和大小主要根據(jù)優(yōu)先因子的系數(shù)正負(fù)和大小。,由于目標(biāo)規(guī)劃是極小化問題，最優(yōu)性標(biāo)準(zhǔn)是：檢驗(yàn)數(shù)非負(fù)。,將優(yōu)先等級(jí)Pk視為正常數(shù)(類似于大 法)(P1P2P3.PK); 正負(fù)偏差變量dk+, dk- 視為松弛變量; 以負(fù)偏差變量 dk- 為初始基變量，建立初始單純形表 檢驗(yàn)數(shù)的計(jì)算與LP單純形表檢驗(yàn)數(shù)的計(jì)算完全相同 最優(yōu)性判別準(zhǔn)則類似于LP的單純形算法：,例3：用單純形法求解下

14、列目標(biāo)規(guī)劃問題,以負(fù)偏差變量作為第一組基變量，填入單純形表,雖然P2行有負(fù)檢驗(yàn)數(shù)，但由于其對(duì)應(yīng)的P1行的檢驗(yàn)數(shù)均為正，所以計(jì)算停止，得到目標(biāo)規(guī)劃的滿意解：x1=10,x2=20。,注意： 對(duì)目標(biāo)的優(yōu)化是按優(yōu)先級(jí)順序逐級(jí)進(jìn)行的，當(dāng)P1行的所有檢驗(yàn)數(shù)均為非負(fù)時(shí)，說明第一優(yōu)先級(jí)的目標(biāo)已得到優(yōu)化，可轉(zhuǎn)入下一級(jí)，再考察P2行的檢驗(yàn)數(shù)是否存在負(fù)值，依次類推。 考察P2行的檢驗(yàn)數(shù)時(shí),注意應(yīng)包括更高級(jí)別的優(yōu)先因子在內(nèi),例如,上面的最后一張單純形表中最下面的P2行有兩個(gè)負(fù)值，其對(duì)應(yīng)的變量d1-的檢驗(yàn)數(shù)為P1-P20,變量d2+的檢驗(yàn)數(shù)為P1-2P20。因此判斷迭代計(jì)算應(yīng)否停止的準(zhǔn)則為：,檢驗(yàn)數(shù)P1,P2,PK行的所有值均非負(fù)； 若P1,P2,Pi行的所有值均非負(fù)，第Pi+1行存在負(fù)檢驗(yàn)數(shù)，但在負(fù)檢驗(yàn)數(shù)所在列的上面行中有正的檢驗(yàn)數(shù)。,作業(yè)： P145. 第 5.3(a)題(圖解法) 第 5.3(c)題(單純形法),課后習(xí)題講解:P145 5.8 某牌號(hào)的酒系