运筹学第五章 整数规划 胡运权.ppt

运筹学,赵明霞山西大学经济与管理学院,2020/4/26,2,第五章整数规划,整数规划的数学模型割平面法分支定界法0-1整数规划指派问题应用,2020/4/26,3,3,求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。在整数规划中:如果所有的变量都为非负整数，则称为纯整数规划问题；如果只有一部分变量为非负整数，则称之为混合整数规划问题。如果所有的变量都为0-1变量，则称之为0-1规划。,2020/4/26,4,4,例5.1某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大?,第一节整数规划的数学模型,2020/4/26,5,5,解：设x1、x2分别为甲、乙两种货物托运的件数，建立模型Maxz=2x1+3x2s.t.195x1+273x213654x1+40 x2140 x14x1，x20为整数。如果去掉最后一个约束，就是一个线性规划问题。,2020/4/26,6,6,得到线性规划的最优解为x1=2.44,x2=3.26,目标函数值为14.66。由图表可看出，整数规划的最优解为x1=4,x2=2,目标函数值为14。,2020/4/26,7,7,性质：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。,2020/4/26,8,13/4,5/2,松弛问题,第二节割平面法,2020/4/26,9,设纯整数规划,伴随LP的最优解,若全为整数，则为IP的最优解。否则，,若不全为整数，设第r行基变量非整。对应方程为,2020/4/26,10,将分离成一个整数与一个非负真分数之和：,则有,等式两边都为整数并且有,2020/4/26,11,加入松弛变量,此式称为以r行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。,将Gomory约束加入到松弛问题(伴随LP)的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。,则,2020/4/26,12,割平面法，即通过添加约束条件，逐步切割可行区域的边角余料，让其整数解逐步的露到边界或顶点上来，只要整数解能曝露到顶点上来，则就可以利用单纯形法求出来。关键是通过添加什么样的约束条件，既能让整数解往边界露，同时又不要切去整数解，这个条件就是Gomory约束条件。Gomory约束只是割去线性规划可行域的一部分，保留了全部整数解。,2020/4/26,13,例5-5,2020/4/26,运筹学-线性规划-线性规划-线性规划,14,选择较大小数的行构造割平面,2020/4/26,运筹学-线性规划-线性规划-线性规划,15,2020/4/26,运筹学-线性规划-线性规划-线性规划,16,2020/4/26,17,分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。先求解整数规划的线性规划问题(伴随LP)。如果其最优解不符合整数条件，则求出整数规划的上下界。增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝）再求解这些子区域上的线性规划问题。不断缩小整数规划上下界的距离，最后得整数规划的最优解。,第三节分枝定界法,2020/4/26,18,18,用分枝定界法求解目标函数值最大的整数规划的步骤，我们将求解的整数规划问题称为A，将与其相对应的线性规划问题称为B：第一步：求解问题B，可得以下情况之一：1.B没有可行解，则A也没有可行解，求解过程停止。2.B有最优解，且符合问题A的整数条件，则B的最优解即为A的最优解，求解过程停止。3.B有最优解，但不符合A的整数条件，记其目标函数值为z1。第二步：确定A的最优目标函数值z*的上下界，其上界即为,再用观察法找到A的一个整数可行解，求其目标函数值作为z*的下界，记为z。第三步：判断是否等于z。若相等，则整数规划最优解即为其目标函数值等于z的A的那个整数可行解；否则进行第四步。,2020/4/26,19,第四步：在B的最优解中任选一个（或最远离整数要求的变量），不妨设此变量为xj，以bj表示小于bj的最大整数，构造以下两个约束条件，并加入问题B，得到B的两个分枝B1和B2。xjbj和xjbj+1第五步：求解B1和B2。修改A问题的最优目标函数值z*的上下界，和z。第六步：比较和剪枝。各分枝的最优目标函数值中若有小于z者，则剪掉这枝（用打表示），即以后不再考虑了。若大于，则不符合整数条件，则重复第三步至第六步，直至=z，求出最优解为止。对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。,2020/4/26,运筹学-线性规划-线性规划-线性规划,20,例5-6,2020/4/26,运筹学-线性规划-线性规划-线性规划,21,例5.1,Max2x1+3x2s.t.195x1+273x213654x1+40 x2140 x14x1,x20且x1,x2为整数,2020/4/26,22,2020/4/26,23,0-1规划的分支定界法0-1规划的适用背景双态变量的归一化（变量）不相容约束的归一化（约束条件）分段线性函数的归一化（目标函数）,第四节0-1规划,24,双态变量的归一化,25,（1）多个不全相容约束的归一化,不全相容约束的归一化,2020/4/26,26,27,（2）约束常数项多个互斥取值的归一化,28,2020/4/26,29,30,（3）多组约束的归一化,2020/4/26,31,31,（1）固定费用的问题例5.2高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。,分段线性函数的归一化（目标函数）,2020/4/26,32,32,解：这是一个整数规划的问题。设x1，x2，x3分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设yi=1(当生产第i种容器,即xi0时)或0（当不生产第i种容器即xi=0时）。引入约束xiMyi，i=1，2，3，M充分大，以保证yi=0 xi=0这样我们可建立如下的数学模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x35002x1+3x2+4x3300 x1+2x2+3x3100 xiMyi，i=1，2，3，M充分大xj0yj为0-1变量，i=1,2,3,33,（2）变动费用的问题,例5.3,2020/4/26,34,0-1规划的解法,隐枚举法:,2020/4/26,35,求解思路:,2020/4/26,36,2020/4/26,37,37,有n项不同的任务，恰好n个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把n项任务指派给n个人，使得完成n项任务的总的效率最高，这就是指派问题。例5.4有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。,第五节指派问题,2020/4/26,38,38,解：引入01变量xij，并令xij=1(当指派第i人去完成第j项工作时)或0（当不指派第i人去完成第j项工作时)这可以表示为一个0-1整数规划问题：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(甲只能干一项工作)x21+x22+x23+x24=1(乙只能干一项工作)x31+x32+x33+x34=1(丙只能干一项工作)x41+x42+x43+x44=1(丁只能干一项工作)x11+x21+x31+x41=1(A工作只能一人干)x12+x22+x32+x42=1(B工作只能一人干)x13+x23+x33+x43=1(C工作只能一人干)x14+x24+x34+x44=1(D工作只能一人干)xij为0-1变量，i,j=1,2,3,4,2020/4/26,运筹学-线性规划-线性规划-线性规划,39,定理6-1,指派问题的匈牙利算法,如果从指派问题效率矩阵的每一行元素中分别减去（或加上）一个常数（称为该行的位势），从每一列分别减去（或加上）一个常数（称为该列的位势），得到一个新的效率矩阵，其中，则的最优解等价于的最优解，这里及均非负。,41,定理6-2若矩阵A的元素可分成“0”与非“0”两部分，则覆盖零元素的最少直线数等于位于不同行不同列的零元素（称为独立元素）的最大个数。,效率矩阵,在效率矩阵中找出4个不同行不同列的数使得它们的总和最小。,效率矩阵的变形,找出4个不同行不同列的0元使得它们的和为最小0，,令这些零元素对应的其余变量=0，得到最优解。,一.算法的基本思想：,43,基本步骤初始变换-0元获得最优性检验非优阵0元的最小直线集合非优阵变换0元移动,标准化：min；cij为方阵；cij为非负常数。,44,2020/4/26,45,其他变异的指派问题,求最大值;人数与任务数不相等;某个人不能完成某项任务;,2020/4/26,46,效率矩阵,(1)求最大值;,如果指派问题求最大值，用一个较大的数M去减效率矩阵中所有元素得到效率矩阵求矩阵B的最小值，矩阵B与矩阵C的最优解相同。通常令这个较大的数等于效率矩阵中的最大元素。,2020/4/26,47,2020/4/26,48,当某人不能完成某项任务时，令对应的效率为一个大M即可。,(3)某个人不能完成某项任务;,49,2020/4/26,50,第六节其它应用,投资问题选址问题人力资源分配问题工件排序问题,51,例5.61亿资金投资建厂，6个地址选择其中，地址1、2互斥，地址3、4互斥；地址1或2是地址3、4的前提条件。该公司应如何选址？,1.投资问题,52,解：设xi为,2020/4/26,53,53,例5.7某公司在今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限；项目B：第三年初需要投资，到第五年末能回收本利128，但规定最低投资金额为3万元，最高金额为5万元；项目C：第二年初需要投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。项目D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?,2020/4/26,54,54,解：1)设xiA、xiB、xiC、xiD(i1，2，3，4，5)分别表示第i年年初给项目A，B，C，D的投资额(元)；设yiA，yiB，是01变量，并规定取1时分别表示第i年给A、B投资，否则取0（i=1,3）。设yiC是非负整数变量，并规定：第2年投资C项目8万元时，取值为4；第2年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2；第2年投资C项目2万元时，取值1；第2年不投资C项目时，取值0；这样我们建立如下的决策变量：第1年第2年第3年第4年第5年Ax1Ax2Ax3Ax4ABx3BCx2C=20000y2CDx1Dx2Dx3Dx4Dx5D,2020/4/26,55,55,2）约束条件：第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是x1A+x1D=100000；第二年：A的投资第二年末才可收回，故第二年年初的资金为1.06x1D，于是x2A+x2C+x2D=1.06x1D；第三年：年初的资金为1.15x1A+1.06x2D，于是x3A+x3B+x3D=1.15x1A+1.06x2D；第四年：年初的资金为1.15x2A+1.06x3D，于是x4A+x4D=1.15x2A+1.06x3D；第五年：年初的资金为1.15x3A+1.06x4D，于是x5D=1.15x3A+1.06x4D。关于项目A的投资额规定:x1A40000y1A，x1A200000y1A，200000是足够大的数；保证当y1A=0时，x1A=0；当y1A=1时，x1A40000。关于项目B的投资额规定:x3B30000y3B，x3B50000y3B；保证当y3B=0时，x3B=0；当y3B=1时，50000x3B30000。关于项目C的投资额规定:x2C=20000y2C，y2C=0，1，2，3，4。,2020/4/26,56,56,3）目标函数及模型：Maxz=1.15x4A+1.40 x2C+1.28x3B+1.06x5Ds.t.x1A