运筹学整数规划补例

《运筹学整数规划补例》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学难点辅导材料整数规划补例1、对（IP）整数规划问题，问用先解相应的线性规划然后凑整的办法能否求到最优整数解？再用分支定界法求解。解先不考虑整数约束，得到线性规划问题（一般称为松弛问题LP）用图解法求出最优解且。如用“舍入取整法”凑整可得到四个点，即（1，3）、（2，3）、（1，4）、（2，4）。代入约束条件发现他们都不是可行解。可将可行域内的所有整数点一一列举（完全枚举法），本例中（2，2）、（3，1）点为最大值。令及最优值。可行域记为D，显然不是整数解。定界：取，再用视察法找一个整数可行解及，取，即分支：（关键点，在B的最优解中任选一个不

2、符合整数条件的变量，其值为，构造两个约束条件，这里用了取整函数呵！）任取最优解中一个不为整数的变量值，例如，根据，构造两个约束条件，形成下面两个子问题（IP1）和（IP2）第24页（共24页）解（IP1）和（IP2），得最优解分别为和，这两个都不是符合整数条件的可行解。修改上下界：根据个分支的最优解，可取新的上界，再分支：由于，故先对（IP2）进行分支，取，根据，构造两个约束条件，形成下面两个子问题（IP3）和（IP4）。解相应的松弛问题（IP3）和（IP4），得（IP4）无可行解，（IP3）的最优解为。在考虑（IP1），由（IP1）的最优解，取

3、，根据，构造两个约束条件，形成下面两个子问题（IP5）和（IP6），得（IP6）无可行解，（IP5）的最优解为。在修改上下界：根据上述两个最优解的情况，有再分支：由（IP3）的最优解，取，根据第24页（共24页），构造两个约束条件，形成下面两个子问题（IP7）和（IP8），得（IP7）的最优解为，（IP8）的最优解为。重新定界：由于的最优解为为整数解，且，故2、对整数规划问题，问用先解相应的线性规划然后凑整的办法能否求到最优整数解？解用单纯形法解对应的LP问题，求到最优解当凑为时，为可行解，；当凑为时，为非可行解；当凑为时，为非可行解；当凑为时，

4、为非可行解；下面用分支定界法来解整数规划问题。令，显然为可行解，从而。将原问题分解为下面两个子问题（用分支，复杂些，不妨去试试！）（IP1）和（IP2）（IP1）的最优解为和（IP2）的为因为，所以，且为整数，则为最优解。第24页（共24页）3、用割平面法求解解引入松弛变量和人工变量及一个充分大的数，先解一个大问题：作初始单纯形表，并进行迭代运算3-1000CB基XB常数033*-2100010540-10105210010，检.0000311-2/31/30005022/3*-5/3-1010307/3-2/3010，检0000316/1110

5、2/11-1/1101/11-115/2201-5/22-3/2203/22031/2200-3/227/22*1-7/22第24页（共24页），检00-17/220313/7101/702/70-19/701-2/703/70031/700-3/7122/7-1，检00-3/70略去人工变量，得最终单纯形表3-1000CB基XB常数313/7101/702/7-19/701-2/703/7031/700-3/7122/7检00-5/7-3/7再略去松弛变量，最优解为，显然不是整数规划的最优解。引进以行为源行的割平面，即，再将变形代入得（该割平面

6、确实割去了松弛问题最优解为，但未割去原问题的任一整数可行点。）引入松弛变量，化为写入上表，得3-10000CB基XB常数313/7101/702/70第24页（共24页）-19/701-2/703/70031/700-3/7122/700-6/700-1/70-2/7*1，检00-5/70-3/7031100001-1001-1/2003/20-500-2*101103001/201-7/2，检00-1/200-3/231100001-15/4010-1/40-5/405/2001-1/20-11/207/40001/41-3/4检验数000-1

7、/40-17/4再略去松弛变量，最优解为，显然仍不是整数规划的最优解。继续作割平面，以行为源行的割平面，利用四个等式约束即可化为，（该割平面确实割去了松弛问题最优解为，也未割去原问题的任一整数可行解。）引入松弛变量，化为写入上表，3-100000CB基XB常数第24页（共24页）311000010-15/4010-1/40-5/4005/2001-1/20-11/2007/40001/41-3/400-3/4000-1/4*0-1/41检验数000-1/40-17/40311000010-1201000-1-10400100-5-20100001

8、-1103000101-4检验数00000-4-1解得4、用割平面法求解解引入松弛变量，得到对应LP问题的初始单纯形表计算如下：0100