运筹学试题及答案.doc

1、第 1 页 （共 页）班级： 学号：姓名： 茂名学院 2009 年成人学士学位主干课程考试卷专业：信息与计算科学 科目：运筹学题 号 一 二 三 四 五 六 七 八 九 总 分得 分阅卷人一、选择题（共 5 小题，每题 4 分）1、 如果一个线性规划问题有 n 个变量，m 个约束方程(mn)，系数矩阵的数为 m，则基可行解的个数最为（ C ） 。Am 个 Bn 个 C D 个mnnmC2、 在 求 最 大 流 量 的 问 题 中 ， 已 知 与 起 点 相 邻 的 三 节 点 单 位 时 间 的 流 量 分 别 为 10,12,15， 则 终 点 单 位 时 间 输 出 的 最 大 流 量 为

2、 （ D ）A. 等 于 27 B.大 于 或 等 于 37C.小 于 37 D.小 于 或 等 于 373、如下图中每条有向边上的数字为该边的容量限制，则从发点到收点的最大流是（ C ）A、18 B、11 C、12 D、16解析：用最大流标记法可得：4、用最小元素法求初始调运方案是，运输表中数字格的个数为（D）个。 A、m*n B、m+n C、m*n-1 D、m+n-15、若用 ESi表示结点 i 的最早开始时间，ES j表示结点 j 的最早开始时间，T i，j 表示活动第 2 页 （共 页）ij 的作业时间，LF i表示结点 i 的最迟完成时间，LF j表示结点 j 的最迟完成时间，则下述

3、公式中正确的是（ A ）A.ESj= B.ESj=max,ijiijTES min,jiijTESC.LFj= D.LFj=,ijiijLF ,ijiijLF二、填空题（共 5 小题，每题 4 分）1、求解运输问题时，常用的判断运输方案是否最优的方法，一个是闭合回路，另一个是_位势法_。2、若用三种时间估计法计算作业时间，则应先估计出最乐观时间、_悲观_时间和最可能时间。3、 Max z=3x 1+8x2+5x34x1+2x215S.t 3x1+x39线性规划问题 x 1、x 2、x 30 的标准形式是_ 答案： Max z=3x 1+8x2+5x3+0*x4+0*x54x1+2x2+x4=1

4、5S.t 3x1+x3+x5=9x1、x 2、x 3、x 4、x 504、写出线性规划问题 的对偶问题_ 0,564372.min32121xtsxZ答案： 0,04675232.5max321321yytsyu5、已知下表是制定生产计划问题的一张 LP 最优单纯形表（极大化问题，约束条件均为“”型不等式） ，其中 x4、x 5、x 6为松弛变量。XB b x 1 x 2 x 3 x4 x 5 x6x 1 2 1 1 0 2 0 1x 3 2/3 0 0 1 1 0 4第 3 页 （共 页）x5 1 0 -2 0 1 1 6Cj -Zj 0 0 0 -4 0 -9对偶问题的最优解：_答案：Y=

5、(4,0,9,0,0,0) T3、计算题（共 6 小题，每题 10 分）1、用单纯形法求线性规划问题 max z = 10x1 + 5x23x1 + 4x2 95x1 + 2x2 8x1,x20解：在问题的约束条件中分别加入松弛变量 x3，x 4，得该线性问题的标准型max z = 10x1 + 5x23x1 + 4x2 + x3 = 95x1 + 2x2 + x4 = 8x1,x2,x3,x40初始单纯形表x1 x2 x3 x4x3 9 3 4 1 0x4 8 5 2 0 1-z 0 10 5 0 0 x 1为进基变量，min9/3,8/5=8/5 x 4为出基变量以 x1代替 x4，进行旋

