1、第章 規(guī)劃擴展,人們探討某些線性規(guī)劃問題，有時必須把全部或部分決策變量限制為整數。這樣的線性規(guī)劃問題，通常稱為整數規(guī)劃。作為線性規(guī)劃的特殊情況，整數規(guī)劃也有最小化和最大化之別。此外，整數規(guī)劃還可以分成純整數規(guī)劃和混整數規(guī)劃。二者的區(qū)別在于：前者的決策變量必定全部取整數。而后者的決策變量只是部分取整數。如果全部的決策變量僅取0或1，稱之為0-1規(guī)劃。,2.1 整 數 規(guī) 劃,例1 (選址決策問題)某公司決定建1到2個新工廠： 甲地,乙地; 同時考慮是否建一倉庫。要求: (1)最多建一個倉庫,如建倉庫,要與工廠在同一地點; (2)公司對此次擴張的資金預算是1000萬; 問:公司如何決策使得投資凈現

2、值最大?,解：,Max z=9x1+5x2+6x3+4x4,St 6x1+3x2+5x3+2x410,x3+x41,-x1+x30,-x2+x40,x1,x2,x3,x4為0-1變量,(1)公司對此次擴張的資金預算是1000萬 (2)最多建一個倉庫 (3)如建倉庫,要與工廠在同一地點;,想一想:,1,0,做第i件事,不做第i件事,n件事中必須做k件并只做k件事,n件事中最多做k件事,做第4件事的充要條件是做第6件事,做第4件事的充要條件是不做第6件事,只在做了第4件事前提下才考慮是否做第6件事,如果做第4件事，則不能做第6件事,例2（布點問題）某城市共有6個區(qū)，每個區(qū)都可以建消防站。市政府希望

3、設置的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火警時，消防車要在15分鐘內趕到現場。據實地測定，各區(qū)之間消防車行駛的時間見右表。,請為該市制定一最節(jié)省消防站數目的計劃。,在第i個地區(qū)建站,Z表示全區(qū)消防站總數,不在第i個地區(qū)建站,i=1,2, ,6,布點問題模型：,最優(yōu)解 x2=1, x4=1,最優(yōu)值 Z=2,例3（背包問題）一個旅行者，為了準備旅行的必備物品，要在背包里裝一些有用的東西，但他最多只能攜帶b公斤的東西，而每件物品都只能整件攜帶，于是他給每件物品規(guī)定了一個“價值”，以表示其有用程度。如果共有m件物品，第i件物品的重量為bi，價值為ci，問題就變成：在攜帶的物品總重量不超過b公斤的

4、條件下，攜帶哪些物品可使總價值最大,解：,Z表示所帶物品的總價值,攜帶物品的總重量,數學模型：,輔助0-1變量的使用,假設有兩個約束條件: x1+5x213 3x1+2x2 18， 要求只 有一個起作用。,x1+5x213+(1-y)M 3x1+2x2 18+My 其中M為足夠大的正數,01決策變量是表示是非決策的01變量； 輔助01變量是引入模型的附加01變量，不代表一個是非決策，僅僅是為了方便建立模型，輔助01變量通常用y表示。,部分約束,選擇取值,固定費用,邏輯關系,例4： 一服裝廠可生產三種服裝，生產不同種類的服裝要租用不同的設備，設備租金和其它經濟參數見下表。假定市場需求不成問題，服

5、裝廠每月可用人工工時為1500小時，問該廠如何安排生產，可以使每月利潤最大。,生產西裝的總利潤=銷售價格*數量-生產成本*數量-設備租金 注意:只有生產西裝,才會產生生產西裝的設備租金.,這個問題的整數規(guī)劃模型為,上述整數規(guī)劃正確嗎?,這個問題的整數規(guī)劃模型為,如果這三種產品的產量之間還要滿足一定的邏輯關系，例如分別考慮以下關系：,每一種產品如果生產，最小批量為150件； 如果產品1安排生產，產品2就不能生產； 如果產品3生產，產品2必須生產，而且至少生產500件；,每一種產品如果生產，最小批量為150件；相應的約束條件：,x1150y1，x2150y2，x3150y3,如果產品1安排生產，產

