第四章整数规划与分配问题(Integer Programming,IP)整数规划的有关概念及特点整数规划的求解方法：分枝定界法、割平面法指派问题及匈牙利解法整数规划的应用2025/4/5
2025/4/5 2 第四章 整数规划与分配问题 （Integer Programming, IP) ◼ 整数规划的有关概念及特点 ◼ 整数规划的求解方法：分枝定界法、割平面法 ◼ 指派问题及匈牙利解法 ◼ 整数规划的应用
$1整数规划的有关概念及特点概念整数规划：要求决策变量取整数值的规划问题。（线性整数规划、非线性整数规划等）纯整数规划：在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题混合整数规划：如果有一部分变量为非负整数，则称之为混合整数规划问题。0-1变量：在整数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量0-1规划：在整数规划问题中，如果所有的变量都为0-1变量，则称之为0-1规划2025/4/5
2025/4/5 3 纯整数规划：在整数规划中，如果所有的变量都为非负整 数，则称为纯整数规划问题； 混合整数规划：如果有一部分变量为非负整数，则称之为 混合整数规划问题。 0-1变量：在整数规划中，如果变量的取值只限于0和1， 这 样的变量我们称之为0-1变量。 0-1规划：在整数规划问题中，如果所有的变量都为0-1变 量，则称之为0-1规划。 §1 整数规划的有关概念及特点 一、 概念 整数规划： 要求决策变量取整数值的规划问题。 （线性整数规划、非线性整数规划等）
整数规划的求解特点二求整数解的线性规划问题，不是用四舍五入法或去尾法对性规划的非整数解加以处理就能解决的，用枚举法又往往会计算量太大，所以要用整数规划的特定方法加以解决例：求解下列整数规划：max z = 3xi +2x22x+3x2≤14s.tx +0.5x2 ≤ 4.5[,≥0,并取整数2025/4/5
2025/4/5 4 求整数解的线性规划问题，不是用四舍五入法或去尾法对 性规划的非整数解加以处理就能解决的，用枚举法又往往 会计算量太大，所以要用整数规划的特定方法加以解决。 例： 求解下列整数规划： 二、 整数规划的求解特点 + + = + , 0,并取整数 0.5 4.5 2 3 14 . max 3 2 1 2 1 2 1 2 1 2 x x x x x x st z x x
分析：若当作一般线性规划求解，X2图解法的结果如下。x +0.5x = 4.51、非整数规划最优解(3.25，2.5)显然不是整数规划的可行解。(3, 3)2、四舍五入后的结果也不是整数规划的可行解。3、可行解是阴影区(3.55, 2.5)域交叉点，可比较这些点对应的函数值，找出最优。(4，1)2x +3x2 =14=3x +2x2XI2025/4/5
2025/4/5 5 1 x 2 x 2x1 +3x2 =14 x1 +0.5x2 = 4.5 3 1 2 2 z = x + x (3.25, 2.5) 分析： 若当作一般线性规划求解， 图解法的结果如下。 1、非整数规划最优解 显然不是整数规划的可行解。 2、四舍五入后的结果 也不是整数规划的可行解。 (3.25, 2.5) (3, 3) 3、可行解是阴影区 域交叉点，可比较这 些点对应的函数值， 找出最优。 (4, 1)
S 2应用举例逻辑变量在数学模型中的应用1、m个约束条件中只有k个起作用设有m个约束条件i=1,2....m≤b,aJ-10第i个约束起作用定义0-1整型变量：y第i个约束不起作用M是任意大正数则原约束中只有k个真正起作用的情况可表示为：Zai, ≤b,+My,i= 1,2,,mi=1yi+y2 +...+ym=m-k2025/4/5
2025/4/5 6 §2 应用举例 一、 逻辑变量在数学模型中的应用 1、m个约束条件中只有k个起作用 设有m个约束条件 a b i m n j ij i , 1,2,., 1 = = 定义0-1整型变量： M是任意大正数。 = 1 0 i y 第i个约束起作用 第i个约束不起作用 则原约束中只有k个真正起作用的情况可表示为： y y y m k a b My i m m n j i j i i + + + = − + = = . , 1,2,., 1 2 1