1、目 標 規 劃 在科學研討、經濟建立和消費實際中，人們經常遇到一類含有多個目的的數學規劃問題，我們稱之為多目的規劃。本章引見一種特殊的多目的規劃叫目的規劃(goal programming)，這是美國學者Charnes等在1952年提出來的。目的規劃在實際中的運用非常廣泛，它的重要特點是對各個目的分級加權與逐級優化，這符合人們處置問題要分別輕重緩急保證重點的思索方式。 本章分目的規劃模型、目的規劃的幾何意義與圖解法和求解目的規劃的單純形方法等三個部分進展引見。 2.1 目的規劃模型 2.1.1 問題提出 為了便于了解目的規劃數學模型的特征及建模思緒, 我們首先舉一個簡單的例子來闡明. 例2.1

2、.1 某公司分廠用一條消費線消費兩種產品A和B ，每周消費線運轉時間為60小時，消費一臺A產品需求4小時，消費一臺B產品需求6小時根據市場預測，A、B產品平均銷售量分別為每周9、8臺，它們銷售利潤分別為12、18萬元。在制定消費方案時，經理思索下述4工程標： 2.1 目的規劃模型2.1.1 問題提出 (續)首先，產量不能超越市場預測的銷售量； 其次，工人加班時間最少； 第三，希望總利潤最大； 最后，要盡能夠滿足市場需求, 當不能滿足時, 市場以為B產品的重要性是A產品的2倍 試建立這個問題的數學模型討論： 假設把總利潤最大看作目的，而把產量不能超越市場預測的銷售量、工人加班時間最少和要盡能夠滿

3、2.1 目的規劃模型 2.1.1 問題提出 (續)足市場需求的目的看作約束，那么可建立一個單目的線性規劃模型 設決策變量 x1，x2 分別為產品A，B的產量 Max Z = 12x1 + 18x2 s.t. 4x1 + 6x2 60 x1 9 x2 8 x1 , x2 0 2.1 目的規劃模型2.1.1 問題提出 (續)容易求得上述線性規劃的最優解為(9,4)T 到 (3,8)T 所在線段上的點, 最優目的值為Z* = 180, 即可選方案有多種. 在實踐上, 這個結果并非完全符合決策者的要求, 它只實現了經理的第一、二、三條目的，而沒有到達最后的一個目的。進一步分析可知，要實現全體目的是不能

4、夠的。2.1 目的規劃模型2.1.2 目的規劃模型的根本概念 把例2.1.1的4個目的表示為不等式.仍設決策變量 x1，x2 分別為產品A，B的產量. 那麼, 第一個目的為: x1 9 ，x2 8 ； 第二個目的為: 4x1 + 6x2 60 ； 第三個目的為: 希望總利潤最大，要表示成不等式需求找到一個目的上界，這里可以估計為252=129 + 188，于是有 12x1 + 18x2 252； 第四個目的為: x1 9，x2 8； 2.1.2 目的規劃模型的根本概念 續下面引入與建立目的規劃數學模型有關的概念 1、正、負偏向變量d +，d - 我們用正偏向變量d + 表示決策值超越目的值的部

5、分；負偏向變量d - 表示決策值缺乏目的值的部分。因決策值不能夠既超越目的值同時又未到達目的值，故恒有 d + d - 0 2、絕對約束和目的約束我們把一切等式、不等式約束分為兩部分：絕對約束和目的約束。2.1.2 目的規劃模型的根本概念 續絕對約束是指必需嚴厲滿足的等式約束和不等式約束；如在線性規劃問題中思索的約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。設例2.1.1 中消費A，B產品所需原資料數量有限制，并且無法從其它渠道予以補充，那么構成絕對約束。目的約束是目的規劃特有的，我們可以把約束右端項看作要努力追求的目的值，但允許發生正式負偏向，用在約束中參與正、負偏向變量

6、來表示，于是稱它們是軟約束。2.1 目的規劃模型 2.1.2 目的規劃模型的根本概念 續 對于例2.1.1, 我們有如下目的約束 x1 + d1- -d1+ = 9 (2.1.1) x2 + d2- -d2+ = 8 (2.1.2) 4x1 + 6x2 + d3- -d3+ = 60 (2.1.3) 12x1+18x2 + d4- -d4+ =252 (2.1.4)2.1 目的規劃模型2.1.2 目的規劃模型的根本概念 續(3)、優先因子與權系數對于多目的問題，設有L個目的函數f1,f2,fL, 決策者在要求到達這些目的時，普通有主次之分。為此，我們引入優先因子Pi ，i = 1,2,L.無妨

7、設預期的目的函數優先順序為f1,f2,fL,我們把要求第一位到達的目的賦于優先因子P1，次位的目的賦于優先因子P2、，并規定 Pi Pi+1，i = 1,2,L-1. 2.1.2 目的規劃模型的根本概念 續 即在計算過程中, 首先保證P1級目的的實現，這時可不思索次級目的；而P2級目的是在實現P1級目的的根底上思索的，以此類推。當需求區別具有一樣優先因子的假設干個目的的差別時，可分別賦于它們不同的權系數wj 。優先因子及權系數的值，均由決策者按詳細情況來確定 4、目的規劃的目的函效 目的規劃的目的函數是經過各目的約束的正、負偏向變量和賦于相應的優先等級來構造的2.1 目的規劃模型2.1.2 目

