版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、第 七 章,目 標(biāo) 規(guī) 劃,第七章 目標(biāo)規(guī)劃,在科學(xué)研究、經(jīng)濟建設(shè)和生產(chǎn)實踐中,人們經(jīng)常遇到一類含有多個目標(biāo)的數(shù)學(xué)規(guī)劃問題,我們稱之為多目標(biāo)規(guī)劃。本章介紹一種特殊的多目標(biāo)規(guī)劃叫目標(biāo)規(guī)劃(goal programming),這是美國學(xué)者Charnes等在1952年提出來的。目標(biāo)規(guī)劃在實踐中的應(yīng)用十分廣泛,它的重要特點是對各個目標(biāo)分級加權(quán)與逐級優(yōu)化,這符合人們處理問題要分別輕重緩急保證重點的思考方式。 本章
2、分目標(biāo)規(guī)劃模型、目標(biāo)規(guī)劃的幾何意義與圖解法和求解目標(biāo)規(guī)劃的單純形方法等三個部分進行介紹。,7.1 目標(biāo)規(guī)劃模型,7.1.1 問題提出 為了便于理解目標(biāo)規(guī)劃數(shù)學(xué)模型的特征及建模思路, 我們首先舉一個簡單的例子來說明. 例7.1.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ù)市場預(yù)測,A、B產(chǎn)品平均銷售量分別為
3、每周9、8臺,它們銷售利潤分別為12、18萬元。在制定生產(chǎn)計劃時,經(jīng)理考慮下述4項目標(biāo):,7.1 目標(biāo)規(guī)劃模型,7.1.1 問題提出 (續(xù))首先,產(chǎn)量不能超過市場預(yù)測的銷售量; 其次,工人加班時間最少; 第三,希望總利潤最大; 最后,要盡可能滿足市場需求, 當(dāng)不能滿足時, 市場認(rèn)為B產(chǎn)品的重要性是A產(chǎn)品的2倍. 試建立這個問題的數(shù)學(xué)模型.討論:
4、 若把總利潤最大看作目標(biāo),而把產(chǎn)量不能超過市場預(yù)測,7.1 目標(biāo)規(guī)劃模型,7.1.1 問題提出 (續(xù))的銷售量、工人加班時間最少和要盡可能滿足市場需求的目標(biāo)看作約束,則可建立一個單目標(biāo)線性規(guī)劃模型 設(shè)決策變量 x1,x2 分別為產(chǎn)品A,B的產(chǎn)量 ? Max Z = 12x1 + 18x2 ? s.t. 4x1 + 6x2 ? 60 ?
5、 x1 ? 9 ? x2 ? 8 ? x1 , x2 ? 0,7.1 目標(biāo)規(guī)劃模型,7.1.1 問題提出 (續(xù))容易求得上述線性規(guī)劃的最優(yōu)解為(9,4)T 到 (3,8)T 所在線段上的點, 最優(yōu)目標(biāo)值為Z* = 180, 即可選方案有多種. 在實際上, 這個結(jié)果并非完全符合決策者的要求, 它只實現(xiàn)了經(jīng)理的第一、二、三條目標(biāo),而沒
6、有達到最后的一個目標(biāo)。進一步分析可知,要實現(xiàn)全體目標(biāo)是不可能的。,7.1 目標(biāo)規(guī)劃模型,7.1.2 目標(biāo)規(guī)劃模型的基本概念 把例7.1.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)上界
7、,這里可以估計為252(=12?9 + 18?8),于是有 12x1 + 18x2 ? 252; 第四個目標(biāo)為: x1 ? 9,x2 ? 8;,7.1 目標(biāo)規(guī)劃模型,7.1.2 目標(biāo)規(guī)劃模型的基本概念 (續(xù))下面引入與建立目標(biāo)規(guī)劃數(shù)學(xué)模型有關(guān)的概念. (1)、正、負(fù)偏差變量d +,d - 我們用正偏差變量d + 表示決策值超過目標(biāo)值的部分;負(fù)偏差變量
8、d - 表示決策值不足目標(biāo)值的部分。因決策值不可能既超過目標(biāo)值同時又末達到目標(biāo)值,故恒有 d + ?d - = 0 . (2)、絕對約束和目標(biāo)約束我們把所有等式、不等式約束分為兩部分:絕對約束和目標(biāo)約束。,7.1 目標(biāo)規(guī)劃模型,7.1.2 目標(biāo)規(guī)劃模型的基本概念 (續(xù))絕對約束是指必須嚴(yán)格滿足的等式約束和不等式約束;如在線性規(guī)劃問題中考慮的約束條件,不能滿足這些約束條件的解稱為非可行解,所以它們是硬約束。設(shè)例7.1.1 中
9、生產(chǎn)A,B產(chǎn)品所需原材料數(shù)量有限制,并且無法從其它渠道予以補充,則構(gòu)成絕對約束。目標(biāo)約束是目標(biāo)規(guī)劃特有的,我們可以把約束右端項看作要努力追求的目標(biāo)值,但允許發(fā)生正式負(fù)偏差,用在約束中加入正、負(fù)偏差變量來表示,于是稱它們是軟約束。,7.1 目標(biāo)規(guī)劃模型,7.1.2 目標(biāo)規(guī)劃模型的基本概念 (續(xù)) 對于例7.1.1, 我們有如下目標(biāo)約束 x1 + d1- -d1+
10、 = 9 (7.1.1) x2 + d2- -d2+ = 8 (7.1.2) 4x1 + 6x2 + d3- -d3+ = 60 (7.1.3) 12x1+18x2 + d4- -d4+ =252 (7.1.4),7.1 目標(biāo)規(guī)劃模型,7.1.2 目標(biāo)規(guī)劃模型的基本概念 (續(xù))(3)、優(yōu)先因子與權(quán)系數(shù).對于多
11、目標(biāo)問題,設(shè)有L個目標(biāo)函數(shù)f1,f2,?,fL, 決策者在要求達到這些目標(biāo)時,一般有主次之分。為此,我們引入優(yōu)先因子Pi ,i = 1,2,?,L.無妨設(shè)預(yù)期的目標(biāo)函數(shù)優(yōu)先順序為f1,f2,?,fL,我們把要求第一位達到的目標(biāo)賦于優(yōu)先因子P1,次位的目標(biāo)賦于優(yōu)先因子P2、…,并規(guī)定 Pi >> Pi+1,i = 1,2,?,L-1.,7.1 目標(biāo)規(guī)劃模型,7.1.2 目標(biāo)規(guī)劃模型的基本概念 (續(xù)) 即在計算過程中,
12、 首先保證P1級目標(biāo)的實現(xiàn),這時可不考慮次級目標(biāo);而P2級目標(biāo)是在實現(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)造的.,§7.1 目標(biāo)規(guī)劃模型,7.1.2 目標(biāo)規(guī)劃模型的基本概念
13、 (續(xù)) 決策者的要求是盡可能從某個方向縮小偏離目標(biāo)的數(shù)值。于是,目標(biāo)規(guī)劃的目標(biāo)函數(shù)應(yīng)該是求極?。簃in f = f (d +,d -). 其基本形式有三種: ① 要求恰好達到目標(biāo)值,即使相應(yīng)目標(biāo)約束的正、負(fù)偏差變量都要盡可能地小。這時取 min (d + + d - ); ② 要求不超過目標(biāo)值,即使相應(yīng)目標(biāo)約束的正偏差變量要盡可能地小。這時取 mi
14、n (d + );,§7.1 目標(biāo)規(guī)劃模型,7.1.2 目標(biāo)規(guī)劃模型的基本概念 (續(xù)) ③ 要求不低于目標(biāo)值,即使相應(yīng)目標(biāo)約束的負(fù)偏差變量要盡可能地小。這時取 min (d - );對于例7.1.1, 我們根據(jù)決策者的考慮知第一優(yōu)先級要求 min(d1+ + d2+ ); 第二優(yōu)先級要求 min(d3+ ); 第三優(yōu)先級要求 min(d4- ); 第四優(yōu)先級要求 min(d1-
15、 + 2d2- ),這里, 當(dāng)不能滿足市場需求時, 市場認(rèn)為B產(chǎn)品的重要性是A產(chǎn)品的2倍.即減少B產(chǎn)品的影響是A產(chǎn)品的2倍,因此我們引入了2:1的權(quán)系數(shù)。,§7.1 目標(biāo)規(guī)劃模型,7.1.2 目標(biāo)規(guī)劃模型的基本概念 (續(xù))綜合上述分析,我們可得到下列目標(biāo)規(guī)劃模型 ? Min f = P1(d1+ + d2+ ) + P2 d3+ + P3 d4- + P4(d1- + 2d2- ) ? s.t.
16、 x1 + d1- -d1+ = 9 ? x2 + d2- -d2+ = 8 ? 4x1 + 6x2 + d3- -d3+ = 60 (7.1.5) ? 12x1 + 18x2 +
17、d4- -d4+ =252 ? x1 , x2 , di- ,di+ ? 0 , i = 1,2,3,4.,§7.1 目標(biāo)規(guī)劃模型,7.1.3 目標(biāo)規(guī)劃模型的一般形式 根據(jù)上面討論,我們可以得到目標(biāo)規(guī)劃的一般形式如下,,§7.1 目標(biāo)規(guī)劃模型,7.1.3 目標(biāo)規(guī)劃模型的一般形式 (續(xù))(LGP)中的第二行是K個目標(biāo)約束,第三行是m個絕對約束
18、,ckj 和gk 是目標(biāo)參數(shù)。§7.2 目標(biāo)規(guī)劃的幾何意義及圖解法 對只具有兩個決策變量的目標(biāo)規(guī)劃的數(shù)學(xué)模型,我們可以用圖解法來分析求解.通過圖解示例,可以看到目標(biāo)規(guī)劃中優(yōu)先因子,正、負(fù)偏差變量及權(quán)系數(shù)等的幾何意義。,§7.2目標(biāo)規(guī)劃的幾何意義及圖解法,§7.2 目標(biāo)規(guī)劃的幾何意義及圖解法 (續(xù))下面用圖解法來求解例7.1.1 我們先在平面直角坐標(biāo)系的第一象限內(nèi),作出與各約束條件對應(yīng)
19、的直線,然后在這些直線旁分別標(biāo)上 G-i ,i = 1,2,3,4。圖中x,y分別表示問題(7.1.5)的x1和x2;各直線移動使之函數(shù)值變大、變小的方向用 +、- 表示 di+ ,di- (如圖7.1.1所示).,§7.2目標(biāo)規(guī)劃的幾何意義及圖解法,§7.2目標(biāo)規(guī)劃的幾何意義及圖解法,下面我們根據(jù)目標(biāo)函數(shù)的優(yōu)先因子來分析求解.首先考慮第一級具有P1優(yōu)先因子的目標(biāo)的實現(xiàn),在目標(biāo)函數(shù)中要求實現(xiàn)min(d1++ d
20、2+ ),取d1+=d2+ =0.圖 7 – 2 中陰影部分即表示出該最優(yōu)解集合的所有點。 我們在第一級目標(biāo)的最優(yōu)解集合中找滿足第二優(yōu)先級要求min(d3+ )的最優(yōu)解.取d3+= 0 ,可得到圖 7 – 3 中陰影部分即是滿足第一、第二優(yōu)先級要求的最優(yōu)解集合。,§7.2目標(biāo)規(guī)劃的幾何意義及圖解法,圖7 - 2,,§7.2目標(biāo)規(guī)劃的幾何意義及圖解法,圖7 – 3,,§7.2目標(biāo)規(guī)劃的幾
21、何意義及圖解法,第三優(yōu)先級要求 min(d4- ),根據(jù)圖示可知,d4- 不可能取0值,我們?nèi)∈筪4- 最小的值72得到圖7–4 中兩陰影部分的交線(黑色粗線),其表示滿足第一、第二及第三優(yōu)先級要求的最優(yōu)解集合。最后,考慮第四優(yōu)先級要求 min(d1- + 2d2- ) ,即要在黑色粗線段中找出最優(yōu)解。由于d1- 的權(quán)因子小于d2- ,因此在這里可以考慮取d2- =0。于是解得d1-=5,最優(yōu)解為A點x = 3,y = 8。,&
22、#167;7.2目標(biāo)規(guī)劃的幾何意義及圖解法,圖7 – 4,,,§7.3 求解目標(biāo)規(guī)劃的單純形方法,目標(biāo)規(guī)劃的數(shù)學(xué)模型,特別是約束的結(jié)構(gòu)與線性規(guī)劃模型沒有本質(zhì)的區(qū)別,只是它的目標(biāo)不止是一個,雖然其利用優(yōu)先因子和權(quán)系數(shù)把目標(biāo)寫成一個函數(shù)的形式, 但在計算中無法按單目標(biāo)處理, 所以可用單純形法進行適當(dāng)改進后求解。在組織、構(gòu)造算法時,我們要考慮目標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點,作以下規(guī)定: (1) 因為目標(biāo)規(guī)劃問題的目標(biāo)
23、函數(shù)都是求最小化,所以檢驗數(shù)的最優(yōu)準(zhǔn)則與線性規(guī)劃是相同的;,§7.3 求解目標(biāo)規(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ù)的正、負(fù)首先決定于 P1 ,P2 ,… ,Pi 優(yōu)先級第k個檢驗數(shù)的正、負(fù)。若P1 級第k個檢驗數(shù)為0,則此檢驗數(shù)的正、
24、負(fù)取決于P2級第k個檢驗數(shù);若P2 級第k個檢驗數(shù)仍為0,則此檢驗數(shù)的正、負(fù)取決于P3級第k個檢驗數(shù),依次類推。換一句話說,當(dāng)某Pi 級第k個檢驗數(shù)為負(fù)數(shù)時,計算中不必再考察Pj( j > I )級第k個檢驗數(shù)的正、負(fù)情況;,§7.3 求解目標(biāo)規(guī)劃的單純形方法 (續(xù)),(3)根據(jù)(LGP)模型特征,當(dāng)不含絕對約束時,di- (i=1,2,… ,K)構(gòu)成了一組基本可行解。在尋找單純形法初始可行點時,這個特點是很有用的。
25、 解目標(biāo)規(guī)劃問題的單純形法的計算步驟 (1)建立初始單純形表.在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行。初始的檢驗數(shù)需根據(jù)初始可行解計算出來,方法同基本單純形法。當(dāng)不含絕對約束時,di- (i=1,2,… ,K)構(gòu)成了一組基本可行解,這時只需利用相應(yīng)單位向量把各級目標(biāo)行中對應(yīng)di- (i=1,2,… ,K)的量消成0即可得到初始單純形表。置k = 1;,§7.3 求解目標(biāo)規(guī)劃的單純形方法 (續(xù)),(2)
26、檢查當(dāng)前第k行中是否存在大于0,且對應(yīng)的前k-1行的同列檢驗數(shù)為零的檢驗數(shù)。若有取其中最大者對應(yīng)的變量為換入變量,轉(zhuǎn)(3)。若無這樣的檢驗數(shù),則轉(zhuǎn)(5); (3)按單純形法中的最小比值規(guī)則確定換出變量,當(dāng)存在兩個和兩個以上相同的最小比值時,選取具有較高優(yōu)先級別的變量為換出變量,轉(zhuǎn)(4);,§7.3 求解目標(biāo)規(guī)劃的單純形方法 (續(xù)),(4)按單純形法進行基變換運算,建立新的單純形表,(注意:要對所有的行進行轉(zhuǎn)軸運算
27、)返回(2); (5)當(dāng)k = K 時,計算結(jié)束。表中的解即為滿意解。否則置k = k+1,返回(2)。,§7.3 求解目標(biāo)規(guī)劃的單純形方法 (續(xù)),例7.3.1 試用單純形法來求解例7.1.1的目標(biāo)規(guī)劃模型(7.1.5) ? Min f = P1(d1+ + d2+ ) + P2 d3+ + P3 d4- + P4(d1- + 2d2- ) ? s.t. x1
28、 + d1- -d1+ = 9 ? x2 + d2- -d2+ = 8 ? 4x1 + 6x2 + d3- -d3+ = 60 ? 12x1 + 18x2 +d4- -d4+ =252
29、 ? x1 , x2 , di- ,di+ ? 0 , i = 1,2,3,4.,§7.3 求解目標(biāo)規(guī)劃的單純形方法 (續(xù)),解: 首先處理初始基本可行解對應(yīng)的各級檢驗數(shù)。 由于P1 , P2 優(yōu)先級對應(yīng)的目標(biāo)函數(shù)中不含di- , 所以其檢驗數(shù)只需取系數(shù)負(fù)值。分別為 ( 0,0,0,-1,0,-1,0,0,0,0 ;0)和 ( 0,0,
30、0, 0,0,0,0,-1,0,0 ;0),,,,,,,,,§7.3 求解目標(biāo)規(guī)劃的單純形方法 (續(xù)),P3 優(yōu)先級對應(yīng)的目標(biāo)函數(shù)中含d4- ,所以其檢驗數(shù)需要把第四個約束行加到取負(fù)值的這一行上,得到 ( 12,18,0,0,0,0,0,0,0,-1;252 )TP4 優(yōu)先級對應(yīng)的目標(biāo)函數(shù)中含(d1- + 2d2- ),所以其檢驗數(shù)需要把第一個約束行與第二個約束行的2倍加到取系數(shù)負(fù)值的這一行上,得到 (
31、1,2,0,-1,0,-2,0,0,0,0;25 )。列目標(biāo)規(guī)劃的初始單純形表,,,,,§7.3 求解目標(biāo)規(guī)劃的單純形方法 (續(xù)),(1)k = 1,在初始單純形表中基變量為 (d1-,d2-,d3-,d4-)T =(9,8,60,252)T ;(2)因為P1與P2優(yōu)先級的檢驗數(shù)均已經(jīng)為非正,所以這個單純形表對P1與P2優(yōu)先級是最優(yōu)單純形表;(3)下面考慮P3優(yōu)先級,第二列的檢驗數(shù)為18,此為進基變量,計算相應(yīng)
32、的比值 bi/aij 寫在 ? 列。通過比較,得到d2- 對應(yīng)的比值最小,于是取a22(標(biāo)為 * 號)為轉(zhuǎn)軸元進行矩陣行變換得到新的單純形表;,,,,§7.3 求解目標(biāo)規(guī)劃的單純形方法 (續(xù)),(4)下面繼續(xù)考慮P3優(yōu)先級,第一列的檢驗數(shù)為18,此為進基變量,計算相應(yīng)的比值 bi/aij 寫在 ? 列。通過比較,得到d3- 對應(yīng)的比值最小,于是取a31(標(biāo)為 * 號)為轉(zhuǎn)軸元進行矩陣行變換得到新的單純形表;,,,,§
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
評論
0/150
提交評論