管理运筹学 课件 05整数规划

整数规划的特点及应用分配问题及匈牙利解法分枝定界法割平面法解0-1规划的隐枚举法第四章整数规划与分配问题例:某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及

托运所受限制如下表：货物体积米3/箱重量百斤/箱利润百元/箱

甲乙54252010托运限制2413问两种货物各托运多少箱，可使获得的利润为最大？§4.1整数规划的特点及应用

一、整数规划的特点线性规划问题解须为整数的情况所求解是机器的台数、完成工作的人数、装货的车数、集装箱数量等；有些数学模型需要通过逻辑变量才能建立。如要不要在某地建工厂，可选用一个逻辑变量x，令：x=0表示不在该地建厂x=1表示在该地建厂。整数规划§4.1整数规划的特点及应用

例1：求整数规划问题的最优解解：用图解法得最优解为（3.25,2.5）如果不考虑整数约束，称为整数规划问题的松弛问题。例1：求整数规划问题的最优解解：用图解法得最优解为（3.25,2.5）最优解为（4,1）

z*=14。凑整法求解：比较四个点（4,3）,（4,2）,（3,3）,（3,2）。(4,1)如果不考虑整数约束，称为整数规划问题的松弛问题。前三个都不是可行解，第四个虽然是可行解，但z=13不是最优解。2、0-1变量3、0-1规划二、相关概念1、整数规划：要求决策变量取整数值的规划问题。纯整数规划混合整数规划§4.1整数规划的特点及应用

1、m个约束条件中只有k个起作用三、逻辑变量在数学模型中的应用设有m个约束条件:定义0-1变量：第i个约束起作用第i个约束不起作用则原约束中只有k个真正起作用表示为：练习1：利用0-1变量把下列问题表示成一般

线性约束问题以下四个约束条件中至少满足两个：练习2：利用0-1变量把下列问题表示成一般

线性约束问题2、约束条件右端项是r个可能值中的一个则通过定义约束条件右端项不是bi约束条件右端项是bi可将上述条件表示为：变量x只能取值0、3、5、7中的一个。

练习3：利用0-1变量把下列问题表示成一般

线性约束问题则通过定义:第i组条件起作用，i=1，2第i组条件不起作用例如表示条件：若，则；否则时令M是任意大的正数，可将上述条件表示为：3、两组条件中满足其中一组若练习4：利用0-1变量把下列问题表示成一般

线性约束问题练习5-某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用最小。若10个井位的代号为s1，s2,…s10,相应的钻探费用为c1，c2,…,c10,并且井位选择上要满足下列限制条件：用逻辑变量建模的应用：（1）或选择s1和s7，或选择钻探s8；（2）选择了s3或s4就不能选择s5，或反过来也一样；（3）在s5,s6,s7,s8,中最多只能选两个；试建立这个问题的整数规划模型。解：建立数学模型：4、表示含有固定费用的函数例如：表示产品j的生产数量，

其生产费用函数为：目标：所有产品的总生产费用最小。其中是与产量无关的生产准备费用定义原问题可表示为设

备生产准备费（元）生产成本（元/件）最大加工数（件）ABC10030020010256008001200练习6-需制造2000件的某种产品，这种产品可利用A，B，C设备的任意一种加工，已知每种设备的生产准备费用，生产该产品时的单件成本，以及每种设备的最大加工量如下表所示，试对此问题建立整数规划模型。例2：有一份说明书，要分别译成英、日、德、俄四种语言，交给甲、乙、丙、丁四人去完成，各人的效率不同，

如何分配任务，可使总效率最高。人任务甲乙丙丁英文21097日文154148德文13141611俄文415139§4.2

分配问题与匈牙利法一、问题4.2.1问题提出与数学模型§4.2

