1、2022-4-251运筹学运筹学OPERATIONS RESEARCH2022-4-252第四章第四章 整数规划与分配问题整数规划与分配问题（Integer Programming, IP) n整数规划的有关概念及特点整数规划的有关概念及特点 n指派问题及匈牙利解法指派问题及匈牙利解法n整数规划的求解方法：分枝定界法、割平面法整数规划的求解方法：分枝定界法、割平面法 n0-1规划的求解方法：隐枚举法规划的求解方法：隐枚举法n整数规划的应用整数规划的应用2022-4-253纯整数规划：纯整数规划：在整数规划中，如果所有的变量都为非负整在整数规划中，如果所有的变量都为非负整 数，则称为数，则称为纯
2、整数规划问题纯整数规划问题；混合整数规划：混合整数规划：如果有一部分变量为非负整数，则称之为如果有一部分变量为非负整数，则称之为 混合整数规划问题混合整数规划问题。0-10-1变量：变量：在整数规划中，如果变量的取值只限于在整数规划中，如果变量的取值只限于0 0和和1 1，这，这 样的变量我们称之为样的变量我们称之为0-10-1变量变量。0-10-1规划：规划：在整数规划问题中，如果所有的变量都为在整数规划问题中，如果所有的变量都为0-10-1变变 量，则称之为量，则称之为0-10-1规划规划。1 1 整数规划的有关概念及特点整数规划的有关概念及特点一、一、 概念概念整数规划：整数规划： 要求
3、决策变量取整数值的规划问题。要求决策变量取整数值的规划问题。 （线性整数规划、非线性整数规划等）（线性整数规划、非线性整数规划等）nqjxqjxmpibxapibxatsxczjjijijnjijijnjnjjj,.,1,.,10,.,1)(,.,1. .min)max(111或中部分或全部取整数jx整数线性规划模型整数线性规划模型整数线性规划类型整数线性规划类型1.：2.：3.：取整数中全部全部jx取整数中部分部分jx1 10 0或或只能取值jx人员安排问题人员安排问题序号时段最少人数安排人数1061060 x12101470 x23141860 x34182250 x45220220 x5
4、6020630 x6最少需要多少护士？最少需要多少护士？人员安排问题人员安排问题n证券投资证券投资：把一定的资金投入到合适的有：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。价证券上以规避风险并获得最大的利润。n项目投资项目投资：财团或银行把资金投入到若干：财团或银行把资金投入到若干项目中以获得中长期的收益最大项目中以获得中长期的收益最大。投资组合问题投资组合问题 现有资金现有资金总额为总额为B B。可供选择的投资项目有。可供选择的投资项目有n n个，项目个，项目j j所需所需投资额投资额和和预期收益分别为预期收益分别为a aj j和和c cj j（j=1,2,.,nj=1,2
5、,.,n）。）。此外，此外， 由于种种原因，有三个附加条件：由于种种原因，有三个附加条件：第一第一，若选择项目，若选择项目1 1，就，就必须同时必须同时选择项目选择项目2 2。反之，则不。反之，则不一定；一定；第二第二，项目，项目3 3和和4 4中中至少至少选择一个；选择一个；第三第三，项目，项目5 5，6 6和和7 7中中恰好恰好选择两个。选择两个。应当怎样选择投资项目，才能使总预期收益最大？应当怎样选择投资项目，才能使总预期收益最大？不投资不投资投资投资jjxj对项目对项目01模模 型型n变量变量每个项目是否投资每个项目是否投资n约束约束总金额总金额不超过限制不超过限制3 3个附加条件个附
6、加条件n目标目标总收益最大总收益最大0 , 1 jxnj.,2 , 1 Bxanjjj1 njjjxc1max217654312xxxxxxx）（或njxxxxxxxxBxaxczjnjjjnjjj,.,2,11021max765431211模模 型型物资运输问题物资运输问题工厂工厂A A1 1和和A A2 2生产某种物资。生产某种物资。由于该种物资供不应求，故需要再建一家工厂。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有相应的建厂方案有A A3 3和和A A4 4两个。两个。这种物资的需求地有这种物资的需求地有B B1 1，B B2 2，B B3 3，B B4 4四个。四个。各
7、工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费c cijij( (i,ji,j=1,2,3,4=1,2,3,4).).工厂工厂A A3 3或或A A4 4开工后，每年的生产费用估计分别为开工后，每年的生产费用估计分别为12001200万元或万元或15001500万元。现要万元。现要决定应该建设工厂决定应该建设工厂A A3 3还是还是A A4 4，才能使今后每年的，才能使今后每年的总费用最少总费用最少？ 4141414115030040035002006004001200miniijjijijijijxxxcz 414141
8、4115030040035020006004001500miniijjijijijijxxxcz再引入一个再引入一个0-1变量变量y 4301AAy若若建建工工厂厂若若建建工工厂厂 41414141150300400350)1(200200600400)1(15001200miniijjijijijijxyyxyyxcz100或或 yxijn特征特征变量变量整数整数性要求性要求n来源来源 问题本身的要求问题本身的要求 引入的引入的逻辑变量逻辑变量的需要的需要n性质性质可行域是可行域是离散离散集合集合模型的特点模型的特点与线性规划的关系与线性规划的关系整数规划整数规划 0.minxbAxtsxc
9、 放松的线性规划放松的线性规划可行解可行解是松弛问题的是松弛问题的可行解可行解最优值最优值不会优于不会优于其松弛问题的最优值其松弛问题的最优值注注 释释n最优解最优解不一定在顶点不一定在顶点上达到上达到n最优解最优解不一定是不一定是松弛问题最优解的松弛问题最优解的邻近整数邻近整数解解n整数可行解整数可行解远多于远多于顶点，枚举法不可取顶点，枚举法不可取2022-4-2518求整数解的线性规划问题，不是用求整数解的线性规划问题，不是用四舍五入四舍五入法或法或去尾法去尾法对对性规划的非整数解加以处理就能解决的，用性规划的非整数解加以处理就能解决的，用枚举法枚举法又往往又往往会计算量太大，所以要用整
10、数规划的特定方法加以解决。会计算量太大，所以要用整数规划的特定方法加以解决。例：例： 求解下列整数规划：求解下列整数规划：二、二、 整数规划的求解特点整数规划的求解特点并取整数, 0,5 . 45 . 01432.23max21212121xxxxxxtsxxz2022-4-25191x2x143221 xx5 . 45 . 021xx2123xxz)5 . 2,25. 3(分析：分析： 若当作一般线性规划求若当作一般线性规划求解，图解法的结果如下。解，图解法的结果如下。1、非整数规划、非整数规划最优解最优解 显然不是整数规划的可行解。显然不是整数规划的可行解。2、四舍五入后的结果四舍五入后的
11、结果 也不是整数规划的可行解。也不是整数规划的可行解。)5 . 2,25. 3()3, 3(3、可行解是阴影区可行解是阴影区域交叉点，可比较这域交叉点，可比较这些点对应的函数值，些点对应的函数值，找出最优。找出最优。) 1, 4(2022-4-25202 2 指派问题及匈牙利解法指派问题及匈牙利解法 一、一、 指派问题与模型指派问题与模型 m m项任务分配给项任务分配给m m个人去完成，每人只能完成其中一项，个人去完成，每人只能完成其中一项，每项任务只能分给一人完成，应如何分配使得效率最高？每项任务只能分给一人完成，应如何分配使得效率最高？ a aijij是第是第j j个人完成第个人完成第i
12、i项任务的效率。项任务的效率。 人任务12 m1a11a12a1m2a21a22a2mmam1am2amm2022-4-2521设设于是建立模型如下：于是建立模型如下： 否则项任务个人完成第第01ijxijmimjijijxaz11min1,.mji,1,01,.mj, 11,.mi, 111或ijmiijmjijxxx2022-4-2522二、二、 指派问题的指派问题的匈牙利解法匈牙利解法该指派问题可当作运输问题解决，但匈牙利解法更有效。该指派问题可当作运输问题解决，但匈牙利解法更有效。解法思想：解法思想：效率矩阵的元素效率矩阵的元素 ，若有一组位于不同，若有一组位于不同行不同列的零元素，则
13、令这些位置的决策变量取值为行不同列的零元素，则令这些位置的决策变量取值为1 1，其，其余均为余均为0 0，这显然就是最优解。，这显然就是最优解。0ija2022-4-2523定理定理2 2：若矩阵若矩阵A A的元素可分为的元素可分为“0 0”元和元和“非非0 0”元，则覆盖元，则覆盖“0 0”元的最少直线数等于位于不同行、不同列的元的最少直线数等于位于不同行、不同列的“0 0”元的元的最大个数。最大个数。定理定理1 1：效率矩阵效率矩阵 的每一行元素分别减去（加上）一个的每一行元素分别减去（加上）一个常数常数 ，每一列元素分别减去（加上）一个元素，每一列元素分别减去（加上）一个元素 ，得，得新
14、效率矩阵新效率矩阵 ， ，则，则 的最优解等的最优解等价于价于 的最优解。的最优解。 ijaiujv ijbjiijijvuab ija ijb2022-4-2524例：例：有一份说明书，要分别译成英、日、德、俄四种语言，有一份说明书，要分别译成英、日、德、俄四种语言，交给甲、乙、丙、丁四人去完成，各人的效率不同，如何交给甲、乙、丙、丁四人去完成，各人的效率不同，如何分配任务，可使总效率最高。分配任务，可使总效率最高。 人任务甲乙丙丁英文21097日文154148德文13141611俄文4151392022-4-2525匈牙利解法匈牙利解法步骤步骤：1 1、在效率矩阵每行减去该行最小元素；在效
15、率矩阵每行减去该行最小元素；2 2、在效率矩阵每列减去该列最小元素；在效率矩阵每列减去该列最小元素；411429131541116141381441579102591100532410011578005005411000324501152802022-4-25263 3、寻找独立寻找独立“0 0”元素元素( (不同行不同列）不同行不同列）（1 1）从第一行开始，若该行只有一个）从第一行开始，若该行只有一个“0 0”元素，则对该元素，则对该“0 0”元素打括号（元素打括号（ ）（表示这一行的人只有这一个任务可（表示这一行的人只有这一个任务可指派），指派），并划去该并划去该“0 0”元素所在的列元
16、素所在的列（表示该项任务不能（表示该项任务不能再指派给别人）再指派给别人） ；若该行无；若该行无“0 0”元素或有两个以上的元素或有两个以上的“0 0”元素（不含划去的元素（不含划去的0 0），则转下一行；），则转下一行；（2 2）从第一列开始，若该列只有一个）从第一列开始，若该列只有一个“0 0”元素，则对该元素，则对该“0 0”元素打括号（元素打括号（ ），并划去该），并划去该“0 0”元素所在的行；若该元素所在的行；若该列无列无“0 0”元素或有两个以上的元素或有两个以上的“0 0”元素（不含划去的元素（不含划去的0 0），），则转下一列；则转下一列；2022-4-2527（0）8251
17、1（0）5423（0）001145完成上述步骤后可能出现下列情况：完成上述步骤后可能出现下列情况：）效率矩阵的每一行都有一个打括号的效率矩阵的每一行都有一个打括号的0 0元素，则按照打元素，则按照打括号的括号的0 0元素位置指派任务，即是最优解；元素位置指派任务，即是最优解；）打括号的打括号的0 0元素个数小于元素个数小于m m，但未被划去的，但未被划去的0 0元素之间存元素之间存在闭回路，则沿此闭回路，每隔一个在闭回路，则沿此闭回路，每隔一个0 0元打一括号，然后对元打一括号，然后对打括号的打括号的0 0元素所在行或所在列画直线；元素所在行或所在列画直线；）矩阵中所有矩阵中所有0 0元素或被
18、打括号，或被划去，但打括号的元素或被打括号，或被划去，但打括号的0 0元素个数元素个数 ，则进入下一步；，则进入下一步；m2022-4-25280000000)0()0(00)0(3 3、设法使每一行都有一个打括号的设法使每一行都有一个打括号的“0 0”元素。按元素。按定理定理1 1继续对继续对矩阵进行变换：矩阵进行变换：）从矩阵未被直线覆盖的元素中找出最小者）从矩阵未被直线覆盖的元素中找出最小者k k，）对矩阵中无直线覆盖的行，令）对矩阵中无直线覆盖的行，令 ，有直线覆盖的列，有直线覆盖的列，令令 。其余为。其余为0 0。）对矩阵的每个元素计算）对矩阵的每个元素计算 ，得到一个新矩阵，得到一
19、个新矩阵，转第三步重复进行，直至每一行都有一打括号的转第三步重复进行，直至每一行都有一打括号的0 0元素。元素。kuikvjjiijvua2022-4-2529（0）82511（0）5423（0）001145根据上图，根据上图，k=2k=2，002254110003245011528020223211000542301130803211)0()0(05423)0(113)0(80最优解：最优解：2811944, 1, 1, 1, 134132241zxxxx2022-4-2530思考：思考：1 1、任务数、任务数 人数人数 时如何处理时如何处理 2 2、指派问题中目标函数变为、指派问题中目标函
20、数变为MAXMAX时如何处理时如何处理 两点说明两点说明1.1.效率矩阵不是方阵的情况。（即人员与工作数不效率矩阵不是方阵的情况。（即人员与工作数不相等）相等） 处理方法处理方法：增加虚拟人或工作，使两者相等。虚：增加虚拟人或工作，使两者相等。虚拟人或工作对应的效率矩阵中元素为拟人或工作对应的效率矩阵中元素为0 0。2.2.最大化分配问题的处理。最大化分配问题的处理。如果给出的效率矩阵中的数字表示每个人完成各项如果给出的效率矩阵中的数字表示每个人完成各项任务的收益，则问题变成了如何分配任务才能使总任务的收益，则问题变成了如何分配任务才能使总收益最大收益最大. .处理方法处理方法：用效率矩阵中的
21、最大元减去矩阵中的各：用效率矩阵中的最大元减去矩阵中的各个元素得到一个新的矩阵，对这个新的矩阵用匈牙个元素得到一个新的矩阵，对这个新的矩阵用匈牙利方法求解。利方法求解。练习练习1. 1. 用匈牙利方法求解下列问题用匈牙利方法求解下列问题例例1：设某工程有：设某工程有B1,B2,B3,B4 四项任务，需由四个工四项任务，需由四个工人人A1,A2,A3,A4去完成，由于任务性质和每个工人的技去完成，由于任务性质和每个工人的技术水平不相同，他们完成各项任务所需的时间也不一术水平不相同，他们完成各项任务所需的时间也不一样（见下表）。问应当如何分配，即哪个人去完成哪样（见下表）。问应当如何分配，即哪个人
22、去完成哪项任务，才能使完成四项任务的总时间最少？项任务，才能使完成四项任务的总时间最少？ 任务任务人员人员B1B2B3B4A1215134A21041415A39141613A478119设设10ijijxij 分分配配第第 人人完完成成第第 项项工工作作未未分分配配第第 人人完完成成第第 项项工工作作44114141min1,1,2,3,4. .1,1,2,3,410ijijijijjijiijza xxis txjx 或或效率矩阵：效率矩阵：2151341041415914161378119A 2151341041415914161378119A 效率矩阵效率矩阵第一步：初始变换第一步：初
23、始变换2151341041415914161378119249701311260101105740142004201370606905320100得解矩阵得解矩阵0001010010000010X 找独立找独立0 0元素元素01370606905320100总时间为总时间为: 4+4+9+11=28: 4+4+9+11=28练习练习2 2：用匈牙利解法解下列分配问题：用匈牙利解法解下列分配问题效率矩阵效率矩阵第一步：初始变换第一步：初始变换000001279798966671712149151466104107109127979896667171214915146610410710976764
24、5020223000010572980040636550202230000105729800406365第二步：寻找独立第二步：寻找独立0 0元素元素 最小元素为最小元素为 min10,5,7,2,6,3,6,5=2-2-2+270202430000835011800404143它有它有5 5个独立个独立0 0元，得到最优解相应的解矩阵为元，得到最优解相应的解矩阵为0100000010000010010010000最优目标值：最优目标值：7+6+9+6+4=32练习练习3：求解下列分配问题：求解下列分配问题效率矩阵效率矩阵10978587754652345 工作工作人员人员ABCD甲甲1097
25、8乙乙5877丙丙5465丁丁2345 109785877546523457542320103221021012300013200032110200122 -1-1+142000210202000114200021020200011第一组最优解第一组最优解00101000000101000010000101001000第二组最优解第二组最优解2022-4-25423 3 分枝定界法分枝定界法 分枝定界法分枝定界法是求解整数规划的一种常用的有效的方法，它是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问既能解决纯整数规划的问题，又能解决混合整数规划的问题。
26、题。 大多数求解整数规划的商用软件就是基于分枝定界法编大多数求解整数规划的商用软件就是基于分枝定界法编制而成的。制而成的。下面举例来说明分枝定界法的思想和步骤。下面举例来说明分枝定界法的思想和步骤。2022-4-2543性质性质 求求MAXMAX的问题的问题：整数规划的最优目标函数值整数规划的最优目标函数值小于或小于或等于等于相应的线性规划的最优目标函数值；相应的线性规划的最优目标函数值； 求求MINMIN的问题：的问题：整数规划的最优目标函数值整数规划的最优目标函数值大于或大于或等于等于相应的线性规划的最优目标函数值。相应的线性规划的最优目标函数值。1、求解整数规划相应的一般线性规划问题（即
27、先去掉整数、求解整数规划相应的一般线性规划问题（即先去掉整数约束）。约束）。 易知：整数规划的可行域（小）包含于线性规划的可行易知：整数规划的可行域（小）包含于线性规划的可行域域 (大）。大）。 若线性规划的最优解恰是整数解，则其就是整数规划的若线性规划的最优解恰是整数解，则其就是整数规划的最优解。否则该最优解，是整数规划最优解的上界或下界。最优解。否则该最优解，是整数规划最优解的上界或下界。2022-4-2544例：例： 求解下列整数规划：求解下列整数规划：并取整数, 0 x,x5 . 4x5 . 0 x14x3x2t . sx2x3zmax212121210,5 . 45 . 01432.
28、23max21212121xxxxxxtsxxz解：解：1 1、解对应的线性规划：、解对应的线性规划：其最优解为其最优解为 ，显然不是整数规划的可行显然不是整数规划的可行解。解。)5 . 2,25. 3(L0：75.140z2022-4-25452 2、分枝与定界：分枝与定界： 将对应的线性规划问题分解成几个子问题，每个子问将对应的线性规划问题分解成几个子问题，每个子问题就是一分枝，而所有子问题的解集之和要包含原整数规题就是一分枝，而所有子问题的解集之和要包含原整数规划的解集。划的解集。 求解每一分枝子问题：求解每一分枝子问题： 若其最优解满足整数约束，则它就是原问题的一个可行若其最优解满足整
29、数约束，则它就是原问题的一个可行解（不一定是最优）；否则，就是该枝的上界或下界。解（不一定是最优）；否则，就是该枝的上界或下界。 若所有分支的最优解都不满足整数条件（即不是原问题若所有分支的最优解都不满足整数条件（即不是原问题的可行解），则选取一个边界值最优的分支继续分解，直的可行解），则选取一个边界值最优的分支继续分解，直至找到一个原问题的可行解。至找到一个原问题的可行解。 若在同一级分枝中同时出现两个以上的原问题可行解，若在同一级分枝中同时出现两个以上的原问题可行解，则保留目标值最优的一个，其余不再考虑。则保留目标值最优的一个，其余不再考虑。从各分枝中找原问题可行解的目的是为下一步的比较与
30、剪枝。从各分枝中找原问题可行解的目的是为下一步的比较与剪枝。2022-4-2546将上述线性规划问题分为两枝，并求解。将上述线性规划问题分为两枝，并求解。5 .14, 2, 5 . 3121zxx解得5 .13, 3, 5 . 2221zxx解得L1：L2：0,25 . 45 . 01432.23max212212121xxxxxxxtsxxz0,35 . 45 . 01432.23max212212121xxxxxxxtsxxz显然两个分枝均非整数可行解，选边界值较大的显然两个分枝均非整数可行解，选边界值较大的L L1 1继续分继续分枝。枝。 2022-4-2547将将L1分为两枝，并求解。
31、分为两枝，并求解。13, 2, 3121zxx解得14, 1, 4221zxx解得L11：L12：0,325 . 45 . 01432.23max2112212121xxxxxxxxtsxxz两个分枝均是整数可行解，保留目标值较大的两个分枝均是整数可行解，保留目标值较大的L L1212。 0,425 . 45 . 01432.23max2112212121xxxxxxxxtsxxz2022-4-25483 3、比较与剪枝比较与剪枝 将各子问题的边界值与保留下的整数可行解对应的目将各子问题的边界值与保留下的整数可行解对应的目标值比较，将边界值劣于可行行解的分支减剪去。标值比较，将边界值劣于可行行
32、解的分支减剪去。 若比较剪枝后，只剩下所保留的整数可行解，则该解就若比较剪枝后，只剩下所保留的整数可行解，则该解就是原整数规划的最优解；否则选取边界值最大的一个分枝是原整数规划的最优解；否则选取边界值最大的一个分枝继续分解，在其后的过程中出现新的整数可行解时，则与继续分解，在其后的过程中出现新的整数可行解时，则与原可行解比较，保留较优的一个，重复第三步。原可行解比较，保留较优的一个，重复第三步。2022-4-2549L0：X22X23X13X14用图表示上例的求解过程与求解结果用图表示上例的求解过程与求解结果75.14, 5 . 2,25. 3121zxx5 .14, 2, 5 . 3121z
33、xx5 .13, 3, 5 . 2221zxx13, 2, 3121zxx14, 1, 4221zxx练习1：用分支定界法求解下列整数规划取整数2121212121,0,3121451149.maxxxxxxxxxtsxxz123123x1=3/2,分为x11与x12x11x12S2S1分别解之分别解之先放弃先放弃“整数整数”要要求求求出一个最优解。求出一个最优解。123123S1S2x11x12x22x23S12S11123123S12x11x12x22x23x12x13S121S122123123x11x12x22x23x12x13S121S1222022-4-25554 割平面法割平面法
34、 一、一、 基本思想基本思想 在整数规划的松弛问题中，依次引进新的约束条件在整数规划的松弛问题中，依次引进新的约束条件（割平面），使问题的可行域逐步减小，但每次割去（割平面），使问题的可行域逐步减小，但每次割去的只是部分非整数解，直到使问题的目标函数值达到的只是部分非整数解，直到使问题的目标函数值达到最优的整数点成为缩小后的可行域的一个顶点，这样最优的整数点成为缩小后的可行域的一个顶点，这样就可以用线性规划的方法求得整数最优解。就可以用线性规划的方法求得整数最优解。2022-4-2556例：例： 求解下列整数规划：求解下列整数规划：并取整数, 0,5 . 45 . 01432.23max212
35、12121xxxxxxtsxxz0,921432.23max21212121xxxxxxtsxxz解：解：1 1、解对应的线性规划（松弛问题），并将约束条件的系解对应的线性规划（松弛问题），并将约束条件的系数均化为整数：数均化为整数：2022-4-2557加入松弛变量后求解，得最终单纯形表：加入松弛变量后求解，得最终单纯形表：25/2011/2-1/2313/410-1/43/400-1/4-5/41x4x3x1x2x2xj如果上述求解结果是整数解，则结束；否则转下一步；如果上述求解结果是整数解，则结束；否则转下一步；2 2、找出非整数解中分数部分最大的一个基变量，并将该行找出非整数解中分数部
36、分最大的一个基变量，并将该行对应的约束方程所有常数（系数及常数项）分解成一个整数对应的约束方程所有常数（系数及常数项）分解成一个整数与一个正分数之和；将所有分式项移到等式右端。与一个正分数之和；将所有分式项移到等式右端。例如上例，取第一行约束例如上例，取第一行约束 2022-4-255843424324322121212212)211(21252121xxxxxxxxxx易知，左端为整数，要是等式成立，右端也必为整数，且易知，左端为整数，要是等式成立，右端也必为整数，且02121211212121214343xxxx将将 代入上式，得代入上式，得214213293214xxxxxx112221
37、 xx2022-4-25591x2x143221 xx5 . 45 . 021xx2123xxz)5 . 2,25. 3() 1, 4(112221 xx这就是一个割平面。将这就是一个割平面。将其添加到原约束中，得其添加到原约束中，得到新的可行域如图所示。到新的可行域如图所示。割去的只是部分非整数割去的只是部分非整数解。解。112221 xx2022-4-25603 3、将新的约束添加到原问题中，得到一个新的线性规划问将新的约束添加到原问题中，得到一个新的线性规划问题，求解此问题，可用灵敏度分析的方法。题，求解此问题，可用灵敏度分析的方法。4 4、重复上述的重复上述的1-31-3步，直至求出整
38、数最优解。步，直至求出整数最优解。25/2011/2-1/20313/410-1/43/400-1/200-1/2-1/2100-1/4-5/40212121021212154343xxxxx将将 反应到最终表中，得反应到最终表中，得1x4x3x1x2x2xj5x5x2022-4-2561运用对偶单纯形法，解得运用对偶单纯形法，解得22010-11/231001-1/2010011-2000-1-1/21x4x3x1x2x2xj3x5x213此解仍非整数解，将基变量此解仍非整数解，将基变量 对应的约束分解为：对应的约束分解为： 1x55415412121321321xxxxxxx得到新的约束得
39、到新的约束 212102121655xxx2022-4-256222010-11/2031001-1/20010011-200-1/20000-1/21000-1-1/201x4x3x1x2x2xj3x5x2136x21010-1023410010-10300110-40100001-2000-10-11x2x3x5x此时已得整数最优解。此时已得整数最优解。2022-4-25631x2x143221 xx5 . 45 . 021xx2123xxz)5 . 2,25. 3() 1, 4(521 xx521 xx021215x约束约束即为即为用割平面法求解整数规划问题用割平面法求解整数规划问题 且
40、为整数且为整数0,023623 max2121212xxxxxxxZ解：增加松弛变量解：增加松弛变量x3和和x4 ，得到得到(LP)的初始单纯形表和的初始单纯形表和最优单纯形表：最优单纯形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201Z00100Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4Z-3/200-1/4-1/4)4141(2112114141234141432432432xxxxxxxxx0)4141(21 43 xx将将 x3=6-3x1-2x2 , x4=3x1-2x2 ,带入带入 中，中，得到等价
41、的割平面条件：得到等价的割平面条件： x2 1 见下图。见下图。21414143 xxx1x233第一个割平面第一个割平面Cj01000CBXBbx1x2x3x4s10 x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41Z-3/200-1/4-1/40现将生成的割平面条件加入松弛变量，然后加到表中：现将生成的割平面条件加入松弛变量，然后加到表中：214141143 sxxCBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4Z-10000-1 此时，此时，X1 (2/3, 1), Z=1,仍不是整数解。
42、继续以仍不是整数解。继续以x1为源为源行生成割平面，其条件为：行生成割平面，其条件为：32323214 sx 用上表的约束解出用上表的约束解出x4 和和s1 ，将它们带入上式得到等价将它们带入上式得到等价的割平面条件：的割平面条件：x1 x2 ，见图：见图：x1x233第一个割平面第一个割平面第二个割平面第二个割平面将生成的割平面条件加入松弛变量，然后加到表中：将生成的割平面条件加入松弛变量，然后加到表中：323232214 ssxCBXBbx1x2x3x4s1s20 x12/3100-1/32/301x210100100 x320011-400s2-2/3000-2/3-2/31Z-1000
43、0-10CBXBbx1x2x3x4s1s20 x1110001-1/21x210100100 x310010-53/20 x4100011-3/2Z-10000-10 至此得到最优表，其最优解为至此得到最优表，其最优解为 X= (1 , 1) , Z = 1, 这这也是原问题的最优解。也是原问题的最优解。 有以上解题过程可见，表中含有分数元素且算法过有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。数对偶割平面算法。 且且为为整整数数0, 205462max21212121xxxxxxxxZ
44、Cj1100CBXBbx1x2x3x40 x3621100 x4204501Z1100CBXBbx1x2x3x41 x15/3105/61/61x28/3012/31/3Z-13/3001/61/6初初始始表表最最优优表表在松弛问题最优解中，在松弛问题最优解中，x1, x2 均为非整数解，由上表均为非整数解，由上表有：有：383132356165432431 xxxxxx将系数和常数都分解成整数和非负真分数之和将系数和常数都分解成整数和非负真分数之和 32231)311(321)651(65432431 xxxxxx 以上式子只须考虑一个即可，解题经验表明，考虑以上式子只须考虑一个即可，解题经
45、验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右任选一个考虑。现选第二个式子，并将真分数移到右边得：边得： )(313224332xxxx 32)(3143 xx引入松弛变量引入松弛变量s1 后得到下式，将此约束条件加到上表后得到下式，将此约束条件加到上表中，继续求解。中，继续求解。 323131143 sxxCj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012
46、/31/300s12/3001/31/31Z13/3001/61/60Cj11000CBXBbx1x2x3x4s11 x10100101x24010120 x3200113Z400001/2 得到整数最优解，即为整数规划的最优解，而且此整数规划得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：有两个最优解： X= (0, 4), Z = 4, 或 X= (2, 2), Z = 4。 5 0-1规划的求解规划的求解 隐枚举法隐枚举法n解 01 规划的隐枚举法有其独特的工作程序，具体过程如下。na. 模型转化为求极小的问题模型转化为求极小的问题nb. 变量替换。极小问题模型的目标函
47、数中所有变量系变量替换。极小问题模型的目标函数中所有变量系数为负的数为负的01变量，可利用变量替换变量，可利用变量替换xk=1xk (xk 是引是引入的新的入的新的01变量变量)，将目标函数中所有变量系数化为正，将目标函数中所有变量系数化为正数。数。nc. 目标函数中变量按系数大小排列，约束条件中变量目标函数中变量按系数大小排列，约束条件中变量排列顺序也相应调整。排列顺序也相应调整。nd. 按目标函数值由小到大的顺序依次排列可能的解，按目标函数值由小到大的顺序依次排列可能的解，并予以可行性检验。并予以可行性检验。ne. 发现求极小问题的最优解并停止。发现求极小问题的最优解并停止。nf. 转化为
48、原问题的最优解。转化为原问题的最优解。 01 整数规划是一种特殊形式的整数规划，这时整数规划是一种特殊形式的整数规划，这时的决策变量的决策变量xi 只取两个值只取两个值0或或1，一般的解法为，一般的解法为隐枚举隐枚举法法。 转化为求极小的问题转化为求极小的问题 Min Z=Min Z=3 3x x1 12 2x x2 25 5x x3 32 2x x4 43 3x x5 5 x x1 1 x x 2 2 x x3 32 2x x4 4 x x5 54 4 7 7x x1 1 3 3x x3 34 4x x 4 43 3x x5 58 8 1111 x x1 1 6 6x x2 2 3 3x x
49、4 4 5 5x x5 53 3 x xj j =0, 1, =0, 1, j j=1, 2, 3, 4, 5.=1, 2, 3, 4, 5. 令令x x 1 1=1=1x x1 1, , x x 2 2=1=1x x2 2, , x x 5 5=1=1x x5 5, , 带入极小问题模型中，得带入极小问题模型中，得 Min Z=3Min Z=3 x x 1 12 2 x x 2 25 5x x3 32 2x x4 43 3 x x 5 58 8 x x 1 1 x x 2 2 x x3 32 2x x4 4 x x 5 51 1 7 7 x x 1 1 3 3x x3 34 4x x 4 4
50、3 3x x 5 52 2 1111x x 1 1 6 6x x 2 2 3 3x x 4 45 5x x 5 57 7 x xj j =0, 1, =0, 1, j j= 3, 4; = 3, 4; x x j j =0, 1, =0, 1, j j= 1, 2, 5. = 1, 2, 5. 目标函数中变量按系数大小排列，约束条件中变量排列顺序也相应调整，得目标函数中变量按系数大小排列，约束条件中变量排列顺序也相应调整，得Min Z=5Min Z=5x x3 33 3 x x 1 13 3 x x 5 52 2 x x 2 22 2x x4 48 8 x x3 3 x x 1 1 x x 5
