运筹学整数规划教材.ppt

第五章 整数规划Integer Programming (IP);一、整数规划的一般形式;2、整数规划一般形式;（1）求解方法方面 ;例2 做图分析例1的最优解(直观);4、IP问题的求解思路;二、整数规划的分类;3、0-1规划问题;一、几何解释;解：图解法;用单纯形法求IP问题的最优解。;三、分枝定界规则;B;B; 问题B x1=4.81 x2=1.82 Z0=356;四、运算步骤;（1）解B，若： B无可行解，则A也无可行解，停止； B有最优解且符合整数条件，则得A最优解，停止； B有最优解但不符合整数条件，记其目标值为 。;例3 求解下列IP问题 ;问题II的解即问题A的最优解;方法1：图解法;方法2：单纯型表;将约束条件直接写入单纯形表：;Cj;Cj;补充作业6-1 ;适用范围：全整数规划问题;找1条切割线割去上部非整数区域，使该整数坐标成为顶点。;二、符号说明;三、Gomory 约束的推导;把(2)(3)代入(1)并移项得：;由于xj为非负整数，故上式左边为整数，而右边与之相等，故也必为整数。那么右边是个怎样的整数呢？由于右边第1项<1,括号内≥0，故右边是<1的整数，那这个整数就只可能以0为上限（即可能的整数是0，-1，-2，...）。上述结论是在xj 为整数条件下得出的。;三、计算步骤 ;解：;Cj;Cj;四、几何解释：图解法求解;x1;一、问题的提出;则0-1规划模型为：;（2）实例2----相互排斥约束条件选择;（2）实例2----相互排斥约束条件选择;（3）实例3----不同生产方式下的固定成本表示;2、0-1整数规划的一般形式; 为了加快检查的速度，先用观察法找1个可行解（如所有变量都取0），以该解的目标值为参照值（门槛）。 检查其它解，先看其目标值是否优于当前参照值，若不是，筛去。 若是，再检查其可行性，若不满足可行性，筛去，若满足，将其目标值作为新的参照值。 这样，将当前参照值作为对其它解检查的过滤条件以加快检查速度的做法称为隐枚举法。 为了进一步提高速度，还有一个技巧：将目标函数按系数大小顺序排列，所有可能解中变量也按此顺序排列，这样就容易看出那些目标值不优于当前参照值的可能解，从而不需任何检查就被淘汰。 ;二、 0-1整数规划的隐枚举法;解：;通过试探可行解(x2,x1,x3)=(0,1,0) 引入下列过滤条件：;改进过滤条件：;改进过滤条件：; 隐枚举法应用的前提是要列出所有可能解，这在变量很少时，可人工观察出来，而当变量稍多时，所有可能解将呈指数剧增（如6个变量，所有可能解为26=64个），这时靠人工观察是困难的，下面提出一种快捷有效的方法： ; 由于n=5,其所有可能解个数为25=32个, 用0-31表示解序号,再用5位字符依次将序号值转换成二进制值, 见下表。例如十进制9的二进制值01001, 就表示第10个可能解 X=（X1 X2 X3 X4 X5）=(0 1 0 0 1)。;十进制 ;编号 ;三、0-1规划与全、纯整数规划的转换;例10：;一、问题的提出;解：设;二、指派问题最优解的性质;证明：;上述任一种样式具有这样的特点：不同行不同列只有一个元素为0，这样的0称为独立0元素。若将这些0对应的xij取1，其余xij取0，则目标值Z=0，易知这是最优目标值，从而这样的解是最优解。; 但实际系数矩阵一般不具上述类似样式，指派问题最优解的性质告诉我们，可以将系数矩阵化为上述类似样式而不影响原最优解。根据这一性质，求指派问题就可归结为设法变换系数矩阵，使其含有n个独立0元素。 ;三、求解指派问题的步骤;1、逐行检查，若该行只有一个未标记的零，对其加?标记，将?标??元素同行同列上其它的零打上/标记。若该行有二个以上未标记的零，暂不标记，转下一行检查，直到所有行检查完；;c. 所有零都已标记，但标有?的零的个数m小于矩阵阶数n，进入step 3。 ;Step 3：检查step 2是否有误;寻找过程： ? 对没有标记 ?的行打?； ? 对打? 行上所有其它零元素对应的列打 ?； ? 再对打 ? 列上有 ?标记的零元素对应的行打 ?； ? 重复以上步骤 ，直至无法继续； ? 对没有打 ? 的行划横线，对所有打 ? 的列划竖线 。 ;划线后会出现两种情况： (1) 标记?的零的个数m小于直线数k，说明矩阵中已存在 k个独立的零元素，但打破僵局时选择不合理，没能找到。回到 step 2的b中重新标记； (2) m=k<n，转入step 4；;Step 4：进一步变换系数矩阵，增加0元素;答：最优分配方案为 x13= x21= x34 = x42 =1，其余为0，