数据模型决策02规划扩展1（PPT45页).ppt

1、第章 规划扩展,人们探讨某些线性规划问题，有时必须把全部或部分决策变量限制为整数。这样的线性规划问题，通常称为整数规划。作为线性规划的特殊情况，整数规划也有最小化和最大化之别。此外，整数规划还可以分成纯整数规划和混整数规划。二者的区别在于：前者的决策变量必定全部取整数。而后者的决策变量只是部分取整数。如果全部的决策变量仅取0或1，称之为0-1规划。,2.1 整 数 规 划,例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个区，每个区都可以建消防站。市政府希望

3、设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见右表。,请为该市制定一最节省消防站数目的计划。,在第i个地区建站,Z表示全区消防站总数,不在第i个地区建站,i=1,2, ,6,布点问题模型：,最优解 x2=1, x4=1,最优值 Z=2,例3（背包问题）一个旅行者，为了准备旅行的必备物品，要在背包里装一些有用的东西，但他最多只能携带b公斤的东西，而每件物品都只能整件携带，于是他给每件物品规定了一个“价值”，以表示其有用程度。如果共有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小时，问该厂如何安排生产，可以使每月利润最大。,生产西装的总利润=销售价格*数量-生产成本*数量-设备租金 注意:只有生产西装,才会产生生产西装的设备租金.,这个问题的整数规划模型为,上述整数规划正确吗?,这个问题的整数规划模型为,如果这三种产品的产量之间还要满足一定的逻辑关系，例如分别考虑以下关系：,每一种产品如果生产，最小批量为150件； 如果产品1安排生产，产品2就不能生产； 如果产品3生产，产品2必须生产，而且至少生产500件；,每一种产品如果生产，最小批量为150件；相应的约束条件：,x1150y1，x2150y2，x3150y3,如果产品1安排生产，产

6、品2就不能生产；相应的约束条件为：,y1+y21,如果产品3安排生产，产品2必须生产，而且至少生 产500件 .相应的约束条件为：,y2y3 x2500y2,非线形规划,在数学规划问题中，当目标函数或约束函数中至少有一个是非线性函数时称这类问题为非线性规划。,基本投资组合模型: 例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,目标函数,年投资收益率的方差极小,二次规划模型(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, 诺贝尔经济学奖,继续考虑例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）,优化问题,结果,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,目标函数,年投资收益率的方差极小,优化模型,对应的收益:,二次规划模型(QP),与前结果A占53%，B占36%，C占11%比较,略有差异,A占53%，B占38%，C占9%,结果,其他目标下的投资组合模型- 例9:保守股票投资,市场上只有两只股票A、B可供某个投资者购买 ,市场只能出现两种可能的情况（1和2）,

14、现要使两种情况下最小的收益最大化（即不管未来发生哪种情况，都能至少获得这个收益），如何建立模型和求解？,优化模型与求解,决策变量,约束条件,目标函数,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发生，股票B的增值将达到30%而不是表中给出的20%。那么，一般人的想法应该是增加对股票B的持有份额。果真如此吗？这个投资人如果将上面模型中的1.2改为1.3计算,也就是说，应该减少对股票B的持有份额，增加对股票A的持有份额！这真是叫人大吃一惊！这相当于说：有人告诉你有某只股票涨幅要增加了，你赶紧说：那我马上把这只股票再卖点吧。之所以出现如此奇怪的现象，就是由于这个例子中的目标的特殊性引起的,某装饰材料公司欲以每桶2元的价钱购进一批彩漆。一般

16、来说随着彩漆售价的提高，预期销售量将减少，并对此进行了估算，见表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