管理運(yùn)籌學(xué) 課件 06目標(biāo)規(guī)劃

OperationalResearch

運(yùn)籌學(xué)田世海教授哈爾濱理工大學(xué)管理學(xué)院SchoolofEconomicsandManagement

HarbinUniversityofScienceandTechnologyChapter6第6章GoalProgramming

目標(biāo)規(guī)劃OperationalResearchIntroduction目標(biāo)規(guī)劃問(wèn)題及模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形法主要內(nèi)容目標(biāo)規(guī)劃靈敏度分析目標(biāo)規(guī)劃應(yīng)用舉例目標(biāo)規(guī)劃問(wèn)題及模型1、問(wèn)題的提出： 目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理多目標(biāo)決策的需要而由線性規(guī)劃逐步發(fā)展起來(lái)的一個(gè)分支。 由于現(xiàn)代化企業(yè)內(nèi)專業(yè)分工越來(lái)越細(xì)，組織機(jī)構(gòu)日益復(fù)雜，為了統(tǒng)一協(xié)調(diào)企業(yè)各部門圍繞一個(gè)整體的目標(biāo)工作，產(chǎn)生了目標(biāo)管理這種先進(jìn)的管理技術(shù)。目標(biāo)規(guī)劃是實(shí)行目標(biāo)管理的有效工具，它根據(jù)企業(yè)制定的經(jīng)營(yíng)目標(biāo)以及這些目標(biāo)的輕重緩急次序，考慮現(xiàn)有資源情況，分析如何達(dá)到規(guī)定目標(biāo)或從總體上離規(guī)定目標(biāo)的差距為最小。目標(biāo)規(guī)劃問(wèn)題及模型例1.某企業(yè)計(jì)劃生產(chǎn)甲，乙兩種產(chǎn)品，這些產(chǎn)品分別要在A,B,C,D四種不同設(shè)備上加工。按工藝文件規(guī)定，如表所示。問(wèn)該企業(yè)應(yīng)如何安排計(jì)劃，使得計(jì)劃期內(nèi)的總利潤(rùn)收入為最大？目標(biāo)規(guī)劃問(wèn)題及模型解：設(shè)甲、乙產(chǎn)品的產(chǎn)量分別為x1，x2，建立線性規(guī)劃模型：其最優(yōu)解為x1＝4，x2＝2，z＊＝14元目標(biāo)規(guī)劃問(wèn)題及模型但企業(yè)的經(jīng)營(yíng)目標(biāo)不僅僅是利潤(rùn)，而且要考慮多個(gè)方面，如：力求使利潤(rùn)指標(biāo)不低于12元；考慮到市場(chǎng)需求，甲、乙兩種產(chǎn)品的生產(chǎn)量需保持1:1的比例；C和D為貴重設(shè)備，嚴(yán)格禁止超時(shí)使用；設(shè)備B必要時(shí)可以加班，但加班時(shí)間要控制；設(shè)備A即要求充分利用，又盡可能不加班。要考慮上述多方面的目標(biāo)，需要借助目標(biāo)規(guī)劃的方法。目標(biāo)規(guī)劃問(wèn)題及模型線性規(guī)劃模型存在的局限性：1）要求問(wèn)題的解必須滿足全部約束條件，實(shí)際問(wèn)題中并非所有約束都需要嚴(yán)格滿足。2）只能處理單目標(biāo)的優(yōu)化問(wèn)題。實(shí)際問(wèn)題中，目標(biāo)和約束可以相互轉(zhuǎn)化。3）線性規(guī)劃中各個(gè)約束條件都處于同等重要地位，但現(xiàn)實(shí)問(wèn)題中，各目標(biāo)的重要性即有層次上的差別，同一層次中又可以有權(quán)重上的區(qū)分。4）線性規(guī)劃尋求最優(yōu)解，但很多實(shí)際問(wèn)題中只需找出滿意解就可以。目標(biāo)規(guī)劃問(wèn)題及模型目標(biāo)規(guī)劃怎樣解決上述線性規(guī)劃模型建模中的局限性？1.設(shè)置偏差變量，用來(lái)表明實(shí)際值同目標(biāo)值之間的差異偏差變量用下列符號(hào)表示：d+——超出目標(biāo)的偏差，稱正偏差變量d-——未達(dá)到目標(biāo)的偏差，稱負(fù)偏差變量正負(fù)偏差變量?jī)烧弑赜幸粋€(gè)為0。當(dāng)實(shí)際值超出目標(biāo)值時(shí)：d+>0,d-=0;

