1、復(fù)習(xí)：某市為方便學(xué)生上學(xué)，擬在新建的居民小區(qū)增設(shè)若干所小學(xué)。已知被選校址代號及其能覆蓋的居民小區(qū)編號如右表所示，問為覆蓋所有小區(qū)至少應(yīng)建多少所小學(xué)，要求建模并求解。,，模型為,最優(yōu)方案為在A、D、E三處建小學(xué)。,第五章 目 標(biāo) 規(guī) 劃,1 問題的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型 2 目標(biāo)規(guī)劃的圖解分析法 3 用單純形法求解目標(biāo)規(guī)劃,在科學(xué)研究、經(jīng)濟(jì)建設(shè)和生產(chǎn)實(shí)踐中，人們經(jīng)常遇到一類含有多個目標(biāo)的數(shù)學(xué)規(guī)劃問題，我們稱之為多目標(biāo)規(guī)劃。本章介紹一種特殊的多目標(biāo)規(guī)劃叫目標(biāo)規(guī)劃(goal programming)，這是美國學(xué)者Charnes等在1952年提出來的。目標(biāo)規(guī)劃在實(shí)踐中的應(yīng)用十分廣泛，它的重要特點(diǎn)是對

2、各個目標(biāo)分級加權(quán)與逐級優(yōu)化，這符合人們處理問題要分別輕重緩急保證重點(diǎn)的思考方式。 本章分問題的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型、目標(biāo)規(guī)劃的圖解分析法、與用單純形法求解目標(biāo)規(guī)劃等三個部分進(jìn)行介紹。,1 問題的提出與目標(biāo)規(guī)劃的數(shù)學(xué)模型,目標(biāo)規(guī)劃模型,問題的提出 為了便于理解目標(biāo)規(guī)劃數(shù)學(xué)模型的特征及建模思路, 我們首先舉一個簡單的例子來說明. 例 1 某公司分廠用一條生產(chǎn)線生產(chǎn)兩種產(chǎn)品A和B ，每周生產(chǎn)線運(yù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)計劃時，需要考慮下述4項(xiàng)目標(biāo)：,目標(biāo)規(guī)

3、劃模型,問題的提出 (續(xù)) 首先，產(chǎn)量不能超過市場預(yù)測的銷售量； 其次，工人加班時間最少； 第三，希望總利潤最大； 最后，要盡可能滿足市場需求, 當(dāng)不能滿足時, 市場認(rèn)為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)量，建立數(shù)學(xué)模型：,目標(biāo)規(guī)劃模型,容易求得上述線性規(guī)劃的最優(yōu)解為(9,4)T 到 (3,8)T 所在線段上的點(diǎn), 最優(yōu)目標(biāo)值為Z* = 180, 即可選方案有多種. 在實(shí)際上, 這個結(jié)果并非完全符合決策者的要求, 它只實(shí)現(xiàn)了既定的第

4、一、二、三條目標(biāo)，而沒有達(dá)到最后的一個目標(biāo)。進(jìn)一步分析可知，要實(shí)現(xiàn)全體目標(biāo)是不可能的。,目標(biāo)規(guī)劃模型,目標(biāo)規(guī)劃模型的基本概念 把例1的4個目標(biāo)表示為不等式.仍設(shè)決策變量x1，x2分別為產(chǎn)品A，B的產(chǎn)量. 那麼, 第一個目標(biāo)為: x1 9 ，x2 8 ； 第二個目標(biāo)為: 4x1 + 6x2 60 ； 第三個目標(biāo)為: 希望總利潤最大，要表示成不等式需要找到一個目標(biāo)上界，這里可以估計為252（=129 + 188），于是有 12x1 + 18x2 252； 第四個目標(biāo)為: x1 9，x2 8；,目標(biāo)規(guī)劃模型,目標(biāo)規(guī)劃模型的基本概念 下面引入與建立目標(biāo)規(guī)劃數(shù)學(xué)模型有關(guān)的概念 （1）、正、負(fù)偏差變量d

5、+，d - 我們用正偏差變量d + 表示決策值超過目標(biāo)值的部分；負(fù)偏差變量d - 表示決策值不足目標(biāo)值的部分。因決策值不可能既超過目標(biāo)值同時又末達(dá)到目標(biāo)值，故恒有 d + d - 0 （2）、絕對約束和目標(biāo)約束 我們把所有等式、不等式約束分為兩部分：絕對約束和目標(biāo)約束。,目標(biāo)規(guī)劃模型,絕對約束是指必須嚴(yán)格滿足的等式約束和不等式約束；如在線性規(guī)劃問題中考慮的約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。設(shè)例 1 中生產(chǎn)A，B產(chǎn)品所需原材料數(shù)量有限制，并且無法從其它渠道予以補(bǔ)充，則構(gòu)成絕對約束。 目標(biāo)約束是目標(biāo)規(guī)劃特有的，我們可以把約束右端項(xiàng)看作要努力追求的目標(biāo)值，但允許發(fā)生正

