《《运筹学基础1》final2008.doc》由会员分享，可在线阅读，更多相关《《运筹学基础1》final2008.doc（6页珍藏版）》请在金锄头文库上搜索。
1、班 级 学 号 姓 名 密封装订线 密封装订线 密封装订线西南交通大学20082009 学年第(一)学期考试试卷课程代码 6041930 课程名称 运筹学基础 考试时间 120 分钟 题号一二三四五六七八九总成绩得分 阅卷教师签字： 一.（10分）有一工厂A计划从下面三个城市中的某一城市中进一批货,能走路径及距离如下图所示,问工厂A应从那个城市进货及走怎样的路径使距离最短. 最短为多少? 4 10 9 B1 C1 D1 E1 3 3 2 12 12 10 5 8 8 5 10 A B2 C2 D2 E2 7 B3 C3 D3 E3 二（10分）下列表是一个指派问题的效率表(工作时间表)，其中A
2、 i为工作人员(i=1, 2, 3, 4)、Bj为工作项目(j=1, 2, 3, 4)，请作工作安排，使总的工作时间最小,最小多少。B1B2B3B4A14174A22235A35643A46324三(18分)已知下面线性规划问题 s.t. 用二阶段法求解时,第一阶段的单纯形表如下: x1 x2 x3 x4 x5 x6 b- - - x 4 1/ 1 2/ 1 1/ 1 1/ 1 0/ 1 0/ 1 18/ 1 x 5 2/ 1 1/ 1 3/ 1 0/ 1 1/ 1 0/ 1 16/ 1 x 6 1/ 1 1/ 1 1/ 1 0/ 1 0/ 1 1/ 1 10/ 1 - c-z | 1/ 1
3、1/ 1 1/ 1 0/ 1 0/ 1 0/ 1 - x 4 0/ 1 3/ 2 -1/ 2 1/ 1 -1/ 2 0/ 1 10/ 1 x 1 1/ 1 1/ 2 3/ 2 0/ 1 1/ 2 0/ 1 8/ 1 x 6 0/ 1 1/ 2 -1/ 2 0/ 1 -1/ 2 1/ 1 2/ 1 - c-z| 0/ 1 1/ 2 -1/ 2 0/ 1 -1/ 2 0/ 1 - x 4 0/ 1 0/ 1 1/ 1 1/ 1 1/ 1 -3/ 1 4/ 1 x 1 1/ 1 0/ 1 2/ 1 0/ 1 1/ 1 -1/ 1 6/ 1 x 2 0/ 1 1/ 1 -1/ 1 0/ 1 -1/ 1
4、 2/ 1 4/ 1 - c-z 0/ 1 0/ 1 0/ 1 0/ 1 0/ 1 -1/ 1 问 (1) 此线性规划问题是否有可行解?为什么? (2) 此线性规划问题是否有最优解?如有,求出最优解,如无说明理由. (3) 用对偶理论,说明其对偶问题是否有最优解? 如有,求出对偶问题的最优解四. .求解整数规划(12分) s.t. 是整数 已知在无整数要求时,其最终单纯形表如下: x 1| 1/ 1 0/ 1 1/ 3 -1/ 3 5/ 3 x 2| 0/ 1 1/ 1 0/ 1 1/ 2 5/ 2 c-z 0/ 1 0/ 1 -1/ 3 -1/ 6 在用割平面法求解时(1) 就对单纯形表中对
5、应的项:x 1| 1/ 1 0/ 1 1/ 3 -1/ 3| 5/ 3 写出割平面方程(2) 对(1)进行求解(要求写出单纯形表) 五(20分) 已知运输问题的运价表和发量和收量如下表所示: B1 B2 B3 B4 B5 发量 A1 10.00 20.00 5.00 9.00 10.00 5.00 A2 2.00 10.00 8.00 30.00 6.00 6.00 A3 1.00 20.00 7.00 10.00 4.00 2.00 A4 8.00 6.00 3.00 7.00 5.00 9.00 收量 4.00 4.00 6.00 2.00 4.00问 (1) 此题不是平衡问题,应怎样处理
6、? (2) 经过特殊处理,下面可行方案能否当成初始基可行解?为什么? B1 B2 B3 B4 B5 B6 A1 1.00 2.00 2.00 5.00 A2 2.00 4.00 6.00 A3 2.00 2.00 A4 4.00 5.00 0.00 9.00 4.00 4.00 6.00 2.00 4.00 2.00 (3) 验证此方案是否是最优解,如不是找出最优方案(4) 的运价在什么范围内,原问题的最优方案可不变 六 (10分)用动态规划求解 七.(10分)证明:如果某线性规划问题有最优解,则其对偶问题也必有最优解且目标值相同.八（10分）设是凸集的任意一个顶点,证明存在某整数向量使得是线性规划问题 的唯一最优解
