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

2、.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項目標：,2.1 目標規(guī)劃模型,2.1.1 問題提出 (續(xù)) 首先，產(chǎn)量不能超過市場預測的銷售量； 其次，工人加班時間最少； 第三，希望總利潤最大； 最后，要盡可能滿足市場需求, 當不能滿足時, 市場認為B產(chǎn)品的重要性是A產(chǎn)品的2倍 試建立這個問題的數(shù)學模型 討論： 若把總利潤最大看作目標，而把產(chǎn)量不能超過市場預測的銷售量、工人加班時間最少和要盡可

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

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

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

6、生正式負偏差，用在約束中加入正、負偏差變量來表示，于是稱它們是軟約束。,2.1 目標規(guī)劃模型,2.1.2 目標規(guī)劃模型的基本概念 （續(xù)） 對于例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 目標規(guī)劃模型,2.1.2 目標規(guī)劃模型的基本概念 （續(xù)） (3)、優(yōu)先因子與權系數(shù) 對于多目標問題，設有L個目標函數(shù)f1,f2,fL, 決策者在要求達到這些目標時，一般有主次

7、之分。為此，我們引入優(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.,2.1.2 目標規(guī)劃模型的基本概念 （續(xù)） 即在計算過程中, 首先保證P1級目標的實現(xiàn)，這時可不考慮次級目標；而P2級目標是在實現(xiàn)P1級目標的基礎上考慮的，以此類推。當需要區(qū)別具有相同優(yōu)先因子的若干個目標的差別時，可分別賦于它們不同的權系數(shù)wj 。優(yōu)先因子及權系數(shù)的值，均由決策者按具體情況來確定 （4）、目標規(guī)劃的目標函效 目標規(guī)劃的目標函數(shù)是通過各目標約束的正、負偏差

8、變量和賦于相應的優(yōu)先等級來構造的,2.1 目標規(guī)劃模型,2.1.2 目標規(guī)劃模型的基本概念 （續(xù)） 決策者的要求是盡可能從某個方向縮小偏離目標的數(shù)值。于是，目標規(guī)劃的目標函數(shù)應該是求極?。簃in f f （d +，d -) 其基本形式有三種： 要求恰好達到目標值，即使相應目標約束的正、負偏差變量都要盡可能地小。這時取 min （d + + d - )； 要求不超過目標值，即使相應目標約束的正偏差變量要盡可能地小。這時取 min （d + )；,2.1.2 目標規(guī)劃模型的基本概念 （續(xù)） 要求不低于目標值，即使相應目標約束的負偏差變量要盡可能地小。這時取 min （d - )； 對于例2.1.1

9、, 我們根據(jù)決策者的考慮知 第一優(yōu)先級要求 min（d1+ + d2+ )； 第二優(yōu)先級要求 min（d3+ )； 第三優(yōu)先級要求 min（d4- )； 第四優(yōu)先級要求 min（d1- + 2d2- )，這里, 當不能滿足市場需求時, 市場認為B產(chǎn)品的重要性是A產(chǎn)品的2倍即減少B產(chǎn)品的影響是A產(chǎn)品的2倍，因此我們引入了2:1的權系數(shù)。,2.1 目標規(guī)劃模型,2.1.2 目標規(guī)劃模型的基本概念 （續(xù)） 綜合上述分析，我們可得到下列目標規(guī)劃模型 Min f = P1（d1+ + d2+ ) + P2 d3+ + P3 d4- + P4（d1- + 2d2- ) s.t. x1 + d1- -d1+

10、 = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+ = 60 (2.1.5) 12x1 + 18x2 +d4- -d4+ =252 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4.,2.1 目標規(guī)劃模型,2.1.3 目標規(guī)劃模型的一般形式 根據(jù)上面討論,我們可以得到目標規(guī)劃的一般形式如下,2.1 目標規(guī)劃模型,2.1.3 目標規(guī)劃模型的一般形式 (續(xù)) （LGP）中的第二行是K個目標約束，第三行是m個絕對約束，ckj 和gk 是目標參數(shù)。 2.2 目標規(guī)劃的幾何意義及圖解法 對只具有兩個決策變量的目標規(guī)劃的數(shù)學模型，我們可以用圖解法來分

11、析求解通過圖解示例，可以看到目標規(guī)劃中優(yōu)先因子，正、負偏差變量及權系數(shù)等的幾何意義。,2.2目標規(guī)劃的幾何意義及圖解法,2.2 目標規(guī)劃的幾何意義及圖解法 （續(xù)） 下面用圖解法來求解例2.1.1 我們先在平面直角坐標系的第一象限內(nèi)，作出與各約束條件對應的直線，然后在這些直線旁分別標上 G-i ，i = 1，2，3，4。圖中x，y分別表示問題（2.1.5）的x1和x2；各直線移動使之函數(shù)值變大、變小的方向用 +、- 表示 di+ ,di- （如圖2.1.1所示）,2.2目標規(guī)劃的幾何意義及圖解法,2.2目標規(guī)劃的幾何意義及圖解法,下面我們根據(jù)目標函數(shù)的優(yōu)先因子來分析求解首先考慮第一級具有P1優(yōu)先

