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

人们探讨某些线性规划问题，有时必须把全部或部分决策变量限制为整数。这样的线性规划问题，通常称为整数规划。作为线性规划的特殊情况，整数规划也有最小化和最大化之别。此外，整数规划还可以分成纯整数规划和混整数规划。二者的区别在于：前者的决策变量必定全部取整数。而后者的决策变量只是部分取整数。如果全部的决策变量仅取0或1，称之为0-1规划。2.1整数规划例1(选址决策问题)某公司决定建1到2个新工厂：甲地,乙地;同时考虑是否建一仓库。要求:(1)最多建一个仓库,如建仓库,要与工厂在同一地点;(2)公司对此次扩张的资金预算是1000万;问:公司如何决策使得投资净现值最大?投资决策投资净现值(百万)资本开支(百万)工厂建在甲地96工厂建在乙地53仓库建在甲地65仓库建在乙地42解：不在乙地建厂在乙地建厂设不在甲地建厂在甲地建厂设,0,1,,0,121xx则数学模型为不在乙地建仓库在乙地建仓库设不在甲地建仓库在甲地建仓库设,0,1,,0,143xxMaxz=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)如建仓库,要与工厂在同一地点;想一想:件事是否做第决策变量ixiix10做第i件事不做第i件事ni,,2,1n件事中必须做k件并只做k件事kxxxn21n件事中最多做k件事kxxxn21做第4件事的充要条件是做第6件事64xx做第4件事的充要条件是不做第6件事1xx64只在做了第4件事前提下才考虑是否做第6件事64xx如果做第4件事，则不能做第6件事1xx64例2（布点问题）某城市共有6个区，每个区都可以建消防站。市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见右表。地区123456101016282720210024321710316240122721428321201525527172715014620102125140请为该市制定一最节省消防站数目的计划。解：01ix在第i个地区建站Z表示全区消防站总数不在第i个地区建站i=1,2,…,6布点问题模型：654321minxxxxxxZ6,,2,11,0ixits.121xx1621xxx143xx1543xxx1652xxx最优解x2=1,x4=1最优值Z=2例3（背包问题）一个旅行者，为了准备旅行的必备物品，要在背包里装一些有用的东西，但他最多只能携带b公斤的东西，而每件物品都只能整件携带，于是他给每件物品规定了一个“价值”，以表示其有用程度。如果共有m件物品，第i件物品的重量为bi，价值为ci，问题就变成：在携带的物品总重量不超过b公斤的条件下，携带哪些物品可使总价值最大解：件物品不带第件物品带第设iixi01Z表示所带物品的总价值件带第iicZmiiixc1携带物品的总重量miiixb1数学模型：m1iiixcZmaxm,2,1i1,0xbxbt.sim1iii，辅助0-1变量的使用假设有两个约束条件:x1+5x2≤133x1+2x2≤18，要求只有一个起作用。，第一个约束不起作用，第一个约束起作用设01yx1+5x2≤13+(1-y)M3x1+2x2≤18+My其中M为足够大的正数0－1决策变量是表示是非决策的0－1变量；辅助0－1变量是引入模型的附加0－1变量，不代表一个是非决策，仅仅是为了方便建立模型，辅助0－1变量通常用y表示。部分约束),...,2,1(...2211mibxaxaxamininii个约束条件：有个起作用要求只有k),...,2,1,0,1miiiyi（个约束条件起作用第个约束条件不起作用第定义：kmyyymiMybxaxaxamiininii...),...,2,1(...212211则有：选择取值NnNbbbxxxfbbbN...,),...,,(),...,,212121，或即：中的某一个个值（是约束条件的右端项可能),...,2,1,0,1Nibyii（否则约束条件右端项为定义：1...),...,,(21121NNiiinyyyybxxxf则有：固定费用0x,00x,cxk)x(Ckx生产费用函数通常为备费用。是同产量无关的生产准代表产品的生产数量，用:,s,p,此时模型为市场需求为并且产品市场价格是润最大当问题是生产产品的利)cxky(pxzmax10y,0xsx.t.s或0Myx0x,00x,1y定义10y,0xsyx.t.s)cxky(pxzmax或逻辑关系无限制则不成立如果必须成立；则如果)x(k,0)x(f0)x(k,0)x(f10yMy)x(k)y1(M)x(f或则有：例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上述整数规划正确吗?1111,x0y0,x0这个问题的整数规划模型为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件；相应的约束条件：x1150y1，x2150y2，x3150y3maxz=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y3x2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.1330.18792520000.0890.3050.7320.3171320010.090.1950.0210.24016420020.0830.390.1310.18367520030.035-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和R30.0099070.0113730.0119860.0113730.0535260.0508080.0119860.0508080.086375模型建立年收益率（的数学期望）不低于15%资金全部用于投资这三种股票决策变量x1投资股票Ax2投资股票Bx3投资股票C约束条件x1,x2,x30，x1+x2+x3=1x1ER1+x2ER2+x3ER3≥0.15313332233112211332211332211),cov(),cov(2),cov(2),cov(2)()()()(jijijiRRxxRxRxRxRxRxRxRxDRxDRxDRxRxRxDV目标函数年投资收益率的方差极小二次规划模型(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.