第五章目標規(guī)劃說課材料

第五章目標規(guī)劃

目標規(guī)劃問題的模型目標規(guī)劃問題的解法

GoalProgramming

1、理解目標規(guī)劃概念；2、掌握目標規(guī)劃建模技巧；3、能夠運用單純形法求解模型。

本章教學基本要求

一個公司可能同時有許多目標；比如：保持比較穩(wěn)定的價格和利潤；提高自己產(chǎn)品的市場占有率；增加產(chǎn)品的品種；維持比較穩(wěn)定的職工隊伍等。各個目標并非都相互協(xié)調(diào)，目標之間甚至還可能是相互矛盾的；由于目標之間的不協(xié)調(diào)性和矛盾性，要想同時實現(xiàn)每一個目標，顯然是不可能的，因此要尋求一種折衷的方案，目標規(guī)劃就是尋找最優(yōu)折衷方案的一種有效的方法。

為什么會產(chǎn)生目標規(guī)劃問題？

東風電機廠生產(chǎn)Ⅰ型和Ⅱ型兩種TV受到A、B兩種關鍵資源的限制必須從另外的廠購買。生產(chǎn)每臺電視機對資源的耗定額及每天可利用的資源數(shù)量已知。東風廠的管理部門提出生產(chǎn)經(jīng)營要達到3個目標：a)原材料A的每日用量控制在90公斤以內(nèi)；b)Ⅰ型TV的日產(chǎn)量在15臺以上；c)

日利潤超過140(百元)多目標決策問題舉例

具有連續(xù)變量的線性目標規(guī)劃，簡稱目標規(guī)劃(GoalProgramming,,簡記為GP)。

目標規(guī)劃中目標函數(shù)和約束條件可以是線性的，也可以是非線的，變量可以是連續(xù)的，也可以是離散的。本書中我們只研究具有連續(xù)變量的線性目標規(guī)劃。

本章目標規(guī)劃的研究范圍

相同等級的目標有優(yōu)先等級的目標

有賦權(quán)的優(yōu)先等級的目標

一、目標規(guī)劃的模型例5-1：東風電機廠生產(chǎn)Ⅰ型和Ⅱ型兩種TV受到A、B兩種關鍵資源的限制必須從另外的廠購買，生產(chǎn)每臺電視機對資源的耗定額及每天可利用的資源數(shù)量如表5.1。需要解決的問題：每天應如何安排兩種TV的產(chǎn)量，才能使利潤最大？

III現(xiàn)有資源A23100B4280利潤45

表5.11、相同等級的目標規(guī)劃的模型例5-1見書P150頁，問題1：設生產(chǎn)TVⅠ型和Ⅱ型產(chǎn)量各為x1，x2則得LP模型為：maxz=4x1+5x2s1t2x1+3x2≤1004x1+2x2≤80x1.x2≥0可求最優(yōu)解為x1﹡=5x2﹡=30Z﹡=170但市場形勢發(fā)生變化：供應A原料的廠家提出，減少10公斤的供應；Ⅰ型產(chǎn)品供不應求，必須擴展Ⅰ型產(chǎn)品的產(chǎn)量x1

。東風廠的管理部門提出對下一階段生產(chǎn)經(jīng)營要達到3個目標：a)原材料A的每日用量控制在90公斤以內(nèi)；b)Ⅰ型TV的日產(chǎn)量在15臺以上；c)

日利潤超過140(百元)。如何用目標規(guī)劃的方法來描述和解決上述問題（1）原材料A的每日用量控制在90公斤以內(nèi)2x1+3x2≤90引進兩個偏差變量d-i和di+d-i表示原材料A的實際日用量未達到目標值的部分；di+表示A的實際日用量超過目標值部分d+1≥0d-1≥0d+1d-1=090是數(shù)量目標，原材料A的實際取值(每日實際用量)與目標值之間可能有一個偏差2x1+3x2–d1++d1-=90目標約束

mind+1

（2）Ⅰ型電視機的日產(chǎn)量在15臺以上x1≥15用d2-和d2+分別表示Ⅰ型電視機的日產(chǎn)量未達到和超過目標值的部分。

x1-d+2+d-2=15目標約束

mind-2

（3）日利潤超過140(百元)4x1+5x2≥140用d-3和d+3分別表示日利潤未達到和超過目標值的部分4x1+5x2–d3++d3-=140目標約束