當(dāng)實(shí)際值未達(dá)到目標(biāo)值時(shí)：d+=0,d->0;

當(dāng)實(shí)際值同目標(biāo)值恰好一致時(shí)：d+=0,d-=0;故恒有d+×d-=0目標(biāo)規(guī)劃問(wèn)題及模型2.統(tǒng)一處理目標(biāo)和約束

對(duì)有嚴(yán)格限制的資源使用建立系統(tǒng)約束，數(shù)學(xué)形式同線性規(guī)劃中的約束條件。如C和D設(shè)備的使用限制。

對(duì)不嚴(yán)格限制的約束，連同原線性規(guī)劃建模時(shí)的目標(biāo)，均通過(guò)目標(biāo)約束來(lái)表達(dá)。1）例如要求甲、乙兩種產(chǎn)品保持1:1的比例，系統(tǒng)約束表達(dá)為：x1=x2。由于這個(gè)比例允許有偏差，當(dāng)x1<x2時(shí)，出現(xiàn)負(fù)偏差d-，即：x1+d-

=x2或x1－x2+d-

=0當(dāng)x1>x2時(shí)，出現(xiàn)正偏差d+，即：x1-d+

=x2或x1－x2-d+

=0目標(biāo)規(guī)劃問(wèn)題及模型∵正負(fù)偏差不可能同時(shí)出現(xiàn)，故總有：x1－x2+d--d+

=0

若希望甲的產(chǎn)量不低于乙的產(chǎn)量，即不希望d->0,用目標(biāo)約束可表為:

若希望甲的產(chǎn)量低于乙的產(chǎn)量，即不希望d＋>0,用目標(biāo)約束可表為:

若希望甲的產(chǎn)量恰好等于乙的產(chǎn)量，即不希望d＋>0,也不希望d->0用目標(biāo)約束可表為:目標(biāo)規(guī)劃問(wèn)題及模型3）設(shè)備B必要時(shí)可加班及加班時(shí)間要控制，目標(biāo)約束表示為：2）力求使利潤(rùn)指標(biāo)不低于12元，目標(biāo)約束表示為：4）設(shè)備A既要求充分利用，又盡可能不加班，目標(biāo)約束表示為：目標(biāo)規(guī)劃問(wèn)題及模型3.目標(biāo)的優(yōu)先級(jí)與權(quán)系數(shù)

在一個(gè)目標(biāo)規(guī)劃的模型中，為達(dá)到某一目標(biāo)可犧牲其他一些目標(biāo)，稱這些目標(biāo)是屬于不同層次的優(yōu)先級(jí)。優(yōu)先級(jí)層次的高低可分別通過(guò)優(yōu)先因子P1,P2,…表示。對(duì)于同一層次優(yōu)先級(jí)的不同目標(biāo)，按其重要程度可分別乘上不同的權(quán)系數(shù)。權(quán)系數(shù)是一個(gè)個(gè)具體數(shù)字，乘上的權(quán)系數(shù)越大，表明該目標(biāo)越重要?，F(xiàn)假定：

第1優(yōu)先級(jí)P1——企業(yè)利潤(rùn)；第2優(yōu)先級(jí)P2——甲乙產(chǎn)品的產(chǎn)量保持1:1的比例第3優(yōu)先級(jí)P3——設(shè)備A,B盡量不超負(fù)荷工作。其中設(shè)備A的重要性比設(shè)備B大三倍。目標(biāo)規(guī)劃問(wèn)題及模型上述目標(biāo)規(guī)劃模型可以表示為：目標(biāo)規(guī)劃問(wèn)題及模型5.目標(biāo)規(guī)劃的目標(biāo)函數(shù)由各目標(biāo)約束的正、負(fù)偏差變量及相應(yīng)的優(yōu)先因子和權(quán)系數(shù)構(gòu)成。從決策者的要求來(lái)分析，總希望得到的結(jié)果與規(guī)定的指標(biāo)值之間的偏差量愈小愈好。由此可構(gòu)造一個(gè)使總偏差量為最小化的目標(biāo)函數(shù)，minZ=f（d+，d-）其基本形式有三種：4.滿意解

