运筹学整数规划补例.doc

运筹学难点辅导材料整数规划补例1、对（IP）整数规划问题，问用先解相应的线性规划然后凑整的办法能否求到最优整数解？再用分支定界法求解。解 先不考虑整数约束，得到线性规划问题（一般称为松弛问题LP）用图解法求出最优解且。如用“舍入取整法”凑整可得到四个点，即（1，3）、（2，3）、（1，4）、（2，4）。代入约束条件发现他们都不是可行解。可将可行域内的所有整数点一一列举（完全枚举法），本例中（2，2）、（3，1）点为最大值。令及最优值。可行域记为D，显然不是整数解。定界：取，再用视察法找一个整数可行解及，取，即分支：（关键点，在B的最优解中任选一个不符合整数条件的变量，其值为，构造两个约束条件，这里用了取整函数呵！）任取最优解中一个不为整数的变量值，例如，根据，构造两个约束条件，形成下面两个子问题（IP1）和（IP2）解（IP1）和（IP2），得最优解分别为和，这两个都不是符合整数条件的可行解。修改上下界：根据个分支的最优解，可取新的上界，再分支：由于，故先对（IP2）进行分支，取，根据，构造两个约束条件，形成下面两个子问题（IP3）和（IP4）。解相应的松弛问题（IP3）和（IP4），得（IP4）无可行解，（IP3）的最优解为。在考虑（IP1），由（IP1）的最优解，取，根据，构造两个约束条件，形成下面两个子问题（IP5）和（IP6），得（IP6）无可行解，（IP5）的最优解为。在修改上下界：根据上述两个最优解的情况，有再分支：由（IP3）的最优解，取，根据，构造两个约束条件，形成下面两个子问题（IP7）和（IP8），得（IP7）的最优解为，（IP8）的最优解为。重新定界：由于的最优解为为整数解，且，故2、对整数规划问题，问用先解相应的线性规划然后凑整的办法能否求到最优整数解？解 用单纯形法解对应的LP问题，求到最优解当凑为时，为可行解，；当凑为时，为非可行解；当凑为时，为非可行解；当凑为时，为非可行解；下面用分支定界法来解整数规划问题。令，显然为可行解，从而。将原问题分解为下面两个子问题（用分支，复杂些，不妨去试试！）（IP1）和（IP2）（IP1）的最优解为和（IP2）的为因为，所以，且为整数，则为最优解。3、用割平面法求解解 引入松弛变量和人工变量及一个充分大的数，先解一个大问题：作初始单纯形表，并进行迭代运算3-1000CB基XB常数033 *-2100010540-10105210010，检.0000311 -2/31/30005022/3 *-5/3-1010307/3-2/3010，检0000316/111 02/11-1/1101/11-115/2201 -5/22-3/2203/22031/2200-3/227/22 *1-7/22，检00-17/220313/71 01/702/70-19/701 -2/703/70031/700-3/7122/7-1，检00-3/70略去人工变量，得最终单纯形表3-1000CB基XB常数313/71 01/702/7-19/701 -2/703/7031/700-3/7122/7检00-5/7-3/7再略去松弛变量，最优解为，显然不是整数规划的最优解。引进以行为源行的割平面，即，再将变形代入得（该割平面确实割去了松弛问题最优解为，但未割去原问题的任一整数可行点。）引入松弛变量，化为写入上表，得3-10000CB基XB常数313/71 01/702/70-19/701 -2/703/70031/700-3/7122/700-6/700-1/70-2/7 *1，检00-5/70-3/70311 00001-1001 -1/2003/20-500-2 *101103001/201 -7/2，检00-1/200-3/2311 00001-15/401 0-1/40-5/405/2001 -1/20-11/207/40001/41 -3/4检验数000-1/40-17/4再略去松弛变量，最优解为，显然仍不是整数规划的最优解。继续作割平面，以行为源行的割平面，利用四个等式约束即可化为，（该割平面确实割去了松弛问题最优解为，也未割去原问题的任一整数可行解。）引入松弛变量，化为写入上表，3-100000CB基XB常数311 000010-15/401 0-1/40-5/4005/2001 -1/20-11/2007/40001/41 -3/400-3/4000-1/4 *0-1/41检验数000-1/40-17/40311 000010-1201 000-1-104001 00-5-20100001 -1103000101-4检验数00000-4-1解得4、用割平面法求解解 引入松弛变量，得到对应LP问题的初始单纯形表计算如下：0100CB基XB常数06321000-3201 检验数010006601-110-3/2101/2 检验数3/200-1/201101/6-1/613/2011/41/4 检验数00-1/4-1/4此时LP问题的最优解，但不是整数最优解。引入割平面。以为源行，所以生成割平面，利用两个等式约束解出代入即可化为等价割平面现将生成的割平面条件加入松弛变量，然后得到下表01000CB基XB常数01101/6-1/6013/2011/41/400-1/200-1/4-1/41 检验数00-1/4-1/4002/3100-1/32/31101001020011-4 检验数0000-1此时LP问题的最优解，但仍不是整数最优解。引入割平面。以为源行，所以生成割平面，利用三个等式约束解出代入即可化为等价割平面现将生成的割平面条件加入松弛变量，然后得到下表01000CB基XB常数02/3100-1/32/3011010010020011-400-2/3000-2/3-2/31 检验数0000-100110001-1/211010010010010-53/20100011-3/2 检验数0000-10此时LP问题的最优解，是整数最优解，所以是原问题的最优解。（从解题过程可见，表中含有分数元素且算法过程始终保持对偶可行性，因此这个算法也称为分数对偶割平面算法）5、用割平面法求解解 引入松弛变量，得到对应LP问题的初始单纯形表计算如下：1100CB基XB常数0621100204501 检验数1100 026/501-1/5144/5101/5 检验数1/500-1/515/3105/6-1/618/301-2/31/3 检验数00-1/6-1/6此时LP问题的最优解，但不是整数最优解。引入割平面。由于与的右端的真分数相等，可任选（如果不等，根据经验选其中较大的一个式子效果较好）。现在以为源行，所以生成割平面，利用两个等式约束解出代入即可化为等价割平面现将生成的割平面条件加入松弛变量，然后得到下表11000CB基XB常数15/3105/6-1/6018/301-2/31/300-2/300-1/3-1/31 检验数00-1/6-1/6010100-15/2140101-2020011-3 检验数0000*-1/2得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解或。6、求解下列0-1规划问题解 用观察法求一个可行解。易看出是一个可行解，对应。由于目标函数求最大，故凡是目标函数值小于这个3的都不必讨论，于是有了一个过滤性条件约束 *优先考虑过虑性条件*，若遇到Z值超过过虑性条件右边的值，则应修改过虑性条件，继续做，列表如下：（最好重排的顺序，使目标函数中的系数保持不减,为最快！）约束条件左边值满足与否Z值*1234(0,0,0)0不满足(0,0,1)5-1101满足5(0,1,0)-2不满足小于5不需讨论(0,1,1)315不满足小于5不需讨论(1,0,0)31110满足小于5不需讨论3(1,0,1)80211满足8(1,1,0)11不满足小于8不需讨论(1,1,1)6626不满足小于8不需讨论用过滤法（隐枚举法的一种）求解过程可以列表简化表示Z值约束条件满足与否过滤条件*123(0,0,0) 0满足满满满(0,0,1)5满足满满满(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)8满足满满满(1,1,0)1(1,1,1)67、求解下列0-1规划问题解 用观察法求一个可行解。易看出是一个可行解，对应。由于目标函数求最小，故凡是目标函数值大于这个2的都不必讨论，于是有了一个过滤性条件约束 *优先考虑过虑性条件*，列表如下：最优解，目标函数最优值约束条件满足与否Z值*123(0,0,1)满足满满满2(0,0,0)满足满不(0,1,0)不(0,1,1)不(1,0,0)不(1,0,1)不(1,1,0)不(1,1,1)不8、求解下列0-1规划问题解 用观察法求一个可行解。易看出是一个可行解，对应。由于目标函数求最小，故凡是目标函数值大于这个2的都不必讨论，于是有了一个过滤性条件约束 *优先考虑过虑性条件*，列表如下：最优解，目标函数最优值约束条件满足与否Z值*123(0,1,0,0)满足满满满4(0,0,0,0)满足满不(0,0,0,1)满不(0,0,1,0)满满不(0,0,1,1)不(0,1,0,1)不(0,1,1,0)不(0,1,1,1)不(1,0,0,0)不(1,0,0,1)不(1,0,1,0)不(1,0,1,1)不(1,1,0,0)不(1,1,0,1)不(1,1,1,0)不(1,1,1,1)不9、求解下列0-1规划问题解 由于目标函数中变量的系数均为负数，可作如下变换，再调整次序：；，可以从开始试算，为最优解。所以，进而10、求解下列0-1规划问题解 令，得到下式，计算过程见下表约束条件满足与否Z值12是否满足(0,0,0,0,0)00否(1,0,0,0,0)1-1否(0,1,0,0,0)-11否(0,0,1,0,0)-21否(0,0,0,1,0)4-4满足8(0,0,0,0,1)3-2否所以为最优解，原问题的最优解为最优解。由于采用了上述算法，实际只作了20次计算！11、用隐枚举法求解下列0-1规划问题解 令，将模型化为标准形式如下：求解过程如右图所示。由，知最优解12、设有甲乙丙丁四个工人，要指派他们分别完成ABCD四项工作，每个人做各项工作所消耗的时间如下表。问如何分配工作才能使总耗费时间最小？试用匈牙利法求解。人 费用 工作ABCD甲15182124乙19232218丙26171619丁19212317解 系数矩阵为1）从系数矩阵的每行元素减去该行的最小元素，得2）从B的每列元素减去该列的最小元素，得，此时系数矩阵A的每行每列都有元素0。第2步：进行试分配，求初始分配方案，得的数目，试指派不成功，转入下一步。第3步：寻找覆盖所有零元素的最少直线，以确定最多零元素的个数。得覆盖所有零元素的最小直线数（矩阵的阶数）第4步：调整，使之增加一些零元素。为此，先找出没有被直线覆盖的元素中的最小元素，然后对绿线未覆盖区所有元素减去1，而绿线覆盖区的交叉元素加1，将变为再返回第二步。进行试分配，得再进行第三步，寻找覆盖所有零元素的最少直线，得覆盖所有零元素的最小直线数。再进行第4步：调整，使之增加一些零元素。为此，先找出没有被绿线覆盖的元素中的最小元素，然后将变为再返回第二步。进行试分配，得于是已求得最优解，其余，即甲B，乙A，丙C，丁-D。目标函数值为。注意：这个问题的最优解不惟一，例如甲A，乙D，丙C，丁B也有最优值15+18+16+21=70。13、设有5项工作ABCDE，需要分配甲乙丙丁戊五个人去完成，每个人只能完成一项工作，每件工作只能由1人去完成。5个人个人分别完成各项工作所需费用如下表。问如何分配工作才能使总费用最省？试用匈牙利法求解。人 费用 工作ABCDE甲759811乙9127119丙85468丁73696戊467511解 先将收益矩阵作如下变换第2步：进行试分配，求初始分配方案，得第3步：寻找覆盖所有零元素的最少直线，以确定最多零元素的个数。得覆盖所有零元素的最小直线数（矩阵的阶数）第4步：调整，使之增加一些零元素。为此，先找出没有被直线覆盖的元素中的最小元素，然后将变为再返回第二步。进行试分配，得再进行第三步，寻找覆盖所有零元素的最少直线，得覆盖所有零元素的最小直线数。再进行第4步：调整，使之增加一些零元素。为此，先找出没有被直线覆盖的元素中的最小元素，然后将变为再返回第二步。进行试分配，得，此时，独立零元素的个数。于是已求得最优解，其余。目标函数值为。注意，甲乙丙丁四个工人，要指派他们分别完成ABCD这个问题有多个最优解，例如也是最优解。14、某地区从电网中分配得到的电力共有6GW，可用于工业，而该地区有机械、化工、轻纺、建材四大部类，各部类获得电力以后，可以为该地区提供的利润如下表。问应该如何分配电力可使该地区所获得的利润达到最大？（改为六人四项任务，即为指派问题）电力/GW 利润/万元 部类机械化工轻纺建材135452676838981041010911512111012613121113解 显然，这是一个非平衡的分配问题，虚设两个工业部类I,II，而令虚设的部类为该地区提供的利润为0，即可得到平衡分配问题的利润矩阵目标函数为，由式将目标函数变为极小化问题，于是有，先将它变换为再进行试分配，得再画线，得最小直线数（矩阵的阶数），故需调整。先求出未被直线覆盖的元素中的最小元素，调整得，进而再进行试分配，得，再画线，得最小直线数，故还需调整。先求出未被直线覆盖的元素中的最小元素，调整得，进而再进行试分配，得，即得最优解，其余。目标函数值为。15、设有5项工作ABCDE，需要分配甲乙丙丁四个人去完成，由于工作任务数多于人数，故考虑：（1）任务E必须完成，其它四项任务中可以任选3项完成；（2）其中有一人完成两项其它每人完成一项。四个人分别完成各项工作所需费用如下表。试分别确定最优分配访案，使完成任务的总时间最少。人 费时 工作ABCDE甲2529314237乙3938262033丙3427284032丁2442362345解 （1）由于任务数多于人数，所以需要一名假想人，设为戊，因为任务E必须完成，故设戊完成E的时间为M ( M为非常大的数) ，其余的假想时间为0 ，建立效率矩阵如下：人 费时 工作ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊0000M用匈牙利法求解过程如下：得最优解，其余，即甲B，乙D，丙E，丁A,，C放弃。目标函数值为小时。（2）由于所有任务都必须由甲乙丙丁完成，所以假想的人戊的效率应该对每项工作而言，都是完成它的最好的人，而不能假设为0值，所以建立效率矩阵如下：人 费时 工作ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊2427262032用用匈牙利法求解，可得最优解，其余，最佳分配方案为甲B，乙C和D，丙E，丁A,。目标函数值为小时。16、某车间需加工4种零件，它们可由车间的四台机床加工，但第一种零件不能由第三台机床加工，第二种零件不能由第四台机床加工，各机床加工零件的费用如下表。问如何安排加工任务才能使加工费最小？零件 费用 / 机床1234155227423393547267解 这是一个分配问题，机床不能加工的零件费用记为，于是费用矩阵成为，利用求分配问题的匈牙利法，解答过程如下：费用矩阵的每行减去该行最小元素，得上述相对费用矩阵的每列减去该列最小元素，得用三条直线可以划去所有含零的行和列，需继续迭代上述相对费用矩阵要用四条直线才能划去含零的行和列，因此可得最优分配表。由表可知零件1由4号、2由3号、3由2号、4由1号机床加工。17、一个公司经理要派4个推销员到4个地区去推销某种商品。四个推销员各有不同的经验和能力，从而他们在每一地区能获得的利润不同，其估计值如下表所示。公司经理应怎样分派四个推销员才能使公司利润最大？推销员 利润 / 地区1234135272837228342940335243233424322528解 由于，等价于，因而利润矩阵可为，用求分配问题的匈牙利法，解答过程如下：由表可知推销员1负责1号地区、2负责4号地区、3负责3号地区、4负责2号地区总利润最大，为35+40+32+32=139。18、某厂为它的一个车间购置了3