6、品2就不能生產；相應的約束條件為：,y1+y21,如果產品3安排生產，產品2必須生產，而且至少生 產500件 .相應的約束條件為：,y2y3 x2500y2,非線形規(guī)劃,在數學規(guī)劃問題中，當目標函數或約束函數中至少有一個是非線性函數時稱這類問題為非線性規(guī)劃。,基本投資組合模型: 例5: 股票投資問題,期望年收益率至少達到15%，應當如何投資？ 表中數據為年收益率數據。,問題分析,收益不確定,收益的期望值,風險 收益的方差,一種股票收益的均值衡量這種股票的平均收益狀況,一種股票收益的方差衡量這種股票收益的波動幅度,兩種股票收益的協方差表示他們之間的相關程度,方差越大，風險越大；方差越小，風險越小

7、。,數學期望： ER1=0.0890833, ER2=0.213667, ER3=0.234583 協方差矩陣： COV =,假設股票A、B、C每年的收益率分別為R1，R2和R3,模型建立,年收益率（的數學期望）不低于15%,資金 全部用于投資這三種股票,決策變量,x1投資股票A,x2投資股票B,x3投資股票C,約束條件,x1, x2 , x3 0，x1+x2 +x3 = 1,x1ER1+x2ER2+x3ER3 0.15,目標函數,年投資收益率的方差極小,二次規(guī)劃模型(QP),數學模型的lingo程序,A占53%，B占36%，C占11%,min=0.009907*x12+0.053526*x2

8、2+0.086375*x32+2*0.011373*x1*x2+2*0.011986*x1*x3+2*0.050808*x3*x2; 0.089083*x1+0.213637*x2+0.234583*x3=0.15; x1+x2+x3=1; end,現有一種無風險的投資方式(如購買國庫券)。假設國庫券的年收益率為5%，如何考慮例5中的問題？,存在無風險資產時的投資組合模型- 例6:,問題分析,無風險的投資方式的收益固定,方差為0,特例,假設國庫券的投資方式記為D,投資A占8%，B占42%，C占14%，D占34%,要求的期望收益:15% 10%,投資A大約占4%，B占21%，C占7%，D（國庫券

9、）占67%,結果分析,風險資產之間的投資比例與期望收益和風險偏好無關,風險資產本身相互之間的比例不變,變化的只是投資于風險資產與無風險資產之間的比例,分離定理,Tobin教授,1981, 諾貝爾經濟學獎,繼續(xù)考慮例5（要求的期望收益率仍定為15%）。假設握有的股票比例為：股票A占50%，B占35%，C占15%。如按交易額的1% 收取交易費，,考慮交易成本的的投資組合模型- 例7:,問題:是否需要對手上的股票進行買賣（換手）？,模型建立,決策變量,x1投資股票A,x2投資股票B,x3投資股票C,假設購買股票A、B、C的比例為y1 、y2和 y3,假設賣出股票A、B、C的比例為z1 、z2和 z3

10、,投資A大約占52.91%，B占35%，C占11.56%，,約束條件,x1, x2 , x3 0，y1, y2 , y3 0 , z1, z2 , z3 0。,x1+x2 +x3 +0.01( y1+y2 +y3 + z1+z2 +z3 )= 1,注:持有的總資金守恒,ci為當前握有的各支股票的份額,xi = ci + yi - zi（i=1，2，3）,三者之和略小于100% ,為什么?,數學模型的lingo程序,min=0.009907*x12+0.053526*x22+0.086375*x32+2*0.011373*x1*x2+2*0.011986*x1*x3+2*0.050808*x3*

11、x2; 0.089083*x1+0.213637*x2+0.234583*x3=0.15; x1+x2+x3+0.01*(y1+y2+y3+z1+z2+z3)=1; x1=0.5+y1-z1; x2=0.35+y2-z2; x3=0.15+y3-z3; end,能否通過一定方式避免協方差的計算，對模型進行簡化呢？,利用股票指數簡化投資組合模型- 例8:,線性回歸,利用股票指數,假設每只股票的收益與股票指數成線性關系,M表示股票指數,均值為m0=E(M)，方差為s02=D(M),股票i，其價值Ri = ui + biM+ ei ,ei是一個隨機誤差項,均值為E(ei)=0，方差為si2=D(ei

12、),假設隨機誤差項ei是與其他股票j（ji）和股票指數M都是獨立的,E(eiej) = E(eiM) =0,如何根據所給數據經過回歸計算得到ui 和 bi?,記12年的數據為 M (k)，Ri (k)，（k=1，2，,12）,優(yōu)化問題,結果,M的均值m0=1.191458，方差為s02=0.02873661,標準差為s0=0.1695188,A:u1 =0.5639761， b1 =0.4407264， s12=0.005748320， s1=0.07581767,B:u2 = -0.2635059， b2 = 1.239802， s22= 0.01564263， s2= 0.1250705,

