Session06线性规划扩展推荐.ppt

Aetna School of Management,S.J.T.U. All Rights Reserved,Ren Jian Biao.,2001 Session6 Beyond Linear Programming 线性规划与电子表格 renjb@ Data, Model and Decisions 数据、模型与决策 Session 6 Beyond Linear Programming 线性规划扩展 Session Topics San Francisco Police Department 旧金山警署 Integer Programming 整数规划 Separable Programming 可分规划 Nonlinear Programming 非线性规划 Goal Programming 目标规划 Binary integer programming 0－1整数规划问题 San Francisco Police Department 旧金山警署 获奖经典 旧金山警署巡逻优化系统：1988年Franz Edelman奖一等奖管理科学研究（1989年Interfaces1－2号） 开发了用于警察工作安排与配置的计算机系统 每年节省开支$11百万，公交传票收入增加$3百万，响应时间也改善了20％ 问题的数学模型中，主要的决策变量是各轮班应在岗位上的警察数量 什么时候需要整数解？ 得到小数解时如何处理呢？ Integer Solutions 整数解 你有什么绝招吗？ The Challenges of Rounding 舍入解的挑战 舍入解可能不是可行解 舍入解与最优解离很远 可能有多个舍入解出现 Some Solution Technique 一些求解技术 Branch-and-Bound Technique 分枝定界技术 Branch-and-Cut Technique 割平面技术 How Integer Programs are Solved 如何求解整数规划 Types of Integer Programming 整数规划问题的类别 Pure integer programming 纯整数规划问题 Mixed integer programming 混合整数规划问题 Binary integer programming 0－1整数规划 Separable Programming 可分规划 线性规划的比例性假设 各种活动对目标函数值的贡献与活动水平成比例， 也就是目标函数中各和项是系数与决策变量的乘积 违背比例性假设 每增加一个单位的活动与前面第一个单位创造的的 收益不同，也就是线性规划活动的收益与活动的水 平不成比例 ? 每周最大产量 产品的单位利润 产品 正常工作时间 加班时间 总计 正常工作时间 加班时间 门 3 1 4 $300 $200 窗 3 3 6 500 100 （3D＋2W?18） Wyndor Glass Co. 伟恩德玻璃公司 实际举例 The Separable Programming Technique 可分规划的求解技术 对于违背比例性假设的任一活动，将其利润线划分 成多段，使得每一段为直线线段，为利润线上的每 一直线段引入新的可分决策变量，以代替原来的单 一决策变量 Wyndor Glass Co. 伟恩德玻璃公司 实际举例 在需要加班的情况下，伟恩德问题的电子表格模型 Nonlinear Programming 非线性规划 线性规划的可加性假设： 线性规划目标函数中每一项都只包含一个决策变 量，表示相应的活动对目标函数值的贡献,目标函 数值是所有活动的贡献的总和 在非线性规划问题中，由于交叉产品往往涉及到 多个决策变量，所以可能会违背可加性假设 Portfolio Selection 投资组合 模型的一般表达形式： Minimize 风险 约束条件 预期回报?最小可接受水平 哈里.马克维茨（Harry Markowtia）威廉.夏普（William Sharpe） Portfolio Selection 投资组合 实际举例 Source of Goal Programming 目标规划的来源 保持稳定的利润 增加市场份额 多样化产品线 保持价格稳定 管理层的目标通常包括下面一些内容： 提高员工的士气 保持对业务的控制力 增加公司的声誉 Goal Programming 目标规划 通过目标规划可以同时实现多个目标，最基本的方法 是为每一个目标建立一个量化的