数据模型决策02规划扩展1

1、 人们人们探讨某些线性规划问题，有时必须把探讨某些线性规划问题，有时必须把全部或部分决策变量限制为整数。这样的线性全部或部分决策变量限制为整数。这样的线性规划问题，通常称为规划问题，通常称为整数规划整数规划。作为线性规划。作为线性规划的特殊情况，整数规划也有最小化和最大化之的特殊情况，整数规划也有最小化和最大化之别。此外，整数规划还可以分成别。此外，整数规划还可以分成纯整数规划纯整数规划和和混整数规划混整数规划。二者的区别在于：前者的决策变。二者的区别在于：前者的决策变量必定量必定。而后者的决策变量。而后者的决策变量。如果全部的决策变量仅取。如果全部的决策变量仅取0 0或或1 1，称，称之为之

2、为0-10-1规划规划。例1 (选址决策问题)某公司决定建1到2个新工厂：甲地,乙地; 同时考虑是否建一仓库。要求:(1)最多建一个仓库,如建仓库,要与工厂在同一地点;(2)公司对此次扩张的资金预算是1000万;问:公司如何决策使得投资净现值最大?投资决策投资净现值(百万) 资本开支(百万)工厂建在甲地96工厂建在乙地53仓库建在甲地65仓库建在乙地42解：不在乙地建厂在乙地建厂设不在甲地建厂在甲地建厂设, 0, 1, 0, 121xx则数学模型为不在乙地建仓库在乙地建仓库设不在甲地建仓库在甲地建仓库设, 0, 1, 0, 143xxMax z=9x1+5x2+6x3+4x4St 6x1+3x

3、2+5x3+2x410 x3+x41-x1+x30-x2+x40 x1,x2,x3,x4为0-1变量(1)公司对此次扩张的资金预算是1000万(2)最多建一个仓库(3)如建仓库,要与工厂在同一地点;想一想:件事是否做第决策变量ixiix10做第i件事不做第i件事ni,2, 1n件事中必须做k件并只做k件事kxxxn21n件事中最多做k件事kxxxn21做第4件事的充要条件是做第6件事64xx做第4件事的充要条件是不做第6件事1xx64只在做了第4件事前提下才考虑是否做第6件事64xx如果做第4件事，则不能做第6件事1xx64例2（布点问题）某城市共有6个区，每个区都可以建消防站。市政府希望设置

4、的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见右表。地区123456101016282720210024321710316240122721428321201525527172715014620102125140 请为该市制定一最节省消防站数目的计划。解：01ix在第i个地区建站Z表示全区消防站总数不在第i个地区建站i=1,2, ,6布点问题模型：654321minxxxxxxZ6 , 2 , 11 , 0ixits.121 xx1621xxx143 xx1543xxx1652xxx最优解x2=1, x4=1最优值Z=2例

5、3（背包问题）一个旅行者，为了准备旅行的必备物品，要在背包里装一些有用的东西，但他最多只能携带b公斤的东西，而每件物品都只能整件携带，于是他给每件物品规定了一个“价值”，以表示其有用程度。如果共有m件物品，第i件物品的重量为bi，价值为ci，问题就变成：在携带的物品总重量不超过b公斤的条件下，携带哪些物品可使总价值最大解：件物品不带第件物品带第设iixi01Z表示所带物品的总价值件带第 iicZmiiixc1携带物品的总重量miiixb1数学模型：m1iiixcZmaxm, 2 , 1i1 , 0 xbxbt . sim1iii，辅助0-1变量的使用假设有两个约束条件: x1+5x213 3x

