整數(shù)規(guī)劃課件VIP

整數(shù)規(guī)劃課件目標(biāo)規(guī)劃問題舉例例3、投資企業(yè)投資時不僅僅要考慮收益率,還要考慮風(fēng)險。一般地,風(fēng)險大得投資其收益率更高。因此,企業(yè)管理者只有在對收益率與風(fēng)險承受水平有明確得期望值時,才能得到滿意得決策。例4、裁員同樣得,企業(yè)裁員時要考慮很多可能彼此矛盾得因素。裁員得首要目得就是壓縮人員開支,但在人人自危得同時員工得忠誠度就很難保證,此外,員工得心理壓力、工作壓力等都會增加,可能產(chǎn)生負(fù)面影響。例5、營銷營銷方案得策劃與執(zhí)行存在多個目標(biāo)。既希望能達到立竿見影得效果,又希望營銷得成本控制在某一個范圍內(nèi)。此外,營銷活動得深入程度也決定了營銷效果得好壞與持續(xù)時間。

例6、一位投資商有一筆資金準(zhǔn)備購買股票。資金總額為90000元,目前可選得股票有A與B兩種(可以同時投資于兩種股票)。其價格以及年收益率與風(fēng)險系數(shù)如表1:從上表可知,A股票得收益率為(3／20)×100％＝15％,股票B得收益率為4／50×100％＝8％,A得收益率比B大,但同時A得風(fēng)險也比B大。這也符合高風(fēng)險高收益得規(guī)律。試求一種投資方案,使得一年得總投資風(fēng)險不高于700,且投資收益不低于10000元。目標(biāo)規(guī)劃得圖解法股票價格（元）年收益（元）／年風(fēng)險系數(shù)A2030.5B5040.2目標(biāo)規(guī)劃得圖解法

顯然,此問題屬于目標(biāo)規(guī)劃問題。它有兩個目標(biāo)變量:一就是限制風(fēng)險,一就是確保收益。在求解之前,應(yīng)首先考慮兩個目標(biāo)得優(yōu)先權(quán)。假設(shè)第一個目標(biāo)(即限制風(fēng)險)得優(yōu)先權(quán)比第二個目標(biāo)(確保收益)大,這意味著求解過程中必須首先滿足第一個目標(biāo),然后在此基礎(chǔ)上再盡量滿足第二個目標(biāo)。建立模型:設(shè)x1、x2分別表示投資商所購買得A股票與B股票得數(shù)量。首先考慮資金總額得約束:總投資額不能高于90000元。即

20x1＋50x2≤90000。目標(biāo)規(guī)劃得圖解法一、約束條件再來考慮風(fēng)險約束:總風(fēng)險不能超過700。投資得總風(fēng)險為0、5x1＋0、2x2。引入兩個變量d1+與d1-,建立等式如下:

0、5x1+0、2x2=700+d1+-d1-

其中,d1+表示總風(fēng)險高于700得部分,d1-表示總風(fēng)險少于700得部分,d1+≥0。目標(biāo)規(guī)劃中把d1+、d1-這樣得變量稱為偏差變量。偏差變量得作用就是允許約束條件不被精確滿足。目標(biāo)規(guī)劃得圖解法把等式轉(zhuǎn)換,可得到

0、5x1+0、2x2-d1++d1-=700。再來考慮年收入:

年收入=3x1+4x2

引入變量d2+與d2-,分別表示年收入超過與低于10000得數(shù)量。于就是,第2個目標(biāo)可以表示為

3x1+4x2-d2++d2-=10000。

目標(biāo)規(guī)劃得圖解法二、有優(yōu)先權(quán)得目標(biāo)函數(shù)本問題中第一個目標(biāo)得優(yōu)先權(quán)比第二個目標(biāo)大。即最重要得目標(biāo)就是滿足風(fēng)險不超過700。分配給第一個目標(biāo)較高得優(yōu)先權(quán)P1,分配給第二個目標(biāo)較低得優(yōu)先權(quán)P2。針對每一個優(yōu)先權(quán),應(yīng)當(dāng)建立一個單一目標(biāo)得線性規(guī)劃模型。首先建立具有最高優(yōu)先權(quán)得目標(biāo)得線性規(guī)劃模型,求解;然后再按照優(yōu)先權(quán)逐漸降低得順序分別建立單一目標(biāo)得線性規(guī)劃模型,方法就是在原來模型得基礎(chǔ)上修改目標(biāo)函數(shù),并把原來模型求解所得得目標(biāo)最優(yōu)值作為一個新得約束條件加入到當(dāng)前模型中,并求解。

