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

第四章整数规划与分配问题(IntegerProgramming,iP)整数规划的有关概念及特点指派问题及匈牙利解法整数规划的求解方法：分枝定界法、割平面法82$3$422024-10-27

2024-10-27 2 第四章 整数规划与分配问题 （Integer Programming, IP) n 整数规划的有关概念及特点 n 指派问题及匈牙利解法 n 整数规划的求解方法：分枝定界法、割平面法 §2 §3 §4

s13整数规划的有关概念及特点概念整数规划：要求决策变量取整数值的规划问题。（线性整数规划、非线性整数规划等）0-1变量：在整数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量0-1规划：在整数规划问题中，如果所有的变量都为0-1变量，则称之为0-1规划。2024-10-27

2024-10-27 3 0-1变量：在整数规划中，如果变量的取值只限于0和1，这 样的变量我们称之为0-1变量。 0-1规划：在整数规划问题中，如果所有的变量都为0-1变 量，则称之为0-1规划。 §1 整数规划的有关概念及特点 一 、 概念 整数规划： 要求决策变量取整数值的规划问题。 （线性整数规划、非线性整数规划等）

0一1规划举例：选址问题一一相互排斥的计划例1：某公司拟于东、西、南三区建立项目部，有7个位置A;（1，2，……，7）可供选择，规定：（1）在东区，由A’A2，A,三点中至多选择2个；（2）在南区，由A4，A,两点中至少选择1个；（3）在西区，由Ab，A,两点中至少选择1个如选用A点，设备投资估计为b元，每年可获利估计为c元，但设备投资总额不能超过B元。问应选择哪几个点可使年利润最大？试建立数学模型。2024-10-27

2024-10-27 4 例1：某公司拟于东、西、南三区建立项目部，有7个位置Ai （i=1，2，.，7）可供选择，规定： （1）在东区，由A1，A2，A3三点中至多选择2个； （2）在南区，由A4，A5两点中至少选择1个； （3）在西区，由A6，A7两点中至少选择1个。 如选用Ai点，设备投资估计为bi元，每年可获利估计为ci元， 但设备投资总额不能超过B元。问应选择哪几个点可使年利 润最大？ 试建立数学模型。 0-1规划举例：选址问题——相互排斥的计划

0一1规划举例：选址问题一一相互排的计划解：引入0-1变量x;，[1选A,(i = 1,2,., 7)X10不选A,则:max z =xCi=11x,b, ≤Bi=X+X2+X3≤2X4 +x, ≥1X +x, ≥1x, = 0或1(i =1,2,,7)2024-10-27

2024-10-27 5 解：引入0-1变量xi， 0-1规划举例：选址问题——相互排斥的计划 1 ( 1, 2, ,7) 0 i i i A x i A       选 不选 则： 7 1 max i i i z x c    x b B i  i i   7 1 x1  x2  x3  2 x4  x5  1 x  0 1(i  1,2, ,7) i 或 x6  x7  1

整数规划的求解特点求整数解的线性规划问题，不是用四舍五入法或去尾法对性规划的非整数解加以处理就能解决的，用枚举法又往往会计算量太大，所以要用整数规划的特定方法加以解决。例：求解下列整数规划：max z = 3x +2x2[2xi +3x2≤14s.t) x, +0.5x2 ≤ 4.5xi,x2≥0,并取整数2024-10-27

2024-10-27 6 求整数解的线性规划问题，不是用四舍五入法或去尾法对 性规划的非整数解加以处理就能解决的，用枚举法又往往 会计算量太大，所以要用整数规划的特定方法加以解决。 例： 求解下列整数规划： 二、 整数规划的求解特点             , 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

分析：若当作一般线性规划求T解，图解法的结果如下。x +0.5x, = 4.51.非整数规划最优解(3.25，2.5)显然不是整数规划的可行解。2.四舍五入后的结果(3，3)也不是整数规划的可行解。3可行解是阴影区(3.25,2.5)域交叉点，可比较这些点对应的函数值，找出最优。(4，1)2x +3x2 =143xi2024-10-27

2024-10-27 7 分析： 若当作一般线性规划求 解，图解法的结果如下。 1. 非整数规划最优解 显然不是整数规划的可行解。 2. 四舍五入后的结果 也不是整数规划的可行解。 (3.25, 2.5) (3, 3) 3. 可行解是阴影区 域交叉点，可比较这 些点对应的函数值， 找出最优。 1 x 2 x 2x1  3x2 14 x1  0.5x2  4.5 2 2 3 2 1 z x   x  (3.25, 2.5) (4, 1)

S23指派问题及牙利解法指派问题与模型m项任务分配给m个人去完成，每人只能完成其中一项，每项任务只能分给一人完成，应如何分配使得效率最高？C;是第j个人完成第项任务的效率。人员21m任务1CllC12C1m.2C21C22C2m........mCmlCm2Cmm2024-10-278

2024-10-27 8 §2 指派问题及匈牙利解法 一 、 指派问题与模型 m项任务分配给m个人去完成，每人只能完成其中一项， 每项任务只能分给一人完成，应如何分配使得效率最高？ cij是第j个人完成第i项任务的效率。 人员 任务 1 2 . m 1 c11 c12 . c1m 2 c21 c22 . c2m . . . . . m cm1 cm2 cmm

1第人完成第项任务设Xi10否则于是建立模型如下：mmZZcyminz=i-l j=lmZ(i=1,2,.. m)X, = 1,j-=1Z(j=1,2... m)=1,Xii=1,=0或1,(i, j=1,2... m)Xii2024-10-27

2024-10-27 9 设 于是建立模型如下：     否则 第 个人完成第 项任务 0 1 j i xij    m i m j ij ij z c x 1 1 min     0 1, i, j 1,2 . m 1, j 1,2 . m 1, i 1,2 . m 1 1 或 ， ， ，           ij m i ij m j ij x x x

指派问题的匈牙利解法该指派问题可当作运输问题解决，但匈牙利解法更有效。解法思想：效率矩阵的元素ci>0，若有一组位于不同行不同列的零元素，则令这些位置的决策变量取值为1，其余均为0，这显然就是最优解。102024-10-27

2024-10-27 10 二、 指派问题的匈牙利解法 该指派问题可当作运输问题解决，但匈牙利解法更有效。 解法思想：效率矩阵的元素cij≥0，若有一组位于不同行不 同列的零元素，则令这些位置的决策变量取值为1，其余均 为0，这显然就是最优解

例：有一份说明书，要分别译成英、日、德、俄四种语言，交给甲、乙、丙、丁四人去完成，各人的效率不同，如何分配任务，可使总效率最高人甲乙丙丁任务729英文108日文15414德文1314161149俄文1513112024-10-27

2024-10-27 11 例：有一份说明书，要分别译成英、日、德、俄四种语言， 交给甲、乙、丙、丁四人去完成，各人的效率不同，如何 分配任务，可使总效率最高。 人 任务 甲 乙 丙 丁 英文 2 10 9 7 日文 15 4 14 8 德文 13 14 16 11 俄文 4 15 13 9