文档介绍：1第2章整数规划教师:胡德敏 Email: ******@. cn 2整数规划问题的提出分支定界解法 0-1 整数规划分配问题目录隐枚举法练****题 3问题的提出?在前面讨论的线性规划问题中,有些最优解可能是分数或小数,但对于某些具体问题,常有要求解答必须是整数的情形(称为整数解)。例如,所求解是机器的台数、完成工作的人数或装货的车数等, 分数或小数的解答就不合要求。为了满足整数解的要求,初看起来,似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的,因为化整后不见得是可行解;或虽是可行解, 但不一定是最优解。因此,对求最优整数解的问题, 有必要另行研究。我们称这样的问题为整数线性规划(integer linear programming) ,简称 ILP ,简称整数规划,整数线性规划是最近几十年来发展起来的规划论中的一个分支。 4 ?整数线性规划中如果所有的变数都限制为(非负)整数,就称为纯整数线性规划(pure integer linear programming) 或称为全整数线性规划(all integer linear programming) ;如果仅一部分变数限制为整数,则称为混合整数规划(mixed integer linear programming) 。纯整数线性规划的一种特殊情形是 0-1 规划,它的变数取值仅限于 0 或1。本章最后讲到的指派问题就是一个 0-1 规划问题。 5 ?现举例说明用前述单纯形法求得的解不能保证是整数最优解。例1 某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制如下表所示。问两种货物各托运多少箱,可使获得利润为最大? 货物体积(m 3/箱) 重量(100kg/ 箱) 利润(100 元/箱) 甲乙 54 25 2010 托运限制 24m 3 1300kg6 ?现在我们解这个问题,设 x 1,x 2 分别为甲、乙两种货物的托运箱数( 当然都是非负整数) 。这是一个(纯)整数线性规划问题,用数学式可表示为: max z =20x 1+10x 2① 5x 1+4x 2≤24 ② 2x 1+5x 2≤13 ③() x 1,x 2≥0 ④ x 1,x 2整数⑤ 7 它和线性规划问题的区别仅在于最后的条件⑤。现在我们暂不考虑这一条件,即解①~④(以后我们称这样的问题为与原问题相应的线性规划问题), 很容易求得最优解为:x 1 = ,x 2 =0 , max z=96 8 但x 1 是托运甲种货物的箱数,现在它不是整数,所以不合条件⑤的要求。?是不是可以把所得的非整数的最优解经过“化整”就可得到合于条件⑤的整数最优解呢? 如将(x 1 = , x 2 =0) 凑整为(x 1 =5 ,x 2 =0) , 这样就破坏了条件②(关于体积的限制) ,因而它不是可行解;如将(x 1 = , x 2 =0) 舍去尾数 ,变为(x 1 =4 ,x 2 =0) , 这当然满足各约束条件,因而是可行解,但不是最优解,因为当x 1 =4 ,x 2 =0, 时 z=80. ?非整数的最优解在 C( , 0)点达到。 9 但当 x 1=4,x 2=1( 这也是可行解)时, z=90 。本例还可以用图解法来说明。见图 5-1 10 ?图中画(+) 号的点表示可行的整数解。凑整的(5,0) 点不在可行域内,而 C 点又不合于条件⑤。为了满足题中要求,表示目标函数的 z的等值线必须向原点平行移动,直到第一次遇到带“+”号B点(x 1=4,x 2=1) 为止。这样, z的等值线就由 z=96 变到 z=90 ,它们的差值?Δz=96-90=6 ?表示利润的降低,这是由于变量的不可分性(装箱)所引起的。