第5章整数规划jssk运筹学.pptVIP

??????????? 运 筹 学 ? Operations? Research;第五章 整数规划; 在求解线性规划问题时，得到的最优解可能是分数或小数，但许多实际问题要求得到的解为整数才行。这种要求线性规划有整数解的问题，称为整数线性规划(Integer linear Programming) 。; 例1 某服务部门各时段（每2h为一时段）需要的服务员人数见下表。按规定服务员连续工作8小时为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。; 例2 现有资金总额为B，可供选择的投资项目n个，项目j所需投资额和预期收益分别为aj和cj，此外，由于种种原因，有三个附加条件：（1）若选择1，则必须选择2，反之则不一定；（2）项目3和4至少选择一个；（3）项目5、6、7中恰好选择2个。应该如何选择项目，才能使总预期收益最大？; 例3 工厂A1和A2生产某种物资。由于该种物资供不应求，故需再建一家工厂，相应的方案有A3和A4两个。这种物资的需求地有B1~B4四个。各工厂的生产能力、各地年需求量、各厂至各需求地的单位运费cij见下表。工厂A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设A3还是A4，才能使每年的总费用（即全部物资运费和新工厂生产费用之和）最少。;设xij表示第i个工厂供应给第j个需求的地的产量，y表示是否建设A3工厂（取1表示建设A3工厂，取0表示不建设A3工厂）;【例4】指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表5－3所示，如何安排他们的工作使总成绩最好。; 【解】此工作分配问题可以采用枚举法求解，即将所有分配方案求出，总分最大的方案就是最优解。本例的方案有 4！＝4×3×2×1＝24种，当人数和工作数较多时，方案数是人数的阶乘，计算量非常大。用0－1规划模型求解此类分配问题显得非常简单。;;引例; 是不是可通过把不考虑整数要求求得的最优解经过“化整”得到满足整数要求的最优解呢？; 此例可解得x1=4.8,x2=0，凑整为x1=5,x2=0，这就破坏了条件(2)，因而不是可行解；如截断小数变为x1=4,x2=0，这当然满足所有约束条件，但不是最优解，因为对x1=4,x2=0有z＝80，而对x1=4,x2=1（也是可行解）有z＝90。;整数规划的数学模型;第二节 割平面法;考虑纯整数规划问题：; 割平面法是R.E.Gomory于1958年提出的一种方法，它主要用于求解纯整数规划。割平面法是用增加新的约束来切割可行域，增加的新约束称为割平面方程或切割方程。其基本思路为： 若其松弛问题的最优解X*不满足整数约束，则从X*的非整分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题中，形成一个新的线性规划，然后求解之。若新的最优解满足整数要求，则它就是整数规划的最优解；否则重复上述步骤，直到获得整数最优解为止。;为最终获得整数最优解，每次增加的线性约束条件应当满足两个基本性质： （1）已获得的不符合整数要求的LP最优解不满足该线性约束条件，从而不可能在以后的解中出现； （2）凡整数可行解均满足该线性约束条件，因而整数最优解始终被保留在每次剩余的线性规划可行域中。 ;;;步骤2：求一个割平面方程; 3）将上述约束方程（4）重新组合。组合的原则是：将非负基变量系数及常数项中的非负真分数移到等号右端，将其他部分移到等号左端，即得： ;很明显，（5）左端为整数，右端1，则有其右端?0，即;割平面方程;1、本题注只用一次割平面就求得了最优解，但大多数问题中不是只用一、二次割平面就能求得整数最优解。若一次割平面不能求得整数最优解，则按步骤2中的4个步骤，在松弛问题的最终单纯形表中找出第二个割平面方程，将此割平面方程加到伴随规划中，过程伴随规划，再用对偶单纯形法(单纯形法)求解。若求得了整数最优解，则停止计算，否则继续再作割平面，缩小可行域，直到求得整数最优解为止。;2、实际解题时，经验表明若从最终单纯形表中选择具有最大分数部分的非整分量所在行构造割平面约束，往往可以提高“切割”效果，减少“切割”次数。 3、在用割平面法解整数规划时，常会遇到收敛很慢的情形，因此实际中通常不单独使用。;第三节 分枝定界法; 分枝定界法(branch and bound method)是20世纪60年代由Land-Doig和Dakin等人提出的。这种方法既可用于纯整数规划问题，也可用于混合整数规划问题，而且便于用计算机求解，所以很快成为解整数规划的最主要的方法。 分枝定界法的主要思路是：首先求解整数规划的松弛问题，如果求得的最优解不符