mind-3

目標規(guī)劃模型(GP問題1)上述目標對于該廠來說，是同等重要的，因此：minz=d1++d2-+d3-s.t.2x1+3x2-d1++d1-=904x1+2x2+s2=80x1-d2++d2-=154x1+5x2-d3++d3-=140x1,x2,s2,d1+,d1-,d2+,d2-,

d3+,d3-≥0東風廠的管理部門提出對下一階段生產(chǎn)經(jīng)營要達到3個目標，決策者認為上例中3個目標并非同等重要，其中：（b）目標為最重要；（c）目標次重要；（a）目標排在第三位：b)Ⅰ型TV的日產(chǎn)量在15臺以上；c)

日利潤超過140(百元)a)原材料A的每日用量控制在90公斤以內(nèi)如何用目標規(guī)劃的方法來描述和解決上述問題2、有優(yōu)先等級的目標規(guī)劃的模型優(yōu)先因子：描述問題中目標重要性程度的差別，一般用pi表示，通常i值越小，代表的優(yōu)先程度越高。在目標規(guī)劃中：對于最重要目標，賦予優(yōu)先因子P1

第二位重要目標，賦予優(yōu)先因子P2以此類推，各個優(yōu)先因子是一些特殊的正常數(shù)，它們之間有如下關系：P1＞＞P2＞＞P3＞＞……“＞＞”遠遠大于目標優(yōu)先級偏差變量b:I型TV日產(chǎn)量≥15臺P1d2+d2-c:日產(chǎn)量≥140百元P2d3+d3-a:A的用量≤90公斤P3d1+d1-minz=P3d1++P1d2-+P2d3-s.t.2x1+3x2-d1++d1-=904x1+2x2+s2=80x1-d2++d2-=154x1+5x2-d3++d3-=140x1,x2,s2,d1+,d1-,d2+,d2-,

d3+,d3-≥0根據(jù)東風廠對3個目標的分級，可寫出GP問題：目標優(yōu)先級權(quán)重1:B≤40P122:A≤70P113:日利潤≥110P2

4：II型TVx2≥18P3

5：I型TVx1≥5P4

3、有賦權(quán)的優(yōu)先等級的目標規(guī)劃的模型有關的偏差變量定義如下:d1+和d1-分別表示日利潤超過和未達到目標值的部分;d2+和d2-分別表示原材料A的日用量超過和未達到目標值的部分;d3+和d3-分別表示原材料B的日用量超過和未達到目標值;d4+和d4-分別表示I型電視機的日產(chǎn)量超過和未達到目標值的部分;d5+和d5-分別表示II型電視機的日產(chǎn)量超過和未達到目標值的部分。minz=2P1d3++P1d2++P2d1-+P3d5-+P4d4-s.t.4x1+5x2-d1++d1-=1102x1+3x2-d2++d2-=704x1+2x2-d3++d3-=40x1-d4++d4-=5x2-d5++d5-=18x1,x2,d1+,……d5+,d1-……d5-≥0各目標有優(yōu)先等級和賦權(quán)情況下，可寫出GP問題：

概念偏差變量：實際值與目標值之間差距的變量表示，通常以

di+di-表示，分別為正、負偏差變量，且有di+》0、

di-》0，di+di-=0優(yōu)先因子：描述問題中目標重要性程度的差別，一般用pi表示，通常i值越小，代表的優(yōu)先程度越高。目標約束：用來描述允許對給定目標值有一定偏離程度的限制條件。目標規(guī)劃的概念

目標規(guī)劃模型的特點：1、引進正負偏差變量2、模型中必須有目標約束3、目標函數(shù)為偏差變量的表達式4、以優(yōu)先級因子描述目標的重要性程度目標規(guī)劃的模型解GP問題,我們首先要找一個初始基并作其單純形表,

由于GP模型的約束條件中,含有許多負偏差變量,其系數(shù)均為1,故?？扇∷鼈?yōu)槌跏蓟兞?；但因目標函?shù)中也常含有負偏差變量,因此將目標函數(shù)行搬上單純形表時,應注意將其中基變量的系數(shù)變?yōu)?。GP問題初始基的確定1、相同等級的目標規(guī)劃的解法為了簡化制表手續(xù),節(jié)省不必要的重復書寫,我們將GP