6、1+2x2 18， 要求只有一个起作用。，第一个约束不起作用，第一个约束起作用设01yx1+5x213+(1-y)M 3x1+2x2 18+My其中M为足够大的正数01决策变量是表示是非决策的01变量；辅助01变量是引入模型的附加01变量，不代表一个是非决策，仅仅是为了方便建立模型，辅助01变量通常用y表示。部分约束),.,2 , 1(.2211mibxaxaxamininii个约束条件：有个起作用要求只有k),.,2 , 1, 0, 1miiiyi（个约束条件起作用第个约束条件不起作用第定义：kmyyymiMybxaxaxamiininii.),.,2 , 1(.212211则有：选择取值N

7、nNbbbxxxfbbbN.,),.,(),.,212121，或即：中的某一个个值（是约束条件的右端项可能),.,2 , 1, 0, 1Nibyii（否则约束条件右端项为定义：1.),.,(21121NNiiinyyyybxxxf则有：固定费用0 x, 00 x,cxk)x(Ckx生产费用函数通常为备费用。是同产量无关的生产准代表产品的生产数量，用:, s, p,此时模型为市场需求为并且产品市场价格是润最大当问题是生产产品的利)cxky(pxzmax10y, 0 xsx. t . s或0Myx0 x, 00 x, 1y定义10y, 0 xsyx. t . s)cxky(pxzmax或逻辑关系无

8、限制则不成立如果必须成立；则如果)x(k,0)x(f0)x(k, 0)x(f10yMy)x(k)y1 (M)x(f或则有：例4： 一服装厂可生产三种服装，生产不同种类的服装要租用不同的设备，设备租金和其它经济参数见下表。假定市场需求不成问题，服装厂每月可用人工工时为1500小时，问该厂如何安排生产，可以使每月利润最大。 设备租金(元)生产成本(元/件)销售价格(元/件)人工工时(小时/件)设备工时(小时/件)设备可用工时(小时)西装500028040053300衬衫2000304010.5300羽绒服300020030042300生产西装的总利润=销售价格*数量-生产成本*数量-设备租金注意注

9、意:只有生产西装只有生产西装,才会产生生产西装的设备租金才会产生生产西装的设备租金.这个问题的整数规划模型为max z=120 x1+10 x2+100 x3-5000y1-2000y2-3000y3st5x1+x2+4x31500 3x1-30000.5x2-30002x3-3000 x1，x2，x30，为整数, y1，y2，y3=0或1上述整数规划正确吗上述整数规划正确吗?1111,x0y0,x0这个问题的整数规划模型为max z=120 x1+10 x2+100 x3-5000y1-2000y2-3000y3st5x1+x2+4x31500 3x1-300y100.5x2-300y202

10、x3-300y30 x1，x2，x30，为整数, y1，y2，y3=0或1如果这三种产品的产量之间还要满足一定的逻辑关系，例如分别考虑以下关系：每一种产品如果生产，最小批量为150件；如果产品1安排生产，产品2就不能生产；如果产品3生产，产品2必须生产，而且至少生产500件；每一种产品如果生产，最小批量为150件；相应的约束条件：x1150y1，x2150y2，x3150y3max z=120 x1+10 x2+100 x3-5000y1-2000y2-3000y3st5x1+x2+4x31500 3x1-300y100.5x2-300y202x3-300y30 x1-150y10 x2-15

11、0y20 x3-150y30 x1，x2，x30，为整数, y1，y2，y3=0或1如果产品1安排生产，产品2就不能生产；相应的约束条件为：y1+y21 max z=120 x1+10 x2+100 x3-5000y1-2000y2-3000y3st5x1+x2+4x32000 3x1-300y100.5x2-300y202x3-300y30y1+y21x1，x2，x30，为整数, y1，y2，y3=0或1如果产品3安排生产，产品2必须生产，而且至少生产500件 .相应的约束条件为：y2y3 x2500y2max z=120 x1+10 x2+100 x3-5000y1-2000y2-3000

12、y3st5x1+x2+4x32000 3x1-300y100.5x2-300y202x3-300y30y2-y30 x2-500y20 x1，x2，x30，为整数, 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.

13、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%，应当如何投资？表中数据为年收益率数据。问题分析收益不确定 收益的期望值 风险 收益的方差一种股票收益的均值衡量这种股票的平均收益状况一种股票收益的方

14、差衡量这种股票收益的波动幅度两种股票收益的协方差表示他们之间的相关程度方差越大，风险越大；方差越小，风险越小。数学期望：ER1=0.0890833, ER2=0.213667, ER3=0.234583协方差矩阵：COV = 假设股票A、B、C每年的收益率分别为R1，R2和R3 0.0099070.0113730.0119860.0113730.0535260.0508080.0119860.0508080.086375模型建立年收益率（的数学期望）不低于15% 资金 全部用于投资这三种股票 决策变量 x1投资股票Ax2投资股票Bx3投资股票C约束条件x1, x2 , x3 0，x1+x2 +

15、x3 = 1 x1ER1+x2ER2+x3ER3 0.15 313332233112211332211332211),cov(),cov(2),cov(2),cov(2)()()()(jijijiRRxxRxRxRxRxRxRxRxDRxDRxDRxRxRxDV目标函数 年投资收益率的方差极小 二次规划模型(QP)数学模型的lingo程序A占53%，B占36%，C占11% min=0.009907*x12+0.053526*x22+0.086375*x32+2*0.011373*x1*x2+2*0.011986*x1*x3+2*0.050808*x3*x2;0.089083*x1+0.2136

16、37*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

17、,诺贝尔经济学奖 继续考虑例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 , y3 0 , z1, z2 , z3 0。 x1+x2 +x3 +0.01( y1+y2

18、 +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*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-z

19、2;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（ji）和股票指数M都是独立的 E(eiej) = E(eiM) =0 如何根据所给数据经过回归计算得到ui 和 bi?记12年的数据为 M (k)，Ri (k)，（k=1，2，,12） 1212

20、)()(1212)(|)(minkkikiikkiRMbue优化问题 结果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 C :u3 = -0.5809590， b3 = 1.523798， s32= 0.03025165， s3= 0.1739300 年收益率(数学期望)不低于15% 决

21、策变量 x1投资股票Ax2投资股票Bx3投资股票C约束条件x1, x2 , x3 0，x1+x2 +x3 = 1 目标函数 年投资收益率的方差极小 优化模型对应的收益:)(3131iiiiiiiieMbuxRxR31031)()(iiiiiiiiimbuxeMbuExER15. 0)(310iiiimbux3122202312)()(iiiiiiiiiisxsbxeMbuDxDR二次规划模型(QP)与前结果A占53%，B占36%，C占11%比较,略有差异 32222201123301123min() 1 . . ()0.15 , , 0 iiiiiiiiix b sx sxxxstx ubmx

22、xxA占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.0 x1+1.2x2 , 1.5x1+0.7x2) 引入一个辅

23、助变量y，这个模型就可以线性化。相应的LINDO模型为： MAX ySubject tox1 + x2 = 1x1 + 1.2 x2 - y 01.5 x1 + 0.7 x2 - 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的

24、持有份额！这真是叫人大吃一惊！这相当于说：有人告诉你有某只股票涨幅要增加了，你赶紧说：那我马上把这只股票再卖点吧。之所以出现如此奇怪的现象，就是由于这个例子中的目标的特殊性引起的 某装饰材料公司欲以每桶2元的价钱购进一批彩漆。一般来说随着彩漆售价的提高，预期销售量将减少，并对此进行了估算，见表1。为了尽快收回资金并获得较多的赢利，装饰材料公司打算做广告，投入一定的广告费后，销售量将有一个增长，可由销售增长因子来表示。根据经验，广告费与销售增长因子关系见表2。现在的问题是装饰材料公司采取怎样怎样的营销战略的营销战略会使预期的利润最大？表1 表2 售价（元） 预期销售量（桶） 2.00 41000 2.50 38000 3.00 34000 3.50 32000 4.00 29000 4.50 28000 5.00 25000 5.50 2200