数据、模型与决策-(6)课件.ppt

1、Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Data,Model and Decisions数据、模型与决策数据、模型与决策Session 6 Beyond Linear Programming 线性规划扩展线性规划扩展Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Session Topics San Francisco Police Department 旧金山警署旧金山警署 Integer Programming 整数规划整数规划 Separable Programming

2、 可分规划可分规划 Nonlinear Programming 非线性规划非线性规划 Goal Programming 目标规划目标规划 Binary integer programming 01整数规划问题整数规划问题Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 San Francisco Police Department旧金山警署旧金山警署获奖经典获奖经典旧金山警署巡逻优化系统：旧金山警署巡逻优化系统：1988年Franz Edelman奖一等奖管理科学研究（1989年Interfaces12号）开发了用于警察工作安排与配置的计算

3、机系统每年节省开支$11百万，公交传票收入增加$3百万，响应时间也改善了20问题的数学模型中，主要的决策变量是各轮班应在岗位上的警察数量Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 什么时候需要整数解？什么时候需要整数解？得到得到小数解时如何处理呢？小数解时如何处理呢？Integer Solutions整数解整数解你有什么绝招吗？你有什么绝招吗？Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 The Challenges of Rounding舍入解的挑战舍入解的挑战舍入解可能不是

4、可行解舍入解与最优解离很远可能有多个舍入解出现 1234512345x1x2Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Some Solution Technique一些求解技术一些求解技术Branch-and-Bound Technique分枝定界技术分枝定界技术Branch-and-Cut Technique割平面技术割平面技术Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 首先放弃变量的整数要求，求线性规划最优解如果最优解恰是一整数解，则最优解就是整数规划的最优解如果最优解

5、不是整数解，则要求构造一个新的约束，对线性规划问题的可行域进行切割，切除已得到的规划的最优解，但保留原可行域中所有的整数解，求解新的线性规划问题，如果最优解仍不是整数解，再增加附加的约束将其切除，但仍保持最初可行域中所有的整数解，如此一直进行，直至得到一个整数的最优解为止。Branch-and-Cut Technique割平面技术割平面技术Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Branch-and-Bound Techniqu

6、e分枝定界技术分枝定界技术 1234512345x1x2 1234512345x1x2Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Types of Integer Programming整数规划问题的类别整数规划问题的类别 Pure integer programming 纯整数规划问题纯整数规划问题 Mixed integer programming 混合整数规划问题混合整数规划问题 Binary integer programm

7、ing 01整数规划整数规划Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Separable Programming可分规划可分规划线性规划的比例性假设线性规划的比例性假设各种活动对目标函数值的贡献与活动水平成比例，也就是目标函数中各和项是系数与决策变量的乘积违背比例性假设违背比例性假设每增加一个单位的活动与前面第一个单位创造的的收益不同，也就是线性规划活动的收益与活动的水平不成比例 Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 每周最大产量每周最大产量产品的单位利润产品的单位利

8、润产品产品正常工作时间加班时间总计正常工作时间加班时间门门314$300$200窗窗336500100（3D2W18）Wyndor Glass Co.伟恩德玻璃公司伟恩德玻璃公司实际举例实际举例Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 The Separable Programming Technique可分规划的求解技术可分规划的求解技术对于违背比例性假设的任一活动，将其利润线划分成多段，使得每一段为直线线段，为利润线上的每一直线段引入新的可分决策变量，以代替原来的单一决策变量Session6Beyond Linear Progr

9、amming线性规划与电子表格线性规划与电子表格 Wyndor Glass Co.伟恩德玻璃公司伟恩德玻璃公司实际举例实际举例在需要加班的情况下，伟恩德问题的电子表格模型在需要加班的情况下，伟恩德问题的电子表格模型 Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Nonlinear Programming非线性规划非线性规划 线性规划的可加性假设线性规划的可加性假设：线性规划目标函数中每一项都只包含一个决策变量，表示相应的活动对目标函数值的贡献,目标函数值是所有活动的贡献的总和在非线性规划问题非线性规划问题中，由于交叉产品往往涉及到多个决

10、策变量，所以可能会违背可加性假设Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Portfolio Selection 投资组合投资组合模型的一般表达形式：模型的一般表达形式：Minimize 风险风险约束条件约束条件 预期回报预期回报 最小可接受水平最小可接受水平哈里.马克维茨（Harry Markowtia）威廉.夏普（William Sharpe）Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Portfolio Selection 投资组合投资组合实际举例实际举例Sessio

11、n6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Source of Goal Programming目标规划的来源目标规划的来源保持稳定的利润增加市场份额 多样化产品线 保持价格稳定 管理层的目标通常包括下面一些内容：管理层的目标通常包括下面一些内容：提高员工的士气 保持对业务的控制力 增加公司的声誉 Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Goal Programming目标规划目标规划通过目标规划目标规划可以同时实现多个目标，最基本的方法是为每一个目标建立一个量化的标准，通过平衡各标

12、准目标的实现程度，求得最优解。分配给各个目标的罚数权重（penalty weights）表示是偏离各目标的严重程度。根据各目标建立总目标函数，该目标函数表示的目标是要使得每个目标函数的偏差之和最小 Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Dewright Corp.德怀特公司德怀特公司实际举例实际举例德怀特公司的目标规划的电子表格模型德怀特公司的目标规划的电子表格模型 Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Binary integer programming 01整