問題的初始單純形表設計為有兩個z行的形式；第一個z行就是將GP模型中z行的系數(shù)反號而得,并將這一行用括號括起來；第二個z行則是正規(guī)單純形表中的z行,其中基變量的檢驗數(shù)都已化為0.GP問題單純形表的結(jié)構(gòu)例5-1求解此GP問題minz=d1++d2-+d3-s.t.2x1+3x2-d1++d1-=904x1+2x2+s2=80x1-d2++d2-=154x1+5x2-d3++d3-=140x1,x2,s2,d1+,d1-,d2+,d2-,

d3+,d3-≥0例5-1建立初始的單純形表

x1x2d1+d1-s2s2d2+d2-d3+d3-右端(z00-1-1000-10-1)z55-100-10-10155d1-23-110000090s242001000080d2-①0000-110015d3-4500000-11140X1為進基變量，d2-為離基變量

x1x2d1+d1-s2s2d2+d2-d3+d3-右端-1z05-1004-5-1080d1-03-1102-20060s2020014-40020x110000-110015d3-050004-4-1180X2為進基變量，s2為離基變量

x1x2d1+d1-s2s2d2+d2-d3+d3-右端-1z00-10-5/2-65-1030d1-00-11-3/2-440030x201001/22-20010x110000-110015d3-0000-5/2-66-1130d2-為進基變量，d3-為離基變量

x1x2d1+d1-s2s2d2+d2-d3+d3-右端-1z00-10-5/12-10-1/6-5/65d1-010x2020x1010d2-0000-5/12-11-1/61/65得到最優(yōu)解1.d1-=10,d1+=0,則A的日用量不超過90公斤,實際為2x1+3x2=80，實現(xiàn)目標

2.d2-=5,則有d2+=0,x1=10即I型TV的日產(chǎn)量僅有10臺,不在15臺以上，沒達到目標3.則通過有x2=20,x1=10可知4x1+5x2=4*10+5*20=140,則有d3+=d3-=0即日利潤正好為140百元。

恰好實現(xiàn)目標。負偏差變量作為初始基變量；但因目標函數(shù)中也常含有負偏差變量,因此將目標函數(shù)行搬上單純形表時,應注意將其中基變量的系數(shù)變?yōu)?.

GP問題初始基的確定2、有優(yōu)先等級的目標規(guī)劃的解法由于此類問題的目標函數(shù)中含有各個優(yōu)先因子,所以在單純形表的z-行中,各檢驗數(shù)將是這些優(yōu)先因子的線性組合；我們將z-行寫成若干行,每一級優(yōu)先因子都各占一行；前一段中節(jié)省制表的方法,我們現(xiàn)在同樣采用,不過在這里,z-行已被分成若干行了,即有幾個優(yōu)先因子就分成幾行,在初始表中用括號括起來的也不是一行,而是好幾行.GP問題單純形表的結(jié)構(gòu)例5-2求解此GP問題minz=P3d1++P1d2-+P2d3-s.t.2x1+3x2-d1++d1-=904x1+2x2+s2=80x1-d2++d2-=154x1+5x2-d3++d3-=140x1,x2,s2,d1+,d1-,d2+,d2-,

d3+,d3-≥0例5-2運算得單純形表最優(yōu)表因為P1≥P2≥P3，所以檢驗數(shù)的符號首先取決于P1

行中各數(shù)的符號,其次決定于P2行中各數(shù)的符號,依次類推。P1行中各數(shù)全部≤0,故P1級目標已實現(xiàn)最優(yōu)。劃去

P1行和非基變量所在列，得到新單純形表繼續(xù)運算當所有非基變量在檢驗數(shù)行的系數(shù)都≤0時，獲得最優(yōu)解。例5-2建立初始單純形表

x1x2d1+d1-s2d2+d2-d3+d3-右端P1000000-100

P20000000000-1

P300-1000000

P110000-10000

P24500000-10

P300-1000000

d1-23-110000090s242001000080d2-①0000-110015d3-4500000-11140X1為進基變量，d2-為離基變量例5-2單純形表2

x1x2d1+d1-s2d2+d2-d3+d3-右端P1000000-100

P2050004-4-10

P300-1000000