6、转运算，得x1 x2 x3 x4x3 21/5 0 14/5 1 -3/5x1 8/5 1 2/5 0 1/5-z -80/5 0 1 0 -2 x 2为进基变量，min 21/5/14/5 , 8/5/2/5 =3/2 x 3为出基变量以 x2代替 x3，进行旋转运算，得x1 x2 x3 x4x2 3/2 0 1 5/14 -3/14x1 1 1 0 -1/7 2/5-z -35/2 0 0 -5/14 -25/14 最优解 x = (1,3/2,0,0)T第 4 页 （共 页） 目标函数的最大值 z = 35/22、用动态规划的方法求出 AD 的最短路径。答案：最短路径为 AB3C1D 为

7、 213、已知线性规划问题Max z=2x1+x2+5x3+6x4 对偶变量2x1 +x3 +x48 y12x1+2x2 + x3 +2x412 y2Xj0， j=1,2.。 。 。4其对偶问题的最优解为 y1* =4， y 2*=1，试应用对偶问题的性质，求原问题的最优解。第 5 页 （共 页）4、用标号法求如图下所示网络的最大流和最小截集(割集)，每弧旁的数字是（ ） 。ijijfc,V1 (4,2) V3(6,6) (6,4)VS (3,1) (3,0) (4,1) Vt(5,3) (7,5)V2 (4,4) V4解：（1）标号过程首先给 Vs 标上（0，+） 。检查 Vs，在弧（Vs,

8、V1）上，fs1=Cs1=6，不满足标号条件。在弧（Vs,V2）上，fs2Cs2,给 V2 标号（Vs，l（V2） ）l（V2）=minl（Vs） ， （Cs2-fs2）=min+，2=2检查 V2，在弧（V2，V4）上，f24=C24=3，不满足标号条件。在弧（V1，V2）上，f12C12，给 V1 标号（-V2，l（V1） ）l（V1）=minl(V2),f12=min2,1=1检查 V1，在弧（V1，V3）上，f13C13,给 V3 标号（V1，l（V3） ）l(V3)=minl(V1),(C13-f13)=min1,2=1在弧（V1，V4）上，f14C14,给 V4 标号（V1，l（V

9、4） ）第 6 页 （共 页）L(V4)=minl(V1),(C14-f14)=min1,3=1在 V3，V4 中任选一个进行检查，例如，在弧（V4，Vt）上，f4tC4t，给 Vt 标号（V4，l（Vt） ）L(Vt)=minl(V4),(C4t-f4t)=min1,2=1（2）调整过程按点的第一个标号找到一条增广链，如下图双箭头V1(-V2,1) (4,2) V3(V1,1)(6,6) (6,4)(0,+)V S (3,1) (3,0) (4,1) Vt(V4,1)(5,3) (7,5)V2 (Vs,2) (4,4) V4(V1,1)易见 u+=(Vs,V2),(V1,V4),(V4,Vt

10、)u-=(V1,V2)按 =1 在 u 上调整 f。u+上：fs2+ =3+1=4f14+ =0+1=1f4t+ =5+1=6 u上：f12- =1-1=0 其余 fij 不变。调整后得到下图所示可行流V1 (4,2) V3(6,6) (6,4)(0,+)V S (3,0) (3,1) (4,1) Vt(5,4) (7,6)V2(Vs,1) (4,4) V4重复上述步骤：开始给 Vs 标以（0，+） ，于是检查 Vs，给 V2 标以（Vs，1） ，检查 V2，弧（V2,V4）上，f24=C24，弧（V1，V2）上，f12=0，均不符合条件，标号过程无法继续下去，算法结束。最大流为：V（f）=f

11、s1+fs2=f3t+f4t=10最小截集：（V1， ）=(Vs,V1),(V2,V4)=101第 7 页 （共 页）5、某地区有 4 个化肥厂，估计每年可供应的数量为 A1 -20 万吨、A 2 -30 万吨、A 3 -40 万吨、 A4-60 万吨，销往 5 个城市，每年每个地区的需求量为 B1- 25 万吨、B 2-15 万吨、B3-35 万吨、B 4-45 万吨、B 5-30 万吨。已知从各化肥厂到各城市的每吨化肥的运价如下表所示（单位：万元） 。 销地产地B1 B2 B3 B4 B5 产量A1 6 9 4 8 5 20A2 10 6 12 8 7 30A3 6 5 9 20 9 40