對(duì)于這種解來(lái)說(shuō)，前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)。目標(biāo)規(guī)劃問(wèn)題及模型（1）要求恰好達(dá)到目標(biāo)值，即正、負(fù)偏差變量都要盡可能地小。構(gòu)造的目標(biāo)函數(shù)是

minZ=f（d++d-

）

（2）要求不超過(guò)目標(biāo)值，但允許達(dá)不到目標(biāo)值，即只有使正偏差量要盡可能地小（實(shí)現(xiàn)最少或?yàn)榱悖?/p>

minZ=f（d+）（3）要求超過(guò)目標(biāo)值，即超過(guò)量不限。要求超額完成規(guī)定目標(biāo)，要實(shí)現(xiàn)負(fù)偏差量為零或?yàn)樽钚?/p>

minZ=f（d-）目標(biāo)規(guī)劃問(wèn)題及模型

建模的步驟1、根據(jù)要研究的問(wèn)題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對(duì)約束；4、對(duì)同一優(yōu)先等級(jí)中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù)。3、給各目標(biāo)賦予相應(yīng)的優(yōu)先因子Pi（i=1.2…L）。2、可根據(jù)決策者的需要，將某些或全部絕對(duì)約束轉(zhuǎn)化為目標(biāo)約束。這時(shí)只需要給絕對(duì)約束加上負(fù)偏差變量和減去正偏差變量即可。目標(biāo)規(guī)劃問(wèn)題及模型目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式目標(biāo)函數(shù)（達(dá)成函數(shù)）目標(biāo)約束其中：gk為第k個(gè)目標(biāo)約束的預(yù)期目標(biāo)值，和為pl優(yōu)先因子對(duì)應(yīng)各目標(biāo)的權(quán)系數(shù)。目標(biāo)規(guī)劃問(wèn)題及模型用目標(biāo)規(guī)劃求解問(wèn)題的過(guò)程：明確問(wèn)題，列出目標(biāo)的優(yōu)先級(jí)和權(quán)系數(shù)構(gòu)造目標(biāo)規(guī)劃模型求出滿意解滿意否？分析各項(xiàng)目標(biāo)完成情況據(jù)此制定出決策方案NY目標(biāo)規(guī)劃問(wèn)題及模型例2.某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案？

在此基礎(chǔ)上考慮：

1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；

2、充分利用設(shè)備有效臺(tái)時(shí)，不加班；

3、利潤(rùn)不小于56元。解:分析第二目標(biāo)P2

：第三目標(biāo)P3

：第一目標(biāo)P1:ⅠⅡ擁有量原材料2111設(shè)備(臺(tái)時(shí))1210單件利潤(rùn)810目標(biāo)規(guī)劃問(wèn)題及模型1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；

2、充分利用設(shè)備有效臺(tái)時(shí)，不加班；

3、利潤(rùn)不小于56元。2x1+x2≤11（在絕對(duì)約束基礎(chǔ)上進(jìn)行目標(biāo)規(guī)劃）

x1-x2+d1--d1+=0

(要求：d1+

盡可能小，最好是0才能滿足≤)x1+2x2+d2--d2+=10

（要求：d2-

和d2+

都盡可能小，最好等于0）

8x1+10x2+d3--d3+=56

（要求：d3-

盡可能小，最好是0才能滿足≥）

x1,x2,di-,di+≥0ⅠⅡ擁有量原材料2111設(shè)備(臺(tái)時(shí))1210單件利潤(rùn)810Introduction目標(biāo)規(guī)劃問(wèn)題及模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形法主要內(nèi)容目標(biāo)規(guī)劃靈敏度分析目標(biāo)規(guī)劃應(yīng)用舉例目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的圖解法：

