运筹学-整数规划(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,南京邮电大学经济与管理学院,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,南京邮电大学经济与管理学院,*,运筹学,运 筹 帷 幄 之 中,决 胜 千 里 之 外,整数规划,Integer Programming,第四章,2,9/5/2025,第四章 整数规划,本章主要内容：,整数,问题规划及其,数学模型,整数规划问题的求解,0-1,型整数规划问题,指派问题,3,9/5/2025,第四章 整数规划,在很多场合，我们建立最优化模型时，实际问题要求决策变量只能取整数值而非连续取值。此时，这类最优化模型就称为整数规划（离散最优化）模型。,整数规划的求解往往比线性规划求解困难得多，而且，一般来说不能简单地将相应的线性规划的解取整来获得。,4,9/5/2025,第四章 整数规划,线性规划模型：,实际问题要求,x,i,为整数！,如机器的台数，人数等,5,9/5/2025,第四章 整数规划,例,:,胜利家具厂生产桌子和椅子两种家具。桌子售价,50,元,/,个，椅子售价,30,元,/,个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工,4,个小时，油漆工,2,小时。生产一个椅子需要木工,3,个小时，油漆工,1,小时。该厂每月可用木工工时为,120,小时，油漆工工时为,50,小时。问该厂如何组织生产才能使每月的销售收入最大？,6,9/5/2025,第四章 整数规划,纯整数规划,7,9/5/2025,第四章 整数规划,例（背包问题）一个旅行者，为了准备旅行的必备物品，要在背包里装一些有用的东西，但他最多只能携带,b,公斤的东西，而每件物品都只能整件携带，于是他给每件物品规定了一个“价值”，以表示其有用程度。如果共有,m,件物品，第,i,件件物品的重量为,b,i,，价值为,c,i,，问题就变成：在携带的物品总重量不超过,b,公斤的条件下，携带哪些物品可使总价值最大,?,8,9/5/2025,第四章 整数规划,9,解：,Z,表示所带物品的总价值,携带物品的总重量,数学模型：,0-1,规划,9/5/2025,第四章 整数规划,10,9/5/2025,第四章 整数规划,解：,数学模型：,混合型整数规划,11,9/5/2025,第四章 整数规划,例,工厂,A,1,和,A,2,生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有,A,3,和,A,4,两个。这种物资的需求地有,B,1,B,2,B,3,B,4,四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费,c,ij,，见下表：,B,1,B,2,B,3,B,4,年生产能力,A,1,2,9,3,4,400,A,2,8,3,5,7,600,A,3,7,6,1,2,200,A,4,4,5,2,5,200,年需求量,350,400,300,150,工厂,A,3,或,A,4,开工后，每年的生产费用估计分别为,1200,万或,1500,万元。现要决定应该建设工厂,A,3,还是,A,4,，才能使今后每年的总费用最少。,12,9/5/2025,第四章 整数规划,解：这是一个物资运输问题，特点是事先不能确定应该建,A,3,还是,A,4,中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入,0-1,变量：,再设,x,ij,为由,A,i,运往,B,j,的物资数量，单位为千吨；,z,表示总费用，单位万元。,则该规划问题的数学模型可以表示为：,13,9/5/2025,第四章 整数规划,混合整数规划问题,14,9/5/2025,第四章 整数规划,整数线性规划问题的种类：,纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。,混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。,0-1,型整数线性规划：决策变量只能取值,0,或,1,的整数线性规划。,15,9/5/2025,第四章 整数规划,纯整数规划的数学模型,：,0-1,规划的数学模型,：,16,9/5/2025,第四章 整数规划,例,Z=130,，可行且,Z=140,不可行,可行,17,9/5/2025,第四章 整数规划,（,IP,）,（,IP,）问题的松弛问题,18,9/5/2025,第四章 整数规划,松弛问题的最优值是原整数规划,的目标函数值的上界,19,9/5/2025,第四章 整数规划,例,设整数规划问题如下,首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。,20,9/5/2025,第四章 整数规划,用图解法求出最优解为：,x,1,3/2,x,2,=10/3,，且有,Z=29/6,现求整数解,(,最优解,):,如用舍入取整法可得到,4,个点即,(1,，,3),(2,，,3),(1,，,4),(2,，,4),。显然，它们都不可能是整数规划的最优解。,x,1,x,2,3,3,(3/2,10/3),按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如右图所示。,其中,(2,2),(3,1),点的目标函数值最大，即为,Z=4,。,21,9/5/2025,第四章 整数规划,-,分支定界法,1,）求整数规划的松弛问题最优解；,若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下一步；,2,）分支与定界：,任意选一个非整数解的变量,x,i,，在松弛问题中加上约束：,x,i,x,i,和,x,i,x,i,+1,组成两个新的松弛问题，称为,分枝,。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的,上界,；当原问题是求最小值时，目标值是分枝问题的,下界,。,检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（,max,）等于其它分枝的目标值，则将其它,分枝剪去,不再计算，若还存在非整数解并且目标值大于,(max),整数解的目标值，需要继续分枝，再检查，直到得到最优解。,分支定界法的解题步骤：,22,9/5/2025,上界,x,1,x*,01,x,1,x*,01,+1,23,9/5/2025,当所有的子问题均被关闭或剪枝后,目标函数值最大的整数解既为所求的最优解,24,9/5/2025,一、分枝定界法的原理,：,1,、分枝,0 1 2 3 4 5 6 7 8,松弛问题的可行域,增加,x,1,3,增加,x,1,4,L,1,L,2,25,x,1,3,x,1,4,父问题,子问题,结论,1,：（,IP,）的最优解一定在某个子问题中,父问题的最优值,3,：子问题中的整数解都是（,IP,）的可行解,子问题的最优解,2,：子问题的可行域,父问题的可行域,26,2,、定界,1,、（,LP,）的最优值是,(IP),的最优值的上界,27,IP,松弛问题,L,0,L,1,L,2,通过对（,L,0,）分枝，使（,IP,）的最优值,的上界不断下降，,L,3,L,4,L,5,L,6,下界不断上升，,上界,=,下界,得最优值,28,0 1 2 3 4 5 6 7 8,x,1,3,x,1,4,z=30 x,1,+20 x,2,4x,1,+x,2,=16.5,2x,1,+3x,2,=14.5,x,2,2,x,2,3,x,1,2,x,1,3,29,混合型,x,1,3,x,1,4,L,0,的最,优单纯型表：,x,1,x,2,x,3,x,4,常数项,检,0,0,-5,-5,Z-155,x,2,0,1,2/5,-1/5,5/2,x,1,1,0,-1/10,3/10,7/2,x,5,x,5,1 0 0 0 1 3,0,0,0,30,x,1,3,x,1,4,x,1,2,x,1,3,x,2,2,x,2,3,31,x,1,x,2,x,3,x,4,解,检,0,0,-5,-5,Z-155,x,2,0,1,2/5,-1/5,5/2,x,1,1,0,-1/10,3/10,7/2,x,5,x,5,1 0 0 0 1 3,0,0,0,x,1,x,2,x,3,x,4,解,检,0,0,-5,-5,Z-155,x,2,0,1,2/5,-1/5,5/2,x,1,1,0,-1/10,3/10,7/2,x,5,x,5,0 0 1/10-3/10 1 -1/2,0,0,0,x,1,x,2,x,3,x,4,解,检,0,0,-20/3,0 -50/3,Z-440/3,x,2,0,1,1/3,0 -2/3,17/6,x,1,1,0,0,0 1,3,0,0,-1/3,1,-10/3 5/3,x,4,x,5,32,x,2,2,x,2,+x,6,=2,x,1,x,2,x,3,x,4,x,5,解,检,0,0,-20/3,0,-50/3,Z-440/3,x,2,0,1,1/3,0,-2/3,17/6,x,1,1,0,0,0,1,3,x,4,0,0,-1/3,1,-10/3,5/3,x,6,0 1 0 0 0 1 2,x,6,0,0,0,0,x,1,x,2,x,3,x,4,x,5,x,6,解,检,0,0,-20/3,0,-50/3,0,Z-440/3,x,2,0,1,1/3,0,-2/3,0,17/6,x,1,1,0,0,0,1,0,3,x,4,0,0,-1/3,1,-10/3,0,5/3,x,6,0,0,-1/3,0,2/3,1,-5/6,x,1,x,2,x,3,x,4,x,5,x,6,解,检,0,0,0,0,-30,-20,Z-130,x,2,0,1,0,0,0,1,2,x,1,1,0,0,0,1,0,3,x,4,0,0,0,1,-4,-1,5/2,x,3,0,0,1,0,-2,-3,5/2,33,x,2,3,X,2,-x,6,=3,x,1,x,2,x,3,x,4,x,5,解,检,0,0,-20/3,0,-50/3,Z-440/3,x,2,0,1,1/3,0,-2/3,17/6,x,1,1,0,0,0,1,3,x,4,0,0,-1/3,1,-10/3,5/3,x,6,0 -1 0 0 0 1 -3,x,6,0,0,0,0,x,1,x,2,x,3,x,4,x,5,x,6,解,检,0,0,-20/3,0,-50/3,0,Z-440/3,x,2,0,1,1/3,0,-2/3,0,17/6,x,1,1,0,0,0,1,0,3,x,4,0,0,-1/3,1,-10/3,0,5/3,x,6,0,0,1/3,0,-2/3,1,-1/6,-X,2,+x,6,=-3,x,1,x,2,x,3,x,4,x,5,x,6,解,检,0,0,-15,0,0,-25,Z-285/2,x,2,0,1,0,0,0,-1,3,x,1,1,0,1/2,0,0,3/2,11/4,x,4,0,0,-2,1,0,-5,5/2,x,5,0,0,-1/2,0,1,-3/2,1/4,34,x,1,x,2,x,3,x,4,x,5,x,6,解,检,0,0,-15,0,0,-25,Z-285/2,x,2,0,1,0,0,0,-1,3,x,1,1,0,1/2,0,0,3/2,11/4,x,4,0,0,-2,1,0,-5,5/2,x,5,0,0,-1/2,0,1,-3/2,1/4,x,1,2,x,1,+x,7,=2,X,7,0,0,0,0,0,x,7,1,0,0,0,0,0,1,2,x,1,x,2,x,3,x,4,x,5,x,6,x,7,解,检,0,0,-20/3,0,0,0,-50/3,Z-130,x,2,0,1,1/3,0,0,0,-2/3,7/2,x,1,1,0,0,0,0,0,1,2,x,4,0,0,-1/3,1,0,0,-10/3,5,x,5,0,0,0,0,1,0,-1,1,x,6,0,0,1/3,0,0,1,-2/3,1/2,0 0 -1/2 0 0 -3/2 1 -3/4,35,如何选择分枝的节点及分枝变量？,1,、分枝节点选择的原则：尽快找到好的整数解，减少搜索节点，,提高搜索效率。,方法：,（,1,）深探法：,（,2,）广探法：,最后打开的节点最先选择,选择有最大目标函数值的节点继续向下分枝,2,、分枝变量选择的原则：,寻找那些对问题影响最大的变量首先分枝,（,1,）按目标函数系数选择：,选择目标函数系数绝对值最大的变量首先分枝,（,2,）按非整数变量选择：,选择与整数值相差最大的非整数变量进行分枝,（,3,）按人为给定的顺序选择,36,x,1,3,x,1,4,x,2,2,x,2,3,x,1,2,x,1,3,37,第四章 整数规划,-,割平面法,割平面法的基本思想：,若整数规划,IP,的松弛规划,L,0,的最优解不是整数解，对,L,0,增加一个约束条件，得线性规划,L,1,，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划,IP,的解均在,L,1,中，若,L,1,的最优解为整数解，则得,IP,的最优解。若,L,1,的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留,IP,所有的整数解，总可以在有限次后得到,IP,的最优解,.,38,9/5/2025,割平面,39,南京邮电大学经济与管理学院,问题,：如何寻找割平面？,增加的约束方程须满足什么条件才能使：,1,、割掉松弛规划的最优解,2,、保留所有的整数解,40,南京邮电大学经济与管理学院,二、,割平面法,41,南京邮电大学经济与管理学院,L,0,的最优单纯形表：,x,1,x,i,x,m,x,m+1,x,m+j,x,n,解,检,0,0,0,1,m+j,n,z-z,0,x,1,1,0,0,a,1m+1,a,1m+j,a,1n,b,10,x,i,0,1,0,a,im+1,a,im+j,a,in,b,i0,x,m,0,0,1,a,mm+1,a,mm+j,a,mn,b,m0,源方程,42,南京邮电大学经济与管理学院,-,对应于生成行,i,的割平面,43,南京邮电大学经济与管理学院,L,0,的最优单纯形表：,x,1,x,i,x,m,x,m+1,x,m+j,x,n,解,检,0,0,0,1,m+j,n,z-z,0,x,1,1,0,0,a,1m+1,a,1m+j,a,1n,b,10,x,i,0,1,0,a,im+1,a,im+j,a,in,b,i0,x,m,0,0,1,a,mm+1,a,mm+j,a,mn,b,m0,生成行,对应于生成行,i,的割平面,非基变量,44,南京邮电大学经济与管理学院,b,0 1 0.5 0 0 -,0.5,1,0 0,-1.75,1 0,3.25 5.5,0 0 -1 0 1 1 3,1 0,-0.25,0 0,0.75,1.5,0 0,-0.5,0 0 -,1.5,z-9,对应第,2,行的割平面：,对应第,4,行的割平面：,45,南京邮电大学经济与管理学院,非基变量,46,南京邮电大学经济与管理学院,如何求解？,47,南京邮电大学经济与管理学院,x,1,x,i,x,m,x,m+1,x,m+j,x,n,解,检,0,0,0,c,1,c,m+j,c,n,z-z,0,x,1,1,0,0,a,1m+1,a,1m+j,a,1n,b,10,x,i,0,1,0,a,im+1,a,im+j,a,in,b,i0,x,m,0,0,1,a,mm+1,a,mm+j,a,mn,b,m0,s,s,0 0 0 -f,im+1,-f,im+j,-f,in,1 f,i0,0,0,0,0,对偶单纯形法,48,南京邮电大学经济与管理学院,割平面计算步骤,第一步：,用单纯形法解整数问题,IP,的松弛问题,L,0,若,L,0,没有最优解，则,IP,没有最优解。停止,若,L,0,有最优解,X,0:,(1)X,0,是整数解，,则,X,0,也是,IP,的最优解，停止,(2)X,0,不是整数解，,转第二步,第二步：,求割平面方程,49,南京邮电大学经济与管理学院,第三步：,将割平面加到,L,0,得,L,1,第四步：,解,L,1,在,L,0,的最优单纯形表中增加一行一列，,得,L,1,的单纯形表，,用对偶单纯形法求解，,若其解是整数解，则该解也是原整数规,划的最优解,否则将该解记为,X,0,，返回第二步,50,南京邮电大学经济与管理学院,例 用割平面法求解,IP,解：,IP,问题的松弛规划的,标准型：,X,1,X,2,X,3,X,4,0 0 -2.25 -1.75,Z-37.5,X,2,0 1 0.25 -0.25,1.5,X,1,1 0 0.125 0.375,3.75,X,5,0,0,0,X,5,0 0 -0.125 -0.375 1 -0.75,X,1,X,2,X,3,X,4,X,5,Z,X,2,X,1,X,4,0 0 0.333 1 -2.667,2,1 0 0 0 1 3,0 1 0.333 0 -0.667 2,0 0 -1.667 0 -4.667 z-34,整数,最优值：,Z=34,51,南京邮电大学经济与管理学院,例：用割平面法求解,解：,IP,的松弛规划的标准型,X,1,X,2,X,3,X,4,0 0 -28/11 -15/11,Z-63,X,2,0 1 7/22 1/22,7/2,X,1,1 0 -1/22 3/22,9/2,X,5,0 0 -7/22 -1/22 1 -1/2,X,5,0,0,0,X,1,X,2,X,3,X,4,X,5,X,2,X,1,X,3,0 0 1 1/7 -22/7,11/7,1 0 0 1/7 -1/7 32/7,0 1 0 0 1 3,0 0 0 -1 -8 Z-59,非整数,52,南京邮电大学经济与管理学院,X,1,X,2,X,3,X,4,X,5,X,2,X,1,X,3,0 0 1 1/7 -22/7,11/7,1 0 0 1/7 -1/7 32/7,0 1 0 0 1 3,0 0 0 -1 -8 Z-59,X,6,0 0 0 -1/7 -6/7 1 -4/7,X,6,0,0,0,0,X,1,X,2,X,3,X,4,X,5,X,6,0 0 0 0 -2 -7,Z-55,X,2,0 1 0 0 1 1,3,X,1,1 0 0 0 -1 1,4,X,3,0 0 1 0 -4 1,1,X,4,0 0 0 1 6 -7,4,整数,最优值：,Z=55,53,南京邮电大学经济与管理学院,作业：,分别用分枝定界法和割平面法求解整数规划：,最优值为：,Z=4,54,南京邮电大学经济与管理学院,第四章 整数规划,-,0-1,整数规划,01,型整数规划是整数规划中的特殊情形，它的变量,x,i,仅取值,0,或,1,。这时,x,i,称为,01,变量，或称二进制变量。,x,i,仅取值,0,或,1,这个条件可由下述约束条件：,x,i,1,x,i,0,，整数,所代替，和一般整数规划的约束条件形式一致的。,55,9/5/2025,第四章 整数规划,-,0-1,整数规划,投资场所的选择,相互排斥的计划,例：某公司拟在市东、西、南三区建立门市部。拟议中有,7,个位置（点）,A,i,（,i,=1,，,2,，,，,7,）可供选择。规定,在东区，由,A,1,，,A,2,，,A,3,三个点中至多选两个；,在西区，由,A,4,，,A,5,两个点中至少选一个；,在南区，由,A,6,，,A,7,两个点中至少选一个。,如选用,A,i,点，设备投资估计为,b,i,元，每年可获利润估计为,C,i,元，但投资总额不能超过,B,元。问应选择哪几个点可使年利润为最大？,56,9/5/2025,第四章 整数规划,-,0-1,整数规划,令,x,i,=1,，,2,，,，,7,（三点中最多选两点）,（两点中至少选一点）,（两点中至少选一点）,决策变量：投资项目,A,i OR,not,投资项目,A,i,利润,57,9/5/2025,第四章 整数规划,-,0-1,整数规划,（,1,）,两个约束中，只有一个起作用。,例：,a,11,x,1,+a,12,x,2,B,1,a,21,x,1,+a,22,x,2,B,2,例,含有相互排斥的约束条件的问题,解：引入,0-1,变量,Y,1,Y,2,和足够大的正数,M,，则,a,11,x,1,+a,12,x,2,B,1,+M,1,Y,1,a,21,x,1,+a,22,x,2,0,（,3,）若,a,个约束条件中只能有,b,个起作用。,则令,0,1,变量之和为,a-b,。,注意：可用统一,M,，但,M,的取值必须足够的大。,59,9/5/2025,第四章 整数规划,-,0-1,整数规划,1,问题的提出,:,已知：两种货物装箱,每种货物装箱利润,体积限制,重量限制,决策变量,:,两种货物各多少箱,Max Z=,利润最大？,箱数不能为分数,货物,X,1,货物,X,2,限量,体积,5,4,24,重量,2,5,13,利润,20,10,相互排斥的约束条件,60,9/5/2025,第四章 整数规划,-,0-1,整数规划,互相排斥的约束条件（假设有车、船,2,种运输方式）,用车运的体积约束,用船运的体积约束,61,9/5/2025,第四章 整数规划,-,0-1,整数规划,固定费用的问题,在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决。,62,9/5/2025,第四章 整数规划,-,0-1,整数规划,例,固定费用问题,解：设,X,j,是第,j,种产品的产量。,Y,j,是,0,1,变量，表示是（,Y,j,=1,）否（,Y,j,=0,）生产第,j,种产品。,单耗量 产品,资源,I,II,III,资源量,A,2,4,8,500,B,2,3,4,300,C,1,2,3,100,单件可变费用,4,5,6,固定费用,100,150,200,单件售价,8,10,12,63,9/5/2025,第四章 整数规划,-,0-1,整数规划,maxZ=4X,1,+5X,2,+6X,3,100Y,1,150Y,2,200Y,3,2X,1,+4X,2,+8X,3,500,2X,1,+3X,2,+4X,3,300,X,1,+2X,2,+3X,3,100,X,1,M,1,Y,1,X,2,M,2,Y,2,X,3,M,3,Y,3,X,1,X,2,X,3,0,整数,Y,1,Y,2,Y,3,为,0,1,变量，,M,1,M,2,M,3,为任意大正数。,s.t.,64,9/5/2025,第四章 整数规划,-,隐枚举法,在整数规划模型中，若变量取值为,0,或,1,两个特殊的数值，则称此类模型为,01,的使用及建立模型的方法。,隐枚举法基本思想：隐枚举法是分枝定界法思想的延伸。通过放松主约束条件（而非变量符号限制条件）求得最优解，再检查是否满足约束条件，再经过分枝与剪枝等工作迭代出最优解。,65,9/5/2025,第四章 整数规划,-,隐枚举法,在,2,n,个可能的变量组合中，往往只有一部分是可行解。,只要发现某个变量组合不满足其中一个约束条件时，就不必 再去检验其他约束条件是否可行。,对于可行解，其目标函数值也有优劣之分。若已发现一个可行解，则根据它的目标函数值可以产生一个过滤条件，对于目标函数值比它差的变量组合不必再去检验它的可行性。,在以后的求解过程中，每当发现比原来更好的可行解，则替换原来的过滤条件。,66,9/5/2025,第四章 整数规划,-,隐枚举法,0-1,规划求解,Max Z=3X,1,2X,2,5X,3,X,1,+2X,2,X,3,=2,（,1,）,X,1,+4X,2,+X,3,=4,（,2,）,X,1,+X,2,=3,（,3,）,4X,2,+X,3,=3,3X,1,2X,2,5X,3,=3,（*）称为,过滤条件,（,Filtering Constraint,）,67,9/5/2025,第四章 整数规划,-,隐枚举法,逐一检查,如下点是否满足约束条件？,约束条件（左边）,满足约束条件,?,Z,值,约束（*）,左,约束（,1,）,左,约束（,2,）,左,约束（,3,）,左,约束（,4,）,左,（,0,，,0,，,0,）,0,不,（,0,，,0,，,1,）,5,1,1,0,1,是,5,（,0,，,1,，,0,）,-2,不,（,1,，,0,，,0,）,3,1,1,1,0,是,（,0,，,1,，,1,）,3,1,不,（,1,，,0,，,1,）,8,0,2,1,1,是,8,（,1,，,1,，,0,）,1,不,（,1,，,1,，,1,）,6,2,不,于是最优解,（,X,1,X,2,X,3,）（,1,，,0,，,1,）,Max Z=8,3X,1,2X,2,5X,3,=3,（*）称为,过滤条件,（,Filtering Constraint,）,68,9/5/2025,第四章 整数规划,-,隐枚举法,Max Z=,2X,2,3X,1,5X,3,目标函数按系数递增（,2,，,3,，,5,）,约束条件也按上面决定的顺序,2X,2,3X,1,5X,3,=3,（*）,2X,2,X,1,X,3,=2,（,1,）,4X,2,+,X,1,X,3,=4,（,2,）,X,2,X,1,=3,（,3,）,4X,2,+,X,3,=6,（,4,）,X,1,X,2,X,3,=0,或者,1,（,5,）,解：变量（,X1,X2,X3,）按下面顺序容易更早发现最优解：,（,0,，,0,，,0,）（,0,，,0,，,1,）（,0,，,1,，,0,）（,0,，,1,，,1,）,.,69,9/5/2025,逐一检查,如下点是否满足约束条件？,约束条件（左边）,满足条件,?,Z,值,（*）,左,（,1,）,左,（,2,）,左,（,3,）,左,（,4,）,左,（,0,，,0,，,0,）,0,3,1,1,0,1,是,5,改进过滤条件，用：,3X,1,2X,2,5X,3,=5,（*）为,过滤条件,逐一检查,如下点是否满足约束条件？,约束条件（左边）,满足条件,?,Z,值,（*）,左,（,1,）,左,（,2,）,左,（,3,）,左,（,4,）,左,（,0,，,1,，,0,）,3,不,（,0,，,1,，,1,）,8,0,2,1,1,是,8,这里已经更换了,x1,x2,的位置,(x2,x1,x3),70,9/5/2025,再改进过滤条件，用：,3X,1,2X,2,5X,3,=8,（*）为,过滤条件,逐一检查如下点是否满足约束条件？,约束条件（左边）,满足条件,?,Z,值,（*）,左,（,1,）,左,（,2,）,左,（,3,）,左,（,4,）,左,（,1,，,0,，,0,）,-2 8,不,（,1,，,0,，,1,）,3 8,不,（,1,，,1,，,0,）,1 8,不,（,1,，,1,，,1,）,6 =3,（*）,2X,2,X,1,X,3,=2,（,1,）,4X,2,+,X,1,X,3,=4,（,2,）,X,2,X,1,=3,（,3,）,4X,2,+,X,3,=6,（,4,）,X,1,X,2,X,3=,0,或者,1,（,5,）,解：变量（,X,1,X,2,X,3,）按下面顺序容易更早发现最优解：,（,1,，,0,，,1,）,对应,目标函数系数（,3,，,-2,，,5,）负系数的,X,i,取,0,，正系数的,X,i,取,1,这时目标函数达到最大值，但不一定满足约束条件；,如果满足约束条件，则不必检验其他解，一步直达。,这里已经更换了,x1,x2,的位置,72,9/5/2025,第四章 整数规划,-,隐枚举法,在解决,0-1,规划问题时，为了进一步减少运算量，常按目标函数中各变量系数的大小顺序重新排列各变量，以使最优解有可能较早出现。,对于最大化问题，可按目标函数中各变量系数由小到大的顺序排列。,对于最小化问题，可按目标函数中各变量系数由大到小的顺序排列。,73,9/5/2025,第四章 整数规划,-,隐枚举法,求解,01,整数规划,max f(x)=3x,1,-2x,2,+5x,3,s.t.x,1,+2x,2,-x,3,2,x,1,+4x,2,+x,3,4,x,1,+x,2,3,4x,2,+x,3,6,x,1,x,2,x,3,=,0,或,1,74,9/5/2025,第四章 整数规划,-,隐枚举法,求解,0-1,整数规划,min f(x)=3x,1,+7x,2,-x,3,+x,4,s.t.2x,1,-x,2,+,x,3,-,x,4,1,x,1,-x,2,+6x,3,+,4x,4,8,5x,1,+3x,2,+,x,4,5,x,1,x,2,x,3,x,4,=,0,或,1,75,9/5/2025,设有,n,个工作，要由,n,个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。,c,ij,表示第,i,个人做第,j,件事的费用,求总费用最低的指派方案。,费用,1 2 j n,1,2,i,n,指派问题模型：,i=1,2,n,j=1,2,n,第,i,个人做第,j,件事,Z,表示总费用,i=1,2,n;j=1,2,n,第,i,个人不做第,j,件事,1,、指派问题的,数学模型,76,i=1,2,n,j=1,2,n,当,n=4,时，,有,16,变量，,8,个约束方程,77,例：现有,4,份工作，,4,个人应聘，由于各人技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一人承担，试求使总费用最小的分派方案。,工作,人,费用,1 2 3 4,1,2,3,4,3 5 4 5,6 7 6 8,8 9 8 10,10 10 9 11,1,0,第,i,人做第,j,件事,Z,表示总费用,i=1,2,3,4;j=1,2,3,4,第,i,人不做第,j,件事,78,2,、费用矩阵,设有,n,个工作，要由,n,个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。,c,ij,表示第,i,个人做第,j,件事的费用,求总费用最低的指派方案。,费用,1 2 j n,1,2,i,n,c,ij,表示第,i,个人做第,j,件事的费用,费用矩阵,79,例：现有,4,份工作，,4,个人应聘，由于个人的技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总费用最小的分派方案。,工作,人,收费用,1 2 3 4,1,2,3,4,3 5 4 5,6 7 6 8,8 9 8 10,10 10 9 11,费用矩阵,对应一个,5,个人,5,个工作的指派问题,第,2,个人做第,4,个工作的费用,5,第,4,个人做第,2,个工作的费用,0,80,定理：在费用矩阵,C=,（,c,ij,）的任一行（列）中,减去一个常数或加上一个常数不改变本,问题的最优解。,n,个人,n,个工作的指派问题,1,-b,3,、,匈牙利法,n,个人,n,个工作的指派问题,2,81,i=1,2,n,j=1,2,n,i=1,2,n,j=1,2,n,-b,82,83,-b,i=1,2,n,j=1,2,n,i=1,2,n,j=1,2,n,84,任务,：,对,C,的行和列减去某个常数，,将,C,化的尽可能简单，,简单到可一眼看出该问题的最优解,-b,85,南京邮电大学经济与管理学院,指派问题的最优解：,若,C,中有,n,个位于不同行不同列的零元素，,则令这些零元素对应的变量取,1,，其余变量,取零，既得指派问题的最优解,i=1,2,3,4,j=1,2,3,4,可行解,最优解,86,匈牙利法的基本思路：,对费用矩阵,C,的行和列减去某个常数，将,C,化成,有,n,个位于不同行不同列的零元素，令这些零元素对应的变量取,1,，其余变量取零，即得指派问题的最优解,87,例：有一份说明书要分别译成英、日、德、俄四种文字，现交给甲、乙丙、丁四个人去完成，每人完成一种。由于个人的专长不同，翻译成不同文字所需的时间（小时数）如右表，问应派哪个人去完成哪个任务，可使总花费时间最少？,工作,人,时间,英 日 德 俄,甲,乙,丙,丁,2 15 13 4,10 4 14 15,9 14 16 13,7 8 11 9,-2,-4,-9,-7,最优方案：,甲翻译俄文,，乙翻译日文,丙翻译英文,，丁翻译德文,总费用：,28,小时,-4,-2,88,-2,-4,-9,-7,-4,-2,最优解的取法：,从含,0,元素最少的行或列开始，圈出一个,0,元素，用 表示，然后划去该所在的行和列中的其余,0,元素，用,表示，依次类推，若能得到,n,个，则得最优解,X,0,89,例：求费用矩阵为右表的,指派问题的最优解,工作,人,费用,A B C D E,甲,乙,丙,丁,戊,12 7 9 7 9,8 9 6 6 6,7 17 12 14 12,15 14 6 6 10,4 10 7 10 6,-7,-6,-7,-6,-4,得,4,个，且不存在没打,的,0,修改方法！,90,对,n,阶费用矩阵,C,，若,C,有,n,个位于不同行不同列的,零元素，即可得最优解,X,0,。,否则，对,C,进行调整。,-2,+2,-2,最优指派方案：甲做,B,工作,，乙做,C,工作,丙做,A,工作,，丁做,D,工作,戊做,E,工作,？,？,91,当,C,没有,n,个位于不同行不同列的零元素时，对,C,进行调整。,第一步：做能复盖所有,0,元素的,最小直线集合,：,1,）对没有的行打号,2,）对打号的行上所有,0,元,素的列打号,3,）再对打号的列上所有的,行打号,4,）重复以上步骤直到得不出新的,打号为止,5,）对没有打号的行画横线，所有,打号的列画纵线，所得到的直线,既是复盖所有,0,元素的最小直线集合,具体步骤：,92,第二步：在没有被直线复盖的元素中找出最,小元素，让打号的列加上这个元,素，打号的行减去这个元素,第三步：对所得到的矩阵画，若能得到,n,个，,则得最优解，否则重复以上步骤，直至得,到,n,个。,+2,-2,-2,93,南京邮电大学经济与管理学院,例：求费用矩阵为下表的,指派问题的最优解,工作,人,费用,A B C D E,甲,乙,丙,丁,戊,12 7 9 7 9,8 9 6 6 6,7 17 12 14 12,15 14 6 6 10,4 10 7 10 6,-7,-6,-7,-6,-4,+2,-2,-2,最优指派方案,：甲做,B,工作,乙做,C,工作,丙做,A,工作,丁做,D,工作,戊做,E,工作,=32,94,匈牙利法的具体步骤：,第一步,：变换指派问题的费用矩阵，使其在各行,各列都出现,0,元素：,方法：首先每行元素减去该行的最小元素，,然后每列减去该列的最小元素,第二步,：进行试指派（画）,方法：从含,0,元素最少的行或列开始，圈出一个,0,元素，用 表示，然后划去该所在的行,和列中的其余,0,元素，用,表示，依次类推。,若矩阵中的的个数等于,n,，则得最优解,若矩阵中的的个数,n,工作,人,费用,1 2 j n,1,2,i,m,n+1 n+2 m,用匈牙利法求解,105,例：现有,4,份工作，,6,个人应聘，由于个人的技术专长不同，他们承担各项工作所需时间如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总时间最少的分派方案。,工作,人,时间,1 2 3 4,1,2,3,4,5,6,5 6,0,0,0,0,0,0,0,0,0,0,0,0,12 7 9 7,7 17 12 14,15 14 6 6,4 10 7 10,6 5 5 8,4 5 7 6,分派方案：,第,3,个人第,4,项工作,第,4,个人第,1,项工作,第,5,个人第,3,项工作,第,6,个人第,2,项工作,第,1,、,2,个人没工作,总时间,=,6+4+5+5=20,106,工作,人,费用,1 2 j n,1,2,i,m,m+1,m+2,n,(b)mn,用匈牙利法求解,107,(3),一个人可做几件事,的指派问题,设,n,个人中的第,k,个人可同时做,t,件事：,把第,k,个人视为,t,个人，,这,t,个人做同一件事的费用系数都一样,问题化为人数为,n-1+t,个人的指派问题,（,4,）,某人一定不能做某事,的指派问题,如在,minZ,问题中，第,k,个人一定不能做