目標(biāo)規(guī)劃（46頁(yè)）--目標(biāo)規(guī)劃模型ppt課件

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

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

3、2.1 目的規(guī)劃模型 2.1.1 問(wèn)題提出 (續(xù))足市場(chǎng)需求的目的看作約束，那么可建立一個(gè)單目的線(xiàn)性規(guī)劃模型 設(shè)決策變量 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 問(wèn)題提出 (續(xù))容易求得上述線(xiàn)性規(guī)劃的最優(yōu)解為(9,4)T 到 (3,8)T 所在線(xiàn)段上的點(diǎn), 最優(yōu)目的值為Z* = 180, 即可選方案有多種. 在實(shí)踐上, 這個(gè)結(jié)果并非完全符合決策者的要求, 它只實(shí)現(xiàn)了經(jīng)理的第一、二、三條目的，而沒(méi)有到達(dá)最后的一個(gè)目的。進(jìn)一步分析可知，要實(shí)現(xiàn)全體目的是不能

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

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

6、來(lái)表示，于是稱(chēng)它們是軟約束。2.1 目的規(guī)劃模型 2.1.2 目的規(guī)劃模型的根本概念 續(xù) 對(duì)于例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)先因子與權(quán)系數(shù)對(duì)于多目的問(wèn)題，設(shè)有L個(gè)目的函數(shù)f1,f2,fL, 決策者在要求到達(dá)這些目的時(shí)，普通有主次之分。為此，我們引入優(yōu)先因子Pi ，i = 1,2,L.無(wú)妨

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

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

9、 mind3+ )； 第三優(yōu)先級(jí)要求 mind4- )； 第四優(yōu)先級(jí)要求 mind1- + 2d2- )，這里, 當(dāng)不能滿(mǎn)足市場(chǎng)需求時(shí), 市場(chǎng)以為B產(chǎn)品的重要性是A產(chǎn)品的2倍即減少B產(chǎn)品的影響是A產(chǎn)品的2倍，因此我們引入了2:1的權(quán)系數(shù)。 2.1 目的規(guī)劃模型 2.1.2 目的規(guī)劃模型的根本概念 續(xù)綜合上述分析，我們可得到以下目的規(guī)劃模型 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 目的規(guī)劃模型2.1.3 目的規(guī)劃模型的普通方式 根據(jù)上面討論,我們可以得到目的規(guī)劃的普通方式如下2.1 目的規(guī)劃模型2.1.3 目的規(guī)劃模型的普通方式 (續(xù))LGP中的第二行是K個(gè)目的約束，第三行是m個(gè)絕對(duì)約束，ckj 和gk 是目的參數(shù)。2.2 目的規(guī)劃的幾何意義及圖解法 對(duì)只具有兩個(gè)決策變量的目的規(guī)劃的數(shù)學(xué)模型，我們可以用圖解法來(lái)分析求解經(jīng)過(guò)圖解例如，可以看到目的規(guī)劃中優(yōu)先因子，正、負(fù)偏向變量及權(quán)系數(shù)等的幾何意義。 2.2目的規(guī)劃的幾何意義及圖解法2.2

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

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

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

14、劃模型沒(méi)有本質(zhì)的區(qū)別，只是它的目的不止是一個(gè),雖然其利用優(yōu)先因子和權(quán)系數(shù)把目的寫(xiě)成一個(gè)函數(shù)的方式, 但在計(jì)算中無(wú)法按單目的處置, 所以可用單純形法進(jìn)展適當(dāng)改良后求解。在組織、構(gòu)造算法時(shí)，我們要思索目的規(guī)劃的數(shù)學(xué)模型一些特點(diǎn)，作以下規(guī)定： (1) 由于目的規(guī)劃問(wèn)題的目的函數(shù)都是求最小化，所以檢驗(yàn)數(shù)的最優(yōu)準(zhǔn)那么與線(xiàn)性規(guī)劃是一樣的； 2.3 求解目的規(guī)劃的單純形方法 (續(xù)) (2) 由于非基變量的檢驗(yàn)數(shù)中含有不同等級(jí)的優(yōu)先因子， Pi Pi+1，i = 1,2,L-1. 于是從每個(gè)檢驗(yàn)數(shù)的整體來(lái)看： Pi+1i = 1,2,L-1優(yōu)先級(jí)第k個(gè)檢驗(yàn)數(shù)的正、負(fù)首先決議于 P1 ，P2 ， ，Pi 優(yōu)先級(jí)

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

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

17、單純形法進(jìn)展基變換運(yùn)算，建立新的單純形表，留意：要對(duì)一切的行進(jìn)展轉(zhuǎn)軸運(yùn)算前往(2)； (5)當(dāng)k K 時(shí)，計(jì)算終了。表中的解即為稱(chēng)心解。否那么置k = k+1，前往2。 2.3 求解目的規(guī)劃的單純形方法 (續(xù))例2.3.1 試用單純形法來(lái)求解例2.1.1的目的規(guī)劃模型(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 求解目的規(guī)劃的單純形方法 (續(xù))解: 首先處置初始根本可行解對(duì)應(yīng)的各級(jí)檢驗(yàn)數(shù)。 由于P1 , P2 優(yōu)先級(jí)對(duì)應(yīng)的目的函數(shù)中不含di- , 所以其檢驗(yàn)數(shù)只需取系數(shù)負(fù)值。分別為 ( 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 求解目的規(guī)劃的單純形方法 (續(xù))P3 優(yōu)先級(jí)對(duì)應(yīng)的目的函數(shù)中含d4- ,所以其檢驗(yàn)數(shù)需求把第四個(gè)約束行加到取負(fù)值的這一行上，得到 ( 12，18，0，0，0，0，0，0，0，-1；252 )TP4 優(yōu)先級(jí)對(duì)應(yīng)的目

20、的函數(shù)中含d1- + 2d2- )，所以其檢驗(yàn)數(shù)需求把第一個(gè)約束行與第二個(gè)約束行的2倍加到取系數(shù)負(fù)值的這一行上，得到 ( 1，2，0，-1，0，-2，0，0，0，0；25 )。列目的規(guī)劃的初始單純形表 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 求解目的規(guī)劃的單純形方法 (續(xù))1k = 1，在初始單純形表

21、中基變量為 d1-,d2-,d3-,d4-)T =9，8,60，252)T ；2由于P1與P2優(yōu)先級(jí)的檢驗(yàn)數(shù)均曾經(jīng)為非正，所以這個(gè)單純形表對(duì)P1與P2優(yōu)先級(jí)是最優(yōu)單純形表；3下面思索P3優(yōu)先級(jí)，第二列的檢驗(yàn)數(shù)為18，此為進(jìn)基變量，計(jì)算相應(yīng)的比值 bi/aij 寫(xiě)在 列。經(jīng)過(guò)比較，得到d2- 對(duì)應(yīng)的比值最小，于是取a22標(biāo)為 * 號(hào)為轉(zhuǎn)軸元進(jìn)展矩陣行變換得到新的單純形表； 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 求解目的規(guī)劃的單純形方法 (續(xù))4下面繼續(xù)思索P3優(yōu)先級(jí)，第一列的檢驗(yàn)數(shù)為18，此為進(jìn)基變量，計(jì)算相應(yīng)的比值 bi/aij 寫(xiě)在 列。經(jīng)過(guò)比較，得到d3- 對(duì)應(yīng)的比值最小，于是取a31標(biāo)為 * 號(hào)為轉(zhuǎn)軸元進(jìn)展矩陣行變換得到新的單純形表； x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10-100000P20000000-1000P3000000-