线性规划扩展整数规划ppt课件.ppt

《线性规划扩展整数规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Data,ModelandDecisions数据、模型与决策Session3BeyondLinearProgramming线性规划扩展——整数规划SessionTopicsSanFranciscoPoliceDepartment旧金山警署IntegerProgramming整数规划Binaryintegerprogramming0－1整数规划问题NonlinearProgramming非线性规划GoalProgramming目标规划SanFranciscoPoliceDepartment旧金山警署(p343)获奖经典旧金山警署巡逻优化系统：1988年FranzE

2、delman奖一等奖管理科学研究（1989年Interfaces1－2号）开发了用于警察工作安排与配置的计算机系统每年节省开支$11百万，公交传票收入增加$3百万，响应时间也改善了20％问题的数学模型中，主要的决策变量是各轮班应在岗位上的警察数量AssumptionsofLinearProgramming线性规划的假设Linearity线性Divisibility可分性Certainty确定性Nonnegativity非负性DivisibilityAssumptionsofLinearProgramming线性规划的可分性假设线性规划的决策变量可以是在满足一定

3、的函数约束和非负约束下，包括分数在内的所有实数。TheChallengesofRounding舍入解的挑战——TBA航空公司案例舍入解可能不是可行解舍入解与最优解离很远可能有多个舍入解出现什么时候需要整数解？得到小数解时如何处理呢？IntegerSolutions整数解你有什么绝招吗？SomeSolutionTechnique一些求解技术Branch-and-BoundTechnique分枝定界技术Branch-and-CutTechnique割平面技术首先放弃变量的整数要求，求线性规划最优解如果最优解恰是一整数解，则最优解就是整数规划的最优解如果最优解不是整数

4、解，则要求构造一个新的约束，对线性规划问题的可行域进行切割，切除已得到的规划的最优解，但保留原可行域中所有的整数解，求解新的线性规划问题，如果最优解仍不是整数解，再增加附加的约束将其切除，但仍保持最初可行域中所有的整数解，如此一直进行，直至得到一个整数的最优解为止。Branch-and-CutTechnique割平面技术Branch-and-BoundTechnique分枝定界技术TBA航空公司问题整数规划模型目标函数MAX利润=S+5L约束条件5S+50L<=100S<=2且S,L>=0S,L都为整数图解法、电子表格建模求解TypesofIntegerProg

5、ramming整数规划问题的类别——案例分析Pureintegerprogramming纯整数规划问题Mixedintegerprogramming混合整数规划问题Binaryintegerprogramming(BIP)0－1整数规划TypesofBinaryintegerprogramming0－1整数规划类型PureBIPproblem纯BIP问题MixedBIPproblem混合BIP问题0－1变量是用来表示是非决策变量的最佳方式，在考虑针对某一选项的是非决策问题时，只有两种选择，接受或拒绝。可以用1表示接受，0表示拒绝。Binaryintegerpro

6、gramming0－1整数规划问题整数变量皆为0－1变量的问题即为0－1整数规划问题（Binaryintegerprogramming）这种问题在实际工作中有哪些？案例分析——加利福尼亚制造公司（p349）MAXNPV=8X1+5X2+6X3+4X4S.T6X1+3X2+5X3+2X4<=10X3+X4<=1——互斥方案（mutuallyexclusiveailternatives）x3<=x1——相依决策（contingentdecision）x4<=x2——相依决策（contingentdecision）x1,x2,x3,x4取0或1Excel敏感性分析报告

7、对于整数规划问题不适用，但第五章其他方法可以！ApplicationsofBIP0－1整数规划应用（p356-360）固定投资方案的资金预算Interfaces1990年7－8月号土耳其炼油公司运用BIP将数千百万的投资用于扩建炼油设施和能源储备上选址Interfaces1997年1－2月号，AT&T公司运用BIP模型帮助其客户选择电话营销中心，1988年AT&T公司为其46个客户快速而准确的作出了选址决策ApplicationsofBIP0－1整数规划应用设计生产与配送网络Interfaces1995年1－2月号数字设备公司对公司整个全球供应链进行重整，年制造

8、成本节省$500百万，物