试题2答案试题2答案.doc

运筹学答案与评分标准（试题2） 一、（30分）给出线性规划问题： max st. 用单纯形法求最优解，写出最终单纯形表。 试分析下列各种条件下最优解（基）的变化： （1）目标函数中变量x3的系数变为5 ； （2）分别确定目标函数中变量x1的系数c1在什么范围内变动时最优解不变； （3）约束右端项由变为； 解：将线性规划问题化为：max st. （3） 因此，可得如下初始单纯形表：（5） cj 2 3 1 0 0 CB 基 b x1 x2 x3 x4 x5 0 x4 1 1/3 1/3 1/3 1 0 0 x5 3 1/3 4/3 7/3 0 1 cj- zj 2 3 1 0 0 因3≥2≥1，所以选x2进基，因3/(4/3)≤1/(1/3)，故选x5出基，则得 cj 2 3 1 0 0 CB 基 b x1 x2 x3 x4 x5 0 x4 1/4 1/4 0 -1/4 1 -1/4 3 x2 9/4 1/4 1 7/4 0 3/4 cj- zj 5/4 0 -17/4 0 -9/4 因5/4≥0，所以选x1进基，因(1/4)/(1/4)≤(9/4)/(1/4)，故选x4出基，则得 cj 2 3 1 0 0 CB 基 b x1 x2 x3 x4 x5 2 x1 1 1 0 -1 4 -1 3 x2 2 0 1 2 -1 1 cj- zj 0 0 -3 -5 -1 最优解为：（1，2，0）。（7分） （1）目标函数中变量x3的系数变为5 时，得如下单纯形表，并用单纯形法求解步骤进行计算，其过程如下： cj 2 3 5 0 0 CB 基 b x1 x2 x3 x4 x5 2 x1 1 1 0 -1 4 -1 3 x2 2 0 1 2 -1 1 cj- zj 0 0 1 -5 -1 因2≥0，所以选x3进基，因2≥0，故选x2出基，则得 cj 2 3 5 0 0 CB 基 b x1 x2 x3 x4 x5 2 x1 2 1 1/2 0 7/2 -1/2 5 x3 1 0 1/2 1 -1/2 1/2 cj- zj 0 -1/2 0 -5/4 -3/2 得最优解为：（2，0，1），代入目标函数得z = 9 。（5分） （2）设目标函数中变量x1的系数为c1，则由原单纯形表得如下单纯形表： cj c1 3 1 0 0 CB 基 b x1 x2 x3 x4 x5 c1 x1 1 1 0 -1 4 -1 3 x2 2 0 1 2 -1 1 cj- zj 0 0 c1-5 3-4c1 c1-3 若要保持原问题最优解不变，则应有所有检验数均小于等于0；即 即 （5分） （3）约束右端项由变为；有＝ = 将上述结果反映到单纯形表中得： cj 2 3 1 0 0 CB 基 b x1 x2 x3 x4 x5 2 x1 0 1 0 -1 4 -1 3 x2 3 0 1 2 -1 1 cj- zj 0 0 -3 -5 -1 此时，上表中的解仍为可行解，故最优解为：（0，3，0），代入目标函数得z = 9 。（5分） 评分标准：1. 单纯形法求最优解15分，若结果不正确，但步骤正确可得10分。2.（1）、（2）（3）小题各5分。3. 其他情况酌情给分。 二、（10分）已知线性规划问题 求：（1）写出其对偶问题；（5分） （2）直接写出对偶问题的最优解。（5分） 解：该问题的对偶问题为： 由对偶问题性质可知： 解之得： 所以Y*=（0，-2）T Max Z=-4 评分标准：写出对偶问题得5分，求解得5分，其他情况酌情给分。 三、（15分）已知某运输问题如下（单位：百元/吨）： 单位运价 销地 产地 B1 B2 B3 供应量（吨） A1 3 7 2 18 A2 5 8 10 12 A3 9 4 5 15 需求量（吨） 16 12 17 求：（1）使总运费最小的调运方案和最小运费。（12分）