《运筹学》课程教学课件（PPT讲稿）第四章 整数规划与分配问题（Integer Programming, IP）

第四章整数规划与分配问题(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   

2、约束条件右端项是r个可能值中的一个Za,≤b, b.. b,i-1则通过定义约束条件右端项不是b；0y, =约束条件右端项是b可将上述条件表示为Za,=Zby,i=1i=1Ji+y2 +...+y, =12025/4/5

2025/4/5 7 2、约束条件右端项是r个可能值中的一个 r n j ai j b ,或b2 ,.或b 1  1 =  则通过定义    = 1 0 i y 约束条件右端项不是bi 约束条件右端项是bi 可将上述条件表示为 . 1 , 1 2 1 1 + + + =    = = r n j r i ij i i y y y a b y

3、两组条件中满足其中一组例如表示条件：若x≤4，，则x2≥1，；否则 x>4，时 ×≤3,则通过定义10第组条件起作用，i=1，2yi=11第组条件不起作用又：M是任意大正数，可将上述条件表示为x≤4+yMX ≥1-MX>4- y2MX2 ≤3+2M[i+y2 =12025/4/5

2025/4/5 8 3、两组条件中满足其中一组 例如表示条件：若 ，则 ； 否则 时 则通过定义    = 1 0 i y 第i组条件起作用，i=1，2 第i组条件不起作用 可将上述条件表示为 4, x1  3, x1  4, x2  1, x2  又：M是任意大正数，          + =  +  −  −  + 1 3 4 1 4 1 2 2 2 1 2 2 1 1 1 y y x y M x y M x y M x y M

4、表示含有固定费用的函数例如：x，表示产品i的生产数量，其生产费用函数为：x,>0K,+c,xi?其中K是与产量无关C,x;的生产准备费用x, =00.目标函数：min z=C,(x,)j=1定义x,=0[0Yx,>0:min z=Z(c,x,+K,y,)则原问题可表示为j=l[0 ≤x, ≤Mys.t=0或12025/4/5

2025/4/5 9 定义 4、表示含有固定费用的函数 例如： x j 表示产品 j 的生产数量，其生产费用函数为： 目标函数： 0 0 0, , ( ) =     + = j j j j j j j x K c x x C x 其中 是与产量无关 的生产准备费用 K j = = n j j j z C x 1 min ( )    = 1 0 j y = 0 j x  0 j x 则原问题可表示为 min ( ) 1 = = + n j j j j j z c x K y     =   0 1 0 . j 或 j j y x My st

应用举例例1：书P120.例3解：设X表示学生在周日的值班时间。0学生i个在周不值班设Yi学生个在周值班165min z=cjxj目标函数i=l j-l2约束条件(1)x, =14,j= 1...6每天开放14小时i=1大学生值班不少于8小时(2)i=1...4x, ≥8,j-12025/4/510

2025/4/5 10 二、 应用举例 例1： 书P120,例3 解：设 xij 表示学生i在周j日的值班时间。 目标函数 = = = 6 1 5 1 min i j j ij z c x 约 束 条 件 (1) 14, 1,.6 6 1  = = = x j i i j 每天开放14小时 (2) 8, 1,.4 5 1   = = x i j ij 大学生值班不少于8小时 设    = 1 0 ij y 学生i个在周j不值班 学生i个在周j值班

E研究生值班不少于7小时(3)i=5,6, ≥7,Xii(4)每周不超过3次i=1....6每天不超过3人(5)j =1,..5i=1(6)每天有一研究生j =1...5Ys; + 6, ≥1(7)i= 1...6, j=1...52yu, ≤x, ≤ajyij值班不超过每人可安排的时间a表示学生在周j日的最多可值班时间。2025/4/511

2025/4/5 11 (3) 7, 5,6 5 1   = = x i j ij 研究生值班不少于7小时 (4) 3, 1,.,6 5 1   = = y i j i j 每周不超过3次 (5) 3, 1,.,5 6 1   = = y j i i j 每天不超过3人 (6) y5 j + y6 j 1 j =1,.,5 每天有一研究生 (7) 2yi j  xi j  ai j yi j i =1,.6, j =1,.,5 值班不超过每人可安排的时间 aij 表示学生i在周j日的最多可值班时间