第２章規劃擴展

人們探討某些線性規劃問題，有時必須把全部或部分決策變量限制為整數。這樣的線性規劃問題，通常稱為整數規劃。作為線性規劃的特殊情況，整數規劃也有最小化和最大化之別。此外，整數規劃還可以分成純整數規劃和混整數規劃。二者的區別在于：前者的決策變量必定全部取整數。而后者的決策變量只是部分取整數。如果全部的決策變量僅取0或1，稱之為0-1規劃。2.1整

數

規

劃例1(選址決策問題)某公司決定建1到2個新工廠：甲地,乙地;同時考慮是否建一倉庫。要求:(1)最多建一個倉庫,如建倉庫,要與工廠在同一地點;(2)公司對此次擴張的資金預算是1000萬;問:公司如何決策使得投資凈現值最大?投資決策投資凈現值(百萬)資本開支(百萬)工廠建在甲地96工廠建在乙地53倉庫建在甲地65倉庫建在乙地42解：Maxz=9x1+5x2+6x3+4x4St6x1+3x2+5x3+2x4≤10x3+x4≤1-x1+x3≤0-x2+x4≤0x1,x2,x3,x4為0-1變量(1)公司對此次擴張的資金預算是1000萬(2)最多建一個倉庫(3)如建倉庫,要與工廠在同一地點;想一想:10做第i件事不做第i件事n件事中必須做k件并只做k件事n件事中最多做k件事做第4件事的充要條件是做第6件事做第4件事的充要條件是不做第6件事只在做了第4件事前提下才考慮是否做第6件事如果做第4件事，則不能做第6件事例2（布點問題）某城市共有6個區，每個區都可以建消防站。市政府希望設置的消防站最少，但必須滿足在城市任何地區發生火警時，消防車要在15分鐘內趕到現場。據實地測定，各區之間消防車行駛的時間見右表。地區123456101016282720210024321710316240122721428321201525527172715014620102125140

請為該市制定一最節省消防站數目的計劃。在第i個地區建站Z表示全區消防站總數不在第i個地區建站i=1,2,…,6布點問題模型：最優解x2=1,x4=1最優值Z=2例3（背包問題）一個旅行者，為了準備旅行的必備物品，要在背包里裝一些有用的東西，但他最多只能攜帶b公斤的東西，而每件物品都只能整件攜帶，于是他給每件物品規定了一個“價值”，以表示其有用程度。如果共有m件物品，第i件物品的重量為bi，價值為ci，問題就變成：在攜帶的物品總重量不超過b公斤的條件下，攜帶哪些物品可使總價值最大解：Z表示所帶物品的總價值攜帶物品的總重量數學模型：輔助0-1變量的使用假設有兩個約束條件:x1+5x2≤133x1+2x2≤18，

要求只有一個起作用。x1+5x2≤13+(1-y)M3x1+2x2≤18+My其中M為足夠大的正數0－1決策變量是表示是非決策的0－1變量；輔助0－1變量是引入模型的附加0－1變量，不代表一個是非決策，僅僅是為了方便建立模型，輔助0－1變量通常用y表示。部分約束選擇取值固定費用邏輯關系例4：一服裝廠可生產三種服裝，生產不同種類的服裝要租用不同的設備，設備租金和其它經濟參數見下表。假定市場需求不成問題，服裝廠每月可用人工工時為1500小時，問該廠如何安排生產，可以使每月利潤最大。設備租金(元)生產成本(元/件)銷售價格(元/件)人工工時(小時/件)設備工時(小時/件)設備可用工時(小時)西裝500028040053300襯衫2000304010.5300羽絨服300020030042300生產西裝的總利潤=銷售價格*數量-生產成本*數量-設備租金注意:只有生產西裝,才會產生生產西裝的設備租金.這個問題的整數規劃模型為maxz=120x1+10x2+100x3-5000y1-2000y2-3000y3st5x1+x2+4x3

15003x1-300

00.5x2-300

02x3-300

0x1，x2，x3

0，為整數,y1，y2，y3=0或1上述整數規劃正確嗎?這個問題的整數規劃模型為maxz=120x1+10x2+100x3-5000y1-2000y2-3000y3st5x1+x2+4x3

15003x1-300y1

00.5x2-300y2

02x3-300y3

0x1，x2，x3

0，為整數,y1，y2，y3=0或1如果這三種產品的產量之間還要滿足一定的邏輯關系，例如分別考慮以下關系：每一種產品如果生產，最小批量為150件；如果產品1安排生產，產品2就不能生產；如果產品3生產，產品2必須生產，而且至少生產500件；每一種產品如果生產，最小批量為150件；相應的約束條件：x1150y1，x2150y2，x3150y3maxz=120x1+10x2+100x3-5000y1-2000y2-3000y3st5x1+x2+4x3

15003x1-300y1

00.5x2-300y2

02x3-300y3

0x1-150y1≥0x2-150y2≥0x3-150y3≥0x1，x2，x3

0，為整數,y1，y2，y3=0或1如果產品1安排生產，產品2就不能生產；相應的約束條件為：y1+y2

1maxz=120x1+10x2+100x3-5000y1-2000y2-3000y3st5x1+x2+4x3

20003x1-300y1

00.5x2-300y2

02x3-300y3

0y1+y2

1x1，x2，x3

0，為整數,y1，y2，y3=0或1如果產品3安排生產，產品2必須生產，而且至少生產500件.相應的約束條件為：y2

y3 x2

500y2maxz=120x1+10x2+100x3-5000y1-2000y2-3000y3st5x1+x2+4x3

20003x1-300y1