目標(biāo)規(guī)劃得圖解法三、圖解法1、針對優(yōu)先權(quán)最高得目標(biāo)建立線性規(guī)劃建立線性規(guī)劃模型如下:

Mind1+s、t、20x1＋50x2≤900000、5x1+0、2x2-d1++d1-=7003x1+4x2-d2++d2-=10000x1,x2,d1+,d1-≥0目標(biāo)規(guī)劃得圖解法圖2圖解法步驟2010002000300040005000200030004000x1x220x1＋50x2≤9000010000.5x1+0.2x2=700目標(biāo)規(guī)劃得圖解法2、針對優(yōu)先權(quán)次高得目標(biāo)建立線性規(guī)劃優(yōu)先權(quán)次高(P2)得目標(biāo)就是總收益超過10000。建立線性規(guī)劃如下:

Mind2-s、t、20x1＋50x2≤900000、5x1+0、2x2-d1++d1-=7003x1+4x2-d2++d2-=10000d1+＝0x1,x2,d1+,d1-,d2+,d2-≥0目標(biāo)規(guī)劃得圖解法3x1+4x2=10000圖3圖解法步驟3010002000300040005000200030004000x1x220x1＋50x2≤9000010000.5x1+0.2x2=700d1+>0d1+＝0d2-=0d2->0(810,1476)大家有疑問的，可以詢問和交流可以互相討論下，但要小聲點目標(biāo)規(guī)劃得圖解法目標(biāo)規(guī)劃得這種求解方法可以表述如下:

1、確定解得可行區(qū)域。

2、對優(yōu)先權(quán)最高得目標(biāo)求解,如果找不到能滿足該目標(biāo)得解,則尋找最接近該目標(biāo)得解。

3、對優(yōu)先權(quán)次之得目標(biāo)進行求解。注意:必須保證優(yōu)先權(quán)高得目標(biāo)不變。

4、重復(fù)第3步,直至所有優(yōu)先權(quán)得目標(biāo)求解完。

目標(biāo)規(guī)劃得圖解法四、目標(biāo)規(guī)劃模型得標(biāo)準(zhǔn)化例6中對兩個不同優(yōu)先權(quán)得目標(biāo)單獨建立線性規(guī)劃進行求解。為簡便,把它們用一個模型來表達,如下:

MinP1(d1+)+P2(d2-)

s、t、20x1＋50x2≤900000、5x1+0、2x2-d1++d1-=7003x1+4x2-d2++d2-=10000x1,x2,d1+,d1-,d2+,d2-≥0

目標(biāo)規(guī)劃得基本概念(1)目標(biāo)規(guī)劃數(shù)學(xué)模型得形式有:線性模型、非線性模型、整數(shù)模型、交互作用模型等(2)一個目標(biāo)中得兩個偏差變量di-、di+至少一個等于零,偏差變量向量得叉積等于零:d－×d＋=0(3)一般目標(biāo)規(guī)劃就是將多個目標(biāo)函數(shù)寫成一個由偏差變量構(gòu)成得函數(shù)求最小值,按多個目標(biāo)得重要性,確定優(yōu)先等級,順序求最小值(4)按決策者得意愿,事先給定所要達到得目標(biāo)值當(dāng)期望結(jié)果不超過目標(biāo)值時,目標(biāo)函數(shù)求正偏差變量最小;當(dāng)期望結(jié)果不低于目標(biāo)值時,目標(biāo)函數(shù)求負(fù)偏差變量最小;當(dāng)期望結(jié)果恰好等于目標(biāo)值時,目標(biāo)函數(shù)求正負(fù)偏差變量之與最小目標(biāo)規(guī)劃得基本概念(5)由目標(biāo)構(gòu)成得約束稱為目標(biāo)約束,目標(biāo)約束具有更大得彈性,允許結(jié)果與所制定得目標(biāo)值存在正或負(fù)得偏差,如例4、1中得5個等式約束;如果決策者要求結(jié)果一定不能有正或負(fù)得偏差,這種約束稱為系統(tǒng)約束,如例4、1得材料約束;(6)目標(biāo)得排序問題。多個目標(biāo)之間有相互沖突時,決策者首先必須對目標(biāo)排序。排序得方法有兩兩比較法、專家評分等方法,構(gòu)造各目標(biāo)得權(quán)系數(shù),依據(jù)權(quán)系數(shù)得大小確定目標(biāo)順序;(7)合理得確定目標(biāo)數(shù)。目標(biāo)規(guī)劃得目標(biāo)函數(shù)中包含了多個目標(biāo),決策者對于具有相同重要性得目標(biāo)可以合并為一個目標(biāo),如果同一目標(biāo)中還想分出先后次序,可以賦予不同得權(quán)系數(shù),按系數(shù)大小再排序。目標(biāo)規(guī)劃得基本概念式中pk

