北航《运筹学试卷A》期末试题amp;参考答案

A 《 运筹学试卷A 》参考答案 一、对线性规划问题 0 , , 1823 2 s.t.54 max 3213212113213321xxxxxxabxxxxcxxz 在第 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  M4 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/5M 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 4M 0 （1）试根据上述求解过程单纯形表，确定参数21a ，1b 和3c 的值，以及该问题的最优解； A （2）以上述线性规划问题为原问题，写出其对偶问题； （3）利用对偶性质，求出对偶问题的最优解。（本题共25 分，第1 小题15 分，第2、3 小题各 5 分） 解： （1）由最终单纯形表3x 的判别数243c，得到23 c； 由中间单纯形表右端项的初等行变换规则：231831b，得到101 b； 由中间单纯形表到最终单纯形表的变换规则：0)1(212321a，得到121 a； 该问题的最优解：10*1 x，0*2 x，0*3 x （2）对偶问题： 0 , 22 532 4 s.t.1810 min 2121212121yyyyyyyyyyw无约束 （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...