运筹学第四章 整数规划与分配问题(新)a

作业：P1254.14.24.3(a)4.4第四章整数规划与分配问题第一节整数规划的特点及应用一、整数规划的一般形式定义：一部分或全部决策变量必须取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划的松弛问题。若松弛问题是线性规划，则该整数规划称为整数线性规划。且部分或全部取整数）或或),,...2,1(0),...2,1((min)max(11njxmibxaxczjijnjijjnjj且均取整数值最优解求下述整数规划问题的例,0,5.45.0143223max.121212121xxxxxxxxz整数线性规划的一般形式:不考虑整数要求时，最优解为：X=(3.25,2.5)TZ=13（见下页图解法）考虑整数要求时，最优解为：X=(4,1)TZ=14凑整（3，2）可行，非最优，Z=13。（4，3），（4，2），（3，3）不可行二、整数规划的分类1.全整数线性规划决策变量全部取整数，约束系数和约束常数项也取整数的整数线性规划。2.纯整数线性规划决策变量全部取整数，约束系数和约束常数项可取非整数的整数线性规划。纯整数线性规划可化为全整数线性规划。3.混合整数线性规划决策变量中有一部分取整数值，另一部分可取非整数值的整数线性规划。4.0-1整数线性规划决策变量只能取0或1的整数线性规划。三、0-1变量（或称逻辑变量）在模型中的应用整数规划模型对研究管理问题有重要意义。很多不能归结为线性规划数学模型的管理问题，却可以通过设置逻辑变量建立起整数规划数学模型。第二节分配问题(指派问题）与匈牙利法2-1问题的提出及数学模型假设有m项任务分配给m个人去完成，并指定每个人完成其中一项，每项任务也只由一个人完成，问应如何分配任务，才能使总效率最高？（或总费用最少，花费的总时间最少等等。）设每个人完成不同任务的耗费见下面的效率矩阵，通常要求aij≥0。mmmmmmmmijaaaaaaaaaaA.....................212222111211),...,2,1,(j0,1mjiijixij项任务。人去完成第不分配第，项任务；人去完成第分配第又设则分配问题的数学模型为),...,2,1,(10),...,2,1(1),...,2,1(1min1111mjixmjxmixxazijmiijmjijmimjijij，或2-2匈牙利法定理1.如果从分配问题效率矩阵(aij)的每一行元素中分别减去（或加上）一个常数ui（称为该行的位势）；从每一列中分别减去（或加上）一个常数vj（称为该列的位势）；得到一个新的效率矩阵bij，其中bij=aij-ui-vj，则aij的最优解等价于bij的最优解。定理2.若效率矩阵A的元素可分成0与非0两部分，则覆盖所有0元素的最少直线数等于位于不同行不同列的0元素的最大个数。匈牙利法的步骤：第一步效率矩阵每行都减去该行的最小元素；第二步效率矩阵每列都减去该列的最小元素；此时，效率矩阵的每行每列都有0元素。第三步寻找位于不同行不同列的0元素，也就是寻找能覆盖所有0元素的最少直线数。方法：1.从只有一个0元素的行开始，对0元素打上（）号，然后对打（）的0元素所在列画一条直线，依次进行到最后一行；2.从只有一个0元素的列开始，对0元素打上（）号，然后对打（）的0元素所在行画一条直线，依次进行到最后一列；3.重复1.、2.两个步骤，可能出现三种情况：（1）若能找到m个位于不同行不同列的0元素（即带（）的0元素），则令（0）处的xij=1,求解结束；（2）若有形成闭回路的0元素，则任选一个打（），然后对每个间隔的0元素打（），同时对打（）的0元素所在行（或列）画一条直线。（3）若位于不同行不同列的0元素[即带（）的0元素]少于m，转第四步。第四步为产生m个位于不同行不同列的0元素，用定理一对效率矩阵进行调整，使之生成新的0元素。方法：1.在效率矩阵未被直线覆盖的元素中找出最小元素k；2.效率矩阵未被直线覆盖的行都减k;3.效率矩阵被直线覆盖的列都加k;4.转回第三步。2-3特殊情况的处理1.人数多于任务数，加虚拟任务。设有n人，m项任务，n＞m,则增加n-m项任务。2.人数少于任务数，加虚拟人员。设有n人，m项任务，n＜m,则增加m-n项任务。此时，效率矩阵的元素全成为负值，不符合要求，根据定理1，令变换后的效率矩阵每行都加M即可。mimjijijxaz11')(minijaMmax3.对求最大值问题的处理设目标函数为可将其变换为mimjijijxaz11max作业：P1264.7（a)4.8(a)第三节分枝定界法一、分枝定界法的基本思想先不考虑整数解的限制，用单纯形法求解其松弛问题，如果求得的解恰好是整数解，则得整数规划最优解，停止计算。否则，将松弛问题分解为两个子问题（也称后继问题），每个子问题都是在原松弛问题的基础上增加一个变量取整数的约束条件，这样就缩小了原来的可行域，然后用单纯形法求解，直至得到最终结果。二、分枝定界法的步骤（最大值问题）第一步寻找替代问题并求解设原整数规划问题为IP，其松弛问题为L0。用单纯形法求L0，若L0无可行解，则IP也无可行解，计算停止。若求得L0为整数解，则得IP的最优解，停止。否则，转下一步；第二步分枝与定界在L0的解中，任选一个不满足整数条件的变量xi，设xi=bi，则做两个子问题iibxL,11,2iibxL不考虑整数条件，用单纯形法求解两个子问题，若得整数解或子问题的最优值小于前面分支中已计算得到的所有整数解的目标函数最大值，则停止分枝；否则，选取所有子问题中目标函数值最大的问题作为L0继续分枝，直至得到整数规划的最优解。第三步剪枝在所有整数解中选取获得最大值的解为最优解。且均取整数值数规划问题的最优解用分枝定界法求下述整例,0,5.45.0143223max.21212121xxxxxxxxz第四节割平面法一、割平面法的基本思想先不考虑整数条件，用单纯形法求解其松弛问题，若得整数解，即得整数规划最优解。否则，增加线性约束条件（称为割平面方程），将原问题的可行域切割掉一部分，被切割掉的都是非整数解，再用单纯形法求解新的线性规划问题，依次进行下去，直到使问题的最优解恰好在可行域的某个具有整数坐标的顶点上得到。二、割平面法的步骤第一步将问题化为全整数规划问题；第二步加非负松弛变量，将约束条件化为等式约束；第三步解相应的线性规划问题1.若线性规划的最优解是整数解，则得整数规划的最优解，停止计算，否则转2;2.求解割平面方程作为附加约束条件，构成新的线性规划问题，继续第三步。三、割平面方程的求法1.求解线性方程组法设xi=bi是整数规划的松弛问题（LP问题）最优解中取分数值（分数部分最大）的基变量，将xi=bi用非基变量表示将bi，aik分解成整数部分和非负真分数部分之和：kkikiixabxkkikikkikiikkikikkikikkikikiiiikikikikiiiixffxNNxxffxNNxfNfNxffNaffNb)()10()10(得kkikiixabx要使所有变量都取非负整数值，上式左端必为整数，从而右端也必为整数，由于fi＞0，fik≥0，故应有这就是所求的割平面方程（Gomory方程）。1kkikixff例设某整数规划的松弛问题最优解中有x1=3.5，x1的非基变量表达式为x1=3.5+2.4x4–3.6x5+4x6=3+0.5+2x4+0.4x4-4x5+0.4x5+4x6或:x1-3-2x4+4x5-4x6=0.5+0.4x4+0.4x5由此可得割平面方程为0.5+0.4x4+0.4x5≥12.借助单纯形表法对求解整数规划问题的松弛问题（LP问题）得到最优单纯形表，设xi=bi是最优解中取分数值（分数部分最大）的基变量，则有kkikiikkikiikikikikiikikikikiiiiikiikkikixffNxNxfNxfNxffNaffNbabbxax即得令真分数部分之和，分解成整数部分和非负将)()10()10(,上式中，要使等式左端为整数，则右端也必为整数，由0＜fi＜1,故应有这就是所求的割平面方程（Gomory方程）。0kkikixff例设某整数规划的松弛问题最优解中有x1=3.5，x1在单纯形表中的约束条件为：x1-2.4x4+3.6x5-4x6=3.5x1-3x4+0.6x4+3x5+0.6x5-4x6=3+0.5或:x1-3-3x4+3x5-4x6=0.5-0.6x4-0.6x5由此可得割平面方程为0.5-0.6x4-0.6x5≤0且均取整数值规划问题的最优解用割平面法求下述整数例,0,5.45.0143223max.21212121xxxxxxxxz解：1.将问题化为全整数规划问题；去掉变量的整数要求，可得其松弛问题G02.加松弛变量，将约束化为等式约束；并用单纯形法求解得到最优表；（表4-4）0,92143223max21212121xxxxxxxxz0,,,92143223max432142132121xxxxxxxxxxxxz3.找出非整数解变量中非整数部分最大的一个基变量（这里是x2），并写出这一行的约束；:02121212121212)212()211()210(2122121434342432432加松弛变量化为等式所以，割平面方程为或即xxxxxxxxxxxx。形表，见表的单纯法继续求解得到中，然后用对偶单纯形的单纯形表解，可将该式直接加入求问题的约束中，得一新的将上式加入松弛问题54LP2121211010543GGGGxxx4.由于表中还有非整数解，找出非整数解变量中非整数部分最大的一个基变量（这里是x1），并写出这一行的约束；:02121212132132121321555415541541加松弛变量化为等式得割平面方程为或即xxxxxxxxxxxx。单纯形表，见表的续求解得到然后用对偶单纯形法继的单纯形表中，可将该式直接加入求解，问题中得一新的将上式加入到64LP2121212165GGGGxx该表已得到整数解，故原整数规划问题的最优解为:x1=4，x2=1，最优值为maxz=14作业：P127~1294.134.144.164.18第五节解0-1规划问题的隐枚举法一、隐枚举法的基本思想首先令所有整数变量都取0值，然后使某些变量取值为1，直到获得一个可行解，将第一个可行解作为临时最优解（称为过滤条件），再继续试探某些变量的取值，若可找到另一个可行解优于临时最优解，则将新的可行解作为临时最优解（新的过滤条件），依此类推，检查整数变量等于0或1的各种组合，不断寻求新的临时最优解，直到获得问题的最优解为止。由于只计算部分可行解的组合（优于临时最优解的组合），故称为隐枚举法。二、举例例3.求解0-1规划解：求解过程可以列表如下10,,6434422523max3213221321321321或xxxxxxxxxxxxxxxxz第五节应用举例例3东方大学计算机实验室聘用4名大学生(代号1、2、3、4)和2名研究生(代号5、6)值班答疑。已知每人从周一至周五每天最多可安排的值班时间及每人每小时值班的报酬如下表4—7所示：该实验室开放时间为上午8:00至晚上10:00，开放时间内须有且仅须一名学生值班。规定大学生每周值班不少于8h，研究生每周不少于7h，每名学生每周值班不超过3次，每次值班不少于2h，每天安排值班的学生不超过3人，且其中