12、A4 2 13 6 14 3 60销量 25 15 35 45 30请用伏格尔法求出其运费最少的方案。答案：销地产地B1 B2 B3 B4 B5 行差额A1 6 9 4 8 5 1A2 10 6 12 8 7 1A3 6 5 9 20 9 1A4 2 13 6 14 3 1列差额 4 1 2 0 2销地产地B1 B2 B3 B4 B5 产量(剩)A1 20A2 30A3 40A4 25 60(35)销量 25 15 35 45 30销地产地B1 B2 B3 B4 B5 行差额A1 6 9 4 8 5 1A2 10 6 12 8 7 1A3 6 5 9 20 9 4A4 2 13 6 14 3

13、3列差额 4 1 2 0 2第 8 页 （共 页）销地产地B1 B2 B3 B4 B5 产量(剩)A1 20A2 30A3 15 40(25)A4 25 60(5)销量 25 15 35 45 30销地产地B1 B2 B3 B4 B5 行差额A1 6 9 4 8 5 1A2 10 6 12 8 7 1A3 6 5 9 20 9 0A4 2 13 6 14 3 3列差额 4 1 2 0 2销地产地B1 B2 B3 B4 B5 产量（剩）A1 20A2 30A3 15 40(25)A4 25 30 60(5)销量 25 15 35 45 30销地产地B1 B2 B3 B4 B5 行差额A1 6 9

14、 4 8 5 4A2 10 6 12 8 7 4A3 6 5 9 20 9 11A4 2 13 6 14 3 8列差额 4 1 2 0 2销地产地B1 B2 B3 B4 B5 产量（剩）A1 20第 9 页 （共 页）A2 30A3 15 25 40(0)A4 25 30 60(5)销量 25 15 35 45 30销地产地B1 B2 B3 B4 B5 行差额A1 6 9 4 8 5 4A2 10 6 12 8 7 4A3 6 5 9 20 9 11A4 2 13 6 14 3 8列差额 4 1 2 0 2销地产地B1 B2 B3 B4 B5 产量（剩）A1 20A2 30A3 15 25 4

15、0(0)A4 25 5 30 60(0)销量 25 15 35 45 30销地产地B1 B2 B3 B4 B5 行差额A1 6 9 4 8 5 4A2 10 6 12 8 7 4A3 6 5 9 20 9 11A4 2 13 6 14 3 8列差额 4 1 8 0 2销地产地B1 B2 B3 B4 B5 产量（剩）A1 5 20(15)A2 30A3 15 25 40(0)A4 25 5 30 60(0)销量 25 15 35 45 30第 10 页 （共 页）销地产地B1 B2 B3 B4 B5 行差额A1 6 9 4 8 5 8A2 10 6 12 8 7 8A3 6 5 9 20 9 1

16、1A4 2 13 6 14 3 8列差额 4 1 8 0 2销地产地B1 B2 B3 B4 B5 产量（剩）A1 5 15 20(0)A2 30 30(0)A3 15 25 40(0)A4 25 5 30 60(0)销量 25 15 35 45 30令 u1=0，则 u2=0、u3=5、u4=2、v1=0、v2=0、v3=4、v4=8、v5=1销地产地B1 B2 B3 B4 B5 uiA1 4 8 u1=0A2 8 u2=0A3 5 9 u3=5A4 2 6 3 u4=2vj v1=0 v2=0 v3=4 v4=8 v5=1得出(u i+vj):销地产地B1 B2 B3 B4 B5 uiA1 0 0 4 8 1 u1=0A2 0 0 4 8 1 u2=0A3 5 5 9 13 6 u3=5A4 2 2 6 10 3 u4=2vj v1=0 v2=0 v3=4 v4=8 v5=1检验数 Cij - (ui+vj)都大于 0，所以为最优解。Cij - (ui+vj)：