8、的規劃模型的根本概念 續 決策者的要求是盡能夠從某個方向減少偏離目的的數值。于是，目的規劃的目的函數應該是求極小：min f f d +，d -) 其根本方式有三種： 要求恰好到達目的值，即使相應目的約束的正、負偏向變量都要盡能夠地小。這時取 min d + + d - )； 要求不超越目的值，即使相應目的約束的正偏向變量要盡能夠地小。這時取 min d + )； 2.1.2 目的規劃模型的根本概念 續 要求不低于目的值，即使相應目的約束的負偏向變量要盡能夠地小。這時取 min d - )；對于例2.1.1, 我們根據決策者的思索知第一優先級要求 mind1+ + d2+ )； 第二優先級要求

9、 mind3+ )； 第三優先級要求 mind4- )； 第四優先級要求 mind1- + 2d2- )，這里, 當不能滿足市場需求時, 市場以為B產品的重要性是A產品的2倍即減少B產品的影響是A產品的2倍，因此我們引入了2:1的權系數。 2.1 目的規劃模型 2.1.2 目的規劃模型的根本概念 續綜合上述分析，我們可得到以下目的規劃模型 Min f = P1d1+ + d2+ ) + P2 d3+ + P3 d4- + P4d1- + 2d2- ) s.t. x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+ = 60 (2.1.

10、5) 12x1 + 18x2 +d4- -d4+ =252 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4.2.1 目的規劃模型2.1.3 目的規劃模型的普通方式 根據上面討論,我們可以得到目的規劃的普通方式如下2.1 目的規劃模型2.1.3 目的規劃模型的普通方式 (續)LGP中的第二行是K個目的約束，第三行是m個絕對約束，ckj 和gk 是目的參數。2.2 目的規劃的幾何意義及圖解法 對只具有兩個決策變量的目的規劃的數學模型，我們可以用圖解法來分析求解經過圖解例如，可以看到目的規劃中優先因子，正、負偏向變量及權系數等的幾何意義。 2.2目的規劃的幾何意義及圖解法2.2

11、 目的規劃的幾何意義及圖解法 續下面用圖解法來求解例2.1.1 我們先在平面直角坐標系的第一象限內，作出與各約束條件對應的直線，然后在這些直線旁分別標上 G-i ，i = 1，2，3，4。圖中x，y分別表示問題2.1.5的x1和x2；各直線挪動使之函數值變大、變小的方向用 +、- 表示 di+ ,di- 如圖2.1.1所示 2.2目的規劃的幾何意義及圖解法0 5 10 15 20 y x2015105+-G-1+-G-2+-G-4+-G-3圖2 - 12.2目的規劃的幾何意義及圖解法 下面我們根據目的函數的優先因子來分析求解首先思索第一級具有P1優先因子的目的的實現，在目的函數中要務虛現min

12、d1+ d2+ ),取d1+=d2+ =0.圖 2 2 中陰影部分即表示出該最優解集合的一切點。 我們在第一級目的的最優解集合中找滿足第二優先級要求mind3+ )的最優解.取d3+= 0 ,可得到圖 2 3 中陰影部分即是滿足第一、第二優先級要求的最優解集合。 2.2目的規劃的幾何意義及圖解法圖2 - 20 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)2.2目的規劃的幾何意義及圖解法圖2 3 0 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)2.2目的規劃的幾何意義及圖解法 第三優先級要求 mind

13、4- )，根據圖示可知，d4- 不能夠取0值，我們取使d4- 最小的值72得到圖24 中兩陰影部分的交線(紅色粗線)，其表示滿足第一、第二及第三優先級要求的最優解集合。最后，思索第四優先級要求 mind1- + 2d2- ) ，即要在黑色粗線段中找出最優解。由于d1- 的權因子小于d2- ，因此在這里可以思索取d2- =0。于是解得d1-=5，最優解為A點x = 3，y = 8。 2.2目的規劃的幾何意義及圖解法圖2 4 0 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)2.3 求解目的規劃的單純形方法 目的規劃的數學模型,特別是約束的構造與線性規

14、劃模型沒有本質的區別，只是它的目的不止是一個,雖然其利用優先因子和權系數把目的寫成一個函數的方式, 但在計算中無法按單目的處置, 所以可用單純形法進展適當改良后求解。在組織、構造算法時，我們要思索目的規劃的數學模型一些特點，作以下規定： (1) 由于目的規劃問題的目的函數都是求最小化，所以檢驗數的最優準那么與線性規劃是一樣的； 2.3 求解目的規劃的單純形方法 (續) (2) 由于非基變量的檢驗數中含有不同等級的優先因子， Pi Pi+1，i = 1,2,L-1. 于是從每個檢驗數的整體來看： Pi+1i = 1,2,L-1優先級第k個檢驗數的正、負首先決議于 P1 ，P2 ， ，Pi 優先級

