Session6线性规划扩展

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