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

第 章规划扩展 人们探讨某些线性规划问题 有时必须把全部或部分决策变量限制为整数 这样的线性规划问题 通常称为整数规划 作为线性规划的特殊情况 整数规划也有最小化和最大化之别 此外 整数规划还可以分成纯整数规划和混整数规划 二者的区别在于 前者的决策变量必定全部取整数 而后者的决策变量只是部分取整数 如果全部的决策变量仅取0或1 称之为0 1规划 2 1整数规划 例1 选址决策问题 某公司决定建1到2个新工厂 甲地 乙地 同时考虑是否建一仓库 要求 1 最多建一个仓库 如建仓库 要与工厂在同一地点 2 公司对此次扩张的资金预算是1000万 问 公司如何决策使得投资净现值最大 解 Maxz 9x1 5x2 6x3 4x4 St6x1 3x2 5x3 2x4 10 x3 x4 1 x1 x3 0 x2 x4 0 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个区 每个区都可以建消防站 市政府希望设置的消防站最少 但必须满足在城市任何地区发生火警时 消防车要在15分钟内赶到现场 据实地测定 各区之间消防车行驶的时间见右表 请为该市制定一最节省消防站数目的计划 在第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小时 问该厂如何安排生产 可以使每月利润最大 生产西装的总利润 销售价格 数量 生产成本 数量 设备租金注意 只有生产西装 才会产生生产西装的设备租金 这个问题的整数规划模型为 上述整数规划正确吗 这个问题的整数规划模型为 如果这三种产品的产量之间还要满足一定的逻辑关系 例如分别考虑以下关系 每一种产品如果生产 最小批量为150件 如果产品1安排生产 产品2就不能生产 如果产品3生产 产品2必须生产 而且至少生产500件 每一种产品如果生产 最小批量为150件 相应的约束条件 x1 150y1 x2 150y2 x3 150y3 如果产品1安排生产 产品2就不能生产 相应的约束条件为 y1 y2 1 如果产品3安排生产 产品2必须生产 而且至少生产500件 相应的约束条件为 y2 y3x2 500y2 非线形规划 在数学规划问题中 当目标函数或约束函数中至少有一个是非线性函数时称这类问题为非线性规划 基本投资组合模型 例5 股票投资问题 期望年收益率至少达到15 应当如何投资 表中数据为年收益率数据 问题分析 收益不确定 收益的期望值 风险收益的方差 一种股票收益的均值衡量这种股票的平均收益状况 一种股票收益的方差衡量这种股票收益的波动幅度 两种股票收益的协方差表示他们之间的相关程度 方差越大 风险越大 方差越小 风险越小 数学期望 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 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投资股票A x2投资股票B x3投资股票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 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 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 决策变量 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 现要使两种情况下最小的收益最大化 即不管未来发生哪种情况 都能至少获得这个收益 如何建立模型和求解 优化模型与求解 决策变量 约束条件 目标函数 X1年初投资股票A X2年初投资股票B x1 x2 0 x1 x2 1 最小收益最大的 保守 目标实际上就是希望 Max min 1 0 x1 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 bxk c dz ez