《整数规划习题解答.ppt》由会员分享，可在线阅读，更多相关《整数规划习题解答.ppt（12页珍藏版）》请在金锄头文库上搜索。
练 习,用割平面法解整数规划问题 解：不考虑整数约束条件求解伴随规划问题,将其标准化： （1）采用M法,（增加了人工变量x4）,练 习,（2）不增加人工变量，通过对约束方程组进行行变换得到 初始可行基,练 习,练 习,伴随规划问题的最优解不是整数解，构造割平面（由 最终表中任意一个不取整数值得基变量所对应的约束方程 进行构造，不妨选x3） 加入上面的最终单纯性表，得,练 习,练 习,练 习,由对偶单纯性法可得,练 习,用匈牙利法求解指派问题，其效率矩阵如下：,练 习,解：第一步：对效率矩阵进行变换：,练 习,第二步：确定独立零元，进行试指派 只找到4个独立零元，（需要确定是否有5个独立零元）进 入下一步。,练 习,第三步：作最少的直线覆盖所有的零元素 所有零元可以用4条直线覆盖，说明只有最多4个独立零元。 需要对效率矩阵进行进一步的变换（增加独立零元个数）,练 习,第四步：增加独立零元素 解矩阵为,