6、式負(fù)偏差，用在約束中加入正、負(fù)偏差變量來表示，于是稱它們是軟約束。,目標(biāo)規(guī)劃模型,對于例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),目標(biāo)規(guī)劃模型,(3)、優(yōu)先因子與權(quán)系數(shù) 對于多目標(biāo)問題，設(shè)有L個目標(biāo)函數(shù)f1,f2,fL, 決策者在要求達(dá)到這些目標(biāo)時，一般有主次之分。為此，我們引入優(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，次

7、位的目標(biāo)賦于優(yōu)先因子P2、，并規(guī)定 Pi Pi+1，i = 1,2,L-1.,目標(biāo)規(guī)劃模型,即在計算過程中, 首先保證P1級目標(biāo)的實(shí)現(xiàn)，這時可不考慮次級目標(biāo)；而P2級目標(biāo)是在實(shí)現(xiàn)P1級目標(biāo)的基礎(chǔ)上考慮的，以此類推。當(dāng)需要區(qū)別具有相同優(yōu)先因子的若干個目標(biāo)的差別時，可分別賦于它們不同的權(quán)系數(shù)wj 。優(yōu)先因子及權(quán)系數(shù)的值，均由決策者按具體情況來確定 （4）、目標(biāo)規(guī)劃的目標(biāo)函效 目標(biāo)規(guī)劃的目標(biāo)函數(shù)是通過各目標(biāo)約束的正、負(fù)偏差變量和賦于相應(yīng)的優(yōu)先等級來構(gòu)造的,目標(biāo)規(guī)劃模型,目標(biāo)規(guī)劃模型的基本概念 （續(xù)） 決策者的要求是盡可能從某個方向縮小偏離目標(biāo)的數(shù)值。于是，目標(biāo)規(guī)劃的目標(biāo)函數(shù)應(yīng)該是求極?。簃in f

8、f （d +，d -) 其基本形式有三種： 要求恰好達(dá)到目標(biāo)值，即使相應(yīng)目標(biāo)約束的正、負(fù)偏差變量都要盡可能地小。這時取 min （d + + d - )； 要求不超過目標(biāo)值，即使相應(yīng)目標(biāo)約束的正偏差變量要盡可能地小。這時取 min （d + )；,目標(biāo)規(guī)劃模型, 要求不低于目標(biāo)值，即相應(yīng)目標(biāo)約束的負(fù)偏差變量要盡可能地小。這時取 min (d - )； 對于例題, 我們根據(jù)決策者的考慮知 第一優(yōu)先級要求 min（d1+ + d2+ )； 第二優(yōu)先級要求 min（d3+ )； 第三優(yōu)先級要求 min（d4- )； 第四優(yōu)先級要求 min（d1- + 2d2- )，這里, 當(dāng)不能滿足市場需求時, 市

9、場認(rèn)為B產(chǎn)品的重要性是A產(chǎn)品的2倍即減少B產(chǎn)品的影響是A產(chǎn)品的2倍，因此我們引入了2:1的權(quán)系數(shù)。,目標(biāo)規(guī)劃模型,綜合上述分析，我們可得到下列目標(biāo)規(guī)劃模型 Min f = P1（d1+ + d2+ ) + P2 d3+ + P3 d4- + P4（d1- + 2d2- ) s.t. x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+ = 60 (5) 12x1 + 18x2 +d4- -d4+ =252 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4.,目標(biāo)規(guī)劃模型,目標(biāo)規(guī)劃模型的一般形式 根據(jù)上面討論,我們可

10、以得到目標(biāo)規(guī)劃的一般形式如下,目標(biāo)規(guī)劃模型,（LGP）中的第二行是K個目標(biāo)約束，第三行是m個絕對約束，ckj 和gk 是目標(biāo)參數(shù)。,目標(biāo)規(guī)劃與線性規(guī)劃的差異,目標(biāo)規(guī)劃是以線性規(guī)劃為基礎(chǔ)而發(fā)展起來的，但在運(yùn)用中，由于要求不同，有不同于線性規(guī)劃之處： 目標(biāo)規(guī)劃中的目標(biāo)不是單一目標(biāo)而是多目標(biāo)，既有總目標(biāo)又有分目標(biāo)。根據(jù)總目標(biāo)建立部門分目標(biāo)，構(gòu)成目標(biāo)網(wǎng)，形成整個目標(biāo)體系。制定目標(biāo)時應(yīng)注意協(xié)調(diào)各個分目標(biāo)，消除分目標(biāo)間的矛盾，以利總目標(biāo)的實(shí)現(xiàn)；各分目標(biāo)必須服從總目標(biāo)的實(shí)現(xiàn)，不能脫離總目標(biāo)。,線性規(guī)劃只尋求目標(biāo)函數(shù)的最優(yōu)值，即最大值或最小值。而目標(biāo)規(guī)劃，由于是多目標(biāo)，其目標(biāo)函數(shù)不是尋求最大值或最小值，而是尋

11、求這些目標(biāo)與預(yù)計成果的最小差距，差距越小，目標(biāo)實(shí)現(xiàn)的可能性越大。目標(biāo)規(guī)劃中有超出目標(biāo)和未達(dá)目標(biāo)兩種差距。一般以d+代表超出目標(biāo)的差距，d-代表未達(dá)目標(biāo)的差距。d+和d-兩者之一必為零，或兩者均為零。當(dāng)目標(biāo)與預(yù)計成果一致時，兩者均為零，即沒有差距。人們求差距，有時求超過目標(biāo)的差距，有時求未達(dá)目標(biāo)的差距。目標(biāo)規(guī)劃的核心問題是確定目標(biāo)，然后據(jù)以建立模型，求解目標(biāo)與預(yù)計成果的最小差距。,用目標(biāo)規(guī)劃求解問題的過程,構(gòu)造目標(biāo)規(guī)劃的模型,求出滿意解,分析各項(xiàng)目標(biāo)完成的情況,滿意否,據(jù)此制定出決策方案,是,否,例1,(1)、原材料價格上漲，超計劃要高價購買，所以要嚴(yán)格控制。 (2)、市場情況，產(chǎn)品銷售量下降，產(chǎn)品的產(chǎn)量不大于產(chǎn)品的產(chǎn)量。 (3)、充分利用設(shè)備，不希望加班。 (4)、盡可能達(dá)到并超過利潤計劃指標(biāo)56千元。,試確定該廠為達(dá)到以上目標(biāo)的最優(yōu)生產(chǎn)計劃。,設(shè)X1 ，X2為