第1节整数线性规划问题的提出 令在前面讨论的线性规划问题中,有些最优解可能是分 数或小数,但对于某些问题,常要求解必须是整数(称 为整数解)。例如,所求解是机器的台数、完成工作的 人数或装货的车数等。 令为满足整数解的要求,初看起来,似乎只要把已得到 的带有分数或小数的解经过“舍入化整”就可以了。 但这常常是不行的,因为化整后不见得是可行解;或 虽是可行解,但不一定是最优解。 令因此,对求最优整数解的问题,有必要另行研究。我 们称这样的问题为整数线性规划( integer linear programmIng),简称‖LP。 清华大学出版社清华大学出版社 3 第1节 整数线性规划问题的提出 ❖ 在前面讨论的线性规划问题中，有些最优解可能是分 数或小数，但对于某些问题，常要求解必须是整数(称 为整数解)。例如，所求解是机器的台数、完成工作的 人数或装货的车数等。 ❖ 为满足整数解的要求，初看起来，似乎只要把已得到 的带有分数或小数的解经过“舍入化整”就可以了。 但这常常是不行的，因为化整后不见得是可行解；或 虽是可行解，但不一定是最优解。 ❖ 因此，对求最优整数解的问题，有必要另行研究。我 们称这样的问题为整数线性规划(integer linear programming)，简称ILP