第3讲整数规划(IntegerProgramming,IP)20181110–整数规划（IntegerProgramming）主要是指整数线性规划。一个线性规划问题，如果要求部分决策变量为整数，则构成一个整数规划问题。–所有变量都要求为整数的称为纯整数规划（PureIntegerProgramming）或称全整数规划（AllintegerProgramming）；–仅有一部分变量要求为整数的称为混合整数规划（MixedIntegerProgramming）；–有的变量限制其取值只能为0或1，这类特殊的整数规划称为0－1规划(0-1IntegerProgramming)。整数规划的有关概念一、整数规划问题例4.1某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A、材料B，有关数据如下，问这两种设备各生产多少使工厂利润最大？设备材料甲乙资源限量材料A（kg）2314材料B（kg）10.54.5利润（元/第一节整数规划问题及其数学模型解：设生产甲、乙这两种设备的数量分别为x1、x2，由于是设备台数，则其变量都要求为整数，建立模型如下：Maxz=3x1+2x22x1+3x2≤14x1+0.5x2≤4.5x1、x2≥0,且为整数要求该模型的解，不考虑整数约束条件，用单纯形法对相应线性规划求解，其最优解为：•凑整得到的（4，2）不在可行域范围内。•（3，2）点尽管在可行域内，但没有使目标达到极大化。•（4，1）使目标函数达到最大，即z＝14。Max=3x1+2*x22*x1+3*x2<=14x1+0.5*x2<=4.5@gin(x1)；@gin(x2);Max=3x1+2*x22*x1+3*x2<=14x1+0.5*x2<=4.5!@gin(x1)；@gin(x2);X1不是整数二、整数规划数学模型的一般形式•由上述例子可得出整数规划数学模型的一般形式：Maxz=CXAX=bX≥0,且为整数或部分为整数•若称该整数规划问题为原问题，则线性规划问题：Maxz=CXAX=bX≥0•为原问题对应的松驰问题（LPRelaxation)。•显然，原问题与松弛问题有如下关系：1)松弛问题可行域包含原问题可行域；2)若两者都有最优解，则松弛问题最优解大于原问题最优解；3)若松弛问题最优解为整数解，则该最优解就是原问题最优解。–整数规划常用的解法有分枝定界法和割平面法，它们适用于解纯整数规划问题和混合整数规划问题。一、分枝定界法基本思想二、割平面法基本思想三、整数规划的计算机解法计算机求解举例第二节整数规划的解法第三节0－1整数规划一、0－1整数规划模型–0－1整数规划在实际中应用较多。因为实际问题中经常碰到大量的决策问题，要求回答“是－否”或“有－无”问题，这类问题可以借助整数规划中的0－1整数变量，使许多复杂的、困难的问题相对变得简单。–0－1变量一般可表示...