為第k

級優(yōu)先因子,k=1、2、……K;wkl-、wkl+,為分別賦予第l個目標(biāo)約束得正負(fù)偏差變量得權(quán)系數(shù);gl為目標(biāo)得預(yù)期目標(biāo)值,l=1,…L、(4、1b)為系統(tǒng)約束,(4、1c)為目標(biāo)約束(8)目標(biāo)規(guī)劃得一般模型、設(shè)xj(j=1,2,…,n)為決策變量10、目標(biāo)規(guī)劃問題得解------------滿意解目標(biāo)規(guī)劃問題得求解就是分級進行得,首先求滿足級目標(biāo)得解,然后在保證級目標(biāo)不被破壞得前提下再求滿足級目標(biāo)得解、以此類推,因此,這樣最后求出得解就不就是通常意義下得最優(yōu)解,稱之為滿意解、

因為對于這種解來說,前面得目標(biāo)就是可以保證實現(xiàn)或部分實現(xiàn)得,后面得目標(biāo)就不一定能保證實現(xiàn)或部分實現(xiàn),有些可能就不能實現(xiàn)、滿意解這一概念得提出就是對最優(yōu)化概念得一個突破、顯然它更切合實際,更便于運用、9、目標(biāo)規(guī)劃得目標(biāo)函數(shù)目標(biāo)規(guī)劃得目標(biāo)函數(shù),就是由各目標(biāo)約束得偏差變量及相應(yīng)得優(yōu)先因子與權(quán)系數(shù)構(gòu)成,當(dāng)一個目標(biāo)規(guī)劃確定后決策者得要求就是盡可能接近各既定目標(biāo)值,也就就是偏差變量盡可能小,目標(biāo)函數(shù)一定就是極小化得,三種基本表達式、(1)要求恰好達到目標(biāo)值、這時決策值超過或低于目標(biāo)值都就是不希望得,因此有:(2)要求不超過目標(biāo)值,即允許達不到目標(biāo)值,就就是正偏差變量要盡可能地小,因此有:

(3)要求不低于目標(biāo)值,即允許超過目標(biāo)值,就就是負(fù)偏差變量要盡可能地小,因此有:復(fù)雜情況下得目標(biāo)規(guī)劃例7、一工藝品廠商手工生產(chǎn)某兩種工藝品A、B,已知生產(chǎn)一件產(chǎn)品A需要耗費人力2工時,生產(chǎn)一件產(chǎn)品B需要耗費人力3工時。A、B產(chǎn)品得單位利潤分別為250元與125元。為了最大效率地利用人力資源,確定生產(chǎn)得首要任務(wù)就是保證人員高負(fù)荷生產(chǎn),要求每周總耗費人力資源不能低于600工時,但也不能超過680工時得極限;次要任務(wù)就是要求每周得利潤超過70000元;在前兩個任務(wù)得前提下,為了保證庫存需要,要求每周產(chǎn)品A與B得產(chǎn)量分別不低于200與120件,因為B產(chǎn)品比A產(chǎn)品更重要,不妨假設(shè)B完成最低產(chǎn)量120件得重要性就是A完成200件得重要性得1倍。試求如何安排生產(chǎn)？復(fù)雜情況下得目標(biāo)規(guī)劃解:本問題中有3個不同優(yōu)先權(quán)得目標(biāo),不妨用P1、P2、P3表示從高至低得優(yōu)先權(quán)。對應(yīng)P1有兩個目標(biāo):每周總耗費人力資源不能低于600工時,也不能超過680工時;對應(yīng)P2有一個目標(biāo):每周得利潤超過70000元;對應(yīng)P3有兩個目標(biāo):每周產(chǎn)品A與B得產(chǎn)量分別不低于200與120件。復(fù)雜情況下得目標(biāo)規(guī)劃采用簡化模式,最終得到目標(biāo)線性規(guī)劃如下:

