運籌學07-目標規(guī)劃.ppt

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