00.5x2-300y2

02x3-300y3

0y2-y3≥0x2-500y2≥0x1，x2，x3

0，為整數,y1，y2，y3=0或1非線形規劃在數學規劃問題中，當目標函數或約束函數中至少有一個是非線性函數時稱這類問題為非線性規劃。年份股票A股票B股票C股票指數19930.30.2250.1490.25899719940.1030.290.260.19752619950.2160.2160.4190.3643611996-0.046-0.272-0.078-0.080711997-0.0710.1440.1690.0570819980.0560.107-0.0350.05501219990.0380.3210.13300890.3050.7320.3171320010.090.1950.0210.24016420020.0830.390.1310035-0.0720.006-0.0098920040.1760.7150.9080.526236基本投資組合模型:例5:股票投資問題期望年收益率至少達到15%，應當如何投資？表中數據為年收益率數據。問題分析收益不確定

收益的期望值風險收益的方差一種股票收益的均值衡量這種股票的平均收益狀況一種股票收益的方差衡量這種股票收益的波動幅度兩種股票收益的協方差表示他們之間的相關程度

方差越大，風險越大；方差越小，風險越小。數學期望：ER1=0.0890833,ER2=0.213667,ER3=0.234583協方差矩陣：

COV=假設股票A、B、C每年的收益率分別為R1，R2和R3

模型建立年收益率（的數學期望）不低于15%資金全部用于投資這三種股票

決策變量x1投資股票Ax2投資股票Bx3投資股票C約束條件x1,x2,x3

0，x1+x2+x3=1

x1ER1+x2ER2+x3ER3≥0.15目標函數年投資收益率的方差極小

二次規劃模型(QP)數學模型的lingo程序A占53%，B占36%，C占11%min=0.009907*x1^2+0.053526*x2^2+0.086375*x3^2+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（國庫券）占67%結果分析

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

y3

假設賣出股票A、B、C的比例為z1

、z2和

z3

投資A大約占52.91%，B占35%，C占11.56%，約束條件x1,x2,x3

0，y1,y2,y30,z1,z2,z30。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*x1^2+0.053526*x2^2+0.086375*x3^2+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+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)

假設隨機誤差項ei是與其他股票j（j≠i）和股票指數M都是獨立的E(eiej)=E(eiM)=0如何根據所給數據經過回歸計算得到ui和

bi?記12年的數據為{M(k)，Ri

(k)}，（k=1，2，…,12）優化問題結果M的均值m0=1.191458，方差為s02=0.02873661標準差為s0=0.1695188A:u1

=0.5639761，b1

=0.4407264，

s12=0.005748320，

s1=0.07581767B:u2

=-0.2635059，

b2

=1.239802，

s22=0.01564263，

s2=0.1250705C:u3

=-0.5809590，

b3

=1.523798，

s32=0.03025165，

s3=0.1739300年收益率(數學期望)不低于15%決策變量

x1投資股票Ax2投資股票Bx3投資股票C約束條件x1,x2,x3

0，x1+x2+x3=1目標函數年投資收益率的方差極小

優化模型對應的收益:二次規劃模型(QP)與前結果A占53%，B占36%，C占11%比較,略有差異A占53%，B占38%，C占9%結果其他目標下的投資組合模型-例9:保守股票投資市場上只有兩只股票A、B可供某個投資者購買,市場只能出現兩種可能的情況（1和2）情形發生概率股票A股票B10.81.01.220.21.50.7現要使兩種情況下最小的收益最大化（即不管未來發生哪種情況，都能至少獲得這個收益），如何建立模型和求解？優化模型與求解決策變量約束條件目標函數X1年初投資股票AX2年初投資股票Bx1,x2

0，x1+x2=1最小收益最大的“保守”目標實際上就是希望：

Max{min(1.0x1+1.2x2,1.5x1+0.7x2)}引入一個輔助變量y，這個模型就可以線性化。相應的LINDO模型為：MAXySubjecttox1+x2=1x1+1.2x2-y>01.5x1+0.7x2-y>0求解得到：應該投資A、B股票各50%，至少可以增值10%求解得到：應該投資A股票54.5455%，B股票45.4545%，至少可以增值13.6364%.現在，假設有一條重要信息：如果情形1發生，股票B的增值將達到30%而不是表中給出的20%。那么，一般人的想法應該是增加對股票B的持有份額。果真如此嗎？這個投資人如果將上面模型中的1.2改為1.3計算也就是說，應該減少對股票B的持有份額，增加對股票A的持有份額！這真是叫人大吃一驚！這相當于說：有人告訴你有某只股票漲幅要增加了，你趕緊說：那我馬上把這只股票再賣點吧。之所以出現如此奇怪的現象，就是由于這個例子中的目標的特殊性引起的

某裝飾材料公司欲以每桶2元的價錢購進一批彩漆。一般來說隨著彩漆售價的提高，預期銷售量將減少，并對此進行了估算，見表1。為了盡快收回資金并獲得較多的贏利，裝飾材料公司打算做廣告，投入一定的廣告費后，銷售量將有一個增長，可由銷售增長因子來表示。根據經驗，廣告費與銷售增長因子關系見表2。現在的問題是裝飾材料公司采取怎樣的營銷戰略會使預期的利潤最大？廣告的費用及其效應表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

系數a，b，c，d，e是待定參數。模型的建立投入廣告費后，實際銷售量s等于預期銷售量y乘以銷售增長因子k，即s=ky。所獲得的利潤：

我們期望利潤P達到最大，即

由于目標函數不是線性函數，因此這一問題的數學模型為有約束條件