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

1、第九章 目標規(guī)劃 Goal Programming,9.1 目標規(guī)劃模型 9.2 目標規(guī)劃的幾何意義與圖解法,在科學研究、經(jīng)濟建設和生產實踐中，人們經(jīng)常遇到一類含有多個目標的數(shù)學規(guī)劃問題，我們稱之為多目標規(guī)劃。本章介紹一種特殊的多目標規(guī)劃叫目標規(guī)劃(goal programming)，這是美國學者Charnes等在1952年提出來的。目標規(guī)劃在實踐中的應用十分廣泛，它的重要特點是對各個目標分級加權與逐級優(yōu)化，這符合人們處理問題要分別輕重緩急保證重點的思考方式,9.1 目標規(guī)劃模型,1) 問題提出 為了便于理解目標規(guī)劃數(shù)學模型的特征及建模思路, 我們首先舉一個簡單的例子來說明. 例 1 某公司分

2、廠用一條生產線生產兩種產品A和B ，每周生產線運行時間為60小時，生產一臺A產品需要4小時，生產一臺B產品需要6小時根據(jù)市場預測，A、B產品平均銷售量分別為每周9、8臺，它們銷售利潤分別為12、18萬元。在制定生產計劃時，經(jīng)理考慮下述4項目標,首先，產量不能超過市場預測的銷售量； 其次，工人加班時間最少； 第三，希望總利潤最大； 最后，要盡可能滿足市場需求, 當不能滿足時, 市場認為B產品的重要性是A產品的2倍 試建立這個問題的數(shù)學模型 討論： 若把總利潤最大看作目標，而把產量不能超過市場預測的銷售量、工人加班時間最少和要盡可能滿足市場需求的目標看作約束，則可建立一個單目標線性規(guī)劃模型,設決策

3、變量 x1，x2 分別為產品A，B的產量 Max Z = 12x1 + 18x2 s.t. 4x1 + 6x2 60 x1 9 x2 8 x1 , x2 0 容易求得上述線性規(guī)劃的最優(yōu)解為(9,4)T 到 (3,8)T 所在線段上的點, 最優(yōu)目標值為Z* = 180, 即可選方案有多種. 在實際上, 這個結果并非完全符合決策者的要求, 它只實現(xiàn)了經(jīng)理的第一、二、三條目標，而沒有達到最后的一個目標。進一步分析可知，要實現(xiàn)全體目標是不可能的,2) 目標規(guī)劃模型的基本概念 把例1的4個目標表示為不等式.仍設決策變量 x1，x2 分別為產品A，B的產量. 那么, 第一個目標為: x1 9 ，x2 8

4、； 第二個目標為: 4x1 + 6x2 60 ； 第三個目標為: 希望總利潤最大，要表示成不等式需要找到一個目標下界，這里可以估計為252（=129 + 188），于是有 12x1 + 18x2 252； 第四個目標為: x1 9，x2 8,下面引入與建立目標規(guī)劃數(shù)學模型有關的概念 （1）正、負偏差變量d +，d - 我們用正偏差變量d + 表示決策值超過目標值的部分；負偏差變量d - 表示決策值不足目標值的部分。因決策值不可能既超過目標值同時又末達到目標值，故恒有 d + d - 0 （2）絕對約束和目標約束 我們把所有等式、不等式約束分為兩部分：絕對約束和目標約束,絕對約束 指必須嚴格滿足

5、的等式約束和不等式約束；如在線性規(guī)劃問題中考慮的約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。設例1 中生產A，B產品所需原材料數(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)

6、先因子與權系數(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ī)定 Pi Pi+1，i = 1,2,L-1. 即在計算過程中, 首先保證P1級目標的實現(xiàn)，這時可不考慮次級目標；而P2級目標是在實現(xiàn)P1級目標的基礎上考慮的，以此類推。當需要區(qū)別具有相同優(yōu)先因子的若干個目標的差別時，可分別賦于它們不同的權系數(shù)wj 。優(yōu)先因子及權系數(shù)的值，均由決策者按具體情況來確定,4）目標規(guī)劃

