重庆邮电大学2010~2011学年2学期 《运筹学》试卷（期末）（A卷）（闭卷）
一、（20分）已知线性规划问题：
minz?2x1?x2?2x3??x1?x2?x3?4 ?st.??x1?x2?x3?6?x?0,x?0,x无约束23?1要求：（1）将上述线性规划问题变换成标准型；（5分）
（2）用单纯形法求出该问题的最优解和最优目标函数值；（10分）
（3）写出该问题的对偶问题，并指出对偶问题的最优解。（5分） 二、（20分）已知线性规划问题：
maxz??x1?18x2?c3x3?c4x4?x1?2x2?3x3?4x4?15 ?st.??3x1?4x2?5x3?6x4?5???x?0,(j?1,?,4)?j要求：（1）当??0时，以x1、x2为基变量的单纯形表；（10分）
（2）若x1、x2为最优基，确定问题最优解不变时c3、c4 的变化范围；（5分） （3）保持最优基不变时的?的变化范围；（5分） 三、（15分）已知某运输问题的产销平衡表、单位运价表如下所示，试运用表上作业法求出使总运费最低的最优运输方案。
销地 产地 A1 A2 A3 销量 B1 10 12 2 5 B2 1 5 14 15 B3 20 9 16 15 B4 11 20 18 10 产量 15 25 5
四、6人完成4项工作，所得利润矩阵估计如下，规定每人只能做一项工作，每项工作只能有一人完成，试用匈牙利法求解利润最大的指派方案（15分）
利润值 1 2 3 4 5 6 1 3 6 8 10 12 13 2 5 7 9 10 11 12 3 4 6 8 9 10 11 4 5 8 10 11 12 13
五、某车最大载重量为7吨，现有A、B、C三种物品可载；三种物品的重量分别为1、2、3吨，单位收益分别为1，2，3；A≥2时的单位收益为1.5；现要求B、C至少运1个,且B不超过两个，试用动态规划的方法求解利润最大的载运方案（15分）
六、某企业有一6年设备更新计划，其费用情况如下：试用双标号（Dijkstra 可直接标号）的方法求解最低成本的更新方案（15分） 年份 购买费 1 20 1 10 12 2 21 2 12 10 3 22 3 15 7 4 23 4 18 3 5 24 5 22 0 6 25 6 27 0 （役龄） 维修费 设备残值