整数规划jssk运筹学.ppt

运 筹 学 Operations Research,Chapter 5 整数规划 Integer Programming,1. 整数规划的数学建模 2. 整数规划的求解算法 3. 案例分析,2019年7月25日星期四,第五章 整数规划,第一节 整数规划的数学模型及解的特点 第二节 解纯整数规划的割平面法 第三节 分枝定界法 第四节 0-1型整数规划 第五节 指派问题,2019年7月25日星期四,在求解线性规划问题时，得到的最优解可能是分数或小数，但许多实际问题要求得到的解为整数才行。这种要求线性规划有整数解的问题，称为整数线性规划(Integer linear Programming) 。,第一节 整数规划的数学模型及解的特点,2019年7月25日星期四,例1 某服务部门各时段（每2h为一时段）需要的服务员人数见下表。按规定服务员连续工作8小时为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。,设xi表示第i时段开始上班的人数,2019年7月25日星期四,例2 现有资金总额为B，可供选择的投资项目n个，项目j所需投资额和预期收益分别为aj和cj，此外，由于种种原因，有三个附加条件：（1）若选择1，则必须选择2，反之则不一定；（2）项目3和4至少选择一个；（3）项目5、6、7中恰好选择2个。应该如何选择项目，才能使总预期收益最大？,设第i个项目为xi，则其有两种状态，选择投资（记为1）和不选择投资（记为0）。,2019年7月25日星期四,例3 工厂A1和A2生产某种物资。由于该种物资供不应求，故需再建一家工厂，相应的方案有A3和A4两个。这种物资的需求地有B1B4四个。各工厂的生产能力、各地年需求量、各厂至各需求地的单位运费cij见下表。工厂A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设A3还是A4，才能使每年的总费用（即全部物资运费和新工厂生产费用之和）最少。,2019年7月25日星期四,设xij表示第i个工厂供应给第j个需求的地的产量，y表示是否建设A3工厂（取1表示建设A3工厂，取0表示不建设A3工厂）,2019年7月25日星期四,【例4】指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表53所示，如何安排他们的工作使总成绩最好。,表53,2019年7月25日星期四,【解】此工作分配问题可以采用枚举法求解，即将所有分配方案求出，总分最大的方案就是最优解。本例的方案有 4！432124种，当人数和工作数较多时，方案数是人数的阶乘，计算量非常大。用01规划模型求解此类分配问题显得非常简单。,设,数学模型如下： 目标函数为,2019年7月25日星期四,每项工作只能安排一人，约束条件为,变量约束：,要求每人做一项工作，约束条件为,2019年7月25日星期四,引例,某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如下：,问两种货物各装运多少箱，可使获得利润最大？,2019年7月25日星期四,是不是可通过把不考虑整数要求求得的最优解经过“化整”得到满足整数要求的最优解呢？,设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2 都要求为整数,于是可建立整数规划模型： Max z20x1+10x2 (1) 5x1+4x224 (2) 2x1+5x213 (3) x1,x20 (4) x1,x2为整数 (5),2019年7月25日星期四,此例可解得x1=4.8,x2=0，凑整为x1=5,x2=0，这就破坏了条件(2)，因而不是可行解；如截断小数变为x1=4,x2=0，这当然满足所有约束条件，但不是最优解，因为对x1=4,x2=0有z80，而对x1=4,x2=1（也是可行解）有z90。,2019年7月25日星期四,整数规划的数学模型,若要求所有 xj 的解为整数，称为纯整数规划 若要求部分 xj 的解为整数，称为混合整数规划 对应没有整数解要求的线性规划称之为松弛问题 整数规划的解是可数个的，最优解不一定发生在极点 整数规划的最优解不会优于其松弛问题的最优解,2019年7月25日星期四,第二节 割平面法,2019年7月25日星期四,考虑纯整数规划问题：,设其中aij和bi皆为整数（若不为整数时，可乘上一个倍数化为整数）。,2019年7月25日星期四,割平面法是R.E.Gomory于1958年提出的一种方法，它主要用于求解纯整数规划。割平面法是用增加新的约束来切割可行域，增加的新约束称为割平面方程或切割方程。其基本思路为： 若其松弛问题的最优解X*不满足整数约束，则从X*的非整分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题中，形成一个新的线性规划，然后求解之。若新的最优解满足整数要求，则它就是整数规划的最优解；否则重复上述步骤，直到获得整数最优解为止。,2019年7月25日星期四,为最终获得整数最优解，每次增加的线性约束条件应当满足两个基本性质： （1）已获得的不符合整数要求的LP最优解不满足该线性约束条件，从而不可能在以后的解中出现； （2）凡整数可行解均满足该线性约束条件，因而整数最优解始终被保留在每次剩余的线性规划可行域中。,2019年7月25日星期四,例1 用割平面法求解整数规划问题,步骤1：标准化其松弛问题B0,2019年7月25日星期四,引进一个割平面来缩小可行域，割平面要切去松弛问题的非整数最优解而又不要切去问题的的任一个整数可行解。,用单纯形法求解：,2019年7月25日星期四,步骤2：求一个割平面方程,1）在最终表上任选一个含有不满足整数条件基变量的约束方程。如选x1，则含x1的约束方程为,2）将所选择的约束方程中非基变量的系数及常数项进行拆分处理。具体规则是：将上述系数和常数项均拆分成一个整数加上一个非负真分数（纯小数）之和。则（3）式变为：,2019年7月25日星期四,3）将上述约束方程（4）重新组合。组合的原则是：将非负基变量系数及常数项中的非负真分数移到等号右端，将其他部分移到等号左端，即得：,等式左端实际上由三部分组成，常数项的整数部分，基变量及非基变量（含松弛变量或剩余变量），前两部分都是整数或应取整数，而松弛变量x3、x4由松弛问题标准型知，也应取非负整数（对于这一点，当原问题的约束方程组中的系数或常数项中有非整数时，要求将约束方程先化为成整数系数及整数常数项，然后再标准化，就可满足）。,2019年7月25日星期四,很明显，（5）左端为整数，右端1，则有其右端0，即,4）将割平面方程加到松弛问题的约束方程中，构成新的松弛问题并求解（对偶单纯形法）。,2019年7月25日星期四,割平面方程,2019年7月25日星期四,1、本题注只用一次割平面就求得了最优解，但大多数问题中不是只用一、二次割平面就能求得整数最优解。若一次割平面不能求得整数最优解，则按步骤2中的4个步骤，在松弛问题的最终单纯形表中找出第二个割平面方程，将此割平面方程加到伴随规划中，过程伴随规划，再用对偶单纯形法(单纯形法)求解。若求得了整数最优解，则停止计算，否则继续再作割平面，缩小可行域，直到求得整数最优解为止。,注意：,2019年7月25日星期四,2、实际解题时，经验表明若从最终单纯形表中选择具有最大分数部分的非整分量所在行构造割平面约束，往往可以提高“切割”效果，减少“切割”次数。 3、在用割平面法解整数规划时，常会遇到收敛很慢的情形，因此实际中通常不单独使用。,2019年7月25日星期四,第三节 分枝定界法,2019年7月25日星期四,分枝定界法(branch and bound method)是20世纪60年代由Land-Doig和Dakin等人提出的。这种方法既可用于纯整数规划问题，也可用于混合整数规划问题，而且便于用计算机求解，所以很快成为解整数规划的最主要的方法。 分枝定界法的主要思路是：首先求解整数规划的松弛问题，如果求得的最优解不符合整数条件，则增加新约束缩小可行域；将原整数规划问题分枝分为两个子规划，再解子规划的松弛规划通过求解一系列子规划的伴随规划及不断地定界，最后得到原整数规划问题的整数最优解。,2019年7月25日星期四,分枝定界法的思路：,1. 求整数规划的松弛问题最优解；,2. 若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；,3. 任意选一个非整数解的变量xi，在松弛问题中加上约束xixi及xixi+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界；,2019年7月25日星期四,分枝定界法的思路：,4. 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。,2019年7月25日星期四,步骤1：用单纯形法求解松弛问题，得到最优解及最优值。,步骤2：分枝。,例2 解整数规划问题,41/910/3, 优先选择B1分枝。,2019年7月25日星期四,无可行解,61/14(B12)10/3(B2), 优先选择B12分枝。,2019年7月25日星期四,410/3，所以B2无需分枝。,2019年7月25日星期四,【例3】用分枝定界法求解,【解】先求对应的松弛问题（记为LP0）：,用图解法得到最优解X（3.57,7.14）,Z0=35.7,如下图所示。,2019年7月25日星期四,10,10,松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7,x1,x2,o,A,B,C,2019年7月25日星期四,10,10,x1,x2,o,A,B,C,LP1,LP2,3,4,LP1:X=(3,7.6),Z1=34.8,LP2:X=(4,6.5),Z2=35.5,2019年7月25日星期四,10,10,x1,x2,o,A,B,C,LP1,LP3,3,4,LP3:X=(4.33,6),Z3=35.33,6,2019年7月25日星期四,10,10,x1,x2,o,A,C,LP1,3,4,6,LP4:X=(4,6),Z4=34,LP5:X=(5,5),Z5=35,5,LP3,2019年7月25日星期四,尽管LP1的解中x1不为整数，但Z5Z因此LP5的最优解就是原整数规划的最优解。,分枝过程如图表示：,LP0:X=(3.57,7.14),Z0=35.7,LP1:X=(3,7.6) Z1=34.8,LP2:X=(4,6.5) Z2=35.5,x13,x14,LP3:X=(4.33,6) Z3=35.33,x26,LP4:X=(4,6) Z4=34,LP5:X=(5,5) Z5=35,x14,x15,无可行解,x27,2019年7月25日星期四,(1)用观察法求整数规划原问题R的一个可行解，其目标值便是R的最优目标值z*的一个下界z。 (2)求解松弛问题R0，若R0无可行解，则R也无可行解，结束；若得到R0的最优解x(0)和最优值z0。若x(0)符合R的整数条件，则显然x(0)也是R的最优解，结束；否则，以R0作为一个分枝标明求解的结果，z0是问题R的最优目标值z*的一个上界z。,分支定界法的步骤,2019年7月25日星期四,(3)分枝。取目标函数值最大的一个枝Rs，在Rs的解中任选一不符合整数条件的变量xj，其值为bj，构造两个约束条件xjbj和xjbj+1。将两个约束条件分别加入问题Rs，得两个后继规划问题Rs1和Rs2。不考虑整数条件求解这两个后继问题，以每个后继问题为一分枝标明求解的结果。,分支定界法的步骤,2019年7月25日星期四,(4)定界。在各分枝中找出目标函数值最大者作为新的上界z；从已符合整数要求的各分枝中，找出目标函数值最大者作为新的下界z。 (5)比较与剪枝。各分枝的最优目标函数值中如果有小于z者，则剪掉这一枝（用打表示），即以后不再考虑了。若已没有大于z的分枝，则已得到R的最优解，结束；否则，转(3)。,2019年7月25日星期四,第四节 0-1 整数规划,2019年7月25日星期四,0-1型整数规划是整数规划的一种特殊形式，它的变量xj仅取值0或1。这种只能取0或1的变量称为0-1变量或二进制变量。,2019年7月25日星期四,例1 (含有互斥约束条件的问题)：设工序B的每周时约束条件为：0.3x1+0.5x2150，现还有一种新的加工方式,对应约束为： 0.2x1+0.4x2120，两种加工方式只能选一种。,互斥,2019年7月25日星期四,如果有m个互相排斥的约束条件(型)： i1x1+i2x2+inxnbi，i=1，2，,m 为保证这m个约束条件只有一个起作用，我们引入m个0-1变量yi(i=1,2,，m)和一个充分大的常数M，将约束条件改为如下形式： i1x+i2x2+inxnbi+yiM i=1,2,，m (5-13) y1+y2+ym=m 1 (5-14) 显然，在m个yi中只有一个能取0值，设yi*=0，就只有i=i*这个约束条件起作用，而别的式子都是多余的。,2019年7月25日星期四,例2 (固定费用问题)：三种资源被用于生产三种产品，资源量、单件可变费用、售价、资源单耗量以及固定成本见右表，制定一个生产计划使总收益最大。,2019年7月25日星期四,对于0-1型整数规划，一般采用隐枚举法，而不必采用完全枚举法。包括: (1)只要发现某个变量组合不满足其中一个约束条件时，就不必再去检验其他约束条件是否可行。 (2)若已发现一个可行解，则可根据它的目标函数值产生一个过滤条件，对于目标函数值比它差的变量组合就不必再去检验它的可行性；在以后的求解中每当发现更好的可行解就替换原来的过滤条件。,0-1型整数规划的解法,2019年7月25日星期四,例3 求解01整数规划,若将目标函数系数按小到大排列：max z=-2x2+3x1+5x3，计算量大减。,2019年7月25日星期四,第五节 指派问题,2019年7月25日星期四,指派问题的标准形式及其数学模型 匈牙利解法求解指派问题 一般的指派问题,2019年7月25日星期四,有n项任务，恰好n个人承担，第i人完成第j 项任务的花费(时间或费用等)为cij，要求确定人和事之间的一一对应的指派方案，使总花费最省？,一、指派问题的标准形式及其数学模型,指派问题的系数矩阵如下：,Cij的含义可以不同，如费用、成本、时间等。,2019年7月25日星期四,为建立标准指派问题的数学模型，引入nn个0-1变量：,指派问题的数学模型可写成如下形式：,1 若派第i人做第j事 0 若不派第i人做第j事 （ij=1，2,，n）,第j项工作由一个人做,第i人做一项工作,2019年7月25日星期四,指派问题的每个可行解，可用矩阵表示如下：,矩阵X中，每行各元素中只有1个元素为1，其余各元素等0；每列各元素中也只有1个元素为1，其余各元素等0 。 指派问题有n！个可行解。,2019年7月25日星期四,例4 有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作，使所需总时间最少？,2019年7月25日星期四,指派问题的数学模型如下：,2019年7月25日星期四,已知条件可用系数矩阵（效率矩阵）表示为：,其可行解也可用每行仅有一个1，每列也仅有一个1的矩阵表示，如：,2019年7月25日星期四,二、匈牙利法解题步骤,1955年，库恩利用匈牙利数学家康尼格的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，称为匈牙利解法。,标准指派问题是一种特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运输问题。,2019年7月25日星期四,匈牙利解法的关键是利用了指派问题最优解的如下性质： 若从指派问题的系数矩阵C的某行（或某列）各元素分别减去一个常数k，得到一个新的矩阵C，则以C和C 为系数矩阵的两个指派问题有相同的最优解。 （系数矩阵的变化并不影响数学模型的约束方程组，而只是目标函数值减少了常数k，所以最优解不变）,二、匈牙利法解题步骤,2019年7月25日星期四,-2 -4 -9 -7,若某行(列)已有0元素，那就不必再减了。例1的计算为：,1. 使系数矩阵各行、各列出现零元素 作法：系数矩阵各行元素减去所在行的最小元素，再从所得矩阵的各列减去所在列最小元素。(因一行中xij 取值一个1，其余为0，cij 同时减去一常数不影响xij取值)。,匈牙利法解题步骤如下：,2019年7月25日星期四,-4 -2,这就保证每行每列至少有一个0元素，同时不出现负元素。,2019年7月25日星期四,2. 试求最优解,作法：由独立0元素的行（列）开始，独立0元素处右上角画“ * ”标记 ，在有“ * ” 的行列中划去其它0元素；再在剩余的0元素中重复此做法，直至不能标记 “ * ”为止。,2019年7月25日星期四,（1）当遇到在所有的行和列中，0元素都不止一个时（存在0元素的闭回路），可任选其中一个0元素加圈，同时划去同行和同列中其他0元素。 （2）如能找出n个位于不同行不同列的零元素，令对应的xij= 1，其余xij = 0，得最优解，结束；否则，看下面的例题转第3步。,2019年7月25日星期四,例5 求表中所示效率矩阵的指派问题的最小解。,经行运算即可得每行每列都有0元素的系数矩阵。,2019年7月25日星期四,再按上述步骤运算，得到：,所画“ 0*