2007级运筹学A试卷.doc

2007级《运筹学》课程试题（A卷） 题号 一 二 三 四 五 六 七 八 总分 分数 合分人： 复查人： 一、计算题：（共11分） 分数 评卷人 下表为某求极大值线性规划问题的初始单纯形表及跌代后的单纯形表，试求表中a ~ l的值及各变量下标m ~ t的值。 XB b x1 x2 x3 x4 x5 xm 6 b c d 1 0 xn 1 -1 3 e 0 1 cj-zj a 1 -2 0 0 … … xs f g 2 -1 1/2 0 xt 4 h i 1 1/2 1 cj-zj 0 7 j k l 二、计算题：（共11分） 分数 评卷人 已知线性规划问题模型如下，其最优解为x1= -5，x2=0，x3= -1。 （1）求k的值。 （2）写出对偶问题的模型并求出最优解。 三、计算题：（共13分） 分数 评卷人 已知线性规划问题模型如下所示： 用单纯形法求得最终单纯形表为： cj 2 -1 1 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 6 1 1 1 1 0 0 x5 10 0 3 1 1 1 cj-zj 0 -3 -1 -2 0 （1）目标函数变为，新的最优解是什么？ （2）约束条件右端项由变为，新的最优解是什么？ （3）增添一个新的约束，新的最优解是什么？ 四、计算题：（共13分） 分数 评卷人 由产地1、2、3向销地A、B、C供应物资，由产地运往销地的单位物资运费、各产地产量、各销地销量如下表所示。若产地 i 有一个单位物资未运出，则将发生存储费用。假定1，2，3产地单位物资存储费用分别为5，4，3。又假定产地 2 的物资至少运出 38 个单位，产地 3 的物资至少运出 27 个单位，试求解此运输问题的最优解。 销地 产地 A B C 产量 1 1 2 2 20 2 1 4 5 40 3 2 3 3 30 销量 30 20 20 五、计算题：（共13分） 分数 评卷人 已知整数规划问题模型及其标准型如下所示： 已知该整数规划松弛问题的最终单纯形表如下所示，求整数规划问题的最优解。 cj 3 -1 0 0 -M 0 CB XB b x1 x2 x3 x4 x5 x6 3 x1 13/7 1 0 1/7 0 0 2/7 -1 x2 9/7 0 1 -2/7 0 0 3/7 0 x4 31/7 0 0 -3/7 1 -1 22/7 cj-zj 0 0 -5/7 0 -M -3/7 六、计算题：（共13分） 分数 评卷人 用动态规划方法求出下述问题的最优解。 七、计算题：（共13分） 分数 评卷人 求从v1到各点的最短路。 八、计算题：（共13分） 分数 评卷人 求网络的最大流，并指出最小割集（图中各条弧上的数字为该弧的容量）。 第 7 页 共 13 页