A 《 运筹学试卷A 》参考答案 一、对线性规划问题 0 , , 1823 2 s.t.54 max 3213212113213321xxxxxxabxxxxcxxz 在第 1 个约束中引入人工变量4x ,第 2 个约束中引入松弛变量5x ,采用大 M 法利用单纯形表求解得到了最优解,单纯形表完整的迭代过程见下表: jc 4 5 3c M 0 BC BX b 1x 2x 3x 4x 5x M 4x 1b 1 [2] 1 1 0 0 5x 18 21a 3 2 0 1 jjzc M4 M25 Mc 3 0 0 jc 4 5 3c M 0 BC BX b 1x 2x 3x 4x 5x 5 2x 2/1b [1/2] 1 1/2 1/2 0 0 5x 3 2/321 a 0 1/2 3/2 1 jjzc 3/2 0 2/53 c 2/5M 0 jc 4 5 3c M 0 BC BX b 1x 2x 3x 4x 5x 4 1x 1b 1 2 1 1 0 0 5x 8 0 1 3/2 1 1 jjzc 0 3 2 4M 0 (1)试根据上述求解过程单纯形表,确定参数21a ,1b 和3c 的值,以及该问题的最优解; A (2)以上述线性规划问题为原问题,写出其对偶问题; (3)利用对偶性质,求出对偶问题的最优解。(本题共25 分,第1 小题15 分,第2、3 小题各 5 分) 解: (1)由最终单纯形表3x 的判别数243c,得到23 c; 由中间单纯形表右端项的初等行变换规则:231831b,得到101 b; 由中间单纯形表到最终单纯形表的变换规则:0)1(212321a,得到121 a; 该问题的最优解:10*1 x,0*2 x,0*3 x (2)对偶问题: 0 , 22 532 4 s.t.1810 min 2121212121yyyyyyyyyyw无约束 (3)依据互补松弛定理。在最优解处,原问题第2 个约束为严格不等式,故02 y。 由于0*1 x,故对偶问题第1 个约束为等式,4 21 yy,得到41 y。 故对偶问题的最优解为4*1 y,0*2 y。 二、用分支定界法求解如下整数规划问题 为整数2121212121 , 0 , 1742 6 s.t. 32max :IPxxxxxxxxxxz 先解其松弛问题LP,得最优解 2/7*1 x, 2/5*2 x,不满足整数要求。显然01 x,02 x为问题IP 的一个可行解。 (1)依据以上信息,给出问题IP 最优目标函数值的初始上下界; (2)写出针对2x 的分支子问题; (3)基于上述分支子问题,完成问题IP 的求解(提示:可用图解法),给出最LP A 优解并更新最优目标函数值的上下界。(本题共10 分,第1...