2010级工管筹学试卷A参考答案.doc

华东交通大学2011—2012学年第二学期考试卷 试卷编号：　　　　（　A　）卷 运筹学 课程 课程类别：必 闭卷（ ） 考试日期： 题号 一 二 三 四 五 六 七 八 九 十 总分 累分人签名 题分 10 23 30 15 22 100 得分 考生注意事项：1、本试卷共 8 页，总分　100　分，考试时间　120　　分钟。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 得分 评阅人 一、填空题 每空2 分，共 10分 1、平衡运输问题（m个产地，n个销地）的基可行解中基变量共有 m+n-1 ；其中决策变量xij所对应的列向量pij （0…1…1…0） 。 2、用对偶单纯形法求解线性规划问题时，根据br 确定xr为换出基变量；根据最小比值法则θ ，确定xk为换入基变量。 3、影子价格是指： 在其它条件不变的情况下，单位资源变化对目标函数的最优值的变化 。 二、综合题（共23分） 得分 评阅人 已知线性规划问题： 求：（1）、用图解法求解；（6分） （2）、写出其对偶问题；（5分） （3）、直接写出对偶问题的最优解。（4分） 解：（1）、 x2 2 Z’ Z’ x1 x1-x2 -1 0 2 4 0.5x1+x2 2 （6分） 由图可知： 解之得： 则最优解为X （4，0）T Max Z -4-0 -4 为唯一最优解 （2）、该问题的对偶问题为： （2分） （1分） （1分） （1分） （3）、由对偶问题性质可知： 解之得： 所以Y* （0，-2）T Max Z -4 （4分） 2、有一整数规划模型为：MaxZ x1+x2 2x1+x2 ≤6 4x1+5x2 ≤20 x1、x2≥0 且为整数 已知经过中间计算，其单纯形表如下： Cj 1 1 0 0 0 Cb Xb b X1 X2 X3 X4 X5 1 0 0 X1 X2 X4 9/5 12/5 4/5 1 0 1 0 -1/5 0 1 -1 0 2/5 0 0 1 1 -6/5 σj 0 0 0 0 -1/5 试写出其合适的Gomory割平面方程（8分）。 解：选x1或x4对应的约束方程为调整对象。 X1对应的Gomory割平面方程： X4对应的Gomory割平面方程： 三、计算题 共 30 分 得分 评阅人 1、已知下列线性规划问题：（20分） 求：用单纯形法求解，并指出问题属于哪一类解。 解：（1）、将原问题划为标准形得： 60 （4分） （计算表每步4分） 6 -3 3 0 0 0 b 0 60 3 1 1 1 0 0 0 20 [2] -2 4 0 1 0 0 60 3 3 -3 0 0 1 6 -3 3 0 0 0 6 -3 3 0 0 0 b 0 30 0 4 -5 1 -3/2 0 6 10 1 -1 2 0 1/2 0 0 30 0 [6] -9 0 -3/2 1 0 3 -9 0 -3 0 6 -3 3 0 0 0 b 0 10 0 0 1 1 -1/2 -2/3 6 15 1 0 1/2 0 1/4 1/6 -3 5 0 1 -3/2 0 -1/4 1/6 0 0 -9/2 0 -9/4 -1/2 所以X （15，5，0，10，0，0）T 为唯一最优解 （2分） Max Z 6*15-3*5 75 （2分） 2、某公司下属的3个分厂A1、A2、A3生产质量相同的工艺品，要运输到B1、B2、B3、B4 ，4个销售点，分厂产量、销售点销量、单位物品的运费数据如下： B1 B2 B3 B4 产量ai A1 23 11 20 15 37 A2 18 16 17 14 34 A3 22 15 12 13 29 销量bj 23 16 25 19 试用最小元素法求出初始运输方案，并求出该方案的运输费用总和。（10分） （要求另外列表表示运输方案，并列出简要的计算过程） 解：该问题为产销不平衡问题，∑产量 37+34+29 100；∑销量 23+16+25+19 83； 产量大于销量。增加虚拟的销地B5， （2分） 得产销平衡表如下：（3分） B1 B2 B3 B4 B5 产量ai A1 23 11 20 15 0 37 A2 18 16 17 14 0 34 A3 22 15 12 13 0 29 销量bj 23 16 25 19 17 100 按最小元素法求出的初始方案为：（4分） B1 B2 B3 B4 B5 产量ai A1 4⑦ 16② 17① 37 A2 19⑥