適用兩個(gè)變量的目標(biāo)規(guī)劃問(wèn)題，但其操作簡(jiǎn)單，原理一目了然。同時(shí)，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過(guò)程。圖解法解題步驟：1.將所有約束條件（包括目標(biāo)約束和絕對(duì)約束，暫不考慮正負(fù)偏差變量）的直線方程分別標(biāo)示于坐標(biāo)平面上。2.確定系統(tǒng)約束的可行域。3.在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向目標(biāo)規(guī)劃的圖解法4.求滿足最高優(yōu)先等級(jí)目標(biāo)的解5.轉(zhuǎn)到下一個(gè)優(yōu)先等級(jí)的目標(biāo)，再不破壞所有較高優(yōu)先等級(jí)目標(biāo)的前提下，求出該優(yōu)先等級(jí)目標(biāo)的解6.重復(fù)5，直到所有優(yōu)先等級(jí)的目標(biāo)都已審查完畢為止7.確定最優(yōu)解和滿意解。目標(biāo)規(guī)劃的圖解法例4.用圖解法求解下列目標(biāo)規(guī)劃問(wèn)題目標(biāo)規(guī)劃的圖解法(a)(b)(c)(d)x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+滿意解(3,3)046834622目標(biāo)規(guī)劃的圖解法x1x2(a)(b)d1+d1-(c)d2-d2+(d)d3-d3+GD滿意解是線段GD上任意點(diǎn)其中G點(diǎn)X＝(2,4)T,D點(diǎn)X＝(10/3,10/3)T05.51055.6112,410/3,10/35107例5.Introduction目標(biāo)規(guī)劃問(wèn)題及模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形法主要內(nèi)容目標(biāo)規(guī)劃靈敏度分析目標(biāo)規(guī)劃應(yīng)用舉例目標(biāo)規(guī)劃的單純形法一般形式：Cj

c1c2cn+2mCBXBb

x1x2xn+2m

cj1xj1bo1e11e12e1n+2mcj2xj2bo2e21e22e2n+2mcjmxjm

bomem1em2emn+2mσkjP1

σ11σ12σ1n+2mP2

σ21σ22σ2n+2mPK

σm1σm2σmn+2m目標(biāo)規(guī)劃的單純形法一、特點(diǎn)1．目標(biāo)函數(shù)：min2．最優(yōu)性判斷：σj≥0時(shí)為最優(yōu)3．非基變量檢驗(yàn)數(shù)的特殊性：含有不同等級(jí)的優(yōu)先因子P1,P2,…,Pk;又因P1>>P2>>P3>>…>>Pk

，所以檢驗(yàn)數(shù)的正負(fù)首先取決于P1的系數(shù)的正負(fù)，若P1

的系數(shù)為0，再由P2

的系數(shù)的正負(fù)決定檢驗(yàn)數(shù)的正負(fù)，然后依次類推。目標(biāo)規(guī)劃的單純形法(1)建立初始單純形表．在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個(gè)數(shù)分別列成K行。初始的檢驗(yàn)數(shù)需根據(jù)初始可行解計(jì)算出來(lái)，方法同基本單純形法。當(dāng)不含絕對(duì)約束時(shí)，di-

（i=1,2,…,K）構(gòu)成了一組基本可行解，這時(shí)只需利用相應(yīng)單位向量把各級(jí)目標(biāo)行中對(duì)應(yīng)di-