13、C :u3 = -0.5809590， b3 = 1.523798， s32= 0.03025165， s3= 0.1739300,年收益率(數學期望)不低于15%,決策變量,x1投資股票A,x2投資股票B,x3投資股票C,約束條件,x1, x2 , x3 0，x1+x2 +x3 = 1,目標函數,年投資收益率的方差極小,優(yōu)化模型,對應的收益:,二次規(guī)劃模型(QP),與前結果A占53%，B占36%，C占11%比較,略有差異,A占53%，B占38%，C占9%,結果,其他目標下的投資組合模型- 例9:保守股票投資,市場上只有兩只股票A、B可供某個投資者購買 ,市場只能出現兩種可能的情況（1和2）,

14、現要使兩種情況下最小的收益最大化（即不管未來發(fā)生哪種情況，都能至少獲得這個收益），如何建立模型和求解？,優(yōu)化模型與求解,決策變量,約束條件,目標函數,X1年初投資股票A,X2年初投資股票B,x1, x2 0，x1+x2 = 1,最小收益最大的“保守”目標實際上就是希望： Max min(1.0 x1+1.2x2 , 1.5x1+0.7x2) ,引入一個輔助變量y，這個模型就可以線性化。相應的LINDO模型為：,MAX y Subject to x1 + x2 = 1 x1 + 1.2 x2 - y 0 1.5 x1 + 0.7 x2 - y 0,求解得到 ：應該投資A、B股票各50%，至少可以

15、增值10%,求解得到 ：應該投資A股票54.5455%， B 股票45.4545%，至少可以增值13.6364% .,現在，假設有一條重要信息：如果情形1發(fā)生，股票B的增值將達到30%而不是表中給出的20%。那么，一般人的想法應該是增加對股票B的持有份額。果真如此嗎？這個投資人如果將上面模型中的1.2改為1.3計算,也就是說，應該減少對股票B的持有份額，增加對股票A的持有份額！這真是叫人大吃一驚！這相當于說：有人告訴你有某只股票漲幅要增加了，你趕緊說：那我馬上把這只股票再賣點吧。之所以出現如此奇怪的現象，就是由于這個例子中的目標的特殊性引起的,某裝飾材料公司欲以每桶2元的價錢購進一批彩漆。一般

16、來說隨著彩漆售價的提高，預期銷售量將減少，并對此進行了估算，見表1。為了盡快收回資金并獲得較多的贏利，裝飾材料公司打算做廣告，投入一定的廣告費后，銷售量將有一個增長，可由銷售增長因子來表示。根據經驗，廣告費與銷售增長因子關系見表2?，F在的問題是裝飾材料公司采取怎樣的營銷戰(zhàn)略會使預期的利潤最大？,廣告的費用及其效應,表1 表2,符號說明及問題的分析,設x表示售價（單位：元），y表示預期銷售量（單位：桶），z表示廣告費（單位：元），k表示銷售增長因子。投入廣告費后，實際銷售量記為s，獲得的利潤記為P（單位：元）。由表1易見預期銷售量 y 隨著售價x 的增加而單調下降，而銷售增長因子k在開始時隨著廣告費z的增加而增加，在廣告費z等于50000元時達到最大值，然后在廣告費增加時反而有所回落，為此可用spss畫出散點圖.,運行之后，可顯示圖1，圖2 圖-1 圖-2,從圖1和圖2易見，預期銷售量y與售價x近似于一條直線， 廣告費 z 與銷售增長因子k近似于一條二次曲線。為此可令： y=a+bx k=c+dz+ez2