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

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

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

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

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

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

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

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

年收入=3x1+4x2

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

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

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

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

Mind1+s、t、20x1＋50x2≤900000、5x1+0、2x2-d1++d1-=7003x1+4x2-d2++d2-=10000x1,x2,d1+,d1-≥0目標規(guī)劃得圖解法圖2圖解法步驟2010002000300040005000200030004000x1x220x1＋50x2≤9000010000.5x1+0.2x2=700目標規(guī)劃得圖解法2、針對優(yōu)先權次高得目標建立線性規(guī)劃優(yōu)先權次高(P2)得目標就是總收益超過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目標規(guī)劃得圖解法3x1+4x2=10000圖3圖解法步驟3010002000300040005000200030004000x1x220x1＋50x2≤9000010000.5x1+0.2x2=700d1+>0d1+＝0d2-=0d2->0(810,1476)大家有疑問的，可以詢問和交流可以互相討論下，但要小聲點目標規(guī)劃得圖解法目標規(guī)劃得這種求解方法可以表述如下:

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

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

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

4、重復第3步,直至所有優(yōu)先權得目標求解完。

目標規(guī)劃得圖解法四、目標規(guī)劃模型得標準化例6中對兩個不同優(yōu)先權得目標單獨建立線性規(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

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

為第k

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

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

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

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

2x1+3x2-d1++d1-=680對應第1個目標

2x1+3x2-d2++d2-=600對應第2個目標

250x1+125x2-d3-+d3+＝70000對應第3個目標

x1-d4++d4-=200對應第4個目標

x2-d5++d5-=120對應第5個目標

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

【例8】某企業(yè)集團計劃用1000萬元對下屬5個企業(yè)進行技術改造,各企業(yè)單位得投資額已知,考慮2種市場需求變化、現(xiàn)有競爭對手、替代品得威脅等影響收益得4個因素,技術改造完成后預測單位投資收益率((單位投資獲得利潤/單位投資額)×100％)如表4－2所示、集團制定得目標就是:(1)希望完成總投資額又不超過預算;(2)總期望收益率達到總投資得30%;(3)投資風險盡可能最小;(4)保證企業(yè)5得投資額占20%左右、集團應如何作出投資決策、復雜情況下得目標規(guī)劃企業(yè)1企業(yè)2企業(yè)3企業(yè)4企業(yè)5單位投資額(萬元)1210151320單位投資收益率預測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復雜情況下得目標規(guī)劃【解】設xj(j=1,2,…,5)為集團對第j個企業(yè)投資得單位數(shù)、

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

（4）企業(yè)5占20%的投資的目標函數(shù)為,約束條件即(3）投資風險約束．投資風險值的大小一般用期望收益率的方差表示，但方差是x的非線性函數(shù)．這里用離差（rij－E(rj)）近似表示風險值，例如，集團投資5個企業(yè)后對于市場需求變化第一情形的風險是：則4種因素風險最小的目標函數(shù)為：，約束條件為復雜情況下得目標規(guī)劃根據(jù)目標重要性依次寫出目標函數(shù),整理后得到投資決策得目標規(guī)劃數(shù)學模型:復雜情況下得目標規(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)品