MinP1(d1+)+P1(d2－)+P2(d3-)+P3(d4-)+P3(2d5-)s、t、

2x1+3x2-d1++d1-=680對應(yīng)第1個目標(biāo)

2x1+3x2-d2++d2-=600對應(yīng)第2個目標(biāo)

250x1+125x2-d3-+d3+＝70000對應(yīng)第3個目標(biāo)

x1-d4++d4-=200對應(yīng)第4個目標(biāo)

x2-d5++d5-=120對應(yīng)第5個目標(biāo)

x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-≥0復(fù)雜情況下得目標(biāo)規(guī)劃使用運籌學(xué)軟件求解可得:x1=250;x2=60;d1+=0;d1-=0;d2+=80;d2-=0;d3+=0;d3-=0;d4+=50;d4-=0;d5+=0;d5-=60,目標(biāo)函數(shù)d4-+2d5-=120?？梢?目標(biāo)1、目標(biāo)3與目標(biāo)4達到了,但目標(biāo)2、目標(biāo)5都有一些偏差。

【例8】某企業(yè)集團計劃用1000萬元對下屬5個企業(yè)進行技術(shù)改造,各企業(yè)單位得投資額已知,考慮2種市場需求變化、現(xiàn)有競爭對手、替代品得威脅等影響收益得4個因素,技術(shù)改造完成后預(yù)測單位投資收益率((單位投資獲得利潤/單位投資額)×100％)如表4－2所示、集團制定得目標(biāo)就是:(1)希望完成總投資額又不超過預(yù)算;(2)總期望收益率達到總投資得30%;(3)投資風(fēng)險盡可能最小;(4)保證企業(yè)5得投資額占20%左右、集團應(yīng)如何作出投資決策、復(fù)雜情況下得目標(biāo)規(guī)劃企業(yè)1企業(yè)2企業(yè)3企業(yè)4企業(yè)5單位投資額(萬元)1210151320單位投資收益率預(yù)測rij市場需求14、3255、845、26、56市場需求23、523、045、084、26、24現(xiàn)有競爭對手3、162、23、563、284、08替代品得威脅2、243、122、62、23、24期望(平均)收益率％3、313、344、273、725、03表4－2復(fù)雜情況下得目標(biāo)規(guī)劃【解】設(shè)xj(j=1,2,…,5)為集團對第j個企業(yè)投資得單位數(shù)、

(1)總投資約束:(2)期望利潤率約束:整理得復(fù)雜情況下得目標(biāo)規(guī)劃

（4）企業(yè)5占20%的投資的目標(biāo)函數(shù)為,約束條件即(3）投資風(fēng)險約束．投資風(fēng)險值的大小一般用期望收益率的方差表示，但方差是x的非線性函數(shù)．這里用離差（rij－E(rj)）近似表示風(fēng)險值，例如，集團投資5個企業(yè)后對于市場需求變化第一情形的風(fēng)險是：則4種因素風(fēng)險最小的目標(biāo)函數(shù)為：，約束條件為復(fù)雜情況下得目標(biāo)規(guī)劃根據(jù)目標(biāo)重要性依次寫出目標(biāo)函數(shù),整理后得到投資決策得目標(biāo)規(guī)劃數(shù)學(xué)模型:復(fù)雜情況下得目標(biāo)規(guī)劃【例1】車間計劃生產(chǎn)I、II兩種產(chǎn)品,每種產(chǎn)品均需經(jīng)過A、B兩道工序加工、工藝資料如表4－3所示、產(chǎn)品工序產(chǎn)品甲產(chǎn)品乙每天加工能力(小時)A22120B12100C2、20、890產(chǎn)品售價(元/件)5070產(chǎn)品