《华中科技大学 运筹学资料[2008终结版本]》由会员分享，可在线阅读，更多相关《华中科技大学 运筹学资料[2008终结版本]（73页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学管理学院考研运筹盟 第 1 页 共 73 页 管理学院考研运筹盟 运筹学复习资料（基础版本） 管理学院考研运筹盟 运筹学复习资料（基础版本） 目 录 目 录 第三章：线性规划的对偶理论.2 第四章：灵敏度分析与参数规划.7 第五章：运输问题.18 相关历年真题收集.18 第六章：目标规划.19 相关历年真题收集：.23 第七章：整数规划.24 相关历年真题收集:.35 第八章：动态规划.36 第九章：图与网络分析.41 相关历年真题收集：.41 第十章：存贮论.43 相关历年真题收集：.46 2002 年运筹学真题解答过程47 2004 年运筹学真题解答过程50 2005 年运筹学
2、真题解答过程54 2006 年运筹学真题解答过程59 2007 年运筹学真题解答过程63 附录一：文字表述题：.66 附录二：复习心得.68 附录三：各章节题型小节.69 附录四：隐枚举法.70 附录五：最小费用最大流问题.71 后记 73 华中科技大学管理学院考研运筹盟 第 2 页 共 73 页 第三章：线性规划的对偶理论 第三章：线性规划的对偶理论 对应书本：134-138 细节： 1、 原问题转化为对偶问题的方法； 2、 弱对偶性、主对偶、互补松弛定理的应用； 3、 单纯形表格的补充； 4、 应用对偶单纯形法。 省略： 1、 对偶单纯形法中初始正则解的求法； 2、 原始对偶单纯形法的应用
3、； 3、 其他非真题题型。 第三章习题解： 1、 原问题： 123 123 123 123 200300250 34260 2240 . . 3320 0;(i=1,2,3) MaxZXXX XXX XXX st XXX Xi =+ += += += = 转化记忆方法：MAX：变量+约束 2、 （1） 、对偶问题为： 10 120 2 14 210 121 . . 2 122 120 MinWyy yy yy st yy yy =+ += += += = 、 （2） 、对偶问题为： 2 125 3 2 1 3 232 3 124 31 . . 5 1 7 26 32 10230 MaxWyyy
4、 yyy yyy st yyy yyy =+ += = = 、 基本结构分析表： C11 C12 C1n C21 C22 C2n Cm1Cm2 Cmn X11 X12 X1n X21 X22 X2n Xm1Xm2 Xmn 1 1 1 a1 1 1 a2 1 1 b1 1 1 b2 1 1 1 bm 对偶问题的目标函数： 11 nm j ji ni ji MinWayby+ = =+ 华中科技大学管理学院考研运筹盟 第 3 页 共 73 页 约束条件： 1111 2112 11 1221 2222 n n nnn n n yyC yyC yyC yyC yyC + + + + + += = +=
5、 = = 、 原问题有X（0，2）符合条件； 对偶问题有Y（0，1，0）符合条件，根据主对 偶定理其原问题和对偶问题都有最优解。 7、 . . 0 MaxZCX AXb st X = = = . . MinWYb YAC st Y = = 无约束 因为原问题有最优解，故 YA=C 成立 当 b 改为 d 后，原问题和对偶问题都有可行解，故 该问题一定有最优解。 9、 （1） 、对偶问题： 5 1 12 2MinWyy=+ 12 22 1 3 21 . . 2 14 23 102 yy yy st yy yy += += += = 、无约束 （2） 、原问题的最优解为：X*（3，2，0） 代入原
6、约束： 32 5 2*33*2 12 + + 并且对偶问题约束为紧约束，为松约束。 所以： 12 22 1 3 21 yy yy += += 14 21 y y = = （3） 、第一种约束的影子价格为 4 *提醒*提醒：影子价格的来源（1）表格法Cj j ;（2）求解对偶问题 10、 20 120 2MinWyy=+ 12 21 2 122 . . 2 1 3 23 3 12 24 120 yy yy styy yy yy += += += += = 、 Y*（1，2，0，2） 将对偶问题最优解代入： 1.20.41 2.40.22 2.40.63 3.60.44 + + += += 所以
7、X1、X20 且 233420 332420 XX XX += += X34、X44 所以 X*（0，0，4，4） Z*28 11、 （1） 、 3 16 22 32 4MaxWyyyy=+ 1 3 248 2 126 . .2343 1236 0;(12 3 4) yyy yy styyy yyy yii +2 40, 12 1 3 248 22 2 126*20 31 233 40 y y yyy y yyW y yy y = = += = += = += = 且对偶问题的第四个约束为松约束 华中科技大学管理学院考研运筹盟 第 5 页 共 73 页 12、B -1 1/ 20 1/61/3
8、 = 还原矩阵 5/ 201/ 211/ 20 5/ 211/ 201/61/3 501220 15/ 233/ 201/ 21 501210 1031101 jC C1 C2 C3 0 0 BC BX b X1 X2 X3 X4 X5 0 X4 5 0 1 2 1 0 0 X5 10 3 -1 1 0 1 由表中：i=（0，-1/4，0，-4，-2）得 () 1/ 20 ( 3, 1)*4,216,310 1/61/3 CCCC = C2-y2*C3+y2*C1=-4C2=-2 整理后为： （1） 、原问题为：6 1 2 2 10 3MaxZxxx=+ 22 35 . . 3 12310 1
9、230 xx stxxx xxx += = += = 、 （3） 、y1*4 y2*2 13、 （1） 、对偶问题为： 4 16 2MaxWyy=+ 122 121 . . 122 120 yy yy st yky yy = += += = 、无约束 （2） 、将 X*（14，0，-4）代入原约束 14418 2*143*416 14410 = += 可得 （2） 、y*（5，0，23） W*53 华中科技大学管理学院考研运筹盟 第 6 页 共 73 页 17、 （1） 、 jC -10 -5 -4 0 0 BC BX b X1 X2 X3 X4 X5 0 X4 -3 -3 -2 3 1 0
10、0 X5 -10 -4 0 -2 0 1 0 X4 -18 -9 -2 0 1 3/2 -4 X3 5 2 0 1 0 -1/2 -2 -5 -10 X1 2 1 2/9 0 -1/9 -1/6 4 X3 1 0 -4/9 1 2/9 -1/6 0 -41/9 0 -2/9 -7/3 X*（2，0，1） Z*-24Z24 （2） 、 jC -2 -1 0 0 0 BC BX b X1 X2 X3 X4 X5 0 X3 -3 -3 -1 1 0 0 0 X4 -6 -4 -3 0 1 0 0 X5 3 1 2 0 0 1 0 X3 -1 -5/3 0 1 -1/3 0 -1 X2 2 4/3 1
11、 0 -1/3 0 0 X5 -1 -5/3 0 0 2/3 1 -2 X1 3/5 1 0 -3/5 1/5 0 -1 X2 6/5 0 1 4/5 -3/5 0 0 X5 0 0 0 -1 1 1 0 0 -2/5 -1/5 0 X*（3/5，6/5） Z*=-12/5Z=12/5 （3） 、 jC -3 -2 -1 0 0 0 BC BX b X1 X2 X3 X4 X5 X6 0 X4 6 1 1 1 1 0 0 0 X5 -4 -1 0 1 0 1 0 0 X6 -3 0 -1 1 0 0 1 0 X4 2 0 1 2 1 1 0 -3 X1 4 1 0 -1 0 -1 0 0 X6
12、 -3 0 -1 1 0 0 1 0 0 -4 0 -3 0 0 X4 -1 0 0 3 1 1 1 -3 X1 4 1 0 -1 0 -1 0 -2 X2 3 0 1 -1 0 0 -1 0 0 -6 0 -3 -2 故无可行解 （4） 、 jC -5 -2 -4 0 0 BC BX b X1 X2 X3 X4 X5 0 X4 -4 -3 -1 -2 1 0 0 X5 -10 -6 -3 -5 0 1 0 X4 -2/3 -1 0 -1/3 1 -1/3 -2 X2 10/3 2 1 5/3 0 -1/3 -1 0 -2/3 0 -2/3 -5 X1 2/3 1 0 1/3 -1 1/3 -
13、2 X2 2 0 1 1 2 -1/3 X*（2/3，2，0） Z*-22/3 Z22/3 华中科技大学管理学院考研运筹盟 第 7 页 共 73 页 第四章：灵敏度分析与参数规划 第四章：灵敏度分析与参数规划 对应书本 169-174 页 细节： 1、B -1的挖掘和应用 2、基变量系数的变化范围 3、最终单纯形表中影子价格的挖掘和利用 习题勘误（仅作参考） 1、3（1）15/40 jC BC BX b X1 X2 X3 X4 X5 14+3 X2 6 1/6 1 0 2/3 -1/6 13 X3 12 1/6 0 1 -1/3 1/3 (3-)/20 0 -（5+2） -2+1/2 3 b2
14、9/2，15 （3） 、 jC 12 4 0 0 BC BX b X1 X2 X3 X4 4 X2 3/2 0 1 5/14 -3/14 12 X1 1 1 0 -1/7 2/7 0 0 2/7 -18/7 0 X3 21/5 0 14/5 1 -3/5 12 X1 8/5 1 2/5 0 1/5 -4/5 0 -12/5 X*（8/5，0，21/5，0） Z*96/5 （4） 、 5/143/14111/7 1/72/71927/7 = 华中科技大学管理学院考研运筹盟 第 9 页 共 73 页 jC 10 5 0 0 BC BX b X1 X2 X3 X4 5 X2 -1/7 0 1 5/1
15、4 -3/14 10 X1 27/7 1 0 -1/7 2/7 0 0 -5/14 -25/14 0 X4 2/3 0 -14/3 -5/3 1 10 X1 11/3 1 4/3 1/3 0 -110/3 0 -25/3 -10/3 0 X*（11/5，0，0，2/3） Z*=110/3 4、 jC 2 -1 1 0 0 BC BX b X1 X2 X3 X4 X5 X1 6 1 1 1 1 0 X5 10 0 3 1 1 1 Z -12 0 -3 -1 -2 0 （1） 、2 1 323MaxZXXX=+ jC 2 3 1 0 0 BC BX b X1 X2 X3 X4 X5 2 X1 6 1 1 1 1 0 0 X5 10 0 3
