第六章整数规划(应用运筹学)综述.ppt

Chapter 6 Integer Programming 整数规划;求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。 在整数规划中，如果所有的变量都为整数，则称为纯整数规划问题；如果有一部分变量为整数，另一部分变量可以不取整数，则称之为混合整数规划问题。在整数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量。在纯整数规划和混合整数规划问题中，如果所有的变量都为0-1变量，则称之为0-1规划。; 例1 TBA 航空公司飞机采购问题Airlines Problem;可分规划 Separable Programming;图解法 Graphical Method for Integer Programming;图解;§1　整数规划的图解法;得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为14.66。 由图表可看出，整数规划的最优解为x1=4, x2=2,目标函数值为14。 性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目 标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目 标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相 应的线性规划的最小目标函数值。;§2 Branch and Bound Technique for Pure IPs整数规划的分枝定界法;分枝定界法步骤; (3) 该分枝最优解不是整数解，但其目标函数值≤ 当前下界 ,该分枝剪掉 (4) 该分枝最优解不是整数解，而其目标函数值 ≥当前下界 ，则该枝需要继续分枝，在各分枝中选目标函数最大的那枝进行分枝。 第六步：修改上、下界 (1)每求出一次符合整数的解，都要考虑修改下界 ，选整数解的目标函数值最大者为新的下界 (2)修改 ，找出所有未 分枝问题目标函数值最大者，为新的上界 当改变完上、下界 ， 后，若 ＝ ，则所有分枝均已查明，得到 A0的最优解， 若 ＞ ，则说明仍有分枝未查明，返回到第四步;例2 考虑下面整数规划 consider the following Integer Programming P73 max z =x1+2x2 s.t. 2x1+5x2≤15 A0 2x1－2x2≤5 x1 , x2≥0 且为整数 ; The optimal solutionfor the LP relaxation B0 is X，不考虑x1, x2为整数的限制条件，得规划B0对应的最优解与最优值如下，而 X=(0，0)为A0的可行解; 考察X的某一分量，不妨选x2 ,因为1x22,为了使x2整数化,剔除1x22对应的可行域。为此,增加约束条件x2≤1及x2≥2,于是可行域R0可分解成两个小可行域R1和R2.原规划B0分解成子(subproblem)规划B1与规划B2，求解得:; 所有松弛规划的上界为 Z ≤6.5，修改上界为;因规划B2的z 值优于规划B1 的z 值，故先分解规划B2。仿上，R2分解成R3与R4=Ф。规划B2分解成规划B3与规划B4; 考察B1 、B3，因规划B3 的z值优于规划B1 的z值，故先分解规划B3。仿上，R3分解成R5与R6。规划B3 分解成规划B5 与规划B6 ： ;分枝定界求解过程;§3 0—1规划Binary integer programming ; 一、Example 1 Site Selection 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?;解：设：0--1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用） 这样我们可建立如下的数学模型： Max z