资源描述：
《运筹学课件 ppt 复习资料 整数规划(运筹学).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹学王莉莉四川农业大学数学系2012年11月学习目标掌握一般整数规划问题概念及模型结构；掌握分支定界法与割平面法的原理，能够运用分支定界法与割平面法求解整数规划问题；熟练掌握0-1变量的应用，能够建立0-1规划模型，并能够用隐枚举法进行求解；掌握分配问题的概念和数学模型，并能用匈牙利算法熟练求解该类问题.第六章—整数规划引言整数规划是规划论中近几十年才发展起来的一个重要分支，主要是由于经济管理中的大量问题在抽象成模型时，人们发现许多量具有不可分割性，因此当它们被作为变量引入到规划中时，常要求满足取整条件.
2、如生产计划中，生产机器多少台(整数)；人力资源管理中，招聘员工多少人(整数)；运输问题中，从一个港口到另一个港口的集装箱调运数量(整数)等.某公司拟以集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如下表：甲乙托运限制体积（立方米/件）3412重量（吨/件）429价值（万元/件）43问两种货物各装多少箱，可使获得利润最大.背包问题设甲、乙货物各装x1，x2箱，利润为zmaxz=4x1+3x2s.t.3x1+4x2≤124x1+2x2≤9x1，x2≥0，x1，x2为整数甲乙托运限
3、制体积（立方米/件）3412重量（吨/件）429价值（万元/件）43某国外大型连锁超市集团准备全面进入某省会城市.拟从可供选择的10个店址中确定5个.每个备选店址用符号L1,L2,…,L10表示.经过调查，每个备选店址相应的前期预计投入和所覆盖的目标顾客数的综合值分别为C1,C2,…,C10(综合值越大越好).并且在店址选择上要满足以下条件：1、L1和L5必须同时选择；2、L8和L1二者必选其一，但不能同选；3、L3，L7不能同选；L4，L7不能同选；4、L5，L6，L7，L8最多只能选两个.试帮助该集团超
4、市给出最佳地选址方案.选址问题整数规划IntegerProgramming整数规划数学模型的一般形式整数规划问题的类型纯整数规划——pureintegerprogramming：全部决策变量都必须取整数值；混合整数规划——mixedintegerprogramming：决策变量中一部分必须取整数值，另一部分可以不取整数值；0-1整数规划——zero-oneintegerprogramming：决策变量只能取值0或1.整数规划的解法从数学模型上看，整数规划似乎是线性规划的一种特殊形式。直觉认为，对于整数规划的
5、求解可以先不考虑对变量的整数约束，作为一般的线性规划来求解，当解是非整数时，可用四舍五入或凑整方法寻找最优解.是否可行？线性规划模型maxz=x1+4x2s.t.14x1+42x2≤196-x1+2x2≤5x1,x2≥0整数规划模型maxz=x1+4x2s.t.14x1+42x2≤196-x1+2x2≤5x1,x2≥0x1,x2为整数0123456784321A(2.6,3.8),z=17.8D(5,3),z=17例如B(2,3),z=14C(3,4)整数规划与对应线性规划解得关系整数规划之相应线性规划的最
6、优解经四舍五入不能得到其最优解.整数规划的最优解不会优于其对应的线性规划的最优解.1、任何求max的整数规划的最优目标函数值小于或等于相应的线性规划的最优目标函数值；(对应线性规划最优解为其上界)2、任何求min的整数规划的最优目标函数值大于或等于相应的线性规划的最优目标函数。(对应线性规划最优解为其下界)整数规划的求解方法整数规划的求解方法有以下三种：枚举法分支定界法割平面法分支定界法branchandboundmethod在20世纪60年代初LandDoing和Dakin等人提出了分支定界法。由于该方法
7、灵活且便于用计算机求解，所以目前已成为解整数规划的重要方法之一。分支定界法可用来求解纯整数规划和混合整数规划问题。分支定界法的关键是分支和定界。首先，不考虑变量的整数约束，求解相应的线性规划，得到线性规划的最优解。如果线性规划的最优解恰好是整数解，则这个解就是整数规划的最优解。如果线性规划的最优解中至少有一个变量不是整数，选择其中一个将线性规划的可行域切割成两部分，分别求解两个线性规划的最优解。如果这两个线性规划的最优解还不是整数解，分别把每一个可行域再进行分割。这个过程，叫做“分枝”。分枝过程得到的整数解
8、中，目标函数值最大的一个叫做整数规划目标函数值的“界”。分枝过程中非整数的线性规划的最优解，如果目标函数值小于或等于这个“界”，就停止继续分枝。这个过程，叫做“定界”。分枝定界法的思路：0123456754321z=15z=19z=24z=28.9(x1,x2)=(3.8,3.5)例maxz=3x1+5x228.9分枝：选择非整变量x1，将可行域分为x1≤3和x1≥4两部分.0123456754321z=15z=
