運籌學(xué)07-目標(biāo)規(guī)劃.ppt

第七章目標(biāo)規(guī)劃7.1目標(biāo)規(guī)劃模型7.2目標(biāo)規(guī)劃的幾何意義與圖解法7.3目標(biāo)規(guī)劃求解的單純形方法在科學(xué)研究、經(jīng)濟建設(shè)和生產(chǎn)實踐中，人們經(jīng)常遇到一類含有多個目標(biāo)的數(shù)學(xué)規(guī)劃問題，我們稱之為多目標(biāo)規(guī)劃。本章介紹一種特殊的多目標(biāo)規(guī)劃叫目標(biāo)規(guī)劃(goalprogramming)，這是美國學(xué)者Charnes等在1952年提出來的。目標(biāo)規(guī)劃在實踐中的應(yīng)用十分廣泛，它的重要特點是對各個目標(biāo)分級加權(quán)與逐級優(yōu)化，這符合人們處理問題要分別輕重緩急保證重點的思考方式。本章分目標(biāo)規(guī)劃模型、目標(biāo)規(guī)劃的幾何意義與圖解法和求解目標(biāo)規(guī)劃的單純形方法等三個部分進行介紹。7.1目標(biāo)規(guī)劃模型(1)問題提出為了便于理解目標(biāo)規(guī)劃數(shù)學(xué)模型的特征及建模思路,我們首先舉一個簡單的例子來說明.例1某公司分廠用一條生產(chǎn)線生產(chǎn)兩種產(chǎn)品A和B，每周生產(chǎn)線運行時間為60小時，生產(chǎn)一臺A產(chǎn)品需要4小時，生產(chǎn)一臺B產(chǎn)品需要6小時根據(jù)市場預(yù)測，A、B產(chǎn)品平均銷售量分別為每周9、8臺，它們銷售利潤分別為12、18萬元。在制定生產(chǎn)計劃時，經(jīng)理考慮下述4項目標(biāo)：首先，產(chǎn)量盡量不要超過市場預(yù)測的銷售量；其次，工人加班時間盡量最少；第三，希望總利潤盡量大；最后，要盡可能滿足市場需求,當(dāng)不能滿足時,市場認為B產(chǎn)品的重要性是A產(chǎn)品的2倍試建立這個問題的數(shù)學(xué)模型討論：若把總利潤最大看作目標(biāo)，而把產(chǎn)量不能超過市場預(yù)測的銷售量、工人加班時間最少和要盡可能滿足市場需求的目標(biāo)看作約束，則可建立一個單目標(biāo)線性規(guī)劃模型。設(shè)決策變量x1，x2分別為產(chǎn)品A，B的產(chǎn)量MaxZ=12x1+18x2s.t.4x1+6x260x19x28x1,x20容易求得上述線性規(guī)劃的最優(yōu)解為(9,4)T到(3,8)T所在線段上的點,最優(yōu)目標(biāo)值為Z*=180,即可選方案有多種.在實際上,這個結(jié)果并非完全符合決策者的要求,它只實現(xiàn)了經(jīng)理的第一、二、三條目標(biāo)，而沒有達到最后的一個目標(biāo)。下面引入與建立目標(biāo)規(guī)劃數(shù)學(xué)模型有關(guān)的概念（1）正、負偏差變量d+，d-我們用正偏差變量d+表示決策值超過目標(biāo)值的部分；負偏差變量d-表示決策值不足目標(biāo)值的部分。因決策值不可能既超過目標(biāo)值同時又末達到目標(biāo)值，故恒有d+d-0（2）絕對約束和目標(biāo)約束我們把所有等式、不等式約束分為兩部分：絕對約束和目標(biāo)約束。(2)目標(biāo)規(guī)劃模型的基本概念絕對約束指必須嚴(yán)格滿足的等式約束和不等式約束；如在線性規(guī)劃問題中考慮的約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。如例1中生產(chǎn)A，B產(chǎn)品所需原材料數(shù)量有限制，并且無法從其它渠道予以補充，則構(gòu)成絕對約束。目標(biāo)約束目標(biāo)規(guī)劃特有的，我們可以把約束右端項看作要努力追求的目標(biāo)值，但允許發(fā)生正或負偏差，用在約束中加入正、負偏差變量來表示，于是稱它們是軟約束。對于例1,我們有如下目標(biāo)約束x1+d1-d1+=9(1)x2+d2-d2+=8(2)4x1+6x2+d3-d3+=60(3)12x1+18x2+d4-d4+=252(4)(3)優(yōu)先因子與權(quán)系數(shù)對于多目標(biāo)問題，設(shè)有L個目標(biāo)函數(shù)f1,f2,fL,決策者在要求達到這些目標(biāo)時，一般有主次之分。為此，我們引入優(yōu)先因子Pi，i=1,2,L.無妨設(shè)預(yù)期的目標(biāo)函數(shù)優(yōu)先順序為f1,f2,fL,我們把要求第一位達到的目標(biāo)賦于優(yōu)先因子P1，次位的目標(biāo)賦于優(yōu)先因子P2、，并規(guī)定PiPi+1，i=1,2,L-1.即在計算過程中,首先保證P1級目標(biāo)的實現(xiàn)，這時可不考慮次級目標(biāo)；而P2級目標(biāo)是在實現(xiàn)P1級目標(biāo)的基