分配问题与匈牙利法一、问题m项任务分配给m个人去完成，每人只能完成其中一项，每项任务只能分给一人完成，应如何分配使得效率最高？人任务12…m1a11a12…a1m2a21a22…a2m……………mam1am2ammaij是第j个人完成第i项任务的效率。4.2.1问题提出与数学模型设于是建立模型如下：二、模型建立4.2.2匈牙利法一、解法思想效率矩阵的元素，若有一组位于不同行不同列的0元素，则令这些位置的决策变量取值为1，其余均为0，这显然就是最优解。例2：有一份说明书，要分别译成英、日、德、俄四种语言，交给甲、乙、丙、丁四人去完成，各人的效率不同，如何分配任务，可使总效率最高。人任务甲乙丙丁英文21097日文154148德文13141611俄文415139定理1：从分配问题效率矩阵A的每一行中元素aij分别减去（或加上）一个常数ui，每一列元素分别减去（或加上）一个元素vj，得新效率矩阵B，B中的元素，则B的最优解等价于A的最优解。二、克尼格定理定理2：若效率矩阵的元素可分为“0”和“非0”两部分，则覆盖“0”元素的最少直线数等于位于不同行、不同列的“0”元素的最大个数。二、克尼格定理三、匈牙利法步骤1、在效率矩阵每行减去该行最小元素；三、匈牙利法步骤2、在效率矩阵每列减去该列最小元素；三、匈牙利法步骤3、寻找独立“0”元素(不同行不同列）（1）从第一行开始，若该行只有一个零元素，就对这个零元素打上（），对打括号的零元素所在的列画一条线，若该行没有零元素或者有两个以上零元素（已划去的不算在内），则转下一行，依次进行到最后一行。三、匈牙利法步骤3、寻找独立“0”元素(不同行不同列）（2）从第一列开始，若该列只有一个零元素，就对这个零元素打上（）（同样不考虑已划去的零元素），再对打括号的零元素所在行画一条直线。若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一列为止。ⅰ）效率矩阵的每一行都有一个打括号的0元素。(3)重复步骤(1)、(2)可能出现三种情况：只要对应这些元素令xij=1就找到了最优解。ⅱ）打括号的0元素个数小于m，但未被划去的0元素之间存在闭回路，(3)重复步骤(1)、(2)可能出现三种情况：ⅲ）矩阵中所有0元素或被打括号，或被划去，但打括号的0元素个数<m，则进入下一步；(3)重复步骤(1)、(2)可能出现三种情况：4、设法使每一行都有一个打括号的“0”元素。

按定理1继续对矩阵进行变换：(1)从矩阵未被直线覆盖的元素中找出最小者k，(2)对矩阵中的每行，当该行有直线覆盖时，令

ui=0，

无直线覆盖的，令ui=k

；(3)对矩阵中有直线覆盖的列，令vj=-k，对无直线覆

盖的列，令vj=0；(4)从原矩阵的每个元素aij中分别减去ui和vj。4、设法使每一行都有一个打括号的“0”元素。

按定理1继续对矩阵进行变换：(1)从矩阵未被直线覆盖的元素中找出最小者k，(2)对矩阵中的每行，当该行有直线覆盖时，令

ui=0，

无直线覆盖的，令ui=k

；(3)对矩阵中有直线覆盖的列，令vj=-k，对无直线覆

盖的列，令vj=0；(4)从原矩阵的每个元素aij中分别减去ui和vj。5、回到第3步，反复进行，直到矩阵的每

一行都有一个打括号的零元素为止，即

找到最优分配方案。最优解：由初始效率矩阵：最优解值：匈牙利算法总结：使系数矩阵每行每列都出现0元素。未被直线覆盖的元素：-k同时被横线和竖线覆盖的元素：+k仅被横线或仅被竖线覆盖的元素：不变在未划去的各数中找出最小值，设为k：反复进行，直到矩阵的每一行都有一个打括号的零元素为止，即找到最优分配方案。逐行检查并圈0划线逐列检查并圈0划线若所画直线等于n，则问题已解决，否则转下一步画最少的0元素覆盖线。例3：5个人完成5项任务，由于能力不同，完成任务所产生的价值不同，具体如下表。问应如何指派才使总效率最高，即总价值最大？人任务12345A134221A245313A343111A431222A5131211、极大化的指派问题4.2.3指派问题的特殊情况设maxaij=a*则令bij=a*-aij每个人只能完成一项工作每项工作只能由一个人完成1、极大化的指派问题4.2.3指派问题的特殊情况解:(1)转化bij=a*-aij使每行出现0使每列出现0(2)处理(3)试求最优解(4)调整并试求最优解(5)最优解为即：x12=x23=x31=x45=x54=1其余为0最优值为：15任务比被指派者多被指派者比任务多每个被指派者可以同时被指派给多于一个的任务有一些被指派者并不能进行某一些的任务

2、任务与被指派者不对应4.2.3指派问题的特殊情况（1）人数与任务数不等的处理

①人数>任务数：增加一个虚拟的任务，每个人完成虚拟任务的效率设定为0。②任务数>人数增加一个虚拟的人，,虚拟人完成所有任务的效率设定为0。00000（1）人数与任务数不等的处理（2）一个人可做多项工作A1可同时做三项工作3.某项工作一定不能由某人做A1不能做B4;A3不能做B3练习9：甲、乙、丙、丁4个人去完成5项任

务：A，B，C，D，E，每人完成各项

任务时间如表所示，由于任务数多

于人数，考虑：人任务ABCDE甲2529314237乙3938262033丙3427284032丁2442362345（1）任务E必须完成，其他4项任务可选3项完成，

但甲不能做A工作解：（1）由于任务数大于人数，所以需要有一个虚拟的人，设为戊，因为工作E必须完成，故设戊完成E的时间为M（任意大），即戊不能做工作E，其他假想时间为0，甲做A工作的时间也为M。建立新的效率矩阵：人任务ABCDE甲M29314237乙3938262033丙3427284032丁2442362345戊0000M用匈牙利法求解：使行出现0使列出现0用匈牙利法求解：使行出现0使列出现0得最优解为即为：x12=x24=x35=x41=x53=1其余为0也就是甲做B，乙做D，丙做E，丁做A工作最优值为：29＋20＋32＋24＝105人任务ABCDE甲2529314237乙3938282033丙3427284032丁2442362345（2）其中有人完成两项，其他人每人完成一项试分别确定总花费时间的最少指派方案练习9：甲、乙、丙、丁4个人去完成5项任

务：A，B，C，D，E，每人完成各项

任务时间如表所示，由于任务数多

于人数，考虑：解：设虚拟人戊，它集5人优势为一身，得新的效率矩阵：人任务ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊2427262032即为：x12=x23=x35=x41=x54=1其余为0也就是甲做B，乙做C和D，丙做E，丁做A工作最优值为：29＋26＋32＋24＋20＝131得最优解为人任务ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊2427262032（3）甲或丙中有一人完成两项任务，乙丁各完成一项。练习9：甲、乙、丙、丁4个人去完成5项任

务：A，B，C，D，E，每人完成各项

任务时间如表所示，由于任务数多

于人数，考虑：（4）每人完成一项任务，其中A和B必须完成，CDE中可以有一项不完成。练习9：甲、乙、丙、丁4个人去完成5项任

务：A，B，C，D，E，每人完成各项

任务时间如表所示，由于任务数多

于人数，考虑：练习10：A、B、C、D、E5个人，挑选其中4人去完成4项工作，已知每人完成各项工作的时间如表所示，规定每项工作只能由一个人去完成，每人最多承担一项工作，又假定A必须分配到一项工作，D因某种原因决定不承担IV项工作，问应如何分配，才能使完成4项工作总的花费时间最少？任务人ABCDEI1023159II5101524III15514715IV20151368任务人ABCDEI1023159II5101524III15514715IV20151368任务人ABCDEI1023159II5101524III15514715IV201513M8VM0000练习10：A、B、C、D、E5个人，挑选其中4人去完成4项工作，已知每人完成各项工作的时间如表所示，规定每项工作只能由一个人去完成，每人最多承担一项工作，又假定A必须分配到一项工作，D因某种原因决定不承担IV项工作，问应如何分配，才能使完成4项工作总的花费时间最少？使行出现0使列出现0用匈牙利法求解：使行出现0使列出现0用匈牙利法求解：使行出现0使列出现0用匈牙利法求解：使行出现0使列出现0用匈牙利法求解：最优解为即：x13=x21=x32=x45=x54=1其余为0也就是A做II，B做III，C做I，E做IV工作，D不分配最优值为：21（一）基本思路

整数规划问题：§4.3

分枝定界法

松弛问题：例1：用分枝定界法求解整数规划问题（图解法）记为（IP）（二）例题§4.3

分枝定界法

解：去掉整数约束，变成一般线性规划问题（LP）§4.3

分枝定界法

x1x2⑴⑵33(18/11,40/11)⑶x1＝18/11,x2=40/11Z(0)=218/11≈(19.8)也是（IP）最大值的上限。LPx1=18/11,x2=40/11Z(0)

＝19.8§4.3

分枝定界法

对于x1＝18/11≈1.64，取值x1≤1，x1≥2对于x2=40/11≈3.64，

取值x2≤3，x2≥4先将（LP）划分为（LP1）和（LP2）,取x1≤1,x1≥2

现在只要求出（LP1）和（LP2）的最优解即可。先将（LP）划分为（LP1）和（LP2）,取x1≤1,x1≥2，有下式：§4.3

分枝定界法

LP1x1=？,x2=？Z(1)

＝？LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=？,x2=？Z(2)

＝？x1≤1x1≥2§4.3

分枝定界法

x1x2⑴⑵33⑶

先求（LP1）11A§4.3

分枝定界法

此时B

在点取得最优解。x1＝1,x2=3,Z(1)＝16BLP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=？,x2=？Z(2)

＝？x1≤1x1≥2§4.3

分枝定界法

求（LP2）

,如图所示。§4.3

分枝定界法

x1x2⑴⑵33⑶11BAC在C

点取得最优解。即x1＝2,x2=10/3,Z(2)

＝56/3≈18.7LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=2,x2=10/3Z(2)

＝18.7x1≤1x1≥2找到整数解，

此枝停止计算§4.3

分枝定界法

∵Z2>Z1＝16∴原问题可能有比16更大的最优解，但x2不是整数，加入条件x2≤3，x2≥4

。对于LP2,加入条件：x2≤3,x2≥4只要求出（LP21）和（LP22）的最优解即可。§4.3

分枝定界法

x1≤1x1≥2x2≥4x2≤3LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=2,x2=10/3Z(2)

＝18.7LP21x1=？,x2=？Z(21)

＝？LP22x1=？,x2=？Z(22)

＝？找到整数解，

此枝停止计算§4.3

分枝定界法

x1x2⑴⑵33⑶11BAC先求（LP21）:§4.3

分枝定界法

此时在D点取得最优解。即x1＝12/5=2.4,x2=3,Z(21)＝87/5=17.4Dx1x2⑴⑵33⑶11BACD求（LP22），如图所示。§4.3

分枝定界法

无可行解，不再分枝。x1≤1x1≥2x2≥4x2≤3LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=2,x2=10/3Z(2)

＝18.7LP21x1=2.4,x2=3Z(21)

＝17.4LP22无可行解找到整数解，

此枝停止计算§4.3

分枝定界法

x1＝2.4不是整数，可继续分枝。即x1≤2，

x1≥3在（LP21）的基础上继续分枝。加入条件x1≤2，

x1≥3有下式：只要求出（LP211）和（LP212）的最优解即可。§4.3

分枝定界法

x1≤2LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=2,x2=10/3Z(2)

＝18.5LP21x1=2.4,x2=3Z(21)

＝17.4LP22无可行解LP211x1=？,x2=？Z(211)

＝？LP212x1=？,x2=？Z(212)

＝？x1≤1x1≥2x2≤3x2≥4x1≥3＃找到整数解，

此枝停止计算§4.3

分枝定界法

先求（LP211）§4.3

分枝定界法

x1⑴⑵33⑶11BACDEx2此时E

在点取得最优解即x1＝2,x2=3,Z(211)＝17求（LP212）§4.3

分枝定界法

x1x2⑴⑵33⑶11BACDEF如图所示。此时F在点取得最优解。x1＝3,x2=2.5,Z(212)＝31/2=15.5LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=2,x2=10/3Z(2)

＝18.5LP21x1=2.4,x2=3Z(21)

＝17.4LP22无可行解LP211x1=2,x2=3Z(211)

＝17LP212x1=3,x2=5/2Z(212)

＝15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃找到整数解，

此枝停止计算找到整数解，

此枝停止计算§4.3

分枝定界法

LP211x1=2,x2=3Z(211)

＝17找到最优解3200CB

XB

b

x1x2x3x40x3921109/20x414230114/2cj-zj32003200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2cj-zj00-5/4-1/4解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。初始表最终表例2:用分枝定界法求解整数规划问题。§4.3

分枝定界法

由单纯形表可知：x1=13/4x2=5/2Z(0)=59/4=14.75

选x2进行分枝，即增加两个约束，x2≤2,x2≥3有下式：

分别在(LP1)和(LP2)中引入松弛变量x5和x6

，将新加约束条件加入上表计算。即x2+x5=2,－x2+x6=－3

得下表:§4.3

分枝定界法

x1=7/2,x2=2Z(1)=29/2=14.5继续分枝，加入约束

x1

≤3,x1≥4LP1LP2x1=5/2,x2=3

Z(2)=27/2=13.5∵

Z(2)<Z(1)∴先不考虑分枝接(LP1)继续分枝，加入约束

x1≤3，

x1≥4有下式：分别引入松弛变量x7和x8，然后进行计算。§4.3

分枝定界法

x1=3,x2=2

Z(3)=13找到整数解，停止计算。LP11x1=4,x2=1

Z(4)=14找到整数解，停止计算。LP12树形图如下：LP1x1=7/2,x2=2Z(1)＝29/2=14.5LPx1=13/4,x2=5/2Z(0)

＝59/4=14.75LP2x1=5/2,x2=3Z(2)＝27/2=13.5LP11x1=3,x2=2Z(3)

＝13LP12x1=4,x2=1Z(4)

＝14x2≤2x2≥3x1≤