（i=1,2,…,K）的量消成0即可得到初始單純形表。置k＝1；解目標(biāo)規(guī)劃問(wèn)題的單純形法的計(jì)算步驟(2)檢查當(dāng)前第k行中是否存在大于0，且對(duì)應(yīng)的前k-1行的同列檢驗(yàn)數(shù)為零的檢驗(yàn)數(shù)。若有取其中最大者對(duì)應(yīng)的變量為換入變量，轉(zhuǎn)(3)。若無(wú)這樣的檢驗(yàn)數(shù)，則轉(zhuǎn)(5)；目標(biāo)規(guī)劃的單純形法(4)按單純形法進(jìn)行基變換運(yùn)算，建立新的單純形表，（注意：要對(duì)所有的行進(jìn)行轉(zhuǎn)軸運(yùn)算）返回(2)；(5)當(dāng)k＝K時(shí)，計(jì)算結(jié)束。表中的解即為滿意解。否則置k=k+1，返回（2）。(3)按單純形法中的最小比值規(guī)則確定換出變量，當(dāng)存在兩個(gè)和兩個(gè)以上相同的最小比值時(shí)，選取具有較高優(yōu)先級(jí)別的變量為換出變量，轉(zhuǎn)（4）；目標(biāo)規(guī)劃的單純形法例1.用單純形法求解下列目標(biāo)規(guī)劃問(wèn)題解：將上述目標(biāo)規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型：目標(biāo)規(guī)劃的單純形法建立初始單純形表：目標(biāo)規(guī)劃的單純形法θ=min｛－，10/2，56/10，11/1｝=5進(jìn)基變量x2Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

001－11－100000P21012001－1000

P3

5681000001－100

x3

11210000001σjP1

000100000P2

－1－20002000P3

－8－100000010換出變量d2-目標(biāo)規(guī)劃的單純形法Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

053/201－11/2-1/20000x251/21001/2-1/2000

P3

63000-551－100

x3

63/2000-1/21/2001σjP1

000100000P2

000011000P3

－30005-5010θ=min｛10/3,10,6/3,12/3｝=2,進(jìn)基變量x1換出變量d3-目標(biāo)規(guī)劃的單純形法Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

02001－13-3-1/21/200x2401004/3-4/3-1/61/600x121000-5/35/31/3-1/300x3

300002-2-1/21/21σjP1

000100000P2

000011000P3

000000100最優(yōu)解為x1＝2，x2＝4。但非基變量d3+的檢驗(yàn)數(shù)為零，故此題有無(wú)窮多最優(yōu)解。目標(biāo)規(guī)劃的單純形法Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

02001－13-3-1/21/200x2401004/3-4/3-1/61/600x121000-5/35/31/3-1/300x3

300002-2-1/21/21σjP1

000100000P2

000011000P3

000000100θ=min｛4,24,－,6｝=4進(jìn)基變量d3+換出變量d1-目標(biāo)規(guī)劃的單純形法Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

04002-26-6-1100x210/301-1/31/31/3-1/30000x110/3102/3-2/31/3-1/30000x3

100-1－1-11001σjP1

000100000P2

000011000P3

000000100最優(yōu)解為x1＝10/3，x2＝10/3。目標(biāo)規(guī)劃的單純形法例2.用單純形法求解下列目標(biāo)規(guī)劃問(wèn)題目標(biāo)規(guī)劃的單純形法Cj00P100P302.5P20P2CBXBbx1x2P1250030121－1000000014021001－100000601000001－1000100010000001－1σjP1

－30－1201000000P2

00000002.501P3

0000010000θ=min｛2500/30,140/2,60/1,

-｝=60,進(jìn)基變量x1換出變量d3-目標(biāo)規(guī)劃的單純形法Cj

00P100P302.5P20P2CBXBbx1x2P17000121－100－30300002001001－1－22000x1601000001－1000100010000001－1σjP1

0－12010030－3000P2

00000002.501P3

0000010000θ=min｛700/30,20/2,－,－｝=10進(jìn)基變量d3+換出變量d2-目標(biāo)規(guī)劃的單純形法Cj

00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000x17011/2001/2-1/200000100010000001-1σjP1

030115-150000P2

0-5/400-5/45/45/2001P3

0000010000θ=min｛400/15,－,－,－｝=10進(jìn)基變量d2+換出變量d1-目標(biāo)規(guī)劃的單純形法Cj

00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000x1250/312/51/30-1/300000000100010000001－1σjP1

0010000000P2

0-1-1/121/12002/5001P3

01/5-1/151/15100000θ=min｛－,350/6,1250/6,100/1｝=75進(jìn)基變量x2換出變量d3+目標(biāo)規(guī)劃的單純形法Cj

00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000x2175/3011/12-1/1200-5/25/2000x160100000-11000125/300-1/121/12005/2-5/21－1σjP1

001000000