§6.1整数规划
整数规划（IP，integer programming）：决策变量的全部或部分取整数值的线性规划.
显然，整数规划去掉对决策变量的整数性要求即为一般线性规划问题.
分类：
1.纯（全）整数规划（IP，AIP，accurate（all，pure） integer programming）：全部决策变量均取整数值的整数规划.
2.混合整数规划（MIP，mixed integer programming）：决策变量的一部分取整数值的整数规划.
显然，当时，即为标准形线性规划问题；当时，即为纯整数规划.
3.0-1规划（Bool规划，BIP，Boolean integer programming）：.
例1（背包问题，knapsack problem）今将种物品装入容积为的背包中.第种物品的体积为，价值为，，问：应如何选择物品装入背包中，才能使得装入物品的总体积不超过背包的容积，且总价值最大？
解：令，则可建立0-1规划
.▌
注：（1）小偷！（2）求解：Greedy算法.
例2（下料问题）今利用一批钢材下零件，有关数据如下表所示：
问：应如何安排下料，才能使得既满足零件的需求量，又费用最省？
解：设采用下料方式下料的钢材的数量为，则可建立如下数学模型
.▌
例3（分派问题，assignment problem）今分派个工人去从事项工作.已知工人从事工作的胜任指数（即工作效率）为.试求一个分派方案，使得每个工人都从事一项工作，每项工作都有一个工人承担，且总胜任指数最大.
解：令
，
则可建立0-1规划
.▌
注：分派问题实际上是一种特殊形式的运输问题（见§1.1例3）.
例4（设施选址问题，facility location）
问：应如何选址设厂并组织运输，才能既满足新旧电厂的用煤量，又使得年运行费用（包括固定费用和运费）最少？
解：令，
每年煤矿运往电厂的煤的数量，，
则可建立整数规划
.▌
注：混合整数规划.
整数规划（IP，integer programming）：决策变量的全部或部分取整数值的线性规划.
显然，整数规划去掉对决策变量的整数性要求即为一般线性规划问题.
分类：
1.纯（全）整数规划（IP，AIP，accurate（all，pure） integer programming）：全部决策变量均取整数值的整数规划.
2.混合整数规划（MIP，mixed integer programming）：决策变量的一部分取整数值的整数规划.
显然，当时，即为标准形线性规划问题；当时，即为纯整数规划.
3.0-1规划（Bool规划，BIP，Boolean integer programming）：.
例1（背包问题，knapsack problem）今将种物品装入容积为的背包中.第种物品的体积为，价值为，，问：应如何选择物品装入背包中，才能使得装入物品的总体积不超过背包的容积，且总价值最大？
解：令，则可建立0-1规划
.▌
注：（1）小偷！（2）求解：Greedy算法.
例2（下料问题）今利用一批钢材下零件，有关数据如下表所示：
问：应如何安排下料，才能使得既满足零件的需求量，又费用最省？
解：设采用下料方式下料的钢材的数量为，则可建立如下数学模型
.▌
例3（分派问题，assignment problem）今分派个工人去从事项工作.已知工人从事工作的胜任指数（即工作效率）为.试求一个分派方案，使得每个工人都从事一项工作，每项工作都有一个工人承担，且总胜任指数最大.
解：令
，
则可建立0-1规划
.▌
注：分派问题实际上是一种特殊形式的运输问题（见§1.1例3）.
例4（设施选址问题，facility location）
问：应如何选址设厂并组织运输，才能既满足新旧电厂的用煤量，又使得年运行费用（包括固定费用和运费）最少？
解：令，
每年煤矿运往电厂的煤的数量，，
则可建立整数规划
.▌
注：混合整数规划.