d1-03-1102-20060s2020014-40020x110000-110015d3-050004-4-1180X2為進基變量，S2為離基變量例5-2建立單純形表3

x1x2d1+d1-s2d2+d3+d3-右端P20000-5/2-600×P300-100000×d1-0001000030X201001/220010X11000000015d3-0000000130求得最優(yōu)解例5-2可知最優(yōu)折衷結(jié)果為：x1=15,d2-=d2+=0,則P1級目標恰好達到.2.x1=15,x2=10,d3-=30,4x1+5x2=4*15+5*10=110≤140,

即有日利潤目標比要求值還差30百元,

則P2級目標沒實現(xiàn).3.P3級目標d1-=30,則d1+=0,2x1+3x2=2*15+3*10=60事實上A還剩30公斤.

日產(chǎn)量不超過90公斤,也已達到

則P3級目標實現(xiàn).負偏差變量作為初始基變量；但因目標函數(shù)中也常含有負偏差變量,因此將目標函數(shù)行搬上單純形表時,應注意將其中基變量的系數(shù)變?yōu)?.

GP問題初始基的確定3、有賦權(quán)優(yōu)先等級的目標規(guī)劃的解法將z行寫成若干行,每一級優(yōu)先因子各占一行；賦權(quán)作為Pi級對應的系數(shù)寫在目標函數(shù)檢驗數(shù)行；以后求解方法實際上與前例相同,只是計算更加繁瑣GP問題單純形表的結(jié)構(gòu)例5-3求解此GP問題minz=2P1d3++P1d2++P2d1-+P3d5-+P4d4-s.t.4x1+5x2-d1++d1-=1102x1+3x2-d2++d2-=704x1+2x2-d3++d3-=40x1-d4++d4-=5x2-d5++d5-=18x1,x2,d1+,……d5+,d1-……d5-≥0例5-3可知最優(yōu)折衷結(jié)果為(P195)：兩個P1級目標(兩種原材料日用量的限制)均已實現(xiàn)(d2+=d3+=0)P2級目標(日利潤110百元)不能完全實現(xiàn),還差10百元(d1-=10)P3級目標(II型電視機日產(chǎn)量不少于18臺)也已實現(xiàn)，事實上還超額2臺(d5+=2)P4級目標(I型電視機日產(chǎn)量5臺)沒有實現(xiàn)(x1=0,d4-=5)

概念偏差變量：實際值與目標值之間差距的變量表示，通常以

di+di-表示，分別為正、負偏差變量，且有di+》0、

di-》0，di+di-=0優(yōu)先因子：描述問題中目標重要性程度的差別，一般用pi表示，通常i值越小，代表的優(yōu)先程度越高。目標約束：用來描述允許對給定目標值有一定偏離程度的限制條件。目標規(guī)劃小結(jié)目標規(guī)劃模型的特點1、引進正負偏差變量2、模型中必須有目標約束3、目標函數(shù)為偏差變量的表達式4、以優(yōu)先級因子描述目標的重要性程度目標規(guī)劃的決策案例例題1某公司管理層的目標:保持穩(wěn)定的利潤;增加市場份額;多樣化的產(chǎn)品線;保持穩(wěn)定的價格;提高員工的士氣;保持對業(yè)務的控制力;增加公司的聲譽.

因素產(chǎn)品的單位貢獻目標權(quán)重123長期利潤（百萬元）129151255雇傭水平534402(+),4(-)資本投資（百萬元）0.50.70.85.53Minz=5y1-+2y2++4y2-+3y3+S.t12x1+9x2+15x3-

y1++y1-=1255x1+3x2+4x3-

y2++y2-=405x1+7x2+8x3-

y3++y3-=55

xi≥0,yj+,yj-≥0

X1=25/3,x2=0,x3=5/3,y1+=0,y1-=0,y2+=25/3,y2-=0,y3+=0,

y3-=0,z=50/3例題2，一位投資商有一筆資金準備購買股票。資金總額為90000元，目前可選的股票有A和B兩種（可以同時投資于兩種股票）。其價格以及年收益率和風險系數(shù)如下表：從上表可知，A股票的收益率為（3／20）×100％＝15％，股票B的收益率為4／50×100％＝8％，A的收益率比B大，但同時A的風險也比B大。這也符合高風險高收益的規(guī)