Session06线性规划扩展.ppt

Data,ModelandDecisions数据、模型与决策,Session6BeyondLinearProgramming线性规划扩展,SessionTopics,SanFranciscoPoliceDepartment旧金山警署IntegerProgramming整数规划SeparableProgramming可分规划NonlinearProgramming非线性规划GoalProgramming目标规划Binaryintegerprogramming01整数规划问题,SanFranciscoPoliceDepartment旧金山警署,获奖经典,旧金山警署巡逻优化系统：1988年FranzEdelman奖一等奖管理科学研究（1989年Interfaces12号）开发了用于警察工作安排与配置的计算机系统每年节省开支$11百万，公交传票收入增加$3百万，响应时间也改善了20问题的数学模型中，主要的决策变量是各轮班应在岗位上的警察数量,什么时候需要整数解？得到小数解时如何处理呢？,IntegerSolutions整数解,你有什么绝招吗？,TheChallengesofRounding舍入解的挑战,舍入解可能不是可行解舍入解与最优解离很远可能有多个舍入解出现,SomeSolutionTechnique一些求解技术,Branch-and-BoundTechnique分枝定界技术Branch-and-CutTechnique割平面技术,HowIntegerProgramsareSolved如何求解整数规划,TypesofIntegerProgramming整数规划问题的类别,Pureintegerprogramming纯整数规划问题Mixedintegerprogramming混合整数规划问题Binaryintegerprogramming01整数规划,SeparableProgramming可分规划,线性规划的比例性假设各种活动对目标函数值的贡献与活动水平成比例，也就是目标函数中各和项是系数与决策变量的乘积违背比例性假设每增加一个单位的活动与前面第一个单位创造的的收益不同，也就是线性规划活动的收益与活动的水平不成比例,WyndorGlassCo.伟恩德玻璃公司,实际举例,TheSeparableProgrammingTechnique可分规划的求解技术,对于违背比例性假设的任一活动，将其利润线划分成多段，使得每一段为直线线段，为利润线上的每一直线段引入新的可分决策变量，以代替原来的单一决策变量,WyndorGlassCo.伟恩德玻璃公司,实际举例,在需要加班的情况下，伟恩德问题的电子表格模型,NonlinearProgramming非线性规划,线性规划的可加性假设：线性规划目标函数中每一项都只包含一个决策变量，表示相应的活动对目标函数值的贡献,目标函数值是所有活动的贡献的总和在非线性规划问题中，由于交叉产品往往涉及到多个决策变量，所以可能会违背可加性假设,PortfolioSelection投资组合,模型的一般表达形式：Minimize风险约束条件预期回报最小可接受水平哈里.马克维茨（HarryMarkowtia）威廉.夏普（WilliamSharpe）,PortfolioSelection投资组合,实际举例,SourceofGoalProgramming目标规划的来源,保持稳定的利润增加市场份额多样化产品线保持价格稳定,管理层的目标通常包括下面一些内容：,提高员工的士气保持对业务的控制力增加公司的声誉,GoalProgramming目标规划,通过目标规划可以同时实现多个目标，最基本的方法是为每一个目标建立一个量化的标准，通过平衡各标准目标的实现程度，求得最优解。分配给各个目标的罚数权重（penaltyweights）表示是偏离各目标的严重程度。根据各目标建立总目标函数，该目标函数表示的目标是要使得每个目标函数的偏差之和最小,DewrightCorp.德怀特公司,实际举例,德怀特公司的目标规划的电子表格模型,Binaryintegerprogramming01整数规划问题,整数变量皆为01变量的问题即为01整数规划问题（Binaryintegerprogramming）,这种问题在实际工作中有哪些？,TypesofBinaryintegerprogramming01整数规划类型,PureBIPproblem纯BIP问题MixedBIPproblem混合BIP问题01变量是用来表示是非决策变量的最佳方式，在考虑针对某一选项的是非决策问题时，只有两种选择，接受或拒绝。可以用1表示接受，0表示拒绝。,ApplicationsofBIP01整数规划应用,固定投资方案的资金预算Interfaces1990年78月号土耳其炼油公司运用BIP将数千百万的投资用于扩建炼油设施和能源储备上选址Interfaces1997年12月号，AT&T公司运用BIP模型帮助其客户选择电话营销中心，1988年AT&T公司为其46个客户快速而准确的作出了选址决策,ApplicationsofBIP01整数规划应用,设计生产与配送网络Interfaces1995年12月号数字设备公司对公司整个全球供应链进行重整，年制造成本节省$500百万，物流成本节省$300百万，所需资金总额减少了$400百万分配运货Interfaces1991年12月号ReynoldsMetalsCo.以BIP为基础建立了自动的配送系统，为其200多家工厂、仓库和供应商解决运货问题，每年节省超过$7百万。,ApplicationsofBIP01整数规划应用,规划相关活动Interfaces1995年12月号，中国国家计划委员会为了最小化折现成本，和世界银行合力开发了一个BIP模型，用于指导决策15年内在能源领域投入至少$2,400亿的规划，在15年内，会为中国节省近$64亿规划资产剥离Interfaces1987年12月号荷马特发展公司面临的一个主要问题是如何出售其购物中心和办公楼。有100多处资产需要在10年内售出。通过运用BIP指导决策，整个资产剥离计划的收入增加了$40百万,ApplicationsofBIP01整数规划应用,航空方面的应用Interfaces1994年12月号Delta航空公司运用一个大型的整数规划模型（包括40,000个函数约束，20,000个01决策变量，40,000个一般整数变量。）来求解飞机的分配问题。每年可为公司节省近$100百万Interfaces1989年78月号以及1991年12月号美洲航空公司运用BIP模型解决其每月的人员规划问题，每年节省了$20多百万,CapitalBudgeting资本预算,实际举例,公司计划在今后几年的资本预算，有十个潜在项目，前5年的预期收益已有估计，每年的资金流出也以知，该选择哪些项目呢？,这种问题在实际工作中有吗？,CapitalBudgeting资本预算,实际举例,SessionSummary本讲小结,小结,线性规划可分性假设允许决策变量取包括分数在内的任何实数，当一些决策变量只能取整数时，就必须采用整数规划线性规划比例性假设各活动的贡献与活动水平成比例，当有一个或几个活动边际收益递减时，就须运用可分规划非线性规划允许目标函数项中包含有交叉产品项，即受多个决策变量影响的产品，甚至不需要符合线性规划和可分规划的可加性假设,SessionSummary本讲小结,小结,目标规划能够使多个目标同时最大限度实现，为各个目标分配数量化的标准，通过平衡各目标的实现程度来求得最优解每个0-1整数规划（BIP）模型都可以同时考虑多个选项，一个01决策变量对应于一个选项，而混合的BIP模型还可以包含一些连续的决策变量在处理一些无法直接建立BIP模型的问题