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