运筹学课件第五章整数规划

1第五章整数规划一、学习目的与要求1、熟悉分支定界法和割平面法的原理及其应用；2、掌握求解0——1规划问题的隐枚举法；3、掌握求解指派问题的匈牙利法。二、课时9学时第一节整数规划的数学模型及解的特点整数规划IP(integerprogramming)：在许多规划问题中，如果要求一部分或全部决策变量必须取整数。例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP。松弛问题(slackproblem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integerlinearprogramming)。一、整数线性规划数学模型的一般形式中部分或全部取整数或或或njinjjijnjjjxxxnjxmibxatsxcz,,,),,2,1(0),,2,1(),(..min)max(2111整数线性规划问题可以分为以下几种类型1、纯整数线性规划(pureintegerlinearprogramming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。2、混合整数线性规划(mixedintegerlinerprogramming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。3、0—1型整数线性规划(zero—oneintegerlinerprogramming)：指决策变量只能取值0或1的整数线性规划。二、整数规划的例子例1某服务部门各时段（每2h为一时段）需要服务员的人数见下表。按规定，服务员连续工作8h（即四个时段为一班）。现在求安排服务员的工作时间，使服务部门服务员总数最少？时段12345678服务员最少数目10891113853解：设在第j时段开始上班的服务员的人数为xj。问题的数学模式略。例2现有资金总额为B。可选择投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j=1，2，…，2n）。此外由于种种原因，有三个附加条件：若选择项目1，就必须选择项目2。反这则不一定；第二，项目3和项目4中至少选择一个；第三，项目5、项目6和项目7恰好选择两个。应当怎样选择投资项目，才能使预期收益最大？解：每一个投资项目都有被选择和不被选择两种可能，为此令),,2,1(01njjjxj不投资项目投资项目这样，问题可表示为njjjxcz1max),,2,1(1021..76543121njxxxxxxxxBxatsjnjjj或例3工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1，B2，B3，B4四个。各工厂年生产能力、各地所需求量、各厂至各需求地的单位物资运费cij（i,j=1,2,…,4）见下表。B1B2B3B4生产能力（kt/年）A12934400A28357600A37612200A44525200需求量（kt/年）350400300150工厂A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用（即全部物资运费和新工厂生产费用之和）最少？解：这是全个物资运输问题，其特点是事先不能确定应该建A3或A4中哪一个，因而不知道新厂投产后的实际生产费用。引入0—1变量4301AAy若建工厂若建工厂再设cij为由Ai运往Bj的物资数量（i,j=1,2,…,4），单位是千吨，z表示总费用。问题数学模型为1400)1(1200min4141yyxczjiijij310),4,3,2,1,(0)1(200200600400150300400350..414413412411414413412411或yjixyxyxxxxxxxtsijijijijijiiiiiiii三、整数规划的解的特点相对于松弛问题而言，二者之间既有联系，又有本质的区别(1)整数规划问题的可行域是其松弛问题的一个子集(2)整数规划问题的可行解一定是其松弛问题的可行解(3)一般情况下，松弛问题的最优解不会刚好满足变量的整数约束条件，因而不是整数规划的可行解，更不是最优解(4)对松弛问题的最优解中非整数变量简单的取整，所得到的解不一定是整数规划问题的最优解，甚至也不一定是整数规划问题的可行解(5)求解还是要先求松弛问题的最优解，然后用分支定界法或割平面法。例4考虑下面的整数规划问题：且取整数0,82332..4max21212121xxxxxxtsxxzx1x2912064第二节解纯整数规划的割平面法考虑纯整数规划问题取整数njinjjijnjjjxxxnjxmibxatsxcz,,,),,2,1(0),,2,1(..max2111设其中aij（i=1,2,…,m,j=1,2,…,n）和bj（j=1,2,…,n）皆为整数。纯整数规划的松驰问题是一个线性规划问题，可以用单纯形法求解。在松驰问题的最优单纯形表中，记Q为m个基变量的下标的集合，K为n-m个非基变量的下标的集合，则m个约束方程可表示为QibxaxiKjjiji（1）而对应的最优解TnxxxX*),*,*,(*21，其中KjQjbxjj0*若jb皆为整数，则此解就是纯整数规划的最优解。否则不是原整数规划最优解。割平面法基本思路：通过增加新的约束来切割可原问题伴随规划的可行域，使它在不断缩小的过程中，将原问题的整数最优解逐渐暴露且趋于可行域极点的位置，这样就有可能用单纯形法求出。每次增加的新的约束条件应当具备两个基本性质：一是已获得的不符合整数要求的线性规划最优解不满足线性约束条件，从而不可能在以后的解中再出现；二是凡整数可行解均满足线性约束条件，因而整数最优解始终被保留在每次形成的线性规划可行域中。为此若)(00Qibi不是整数，在（1）式中的约束方程为000,iKjjjiibxax（2）其中)(,0Kjxxji应为整数，按)(00Qibi不是整数，jia,0可能是整数也可能不是整数。分解00,ijiba和成两个部分。一部分是不超过该数的最大整数，另一部分是余下的小数。即)(10,,,,,,,,000000KjfaNfNajijijijijiji且为整数10,,000000iiiiiifbNfNb且为整数（2）式变为KjjjiiiKjjjiixffNxNx,,00000因此有Kjjjiixff0,00，即500,iKjjjifxf（3）上式满足上面要求的两个性质（证明见书P128）。实际解题时，经验表明若从最优单纯表中选择具有最大（小）数部分的非整分量所在行构造割平面约束条件，往往可以提高切割效果，减少切割次数。例5用割平面法解整数规划问题且为整数0,5210453233max2121212121xxxxxxxxxxz解：将原整数规划问题称为原问题A0，不考虑整数条件的松驰问题为问题B0，求解过程如下：1．用单纯形法求解B0，得最优单纯形表Cj3-1000CB基bx1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70x431/700-3/7122/7cj-zj00-5/70-3/72．求一个割平面方程在最终表上任选一个含有不满足整数条件基变量的约束方程。若选x1，则含x1的约束方程为：76573371xx上式加入松驰变量x6得766573371xxx3、将上述约束方程重新组合。用对偶单纯形法解新线性规划Cj3-10000CB基bx1x2x3x4x5x63x113/7101/702/70-1x29/701-2/703/700x431/700-3/7122/700x6-6/700-1/70-3/71cj-zj00-5/70-3/7063x11100001-1x25/4010-1/40-5/40x35/2001-1/20-11/20x57/40001/41-3/4cj-zj000-1/40-17/4类似的得新割平面约束条件737641441xxx再解新线性规划得Cj3-100000CB基bx1x2x3x4x5x6x73x111000010-1x2201000-1-10x3400100-5-20x5100001-110x41000101-4cj-zj00000-4-1得最优解。割平面法解整数规划问题的基本步骤第一步：用单纯形法解松弛问题，得到最优单纯形表。第二步：求一个割平面方程，加到最优单纯形表中，用对偶单纯形法继续求解。第三步：若没有得到整数最优解，则继续作割平面方程，转第二步。7第三节分支定界法分枝定界法是一种隐枚举法或部分枚举法，它不是一种有效算法，是枚举法基础的改进。分枝定界法的关键是分支和定界。分支定界法的主要思路是首先求解整数规划的伴随规划，如果求得的最优解不符合整数条件，则增加新约束——缩小可行域；将原整数规划问题分支——分为两个子规划，再解子规划的伴随规划……，最后得到原整数规划的伴随规划。这就是所谓的“分支”。所谓“定界”，是在分支过程中，若某个后继问题恰巧获得整数规划问题的一个可行解，那么，它的目标函数值就是一个“界限”，可以作为衡量处理其它分支的一个依据。“分支”为整数规划最优解的出现创造了条件，而“定界”则可以提高搜索的效率。例用分支定界法求解整数规划问题且为整数0,3121451149max21212121xxxxxxxxz解：记整数规划为（IP），它的松驰问题为（LP）。(1)首先解该整数规划的松松驰驰问问题题为为（（LLPP）），如图所示，用图解法其最优解为X*=(3/2,10/3)’，图中点A，Z*=29/6。不符合整数要求，可任选一个变量，如x1=3/2进行分支。由于最接近3/2的整数是1和2，因而可以构造两个约束条件x1≥2和x1≤1，分别并入原来的约束条件，形成两个分支S1、S1，松驰问题分别记为（LP1）、（LP2）。（LP1）其最优解为X*=(2,23/9)’，图中点B，Z*=41/9；（LP2）其最优解为X*=(1,7/3)’，图中点C，Z*=10/3；都不整数解，因41/97/3，优先S1分枝。因x2=23/9，进行分支。由于最接近23/9的整数是2和3，因而可以构造两个约束条件x2≥3和x2≤2，分别并入原来的约束条件，形成两个分支S11、S12，松驰问题分别记为（LP11）、（LP12）。（LP11）其最优解为为空；（LP12）其最优解为X*=(33/14,2)’，图中点D，Z*=61/14；不是整数解。x1x2A(3/2,10/3)x1x2S1S2x2S12S2x2S2S121S122B(2,23/9）C(1,7/3)D(33/14,2)F(2,2)8因x1=33/14，进行分支。由于最接近33/14的整数是2和3，因而可以构造两个约束条件x1≥3和x1≤2，分别并入原来的约束条件，形成两个分支S121、S122，松驰问题分别记为（LP121）、（LP122）。（LP121）其最优解为X*=(3,1)’，图中点E，Z*=4；（LP122）其最优解为X*=(2,2)’，图中点F，Z*=4。因此有两个最优解，分别是（2，2）、（3，1），最大值为4。分支定界法的计算步骤第一步：计算原问题目标函数值的初始上界第二步：计算原问题目标函数值的初始下界第三步：增加约束条件将原问题分支第四步：分别求解一对分支第五步：修改上、下界第六步：比较上、下界大小，如有上界＝下界，停止计算，找到最优解，否则转3E(3,1)9第四节0—1