13、数规划问题整数规划问题整数变量皆为整数变量皆为01变量的问题即为变量的问题即为01整数规整数规划问题（划问题（Binary integer programming）这种问题在实际工作中有哪些？这种问题在实际工作中有哪些？Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Types of Binary integer programming 01整数规划类型整数规划类型 Pure BIP problem纯纯BIP问题问题 Mixed BIP problem混合混合BIP问题问题01变量变量是用来表示是非决策变量是非决策变量的最佳方式，在考虑针

14、对某一选项的是非决策问题时，只有两种选择，接受或拒绝。可以用1表示接受，0表示拒绝。Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Applications of BIP 01整数规划应用整数规划应用 固定投资方案的资金预算固定投资方案的资金预算 Interfaces 1990年78月号土耳其炼油公司运用BIP 将数千百万的投资用于扩建炼油设施和能源储备上 选址选址 Interfaces 1997年12月号，AT&T公司运用BIP模 型帮助其客户选择电话营销中心，1988年AT&T公 司为其46个客户快速而准确的作出了选址决策Sessio

15、n6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Applications of BIP 01整数规划应用整数规划应用设计生产与配送网络设计生产与配送网络Interfaces 1995年12月号数字设备公司对公司整个全球供应链进行重整，年制造成本节省$500百万，物流成本节省$300百万，所需资金总额减少了$400百万 分配运货分配运货 Interfaces1991年12月号Reynolds Metals Co.以BIP为基础建立了自动的配送系统，为其200多家工厂、仓库和供应商解决运货问题，每年节省超过$7百万。Session6Beyond Line

16、ar Programming线性规划与电子表格线性规划与电子表格 Applications of BIP 01整数规划应用整数规划应用规划相关活动规划相关活动 Interfaces1995年12月号，中国国家计划委员会为了最小化折现成本，和世界银行合力开发了一个BIP模型，用于指导决策15年内在能源领域投入至少$2,400亿的规划，在15年内，会为中国节省近$64亿规划资产剥离规划资产剥离 Interfaces1987年12月号荷马特发展公司面临的一个主要问题是如何出售其购物中心和办公楼。有100多处资产需要在10年内售出。通过运用BIP指导决策，整个资产剥离计划的收入增加了$40百万 Ses

17、sion6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Applications of BIP 01整数规划应用整数规划应用航空方面的应用航空方面的应用 Interfaces1994年12月号Delta 航空公司航空公司运用一个大型的整数规划模型（包括40,000个函数约束，20,000个01决策变量，40,000个一般整数变量。）来求解飞机的分配问题。每年可为公司节省近$100百万 Interfaces1989年78月号以及1991年12月号美洲航美洲航空公司空公司 运用BIP模型解决其每月的人员规划问题，每年节省了$20多百万 Session6Be

18、yond Linear Programming线性规划与电子表格线性规划与电子表格 Capital Budgeting资本预算资本预算实际举例实际举例公司计划在今后几年的资本预算，有十个潜在项目，前5年的预期收益已有估计，每年的资金流出也以知，该选择哪些项目呢？这种问题在实际工作这种问题在实际工作中有吗？中有吗？Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Cash Outflow Required($million)CashProjectAvailable 12345678910($million)Year 1140443282625

19、Year 2222223233625Year 3325242348225Year 4445453121125Year 5110655511225NPV($mil)20252230422518352833 Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Capital Budgeting资本预算资本预算实际举例实际举例12345678910111213141516ABCDEFGHIJKLMNOC Ca ap pi it ta al l B Bu ud dg ge et ti in ng gProjectProjectProjectProje

20、ctProjectProjectProjectProjectProjectProject12345678910NPV($million)20252230422518352833Cash Outflow Required($million)Total Outflow AvailableYear 1140443282623=25Year 2222223233620=25Year 3325242348225=25Year 4445453121123=25Year 5110655511220=25ProjectProjectProjectProjectProjectProjectProjectProj

21、ectProjectProjectTotal NPV12345678910($million)Undertake?0111110011205Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Session Summary本讲小结本讲小结 小结小结线性规划可分性假设允许决策变量取包括分数在内的任何实数，当一些决策变量只能取整数时，就必须采用整数规划线性规划比例性假设各活动的贡献与活动水平成比例，当有一个或几个活动边际收益递减时，就须运用可分规划非线性规划允许目标函数项中包含有交叉产品项，即受多个决策变量影响的产品，甚至不需要符合线性规划和可分

22、规划的可加性假设 Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Session Summary本讲小结本讲小结 小结小结目标规划能够使多个目标同时最大限度实现，为各个目标分配数量化的标准，通过平衡各目标的实现程度来求得最优解每个0-1整数规划（BIP）模型都可以同时考虑多个选项，一个01决策变量对应于一个选项，而混合的BIP模型还可以包含一些连续的决策变量 在处理一些无法直接建立BIP模型的问题时，运用辅助01变量是很有用的，辅助变量可以将问题标准化，从而可以用标准的算法求解。辅助变量可用来处理很多问题 Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 Case Study案例研究案例研究 案例案例案例案例5：主教大学的排课计划作业作业:第8、9章奇数习题 政府债券组合（See the Course Package）下一讲：下一讲：数据、统计与决策简介阅读：阅读：Text2,Chapter1 和课件及课程网页相关内容Session6Beyond Linear Programming线性规划与电子表格线性规划与电子表格 The End of Session 6