版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
OperationalResearch
運籌學(xué)田世海教授哈爾濱理工大學(xué)管理學(xué)院SchoolofEconomicsandManagement
HarbinUniversityofScienceandTechnologyChapter6第6章GoalProgramming
目標(biāo)規(guī)劃OperationalResearchIntroduction目標(biāo)規(guī)劃問題及模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形法主要內(nèi)容目標(biāo)規(guī)劃靈敏度分析目標(biāo)規(guī)劃應(yīng)用舉例目標(biāo)規(guī)劃問題及模型1、問題的提出: 目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上,為適應(yīng)經(jīng)濟管理多目標(biāo)決策的需要而由線性規(guī)劃逐步發(fā)展起來的一個分支。 由于現(xiàn)代化企業(yè)內(nèi)專業(yè)分工越來越細(xì),組織機構(gòu)日益復(fù)雜,為了統(tǒng)一協(xié)調(diào)企業(yè)各部門圍繞一個整體的目標(biāo)工作,產(chǎn)生了目標(biāo)管理這種先進的管理技術(shù)。目標(biāo)規(guī)劃是實行目標(biāo)管理的有效工具,它根據(jù)企業(yè)制定的經(jīng)營目標(biāo)以及這些目標(biāo)的輕重緩急次序,考慮現(xiàn)有資源情況,分析如何達到規(guī)定目標(biāo)或從總體上離規(guī)定目標(biāo)的差距為最小。目標(biāo)規(guī)劃問題及模型例1.某企業(yè)計劃生產(chǎn)甲,乙兩種產(chǎn)品,這些產(chǎn)品分別要在A,B,C,D四種不同設(shè)備上加工。按工藝文件規(guī)定,如表所示。問該企業(yè)應(yīng)如何安排計劃,使得計劃期內(nèi)的總利潤收入為最大?目標(biāo)規(guī)劃問題及模型解:設(shè)甲、乙產(chǎn)品的產(chǎn)量分別為x1,x2,建立線性規(guī)劃模型:其最優(yōu)解為x1=4,x2=2,z*=14元目標(biāo)規(guī)劃問題及模型但企業(yè)的經(jīng)營目標(biāo)不僅僅是利潤,而且要考慮多個方面,如:力求使利潤指標(biāo)不低于12元;考慮到市場需求,甲、乙兩種產(chǎn)品的生產(chǎn)量需保持1:1的比例;C和D為貴重設(shè)備,嚴(yán)格禁止超時使用;設(shè)備B必要時可以加班,但加班時間要控制;設(shè)備A即要求充分利用,又盡可能不加班。要考慮上述多方面的目標(biāo),需要借助目標(biāo)規(guī)劃的方法。目標(biāo)規(guī)劃問題及模型線性規(guī)劃模型存在的局限性:1)要求問題的解必須滿足全部約束條件,實際問題中并非所有約束都需要嚴(yán)格滿足。2)只能處理單目標(biāo)的優(yōu)化問題。實際問題中,目標(biāo)和約束可以相互轉(zhuǎn)化。3)線性規(guī)劃中各個約束條件都處于同等重要地位,但現(xiàn)實問題中,各目標(biāo)的重要性即有層次上的差別,同一層次中又可以有權(quán)重上的區(qū)分。4)線性規(guī)劃尋求最優(yōu)解,但很多實際問題中只需找出滿意解就可以。目標(biāo)規(guī)劃問題及模型目標(biāo)規(guī)劃怎樣解決上述線性規(guī)劃模型建模中的局限性?1.設(shè)置偏差變量,用來表明實際值同目標(biāo)值之間的差異偏差變量用下列符號表示:d+——超出目標(biāo)的偏差,稱正偏差變量d-——未達到目標(biāo)的偏差,稱負(fù)偏差變量正負(fù)偏差變量兩者必有一個為0。當(dāng)實際值超出目標(biāo)值時:d+>0,d-=0;
當(dāng)實際值未達到目標(biāo)值時:d+=0,d->0;
當(dāng)實際值同目標(biāo)值恰好一致時:d+=0,d-=0;故恒有d+×d-=0目標(biāo)規(guī)劃問題及模型2.統(tǒng)一處理目標(biāo)和約束
對有嚴(yán)格限制的資源使用建立系統(tǒng)約束,數(shù)學(xué)形式同線性規(guī)劃中的約束條件。如C和D設(shè)備的使用限制。
對不嚴(yán)格限制的約束,連同原線性規(guī)劃建模時的目標(biāo),均通過目標(biāo)約束來表達。1)例如要求甲、乙兩種產(chǎn)品保持1:1的比例,系統(tǒng)約束表達為:x1=x2。由于這個比例允許有偏差,當(dāng)x1<x2時,出現(xiàn)負(fù)偏差d-,即:x1+d-
=x2或x1-x2+d-
=0當(dāng)x1>x2時,出現(xiàn)正偏差d+,即:x1-d+
=x2或x1-x2-d+
=0目標(biāo)規(guī)劃問題及模型∵正負(fù)偏差不可能同時出現(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ī)劃問題及模型3)設(shè)備B必要時可加班及加班時間要控制,目標(biāo)約束表示為:2)力求使利潤指標(biāo)不低于12元,目標(biāo)約束表示為:4)設(shè)備A既要求充分利用,又盡可能不加班,目標(biāo)約束表示為:目標(biāo)規(guī)劃問題及模型3.目標(biāo)的優(yōu)先級與權(quán)系數(shù)
在一個目標(biāo)規(guī)劃的模型中,為達到某一目標(biāo)可犧牲其他一些目標(biāo),稱這些目標(biāo)是屬于不同層次的優(yōu)先級。優(yōu)先級層次的高低可分別通過優(yōu)先因子P1,P2,…表示。對于同一層次優(yōu)先級的不同目標(biāo),按其重要程度可分別乘上不同的權(quán)系數(shù)。權(quán)系數(shù)是一個個具體數(shù)字,乘上的權(quán)系數(shù)越大,表明該目標(biāo)越重要?,F(xiàn)假定:
第1優(yōu)先級P1——企業(yè)利潤;第2優(yōu)先級P2——甲乙產(chǎn)品的產(chǎn)量保持1:1的比例第3優(yōu)先級P3——設(shè)備A,B盡量不超負(fù)荷工作。其中設(shè)備A的重要性比設(shè)備B大三倍。目標(biāo)規(guī)劃問題及模型上述目標(biāo)規(guī)劃模型可以表示為:目標(biāo)規(guī)劃問題及模型5.目標(biāo)規(guī)劃的目標(biāo)函數(shù)由各目標(biāo)約束的正、負(fù)偏差變量及相應(yīng)的優(yōu)先因子和權(quán)系數(shù)構(gòu)成。從決策者的要求來分析,總希望得到的結(jié)果與規(guī)定的指標(biāo)值之間的偏差量愈小愈好。由此可構(gòu)造一個使總偏差量為最小化的目標(biāo)函數(shù),minZ=f(d+,d-)其基本形式有三種:4.滿意解
對于這種解來說,前面的目標(biāo)可以保證實現(xiàn)或部分實現(xiàn),而后面的目標(biāo)就不一定能保證實現(xiàn)或部分實現(xiàn),有些可能就不能實現(xiàn)。目標(biāo)規(guī)劃問題及模型(1)要求恰好達到目標(biāo)值,即正、負(fù)偏差變量都要盡可能地小。構(gòu)造的目標(biāo)函數(shù)是
minZ=f(d++d-
)
(2)要求不超過目標(biāo)值,但允許達不到目標(biāo)值,即只有使正偏差量要盡可能地小(實現(xiàn)最少或為零)
minZ=f(d+)(3)要求超過目標(biāo)值,即超過量不限。要求超額完成規(guī)定目標(biāo),要實現(xiàn)負(fù)偏差量為零或為最小
minZ=f(d-)目標(biāo)規(guī)劃問題及模型
建模的步驟1、根據(jù)要研究的問題所提出的各目標(biāo)與條件,確定目標(biāo)值,列出目標(biāo)約束與絕對約束;4、對同一優(yōu)先等級中的各偏差變量,若需要可按其重要程度的不同,賦予相應(yīng)的權(quán)系數(shù)。3、給各目標(biāo)賦予相應(yīng)的優(yōu)先因子Pi(i=1.2…L)。2、可根據(jù)決策者的需要,將某些或全部絕對約束轉(zhuǎn)化為目標(biāo)約束。這時只需要給絕對約束加上負(fù)偏差變量和減去正偏差變量即可。目標(biāo)規(guī)劃問題及模型目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式目標(biāo)函數(shù)(達成函數(shù))目標(biāo)約束其中:gk為第k個目標(biāo)約束的預(yù)期目標(biāo)值,和為pl優(yōu)先因子對應(yīng)各目標(biāo)的權(quán)系數(shù)。目標(biāo)規(guī)劃問題及模型用目標(biāo)規(guī)劃求解問題的過程:明確問題,列出目標(biāo)的優(yōu)先級和權(quán)系數(shù)構(gòu)造目標(biāo)規(guī)劃模型求出滿意解滿意否?分析各項目標(biāo)完成情況據(jù)此制定出決策方案NY目標(biāo)規(guī)劃問題及模型例2.某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品,有關(guān)數(shù)據(jù)如表所示。試求獲利最大的生產(chǎn)方案?
在此基礎(chǔ)上考慮:
1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量;
2、充分利用設(shè)備有效臺時,不加班;
3、利潤不小于56元。解:分析第二目標(biāo)P2
:第三目標(biāo)P3
:第一目標(biāo)P1:ⅠⅡ擁有量原材料2111設(shè)備(臺時)1210單件利潤810目標(biāo)規(guī)劃問題及模型1、產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量;
2、充分利用設(shè)備有效臺時,不加班;
3、利潤不小于56元。2x1+x2≤11(在絕對約束基礎(chǔ)上進行目標(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è)備(臺時)1210單件利潤810Introduction目標(biāo)規(guī)劃問題及模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形法主要內(nèi)容目標(biāo)規(guī)劃靈敏度分析目標(biāo)規(guī)劃應(yīng)用舉例目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的圖解法:
適用兩個變量的目標(biāo)規(guī)劃問題,但其操作簡單,原理一目了然。同時,也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。圖解法解題步驟:1.將所有約束條件(包括目標(biāo)約束和絕對約束,暫不考慮正負(fù)偏差變量)的直線方程分別標(biāo)示于坐標(biāo)平面上。2.確定系統(tǒng)約束的可行域。3.在目標(biāo)約束所代表的邊界線上,用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向目標(biāo)規(guī)劃的圖解法4.求滿足最高優(yōu)先等級目標(biāo)的解5.轉(zhuǎn)到下一個優(yōu)先等級的目標(biāo),再不破壞所有較高優(yōu)先等級目標(biāo)的前提下,求出該優(yōu)先等級目標(biāo)的解6.重復(fù)5,直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止7.確定最優(yōu)解和滿意解。目標(biāo)規(guī)劃的圖解法例4.用圖解法求解下列目標(biāo)規(guī)劃問題目標(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上任意點其中G點X=(2,4)T,D點X=(10/3,10/3)T05.51055.6112,410/3,10/35107例5.Introduction目標(biāo)規(guī)劃問題及模型目標(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ī)劃的單純形法一、特點1.目標(biāo)函數(shù):min2.最優(yōu)性判斷:σj≥0時為最優(yōu)3.非基變量檢驗數(shù)的特殊性:含有不同等級的優(yōu)先因子P1,P2,…,Pk;又因P1>>P2>>P3>>…>>Pk
,所以檢驗數(shù)的正負(fù)首先取決于P1的系數(shù)的正負(fù),若P1
的系數(shù)為0,再由P2
的系數(shù)的正負(fù)決定檢驗數(shù)的正負(fù),然后依次類推。目標(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;解目標(biāo)規(guī)劃問題的單純形法的計算步驟(2)檢查當(dāng)前第k行中是否存在大于0,且對應(yīng)的前k-1行的同列檢驗數(shù)為零的檢驗數(shù)。若有取其中最大者對應(yīng)的變量為換入變量,轉(zhuǎn)(3)。若無這樣的檢驗數(shù),則轉(zhuǎn)(5);目標(biāo)規(guī)劃的單純形法(4)按單純形法進行基變換運算,建立新的單純形表,(注意:要對所有的行進行轉(zhuǎn)軸運算)返回(2);(5)當(dāng)k=K時,計算結(jié)束。表中的解即為滿意解。否則置k=k+1,返回(2)。(3)按單純形法中的最小比值規(guī)則確定換出變量,當(dāng)存在兩個和兩個以上相同的最小比值時,選取具有較高優(yōu)先級別的變量為換出變量,轉(zhuǎn)(4);目標(biāo)規(guī)劃的單純形法例1.用單純形法求解下列目標(biāo)規(guī)劃問題解:將上述目標(biāo)規(guī)劃問題化為標(biāo)準(zhǔn)型:目標(biāo)規(guī)劃的單純形法建立初始單純形表:目標(biāo)規(guī)劃的單純形法θ=min{-,10/2,56/10,11/1}=5進基變量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,進基變量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+的檢驗數(shù)為零,故此題有無窮多最優(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進基變量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ī)劃問題目標(biāo)規(guī)劃的單純形法Cj00P100P302.5P20P2CBXBbx1x2P1250030121-1000000014021001-100000601000001-1000100010000001-1σjP1
-30-1201000000P2
00000002.501P3
0000010000θ=min{2500/30,140/2,60/1,
-}=60,進基變量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進基變量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進基變量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進基變量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
溫馨提示
- 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. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度首付分期購房借款合同范本規(guī)定6篇
- 年度線性低密度聚乙烯產(chǎn)業(yè)分析報告
- 年度吸污車產(chǎn)業(yè)分析報告
- 2025年度樓房建筑工程合同糾紛解決協(xié)議4篇
- 二零二四年養(yǎng)老社區(qū)三方物業(yè)服務(wù)委托合同文本3篇
- 二零二五年度船舶租賃船運輸協(xié)議合同3篇
- 二零二五年酒店客房家具更新?lián)Q代合同3篇
- 2025年度智能交通信號系統(tǒng)安裝與維護承包協(xié)議合同范本3篇
- 二零二五版教育培訓(xùn)機構(gòu)合同標(biāo)的課程開發(fā)與教學(xué)質(zhì)量承諾3篇
- 2025年度生物質(zhì)能發(fā)電項目合作協(xié)議合同范本
- GB/T 33688-2017選煤磁選設(shè)備工藝效果評定方法
- GB/T 304.3-2002關(guān)節(jié)軸承配合
- 漆畫漆藝 第三章
- CB/T 615-1995船底吸入格柵
- 光伏逆變器一課件
- 貨物供應(yīng)、運輸、包裝說明方案
- (完整版)英語高頻詞匯800詞
- 《基礎(chǔ)馬來語》課程標(biāo)準(zhǔn)(高職)
- IEC61850研討交流之四-服務(wù)影射
- 《兒科學(xué)》新生兒窒息課件
- 材料力學(xué)壓桿穩(wěn)定
評論
0/150
提交評論