整数规划习题解答-PPT

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,练 习,用割平面法解整数规划问题,解：不考虑整数约束条件求解伴随规划问题,将其标准化：,（,1,）采用,M,法,（增加了人工变量,x,4,）,练 习,（,2,）不增加人工变量，通过对约束方程组进行行变换得到,初始可行基,练 习,练 习,伴随规划问题的最优解不是整数解，构造割平面（由,最终表中任意一个不取整数值得基变量所对应的约束方程,进行构造，不妨选,x,3,）,加入上面的最终单纯性表，得,练 习,练 习,练 习,由对偶单纯性法可得,大家应该也有点累了，稍作休息,大家有疑问的，可以询问和交流,8,练 习,任务,1 2 3 4 5,人员,甲,4 8 7 15 12,乙,7 9 17 14 10,丙,6 9 12 8 7,丁,6 7 14 6 10,戊,6 9 12 10 6,用匈牙利法求解指派问题，其效率矩阵如下：,练 习,解：第一步：对效率矩阵进行变换：,练 习,第二步：确定独立零元，进行试指派,只找到,4,个独立零元，（需要确定是否有,5,个独立零元）进,入下一步。,练 习,第三步：作最少的直线覆盖所有的零元素,所有零元可以用,4,条直线覆盖，说明只有最多,4,个独立零元。,需要对效率矩阵进行进一步的变换（增加独立零元个数）,