整数规划与分配问题-运筹学课件

整数规划与分配问题-运筹学2024/6/252第四章第四章整数规划与分配问题整数规划与分配问题（IntegerProgramming,IP)n整数规划的有关概念及特点整数规划的有关概念及特点n指派问题及匈牙利解法指派问题及匈牙利解法n整数规划的求解方法：分枝定界法、割平面法整数规划的求解方法：分枝定界法、割平面法n0-1规划的求解方法：隐枚举法规划的求解方法：隐枚举法n整数规划的应用整数规划的应用整数线性规划类型整数线性规划类型1.纯纯纯纯整数线性规划整数线性规划整数线性规划整数线性规划：2.混合混合混合混合整数线性规划整数线性规划整数线性规划整数线性规划：3.0 01 1型型型型整数线性规划整数线性规划整数线性规划整数线性规划：人员安排问题人员安排问题人员安排问题人员安排问题投资组合问题投资组合问题投资组合问题投资组合问题物资运输问题物资运输问题物资运输问题物资运输问题人员安排问题人员安排问题n n医院护士医院护士2424小时值班，每次值班小时值班，每次值班8 8小时。不同小时。不同时段需要的护士人数不等。据统计：时段需要的护士人数不等。据统计：序号时段最少人数安排人数1061060 x12101470 x23141860 x34182250 x45220220 x56020630 x6最少需要多少护士？最少需要多少护士？minminz=xz=x1 1+x+x2 2+x+x3 3+x+x4 4+x+x5 5+x+x6 6 x x1 1+x+x2 2 70 70 x x2 2+x+x3 3 60 60 x x3 3+x+x4 4 50 50 x x4 4+x+x5 5 20 20 x x5 5+x+x6 6 30 30 x x6 6x x1 16060 x xj j 0,j=1,2,6 0,j=1,2,6设设x1,x2,x6为各班为各班新新上班上班人数人数人员安排问题人员安排问题n证券投资证券投资：把一定的资金投入到合适的有：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。价证券上以规避风险并获得最大的利润。n项目投资项目投资：财团或银行把资金投入到若干：财团或银行把资金投入到若干项目中以获得中长期的收益最大项目中以获得中长期的收益最大。投资组合问题投资组合问题 现有资金现有资金总额为总额为B B。可供选择的投资项目有。可供选择的投资项目有n n个，项目个，项目j j所需所需投资额投资额和和预期收益分别为预期收益分别为a aj j和和c cj j（j=1,2,.,nj=1,2,.,n）。）。此外，此外，由于种种原因，有三个附加条件：由于种种原因，有三个附加条件：第一第一，若选择项目，若选择项目1 1，就，就必须同时必须同时选择项目选择项目2 2。反之，则不。反之，则不一定；一定；第二第二，项目，项目3 3和和4 4中中至少至少选择一个；选择一个；第三第三，项目，项目5 5，6 6和和7 7中中恰好恰好选择两个。选择两个。应当怎样选择投资项目，才能使总预期收益最大？应当怎样选择投资项目，才能使总预期收益最大？模模 型型n变量变量每个项目是否投资每个项目是否投资n约束约束总金额总金额不超过限制不超过限制3 3个附加条件个附加条件n目标目标总收益最大总收益最大模模 型型物资运输问题物资运输问题工厂工厂A A1 1和和A A2 2生产某种物资。生产某种物资。由于该种物资供不应求，故需要再建一家工厂。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有相应的建厂方案有A A3 3和和A A4 4两个。两个。这种物资的需求地有这种物资的需求地有B B1 1，B B2 2，B B3 3，B B4 4四个。四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费c cijij(i,j=1,2,3,4i,j=1,2,3,4).).B B1 1B B2 2B B3 3B B4 4生产能力生产能力生产能力生产能力A A1 12 29 93 34 4400400A A2 28 83 35 57 7600600A A3 37 76 61 12 2200200A A4 44 45 52 25 5200200需求量需求量需求量需求量35035040040030030015015012001200工厂工厂A A3 3或或A A4 4开工后，每年的生产费用估计分别为开工后，每年的生产费用估计分别为12001200万元或万元或15001500万元。现要万元。现要决定应该建设工厂决定应该建设工厂A A3 3还是还是A A4 4，才能使今后每年的，才能使今后每年的总费用最少总费用最少？再引入一个再引入一个0-1变量变量yn特征特征变变量量整数整数性要求性要求n来源来源 问题本身的要求问题本身的要求 引入的引入的逻辑变量逻辑变量的需要的需要n性质性质可可行域是行域是离散离散集合集合模型的特点模型的特点与线性规划的关系与线性规划的关系整数规划整数规划放松的线性规划放松的线性规划可行解可行解是松弛问题的是松弛问题的可行解可行解最优值最优值不会优于不会优于其松弛问题的最优值其松弛问题的最优值注注 释释n最优解最优解不一定在顶点不一定在顶点上达到上达到n最优解最优解不一定是不一定是松弛问题最优解的松弛问题最优解的邻近整数邻近整数解解n整数可行解整数可行解远多于远多于顶点，枚举法不可取顶点，枚举法不可取2024/6/2518求整数解的线性规划问题，不是用求整数解的线性规划问题，不是用四舍五入四舍五入法或法或去尾法去尾法对对性规划的非整数解加以处理就能解决的，用性规划的非整数解加以处理就能解决的，用枚举法枚举法又往往又往往会计算量太大，所以要用整数规划的特定方法加以解决。会计算量太大，所以要用整数规划的特定方法加以解决。例：例：求解下列整数规划：求解下列整数规划：二、二、整数规划的求解特点整数规划的求解特点2024/6/2519分析：分析：若当作一般线性规划求解，若当作一般线性规划求解，图解法的结果如下。图解法的结果如下。1、非整数规划、非整数规划最优解最优解 显然不是整数规划的可行解。显然不是整数规划的可行解。2、四舍五入后的结果四舍五入后的结果 也不是整数规划的可行解。也不是整数规划的可行解。3、可行解是阴影区可行解是阴影区域交叉点，可比较这域交叉点，可比较这些点对应的函数值，些点对应的函数值，找出最优。找出最优。2024/6/25202 2 指派问题及匈牙利解法指派问题及匈牙利解法 一、一、指派问题与模型指派问题与模型 m m项任务分配给项任务分配给m m个人去完成，每人只能完成其中一项，个人去完成，每人只能完成其中一项，每项任务只能分给一人完成，应如何分配使得效率最高每项任务只能分给一人完成，应如何分配使得效率最高？a aijij是第是第j j个人完成第个人完成第i i项任务的效率。项任务的效率。人任务12 m1a11a12a1m2a21a22a2mmam1am2amm2024/6/2521设设于是建立模型如下：于是建立模型如下：2024/6/2522二、二、指派问题的指派问题的匈牙利解法匈牙利解法该指派问题可当作运输问题解决，但匈牙利解法更有效。该指派问题可当作运输问题解决，但匈牙利解法更有效。解法思想：解法思想：效率矩阵的元素效率矩阵的元素 ，若有一组位于不同，若有一组位于不同行不同列的零元素，则令这些位置的决策变量取值为行不同列的零元素，则令这些位置的决策变量取值为1 1，其，其余均为余均为0 0，这显然就是最优解。，这显然就是最优解。2024/6/2523定理定理2 2：若矩阵若矩阵A A的元素可分为的元素可分为“0 0”元和元和“非非0 0”元，则覆元，则覆盖盖“0 0”元的最少直线数等于位于不同行、不同列的元的最少直线数等于位于不同行、不同列的“0 0”元的最大个数。元的最大个数。定理定理1 1：效率矩阵效率矩阵 的每一行元素分别减去（加上）一个的每一行元素分别减去（加上）一个常数常数 ，每一列元素分别减去（加上）一个元素，每一列元素分别减去（加上）一个元素 ，得，得新效率矩阵新效率矩阵 ，则，则 的最优解等的最优解等价于价于 的最优解。的最优解。2024/6/2524例：例：有一份说明书，要分别译成英、日、德、俄四种语言，有一份说明书，要分别译成英、日、德、俄四种语言，交给甲、乙、丙、丁四人去完成，各人的效率不同，如何交给甲、乙、丙、丁四人去完成，各人的效率不同，如何分配任务，可使总效率最高。分配任务，可使总效率最高。人任务甲乙丙丁英文21097日文154148德文13141611俄文4151392024/6/2525匈牙利解法匈牙利解法步骤步骤：1 1、在效率矩阵每行减去该行最小元素；在效率矩阵每行减去该行最小元素；2 2、在效率矩阵每列减去该列最小元素；在效率矩阵每列减去该列最小元素；2024/6/25263 3、寻找独立寻找独立“0 0”元素元素(不同行不同列）不同行不同列）（1 1）从第一行开始，若该行只有一个）从第一行开始，若该行只有一个“0 0”元素，则对该元素，则对该“0 0”元素打括号（元素打括号（）（表示这一行的人只有这一个任务可（表示这一行的人只有这一个任务可指派），指派），并划去该并划去该“0 0”元素所在的列元素所在的列（表示该项任务不能（表示该项任务不能再指派给别人）再指派给别人）；若该行无；若该行无“0 0”元素或有两个以上的元素或有两个以上的“0 0”元素（不含划去的元素（不含划去的0 0），则转下一行；），则转下一行；（2 2）从第一列开始，若该列只有一个）从第一列开始，若该列只有一个“0 0”元素，则对该元素，则对该“0 0”元素打括号（元素打括号（），并划去该），并划去该“0 0”元素所在的行；若元素所在的行；若该列无该列无“0 0”元素或有两个以上的元素或有两个以上的“0 0”元素（不含划去的元素（不含划去的0 0），则转下一列；），则转下一列；2024/6/2527（0）82511（0）5423（0）001145完成上述步骤后可能出现下列情况：完成上述步骤后可能出现下列情况：）效率矩阵的每一行都有一个打括号的效率矩阵的每一行都有一个打括号的0 0元素，则按照打括元素，则按照打括号的号的0 0元素位置指派任务，即是最优解；元素位置指派任务，即是最优解；）打括号的打括号的0 0元素个数小于元素个数小于m m，但未被划去的，但未被划去的0 0元素之间存元素之间存在闭回路，则沿此闭回路，每隔一个在闭回路，则沿此闭回路，每隔一个0 0元打一括号，然后对元打一括号，然后对打括号的打括号的0 0元素所在行或所在列画直线；元素所在行或所在列画直线；）矩阵中所有矩阵中所有0 0元素或被打括号，或被划去，但打括号的元素或被打括号，或被划去，但打括号的0 0元素个数元素个数 ，则进入下一步；，则进入下一步；2024/6/25283 3、设法使每一行都有一个打括号的设法使每一行都有一个打括号的“0 0”元素。按元素。按定理定理1 1继续继续对矩阵进行变换：对矩阵进行变换：）从矩阵未被直线覆盖的元素中找出最小者）从矩阵未被直线覆盖的元素中找出最小者k k，）对矩阵中无直线覆盖的行，令）对矩阵中无直线覆盖的行，令 ，有直线覆盖的列，有直线覆盖的列，令令 。其余为。其余为0 0。）对矩阵的每个元素计算）对矩阵的每个元素计算 ，得到一个新矩阵，得到一个新矩阵，转第三步重复进行，直至每一行都有一打括号的转第三步重复进行，直至每一行都有一打括号的0 0元素。元素。2024/6/2529（0）82511（0）5423（0）001145根据上图，根据上图，k=2k=2，最优解：最优解：2024/6/2530思考：思考：1 1、任务数、任务数 人数人数 时如何处理时如何处理 2 2、指派问题中目标函数变为、指派问题中目标函数变为MAXMAX时如何处理时如何处理 两点说明两点说明1.1.效率矩阵不是方阵的情况。（即人员与工作数不效率矩阵不是方阵的情况。（即人员与工作数不相等）相等）处理方法处理方法：增加虚拟人或工作，使两者相等。虚：增加虚拟人或工作，使两者相等。虚拟人或工作对应的效率矩阵中元素为拟人或工作对应的效率矩阵中元素为0 0。2.2.最大化分配问题的处理。最大化分配问题的处理。如果给出的效率矩阵中的数字表示每个人完成各项如果给出的效率矩阵中的数字表示每个人完成各项任务的收益，则问题变成了如何分配任务才能使总任务的收益，则问题变成了如何分配任务才能使总收益最大收益最大.处理方法处理方法：用效率矩阵中的最大元减去矩阵中的各：用效率矩阵中的最大元减去矩阵中的各个元素得到一个新的矩阵，对这个新的矩阵用匈牙个元素得到一个新的矩阵，对这个新的矩阵用匈牙利方法求解。利方法求解。练习练习1.1.用匈牙利方法求解下列问题用匈牙利方法求解下列问题例例1：设设某某工工程程有有B1,B2,B3,B4 四四项项任任务务，需需由由四四个个工工人人A1,A2,A3,A4去去完完成成，由由于于任任务务性性质质和和每每个个工工人人的的技技术术水水平平不不相相同同，他他们们完完成成各各项项任任务务所所需需的的时时间间也也不不一一样样（见见下下表表）。问问应应当当如如何何分分配配，即即哪哪个个人人去去完完成成哪哪项任务，才能使完成四项任务的总时间最少？项任务，才能使完成四项任务的总时间最少？任务任务人员人员B1B2B3B4A1215134A21041415A39141613A478119设设效率矩阵：效率矩阵：效率矩阵效率矩阵第一步：初始变换第一步：初始变换2151341041415914161378119249701311260101105740142004201370606905320100得解矩阵得解矩阵找独立找独立0 0元素元素01370606905320100总时间为总时间为:4+4+9+11=28:4+4+9+11=28练习练习2 2：用匈牙利解法解下列分配问题：用匈牙利解法解下列分配问题效率矩阵效率矩阵第一步：初始变换第一步：初始变换0000012797989666717121491514661041071091279798966671712149151466104107109767645020223000010572980040636550202230000105729800406365第二步：寻找独立第二步：寻找独立0 0元素元素最小元素为最小元素为 min10,5,7,2,6,3,6,5=2-2-2+270202430000835011800404143它有它有5 5个独立个独立0 0元，得到最优解相应的解矩阵为元，得到最优解相应的解矩阵为最优目标值：最优目标值：7+6+9+6+4=32练习练习3：求解下列分配问题：求解下列分配问题效率矩阵效率矩阵10978587754652345工作工作人员人员ABCD甲甲10978乙乙5877丙丙5465丁丁2345 109785877546523457542320103221021012300013200032110200122-1-1+142000210202000114200021020200011第一组最优解第一组最优解第二组最优解第二组最优解2024/6/25423 3 分枝定界法分枝定界法 分枝定界法分枝定界法是求解整数规划的一种常用的有效的方法，它是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问既能解决纯整数规划的问题，又能解决混合整数规划的问题。题。大多数求解整数规划的商用软件就是基于分枝定界法编大多数求解整数规划的商用软件就是基于分枝定界法编制而成的。制而成的。下面举例来说明分枝定界法的思想和步骤。下面举例来说明分枝定界法的思想和步骤。2024/6/2543性质性质 求求MAXMAX的问题的问题：整数规划的最优目标函数值整数规划的最优目标函数值小于或小于或等于等于相应的线性规划的最优目标函数值；相应的线性规划的最优目标函数值；求求MINMIN的问题：的问题：整数规划的最优目标函数值整数规划的最优目标函数值大于或大于或等于等于相应的线性规划的最优目标函数值。相应的线性规划的最优目标函数值。1、求解整数规划相应的一般线性规划问题（即先去掉整数、求解整数规划相应的一般线性规划问题（即先去掉整数约束）。约束）。易知：整数规划的可行域（小）包含于线性规划的可行易知：整数规划的可行域（小）包含于线性规划的可行域域(大）。大）。若线性规划的最优解恰是整数解，则其就是整数规划的最若线性规划的最优解恰是整数解，则其就是整数规划的最优解。否则该最优解，是整数规划最优解的上界或下界。优解。否则该最优解，是整数规划最优解的上界或下界。2024/6/2544例：例：求解下列整数规划：求解下列整数规划：解：解：1 1、解对应的线性规划：、解对应的线性规划：其最优解为其最优解为 ，显然不是整数规划的可行显然不是整数规划的可行解。解。L0：2024/6/25452 2、分枝与定界：分枝与定界：将对应的线性规划问题分解成几个子问题，每个子问将对应的线性规划问题分解成几个子问题，每个子问题就是一分枝，而所有子问题的解集之和要包含原整数规题就是一分枝，而所有子问题的解集之和要包含原整数规划的解集。划的解集。求解每一分枝子问题：求解每一分枝子问题：若其最优解满足整数约束，则它就是原问题的一个可行若其最优解满足整数约束，则它就是原问题的一个可行解（不一定是最优）；否则，就是该枝的上界或下界。解（不一定是最优）；否则，就是该枝的上界或下界。若所有分支的最优解都不满足整数条件（即不是原问题若所有分支的最优解都不满足整数条件（即不是原问题的可行解），则选取一个边界值最优的分支继续分解，直的可行解），则选取一个边界值最优的分支继续分解，直至找到一个原问题的可行解。至找到一个原问题的可行解。若在同一级分枝中同时出现两个以上的原问题可行解，若在同一级分枝中同时出现两个以上的原问题可行解，则保留目标值最优的一个，其余不再考虑。则保留目标值最优的一个，其余不再考虑。从各分枝中找原问题可行解的目的是为下一步的比较与剪枝。从各分枝中找原问题可行解的目的是为下一步的比较与剪枝。2024/6/2546将上述线性规划问题分为两枝，并求解。将上述线性规划问题分为两枝，并求解。解得解得L1：L2：显然两个分枝均非整数可行解，选边界值较大的显然两个分枝均非整数可行解，选边界值较大的L L1 1继续分继续分枝。枝。2024/6/2547将将L1分为两枝，并求解。分为两枝，并求解。解得解得L11：L12：两个分枝均是整数可行解，保留目标值较大的两个分枝均是整数可行解，保留目标值较大的L L1212。2024/6/25483 3、比较与剪枝比较与剪枝 将各子问题的边界值与保留下的整数可行解对应的目将各子问题的边界值与保留下的整数可行解对应的目标值比较，将边界值劣于可行行解的分支减剪去。标值比较，将边界值劣于可行行解的分支减剪去。若比较剪枝后，只剩下所保留的整数可行解，则该解就若比较剪枝后，只剩下所保留的整数可行解，则该解就是原整数规划的最优解；否则选取边界值最大的一个分枝是原整数规划的最优解；否则选取边界值最大的一个分枝继续分解，在其后的过程中出现新的整数可行解时，则与继续分解，在其后的过程中出现新的整数可行解时，则与原可行解比较，保留较优的一个，重复第三步。原可行解比较，保留较优的一个，重复第三步。2024/6/2549L0：X22X23X13X14用图表示上例的求解过程与求解结果用图表示上例的求解过程与求解结果练习1：用分支定界法求解下列整数规划123123(3/2,10/3)(3/2,10/3)x1=3/2,分为x11与x12SS2S1x11x12S2S1分别解之分别解之先放弃先放弃“整数整数”要要求求求出一个最优解。求出一个最优解。123123S1S2n n解解S S1 1,求出一个最优解求出一个最优解(2,23/9),max(2,23/9),maxz=41/9n n解解S S2 2,求出一个最优解求出一个最优解(1,7/3),max(1,7/3),maxz=10/3S SS S2 2S S1 1x11x12(2,23/9)(2,23/9)(2,23/9)(2,23/9)x x2 2=23/9=23/9,分为分为分为分为x x2 222与与与与x x2 233S S1212S S1111x22x23可可可可行行行行域域域域为为为为空空空空S12S11123123S12(33/14,2)(33/14,2)(33/14,2)(33/14,2)n n解解S S1212,求出一个最优解求出一个最优解(33/14,2),max(33/14,2),maxz=61/14S SS S2 2S S1 1x11x12S S1212S S1111x22x23可可可可行行行行域域域域为为为为空空空空10/310/361/1461/14S S122122S S121121x12x13x x1 1=33/14=33/14,分为分为分为分为x x1 122与与与与x x1 133S121S122123123S SS S2 2S S1 1x11x12S S1212S S1111x22x23可可可可行行行行域域域域为为为为空空空空10/310/3S S122122S S121121x12x13S121S122n n解解S S121121,求出一个最优解求出一个最优解(3,1),max(3,1),maxz=4n n解解S S122122,求出一个最优解求出一个最优解(2,2),max(2,2),maxz=4(2,2)(2,2)(2,2)(2,2)(3,1)(3,1)(3,1)(3,1)44最优整数最优整数最优整数最优整数解解解解为为为为(3,1)(3,1)和和和和(2,2)(2,2)最优最优最优最优值值值值为为为为4 42024/6/25554 割平面法割平面法 一、一、基本思想基本思想 在整数规划的松弛问题中，依次引进新的约束条件在整数规划的松弛问题中，依次引进新的约束条件（割平面），使问题的可行域逐步减小，但每次割去（割平面），使问题的可行域逐步减小，但每次割去的只是部分非整数解，直到使问题的目标函数值达到的只是部分非整数解，直到使问题的目标函数值达到最优的整数点成为缩小后的可行域的一个顶点，这样最优的整数点成为缩小后的可行域的一个顶点，这样就可以用线性规划的方法求得整数最优解。就可以用线性规划的方法求得整数最优解。2024/6/2556例：例：求解下列整数规划：求解下列整数规划：解：解：1 1、解对应的线性规划（松弛问题），并将约束条件的系解对应的线性规划（松弛问题），并将约束条件的系数均化为整数：数均化为整数：2024/6/2557加入松弛变量后求解，得最终单纯形表：加入松弛变量后求解，得最终单纯形表：25/2011/2-1/2313/410-1/43/400-1/4-5/4如果上述求解结果是整数解，则结束；否则转下一步；如果上述求解结果是整数解，则结束；否则转下一步；2 2、找出非整数解中分数部分最大的一个基变量，并将该行找出非整数解中分数部分最大的一个基变量，并将该行对应的约束方程所有常数（系数及常数项）分解成一个整数对应的约束方程所有常数（系数及常数项）分解成一个整数与一个正分数之和；将所有分式项移到等式右端。与一个正分数之和；将所有分式项移到等式右端。例如上例，取第一行约束例如上例，取第一行约束 2024/6/2558易知，左端为整数，要是等式成立，右端也必为整数，且易知，左端为整数，要是等式成立，右端也必为整数，且将将 代入上式，得代入上式，得2024/6/2559这就是一个割平面。将这就是一个割平面。将其添加到原约束中，得其添加到原约束中，得到新的可行域如图所示。到新的可行域如图所示。割去的只是部分非整数割去的只是部分非整数解。解。2024/6/25603 3、将新的约束添加到原问题中，得到一个新的线性规划问将新的约束添加到原问题中，得到一个新的线性规划问题，求解此问题，可用灵敏度分析的方法。题，求解此问题，可用灵敏度分析的方法。4 4、重复上述的重复上述的1-31-3步，直至求出整数最优解。步，直至求出整数最优解。25/2011/2-1/20313/410-1/43/400-1/200-1/2-1/2100-1/4-5/40将将 反应到最终表中，得反应到最终表中，得2024/6/2561运用对偶单纯形法，解得运用对偶单纯形法，解得22010-11/231001-1/2010011-2000-1-1/2此解仍非整数解，将基变量此解仍非整数解，将基变量 对应的约束分解为：对应的约束分解为：得到新的约束得到新的约束 2024/6/256222010-11/2031001-1/20010011-200-1/20000-1/21000-1-1/2021010-1023410010-10300110-40100001-2000-10-1此时已得整数最优解。此时已得整数最优解。2024/6/2563约束约束即为即为用割平面法求解整数规划问题用割平面法求解整数规划问题解：增加松弛变量解：增加松弛变量x3和和x4，得到得到(LP)的初始单纯形表和的初始单纯形表和最优单纯形表：最优单纯形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201Z00100Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4Z-3/200-1/4-1/4割平面法练习割平面法练习1将将 x3=6-3x1-2x2,x4=3x1-2x2 ,带入带入 中，中，得到等价的割平面条件：得到等价的割平面条件：x2 1 见下图。见下图。x1x233第一个割平面第一个割平面Cj01000CBXBbx1x2x3x4s10 x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41Z-3/200-1/4-1/40现将生成的割平面条件加入松弛变量，然后加到表中：现将生成的割平面条件加入松弛变量，然后加到表中：CBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4Z-10000-1 此时，此时，X1(2/3,1),Z=1,仍不是整数解。继续以仍不是整数解。继续以x1为源为源行生成割平面，其条件为：行生成割平面，其条件为：用上表的约束解出用上表的约束解出x4 和和s1，将它们带入上式得到等价将它们带入上式得到等价的割平面条件：的割平面条件：x1 x2，见图：见图：x1x233第一个割平面第一个割平面第二个割平面第二个割平面将生成的割平面条件加入松弛变量，然后加到表中：将生成的割平面条件加入松弛变量，然后加到表中：CBXBbx1x2x3x4s1s20 x12/3100-1/32/301x210100100 x320011-400s2-2/3000-2/3-2/31Z-10000-10CBXBbx1x2x3x4s1s20 x1110001-1/21x210100100 x310010-53/20 x4100011-3/2Z-10000-10 至此得到最优表，其最优解为至此得到最优表，其最优解为 X=(1,1),Z=1,这这也是原问题的最优解。也是原问题的最优解。有以上解题过程可见，表中含有分数元素且算法过有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。数对偶割平面算法。割平面法练习割平面法练习2Cj1100CBXBbx1x2x3x40 x3621100 x4204501Z1100CBXBbx1x2x3x41 x15/3105/61/61x28/3012/31/3Z-13/3001/61/6初初始始表表最最优优表表在在松松弛弛问问题题最最优优解解中中，x1,x2 均均为为非非整整数数解解，由由上上表表有：有：将系数和常数都分解成整数和非负真分数之和将系数和常数都分解成整数和非负真分数之和 以上式子只须考虑一个即可，解题经验表明，考虑以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右任选一个考虑。现选第二个式子，并将真分数移到右边得：边得：引入松弛变量引入松弛变量s1 后得到下式，将此约束条件加到上表后得到下式，将此约束条件加到上表中，继续求解。中，继续求解。Cj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31Z13/3001/61/60Cj11000CBXBbx1x2x3x4s11 x10100101x24010120 x3200113Z400001/2 得得到到整整数数最最优优解解，即即为为整整数数规规划划的的最最优优解解，而而且且此此整整数数规规划划有两个最优解：有两个最优解：X=(0,4),Z=4,或 X=(2,2),Z=4。第五节第五节01问题问题50-1规划的求解规划的求解隐枚举法隐枚举法n解 01 规划的隐枚举法有其独特的工作程序，具体过程如下。na.模型转化为求极小的问题模型转化为求极小的问题nb.变量替换。极小问题模型的目标函数中所有变量系变量替换。极小问题模型的目标函数中所有变量系数为负的数为负的01变量，可利用变量替换变量，可利用变量替换xk=1xk(xk是引是引入的新的入的新的01变量变量)，将目标函数中所有变量系数化为正，将目标函数中所有变量系数化为正数。数。nc.目标函数中变量按系数大小排列，约束条件中变量目标函数中变量按系数大小排列，约束条件中变量排列顺序也相应调整。排列顺序也相应调整。nd.按目标函数值由小到大的顺序依次排列可能的解，按目标函数值由小到大的顺序依次排列可能的解，并予以可行性检验。并予以可行性检验。ne.发现求极小问题的最优解并停止。发现求极小问题的最优解并停止。nf.转化为原问题的最优解。转化为原问题的最优解。01 整数规划是一种特殊形式的整数规划，这时整数规划是一种特殊形式的整数规划，这时的决策变量的决策变量xi 只取两个值只取两个值0或或1，一般的解法为，一般的解法为隐枚举隐枚举法法。1、m个约束条件只有k个起作用m个约束条件可表示为：增加变量定义为：又设M为任意大的数，则 表明：m个约束条件中有m-k个的右端项为bi+Myi，不起约束作用6应用举例应用举例【实例实例】maxZ=3x1+5 x2 x1 8 2x2 12三个约束中只有两个起作用三个约束中只有两个起作用 3x1+4 x2 36 x1 0,x2 0 引入辅助变量 模型化为：maxZ=3x1+5 x2 x1 8+My1 2x2 12+My2 3x1+4 x2 36+My3 y1+y2+y3=1 x1 0,x2 0,yi只取只取0或或12、约束条件的右端可能是、约束条件的右端可能是b1或或b2br即：引入变量定义为：则原约束可表示为【例如】某约束为 2x1+5x2-x32或3引入辅助变量y1,y2,约束化为2x1+5x2-x32y1+3y2y1+y2=1y1,y2只取0或13、两组条件满足其中一组、两组条件满足其中一组若x14,则 x21；否则（即x14时），x23引入变量定义为：又M为任意大的数，则问题可表达为4、用以表示含固定费用的函数、用以表示含固定费用的函数用xj代表产品j的生产量，其生产费用函数通常可表示为：Kj为与生产量无关的生产准备费用解决方法：设置一个逻辑变量yj，当 xj=0时，yi=0，当xj0时，yj=1 可以看出当xj=0时，yi=0为此引进一个特殊的约束条件，则模型设为【应用应用1】工厂的各种产品所需要的机时、人工工时、原材料的资源数量及可用资源的总量、产品的售价和各种资源的价格等因素。有关信息在下表中给出。产品A 产品B 资源总量资源价格（元单位）机器（时）6 8 120人工（时）10 5 10020 原材料(公斤)11 8 130 1产品售价（元）600 400 设 x1,x2分别为产品A、B的生产量。如果生产产品A，工厂要花费1000元的固定成本，如果生产产品B，工厂要花费800元的固定成本。假设其它情况不变，请你为该工厂设计一个使利润最大化的生产方案。再令y1,y2分别表示生产A、B和可能性（即1为生产，0为不生产）例例2 东方大学计算机实验室聘用4名大学生（代号为1、2、3、4），两名研究生（代号为5、6）值班答疑，已经每人周一至周五每天最多可安排时间及每人每小时的报酬如下表：学生代学生代号号报酬报酬每天最多可安排的值班时间每天最多可安排的值班时间周一周一周二周二周三周三周四周四周五周五1 110106 60 06 60 07 72 210100 06 60 06 60 03 39.99.94 48 83 30 05 54 49.89.85 55 56 60 04 45 510.810.83 30 04 48 80 06 611.311.30 06 60 06 63 3 实验室开放时间为早8：00至晚10：00，值班时须有且仅须有一名学生值班，规定大学生每周值班不少于8小时，研究生每周值班不少于7小时，每名学生值班不超过3次，每次不少于2小时，每天安排值班不超过3人，且一名为研究生。试安排一张，使总报酬最低。例例2设：xij为学生i在周j值班时间，aij代表学生i在周j 最多值班时间，ci代表学生i的报酬。例例3 红星日用化工厂为发运产品，下一年度需6种不同容积的包装，每种包装的需求量及生产一个的可变费用如下表：由于生产不同容积包装箱需进行专门准备、下料等，生产某一容积包装箱的固定费用为1200元，又若某一容积包装箱数量不够时，可用比它容积大的代替。试问化工厂应订做哪几种代号的包装箱各多少个，使费用最节省。包装箱代号包装箱代号1 12 23 34 45 56 6容积（容积（m3m3）0.080.080.10.10.120.120.150.150.20.20.250.25需求量（个需求量（个)500500550550700700900900450450400400可变费用（元可变费用（元/个）个）5 58 8101012.112.116.316.318.218.2设：xj为代号j包装箱的订做数量。