15、第k個檢驗數的正、負。假設P1 級第k個檢驗數為0，那么此檢驗數的正、負取決于P2級第k個檢驗數；假設P2 級第k個檢驗數仍為0，那么此檢驗數的正、負取決于P3級第k個檢驗數，依次類推。換一句話說，當某Pi 級第k個檢驗數為負數時，計算中不用再調查Pj j I 級第k個檢驗數的正、負情況； 2.3 求解目的規劃的單純形方法 (續)3根據LGP模型特征，當不含絕對約束時，di- i=1,2, ,K構成了一組根本可行解。在尋覓單純形法初始可行點時，這個特點是很有用的。 解目的規劃問題的單純形法的計算步驟 (1)建立初始單純形表在表中將檢驗數行按優先因子個數分別列成K行。初始的檢驗數需根據初始可行解

16、計算出來，方法同根本單純形法。當不含絕對約束時，di- i=1,2, ,K構成了一組根本可行解，這時只需利用相應單位向量把各級目的行中對應di- i=1,2, ,K的量消成0即可得到初始單純形表。置k 1； 2.3 求解目的規劃的單純形方法 (續) (2)檢查當前第k行中能否存在大于0，且對應的前k-1行的同列檢驗數為零的檢驗數。假設有取其中最大者對應的變量為換入變量，轉(3)。假設無這樣的檢驗數，那么轉(5)； (3)按單純形法中的最小比值規那么確定換出變量，當存在兩個和兩個以上一樣的最小比值時，選取具有較高優先級別的變量為換出變量，轉4； 2.3 求解目的規劃的單純形方法 (續) (4)按

17、單純形法進展基變換運算，建立新的單純形表，留意：要對一切的行進展轉軸運算前往(2)； (5)當k K 時，計算終了。表中的解即為稱心解。否那么置k = k+1，前往2。 2.3 求解目的規劃的單純形方法 (續)例2.3.1 試用單純形法來求解例2.1.1的目的規劃模型(2.1.5) Min f = P1d1+ + d2+ ) + P2 d3+ + P3 d4- + P4d1- + 2d2- ) s.t. x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+ = 60 12x1 + 18x2 +d4- -d4+ =252 x1 , x2

18、 , di- ,di+ 0 , i = 1,2,3,4. 2.3 求解目的規劃的單純形方法 (續)解: 首先處置初始根本可行解對應的各級檢驗數。 由于P1 , P2 優先級對應的目的函數中不含di- , 所以其檢驗數只需取系數負值。分別為 ( 0，0，0，-1，0，-1，0，0，0，0 ；0)和 ( 0，0，0， 0，0，0，0，-1，0，0 ；0) x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10-100000P20000000-1000P300000000-100P400-10-2000000d1-101-10000009d2-01001-100008d3-4

19、600001-10060d4-12180000001-1252x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10-100000P20000000-1000P312180000000-1252P400-10-2000000d1-101-10000009d2-0*1001-100008d3-4600001-10060d4-12180000001-12522.3 求解目的規劃的單純形方法 (續)P3 優先級對應的目的函數中含d4- ,所以其檢驗數需求把第四個約束行加到取負值的這一行上，得到 ( 12，18，0，0，0，0，0，0，0，-1；252 )TP4 優先級對應的目

20、的函數中含d1- + 2d2- )，所以其檢驗數需求把第一個約束行與第二個約束行的2倍加到取系數負值的這一行上，得到 ( 1，2，0，-1，0，-2，0，0，0，0；25 )。列目的規劃的初始單純形表 x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10-100000P20000000-1000P312180000000-1252P4120-10-2000025d1-101-10000009d2-0*1001-1000088d3-4600001-1006010d4-12180000001-1252142.3 求解目的規劃的單純形方法 (續)1k = 1，在初始單純形表

21、中基變量為 d1-,d2-,d3-,d4-)T =9，8,60，252)T ；2由于P1與P2優先級的檢驗數均曾經為非正，所以這個單純形表對P1與P2優先級是最優單純形表；3下面思索P3優先級，第二列的檢驗數為18，此為進基變量，計算相應的比值 bi/aij 寫在 列。經過比較，得到d2- 對應的比值最小，于是取a22標為 * 號為轉軸元進展矩陣行變換得到新的單純形表； x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10-100000P20000000-1000P312000-1818000-1108P4100-1-2000009d1-101-100000099x201001-100008d3-*4000-661-100123d4-12000-1818001-110892.3 求解目的規劃的單純形方法 (續)4下面繼續思索P3優先級，第一列的檢驗數為18，此為進基變量，計算相應的比值 bi/aij 寫在 列。經過比較，得到d3- 對應的比值最小，于是取a31標為 * 號為轉軸元進展矩陣行變換得到新的單純形表； x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10-100000P20000000-1000P3000000-