7、的目標函效 目標規(guī)劃的目標函數(shù)是通過各目標約束的正、負偏差變量和賦于相應的優(yōu)先等級來構造的 決策者的要求是盡可能從某個方向縮小偏離目標的數(shù)值。于是，目標規(guī)劃的目標函數(shù)應該是求極?。?Min f f （d +，d -) 其基本形式有三種,要求恰好達到目標值，即使相應目標約束的正、負偏差變量都要盡可能地小。 這時取 Min （d + + d - )； 要求不超過目標值，即使相應目標約束的正偏差變量要盡可能地小。 這時取 Min （d + )； 要求不低于目標值，即使相應目標約束的負偏差變量要盡可能地小。 這時取 Min （d -,對于例 1, 我們根據(jù)決策者的考慮知 第一優(yōu)先級要求 Min（d1+

8、 + d2+ )； 第二優(yōu)先級要求 Min（d3+ )； 第三優(yōu)先級要求 Min（d4- )； 第四優(yōu)先級要求 Min（d1- + 2d2- )， 這里, 當不能滿足市場需求時, 市場認為B產品的重要性是A產品的2倍即減少B產品的影響是A產品的2倍，因此我們引入了2:1的權系數(shù),綜合上述分析，可得到下列目標規(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 12x1 + 18x2 +d4

9、- -d4+ = 252 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4,3) 目標規(guī)劃模型的一般形式,式中的第二行是L個目標約束，第三行是m個絕對約束，clj 和gl 是目標參數(shù),例2 甲 乙 有效工時 金工 4 2 400 裝配 2 4 500 收益 100 80 LP： Max Z=100X1 + 80X2 2X1+4X2 500 s.t 4X1+2X2 400 X* =(50,100) X1 , X2 0 Z* =13000,目標：去年總收益9000，增長要求11.1% 即：今年希望總收益不低于10000 引入 d+：決策超過目標值部分(正偏差變量) d-：決策不

10、足目標值部分(負偏差變量) 目標約束： 100X1+80X2 -d+d- =10000 d+d- =0 d+,d- 0,例3 資源擁有量 原材料(公斤) 2 1 11 設備(小時) 1 2 10 利潤(千元/件) 8 10 原材料價格上漲，超計劃要高價購買，所以要嚴格控制 市場情況，產品銷售量下降，產品的產量不大于產品的產量 充分利用設備，不希望加班 盡可能達到并超過利潤計劃指標56千元,建模： 設定約束條件。(目標約束、絕對約束) 規(guī)定目標約束優(yōu)先級 建立模型 設X1 ，X2為產品，產品產量,d1- : X1產量不足X2 部分 d1+ : X1產量超過X2 部分 d2- : 設備使用不足10

11、 部分 d2+ :設備使用超過10 部分 d3- : 利潤不足56 部分 d3+ :利潤超過56 部分,或 Min Z1 = d1+ Min Z2 = d2- +d2+ Min Z3 = d3,Min Z=p1d1+p2(d2-+d2+)+p3(d3,對只具有兩個決策變量的目標規(guī)劃的數(shù)學模型，我們可以用圖解法來分析求解通過圖解示例，可以看到目標規(guī)劃中優(yōu)先因子，正、負偏差變量及權系數(shù)等的幾何意義。 下面用圖解法來求解例1 我們先在平面直角坐標系的第一象限內，作出與各約束條件對應的直線，然后在這些直線旁分別標上 G-i ，i = 1，2，3，4。圖中x，y分別表示問題的x1和x2；各直線移動使之函數(shù)值變大、變小的方向用 +、- 表示 di+ ,di-,9.2 目標規(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 12x1 + 18x2 +d4- -d4+ = 252 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4,