《整数规划与分配问题运筹学.ppt》由会员分享，可在线阅读，更多相关《整数规划与分配问题运筹学.ppt（91页珍藏版）》请在三一办公上搜索。
1、,运筹学,讲授：毕德春辽东学院信息技术学院信息管理系,2023/8/15,第 2页,第4章 整数规划与分配问题,2023/8/15,第 3页,例4.1 某服务部门各时段（每2小时为一时段）需要的服务员人数如下表，按规定，服务员连续工作8小时（即4个时段）为一班，现要求安排服务员的工作时间，使服务部门服务员总数最小。,4.1 整数规划问题的数学模型,2023/8/15,第 4页,解：设在第j时段开始时上班的服务员人数为xj，由于第j时段开始时上班的服务员将在第(j+3)时段结束时下班，故决策变量只需考虑x1,x2,x3,x4,x5，此问题的数学模型为：,2023/8/15,第 5页,此类问题数学
2、模型的一般形式为：求一组变量X1,X2,Xn，使,2023/8/15,第 6页,例4.2 某单位有5个拟选择的投资项目，其所需投资额与期望收益如下表。由于各项目之间有一定联系，A、C、E之间必须选择一项且仅需选择一项；B和D之间需选择也仅需选择一项；又由于C和D两项目密切相关，C的实施必须以D的实施为前提条件，该单位共筹集资金15万元，问应该选择哪些项目投资，使期望收益最大？,2023/8/15,第 7页,解：决策变量：设,目标函数：期望收益最大,约束条件：投资额限制条件 6x1+4x2+2x3+4x4+5x515,项目A、C、E之间必须且只需选择一项：x1+x3+x5=1,项目C的实施要以项
3、目D的实施为前提条件：x3 x4,项目B、D之间必须且只需选择一项：x2+x4=1,归纳起来，其数学模型为：,2023/8/15,第 8页,上面此例表明，利用0-1变量处理一类“可供选择条件”的问题非常简明方便。下面再进一步分别说明对0-1变量的应用。假定现有m种资源对可供选择的n个项目进行投资的数学模型为：求一组决策变量X1,X2,Xn，使,2023/8/15,第 9页,根据变量取整数的情况,将整数规划分为：（1）纯整数规划，所有变量都取整数.（2）混合整数规划，一部分变量取整数,一部分变量取实数（3）0-1整数规划,所有变量均取0或1,对决策变量只限于不能取负值的连续型数值，即可以是正分数
4、或正小数。然而在许多经济管理的实际问题中，决策变量只有非负整数才有实际意义。对求整数最优解的问题，称为整数规划(Integer Programming)(简记为IP)。又称约束条件和函数均为线性的IP为整数线性规划(Integer Linear Programming)(简记为ILP)。,2023/8/15,第 10页,考虑纯整数问题：,整数问题的松弛问题：,2023/8/15,第 11页,求解ILP问题方法的思考：,“舍入取整”法：即先不考虑整数性约束，而去求解其相应的LP问题（称为松驰问题），然后将得到的非整数最优解用“舍入取整”的方法。这样能否得到整数最优解？但在处理个别实际问题时，如果
5、允许目标函数值在某一误差范围内，有时也可采用“舍入取整”得到的整数可行解作为原问题整数最优解的近似。这样可节省求解的人力、物力和财力。,2023/8/15,第 12页,例4.3 设整数规划问题如下,首先不考虑整数约束，得到线性规划问题（松弛问题）。,2023/8/15,第 13页,用图解法求出最优解x13/2,x2=10/3且有Z=29/6,x1,x2,3,3,(3/2,10/3),现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。,按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划
6、问题的可行解集是一个有限集，如图所示。,2023/8/15,第 14页,因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。,目前，常用的求解整数规划的方法有：割平面法和分支定界法，对于特别的01规划问题采用隐枚举法和匈牙利法。,2023/8/15,第 15页,在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（
7、或所需时间最少），这类问题称为指派问题或分派问题。,4.2 分配问题与匈牙利法,2023/8/15,第 16页,分配第i个人去完成第j项任务不分配第i个人去完成第j项任务,例4.4 有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间（h）如下表，应如何分配，使这四个人分别完成这四项任务总的时间为最小？,2023/8/15,第 17页,2023/8/15,第 18页,分配问题的数学模型：设n 个人被分配去做n 件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第I 个人去做第j 件工作的的效率（时间或费用）为Ci
8、j(i=1.2n;j=1.2n)并假设Cij 0。问应如何分配才能使总效率（时间或费用）最高？,设决策变量 1 分配第i 个人去做第j 件工作 xij=0 相反(I,j=1.2.n),其数学模型为：,2023/8/15,第 19页,匈牙利法,指派问题是0-1 规划的特例，也是运输问题的特例，当然可用整数规划，0-1 规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。,第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中
9、都出现0元素，即（1）从（cij）的每行元素都减去该行的最小元素；（2）再从所得新系数矩阵的每列元素中减去该列的最小元素。,2023/8/15,第 20页,第二步：进行试指派，以寻求最优解。在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：（1）从只有一个0元素的行(列)开始，给这个0元素加圈，记作。然后划去 所在列(行)的其它0元素，记作；这表示这列所代表的任务已指派完，不必再考虑别人了。（2）给只有一个0元素的列(行)中的0元素加圈，记作；然后划去 所在行的0元素，记作（
10、3）反复进行（1），（2）两步，直到尽可能多的0元素都被圈出和划掉为止。,2023/8/15,第 21页,（4）若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。（5）若 元素的数目m 等于矩阵的阶数n，那么这指派问题的最优解已得到。若m n,则转入下一步。第三步：作最少的直线覆盖所有0元素。（1）对没有的行打号；（2）对已打号的行中所有含元素的列打号；（3）再对打有号
11、的列中含 元素的行打号；,2023/8/15,第 22页,（4）重复（2），（3）直到得不出新的打号的行、列为止；（5）对没有打号的行画横线，有打号的列画纵线，这就得到覆盖所有0元素的最少直线数 l。l 应等于m，若不相等，说明试指派过程有误，回到第二步（4），另行试指派；若 lm n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。第四步：变换矩阵(bij)以增加0元素。在没有被直线覆盖的所有元素中找出最小元素，然后打各行都减去这最小元素；打各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。,2023/8/15,第 23页,例
12、4.5,2023/8/15,第 24页,2,4,9,7,2023/8/15,第 25页,4,2,2023/8/15,第 26页,2023/8/15,第 27页,例 4.7 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？,2023/8/15,第 28页,求解过程如下：第一步，变换系数矩阵：,5,第二步，试指派：,找到 3 个独立零元素 但 m=3 n=4,2023/8/15,第 29页,第三步，作最少的直线覆盖所有0元素：,独立零元素的个数m等于最少直线数l，
13、即lm=3n=4；,第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打各行都减去1；打各列都加上1，得如下矩阵，并转第二步进行试指派：,2023/8/15,第 30页,得到4个独立零元素，所以最优解矩阵为：,15,2023/8/15,第 31页,练习：,11,5,7,6,4,戊,6,9,6,3,7,丁,8,6,4,5,8,丙,9,11,7,12,9,乙,11,8,9,5,7,甲,E,D,C,B,A,费 工作 用人员,2023/8/15,第 32页,-1,-2,2023/8/15,第 33页,2023/8/15,第 34页,l=m=4 n=5,2023/8/
14、15,第 35页,2023/8/15,第 36页,2023/8/15,第 37页,l=m=4 n=5,2023/8/15,第 38页,2023/8/15,第 39页,此问题有多个最优解,28,2023/8/15,第 40页,2023/8/15,第 41页,2023/8/15,第 42页,用匈牙利法求解下列指派问题，已知效率矩阵分别如下：,2023/8/15,第 43页,4.2.3 两点说明,1.分配问题中如果人数和工作任务数不相等是的处理方法,2023/8/15,第 44页,2如果效率矩阵的数字是表示每人每天能完成的翻译成汉字的字数，问题就变成如何分配任务，使每天完成的任务量为大最，目标函数就
15、变为：,等价于：,2023/8/15,第 45页,01 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法。,例 4.11 求解下列01 规划问题,01 整数规划与隐枚举法,2023/8/15,第 46页,解：对于01 规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1 组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。,2023/8/15,第 47页,由上表可知，问题的最优解为 X*=(x1=1 x2=0 x3=1)由上表可知：x1
16、=0 x2=0 x3=1 是一个可行解，为尽快找到最优解，可将3 x12 x25 x3 5 作为一个约束，凡是目标函数值小于5 的组合不必讨论，如下表。,2023/8/15,第 48页,例 4.12 求解下列01 规划问题,解：由于目标函数中变量x1,x2,x4 的系数均为负数，可作如下变换：,令 x1 1 x1,x2=1-x2,x3=x3,x4=1-x4带入原题中，但需重新调整变量编号。令 x3=x1,x4=x2得到下式。,2023/8/15,第 49页,可以从(1.1.1.1)开始试算，x(3)(1.1.0.1)最优解。x(3)(1.0.1.0)是原问题的最优解，Z*=2,2023/8/1
17、5,第 50页,例 4.13 求解下列01 规划问题,令 y1=x5,y2=x4,y3=x2,y4=x3,y5=x1 得到下式,2023/8/15,第 51页,所以，Y*=（），原问题的最优解为：X*（），Z*=8,2023/8/15,第 52页,（0，1，1，0，0）,练习：用隐枚举法求解01规划问题,2023/8/15,第 53页,4.3.1 基本思路,4.3 分枝定界法,只解松弛问题1、在全部可行性域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最优解2、分枝过程若松弛问题最优解中某个 xk=bk 不是整数，令 bk 为 bk 的整数部分构造两个新的约束条件 xk bk 和 x
18、k bk+1，分别加于原松弛问题，形成两个新的整数规划3、求解分枝的松弛问题 定界过程设两个分枝的松弛问题分别为问题 1 和问题 2，它们的最优解有如下情况,2023/8/15,第 54页,分枝问题解可能出现的情况,情况 2,4,5 找到最优解情况 3 在缩减的域上继续分枝定界法情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后续分枝所得到的解进行比较，结论如情况 4 或 5,2023/8/15,第 55页,例4.8 用分枝定界法求解整数规划问题（用图解法计算）,记为（IP）,解：首先去掉整数约束，变成一般线性规划问题,记为（LP）,2023/8/15,第 56页,用图解法求（
19、LP）的最优解，如图所示。,x1,x2,3,3,(18/11,40/11),对于x118/111.64，取值x1 1，x1 2对于x2=40/11 3.64，取值x2 3，x2 4先将（LP）划分为（LP1）和（LP2）,取x1 1,x1 2,x118/11,x2=40/11Z(0)=218/11(19.8)即Z 也是（IP）最小值的下限。,2023/8/15,第 57页,有下式：,现在只要求出（LP1）和（LP2）的最优解即可。,2023/8/15,第 58页,x1,x2,3,3,(18/11,40/11),先求（LP1）,如图所示。此时B 在点取得最优解。x11,x2=3,Z(1)16找到
20、整数解，问题已探明，此枝停止计算。,1,1,同理求（LP2）,如图所示。在C 点取得最优解。即x12,x2=10/3,Z(2)56/318.7 Z2 Z116 原问题有比（16）更小的最优解，但 x2 不是整数，故利用 3 10/34 加入条件。,B,A,C,2023/8/15,第 59页,加入条件：x23,x24 有下式：,只要求出（LP3）和（LP4）的最优解即可。,2023/8/15,第 60页,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,先求（LP3）,如图所示。此时D 在点取得最优解。即 x112/52.4,x2=3,Z(3)-87/5-17.4Z-19.8但
21、x112/5不是整数，可继续分枝。即 3x12。,D,求（LP4），如图所示。无可行解，不再分枝。,2023/8/15,第 61页,在（LP3）的基础上继续分枝。加入条件3x12有下式：,只要求出（LP5）和（LP6）的最优解即可。,2023/8/15,第 62页,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,D,先求（LP5）,如图所示。此时E 在点取得最优解。即 x12,x2=3,Z(5)17找到整数解，问题已探明，此枝停止计算。,E,求（LP6），如图所示。此时 F在点取得最优解。x13,x2=2.5,Z(6)31/215.5 Z(5),F,如对 Z(6)继续分解，
22、其最小值也不会低于15.5，问题探明,剪枝。,2023/8/15,第 63页,至此，原问题（IP）的最优解为：x1=2，x2=3,Z*=Z(5)17以上的求解过程可以用一个树形图表示如右：,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=2,x2=10/3Z(2)18.5,LP3x1=12/5,x2=3Z(3)17.4,LP4无可行解,LP5x1=2,x2=3Z(5)17,LP6x1=3,x2=5/2Z(6)15.5,x11,x12,x23,x24,x12,x13,2023/8/15,第 64页,练习：用分枝定界法求解整数规划问题（图解
23、法）,2023/8/15,第 65页,x11,x12,x22,x23,x22,x23,x12,x13,2023/8/15,第 66页,LP1x1=1,x2=7/3Z(1)10/3,LPx1=2/3,x2=10/3Z(0)29/6,LP2x1=2,x2=23/9Z(2)41/9,LP3x1=33/14,x2=2Z(3)61/14,LP4无可行解,LP7x1=2,x2=2Z(7)4,LP8x1=3,x2=1Z(8)4,x11,x12,x22,x23,x12,x13,2023/8/15,第 67页,解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。,初始表,最终表,例4.10 用分枝定界法求
24、解整数规划问题（单纯形法）,2023/8/15,第 68页,x1=13/4 x2=5/2 Z(0)=59/414.75 选 x2 进行分枝，即增加两个约束，2 x2 3 有下式：,分别在(LP1)和(LP2)中引入松弛变量x5和x6，将新加约束条件加入上表计算。即 x2+x5=2,x2+x6=3 得下表:,2023/8/15,第 69页,x1=7/2,x2=2 Z(1)=29/2=14.5继续分枝，加入约束 3 x1 4,LP1,2023/8/15,第 70页,LP2,x1=5/2,x2=3 Z(2)=27/2=13.5 Z(2)Z(1)先不考虑分枝,2023/8/15,第 71页,接(LP1
25、)继续分枝，加入约束 4 x1 3，有下式：,分别引入松弛变量x7 和 x8，然后进行计算。,2023/8/15,第 72页,x1=3,x2=2 Z(3)=13找到整数解，问题已探明，停止计算。,LP3,2023/8/15,第 73页,x1=4,x2=1 Z(4)=14找到整数解，问题已探明，停止计算。,LP4,2023/8/15,第 74页,树形图如下：,LP1x1=7/2,x2=2Z(1)29/2=14.5,LPx1=13/4,x2=5/2Z(0)59/4=14.75,LP2x1=5/2,x2=3Z(2)27/2=13.5,LP3x1=3,x2=2Z(3)13,LP4x1=4,x2=1Z(
26、4)14,x22,x23,x13,x14,2023/8/15,第 75页,练习：用分枝定界法求解整数规划问题（单纯形法）,2023/8/15,第 76页,2023/8/15,第 77页,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=2,x2=10/3Z(2)18.5,LP3x1=12/5,x2=3Z(3)17.4,LP4无可行解,LP5x1=2,x2=3Z(5)17,LP6x1=3,x2=5/2Z(6)15.5,x11,x12,x23,x24,x12,x13,2023/8/15,第 78页,4.4 割平面法的基本思想,若的分量不全是整
27、数，则对增加一个割平面条件，将的可行区域割掉一块，恰好在被割掉的区域内，而原ILP问题的任何一个可行解（格点）都没有被割去.,2023/8/15,第 79页,把增添了割平面条件的问题记为，用对偶单纯形法求解LP问题.若 的最优解 是整数向量，则 是原ILP问题 的最优解，计算结束；,否则对问题 在增加一个割平面条件，形成问题，如此继续下去，通过求解不断改进的松弛LP问题，知道得到最优整数解为止。,2023/8/15,第 80页,例4.7 用割平面法求解整数规划问题,解：增加松弛变量x3和x4，得到(LP)的初始单纯形表和最优单纯形表：,2023/8/15,第 81页,此题的最优解为：X(1,3
28、/2)Z=3/2 但不是整数最优解，引入割平面。以x2 为源行生成割平面，由于 1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为:,也即：,2023/8/15,第 82页,将 x3=6-3x1-2x2,x4=3x1-2x2,带入 中，得到等价的割平面条件：x2 1 见下图。,x1,x2,3,3,第一个割平面,2023/8/15,第 83页,现将生成的割平面条件加入松弛变量，然后加到表中：,2023/8/15,第 84页,此时，X1(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：,用上表的约束解出x4 和s1，将它们
29、带入上式得到等价的割平面条件：x1 x2，见图：,x1,x2,3,3,第一个割平面,第二个割平面,2023/8/15,第 85页,将生成的割平面条件加入松弛变量，然后加到表中：,2023/8/15,第 86页,至此得到最优表，其最优解为 X=(1,1),Z=1,这也是原问题的最优解。,有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。,2023/8/15,第 87页,例4.10 用割平面法求解数规划问题,初始表,最优表,2023/8/15,第 88页,在松弛问题最优解中，x1,x2 均为非整数解，由上表有：,将系数和常数都分解成整数和非负真分数之和,2023/8/15,第 89页,以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：,引入松弛变量s1 后得到下式，将此约束条件加到上表中，继续求解。,2023/8/15,第 90页,得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：X=(0,4),Z=4,或 X=(2,2),Z=4。,2023/8/15,第 91页,