12、因子的目標的實現(xiàn)，在目標函數(shù)中要求實現(xiàn)min（d1+ d2+ ),取d1+=d2+ =0.圖 2 2 中陰影部分即表示出該最優(yōu)解集合的所有點。 我們在第一級目標的最優(yōu)解集合中找滿足第二優(yōu)先級要求min（d3+ )的最優(yōu)解.取d3+= 0 ,可得到圖 2 3 中陰影部分即是滿足第一、第二優(yōu)先級要求的最優(yōu)解集合。,2.2目標規(guī)劃的幾何意義及圖解法,圖2 - 2,2.2目標規(guī)劃的幾何意義及圖解法,圖2 3,2.2目標規(guī)劃的幾何意義及圖解法,第三優(yōu)先級要求 min（d4- )，根據(jù)圖示可知，d4- 不可能取0值，我們?nèi)∈筪4- 最小的值72得到圖24 中兩陰影部分的交線(紅色粗線)，其表示滿足第一、第

13、二及第三優(yōu)先級要求的最優(yōu)解集合。 最后，考慮第四優(yōu)先級要求 min（d1- + 2d2- ) ，即要在黑色粗線段中找出最優(yōu)解。由于d1- 的權因子小于d2- ，因此在這里可以考慮取d2- =0。于是解得d1-=5，最優(yōu)解為A點x = 3，y = 8。,2.2目標規(guī)劃的幾何意義及圖解法,圖2 4,2.3 求解目標規(guī)劃的單純形方法,目標規(guī)劃的數(shù)學模型,特別是約束的結構與線性規(guī)劃模型沒有本質(zhì)的區(qū)別，只是它的目標不止是一個,雖然其利用優(yōu)先因子和權系數(shù)把目標寫成一個函數(shù)的形式, 但在計算中無法按單目標處理, 所以可用單純形法進行適當改進后求解。在組織、構造算法時，我們要考慮目標規(guī)劃的數(shù)學模型一些特點，作

14、以下規(guī)定： (1) 因為目標規(guī)劃問題的目標函數(shù)都是求最小化，所以檢驗數(shù)的最優(yōu)準則與線性規(guī)劃是相同的；,2.3 求解目標規(guī)劃的單純形方法 (續(xù)),(2) 因為非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子， Pi Pi+1，i = 1,2,L-1. 于是從每個檢驗數(shù)的整體來看： Pi+1（i = 1,2,L-1）優(yōu)先級第k個檢驗數(shù)的正、負首先決定于 P1 ，P2 ， ，Pi 優(yōu)先級第k個檢驗數(shù)的正、負。若P1 級第k個檢驗數(shù)為0，則此檢驗數(shù)的正、負取決于P2級第k個檢驗數(shù)；若P2 級第k個檢驗數(shù)仍為0，則此檢驗數(shù)的正、負取決于P3級第k個檢驗數(shù)，依次類推。換一句話說，當某Pi 級第k個檢驗數(shù)為負數(shù)時，

15、計算中不必再考察Pj（ j I ）級第k個檢驗數(shù)的正、負情況；,2.3 求解目標規(guī)劃的單純形方法 (續(xù)),（3）根據(jù)（LGP）模型特征，當不含絕對約束時，di- （i=1,2, ,K）構成了一組基本可行解。在尋找單純形法初始可行點時，這個特點是很有用的。 解目標規(guī)劃問題的單純形法的計算步驟 (1)建立初始單純形表在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行。初始的檢驗數(shù)需根據(jù)初始可行解計算出來，方法同基本單純形法。當不含絕對約束時，di- （i=1,2, ,K）構成了一組基本可行解，這時只需利用相應單位向量把各級目標行中對應di- （i=1,2, ,K）的量消成0即可得到初始單純形表。置k 1；

16、,2.3 求解目標規(guī)劃的單純形方法 (續(xù)),(2)檢查當前第k行中是否存在大于0，且對應的前k-1行的同列檢驗數(shù)為零的檢驗數(shù)。若有取其中最大者對應的變量為換入變量，轉(zhuǎn)(3)。若無這樣的檢驗數(shù)，則轉(zhuǎn)(5)； (3)按單純形法中的最小比值規(guī)則確定換出變量，當存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量，轉(zhuǎn)（4）；,2.3 求解目標規(guī)劃的單純形方法 (續(xù)),(4)按單純形法進行基變換運算，建立新的單純形表，（注意：要對所有的行進行轉(zhuǎn)軸運算）返回(2)； (5)當k K 時，計算結束。表中的解即為滿意解。否則置k = k+1，返回（2）。,2.3 求解目標規(guī)劃的單純形方法

17、(續(xù)),例2.3.1 試用單純形法來求解例2.1.1的目標規(guī)劃模型(2.1.5) 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.,2.3 求解目標規(guī)劃的單純形方法 (續(xù)),解: 首先處理初始基本可行解對應的各級檢驗數(shù)。 由于P1 , P2 優(yōu)先級對應的目標函數(shù)中不含di

18、- , 所以其檢驗數(shù)只需取系數(shù)負值。分別為 ( 0，0，0，-1，0，-1，0，0，0，0 ；0) 和 ( 0，0，0， 0，0，0，0，-1，0，0 ；0),2.3 求解目標規(guī)劃的單純形方法 (續(xù)),P3 優(yōu)先級對應的目標函數(shù)中含d4- ,所以其檢驗數(shù)需要把第四個約束行加到取負值的這一行上，得到 ( 12，18，0，0，0，0，0，0，0，-1；252 )T P4 優(yōu)先級對應的目標函數(shù)中含（d1- + 2d2- )，所以其檢驗數(shù)需要把第一個約束行與第二個約束行的2倍加到取系數(shù)負值的這一行上，得到 ( 1，2，0，-1，0，-2，0，0，0，0；25 )。 列目標規(guī)劃的初始單純形表,2.3 求解目標規(guī)劃的單純形方法 (續(xù)),（1）k = 1，在初始單純形表