运筹学试题及答案.doc

班级： 学号： 姓名： 茂名学院2009 年成人学士学位主干课程考试卷专业：信息与计算科学 科目：运筹学题号一二三四五六七八九总分得分阅卷人一、选择题（共5小题，每题4分）1、 如果一个线性规划问题有n个变量，m个约束方程(mn)，系数矩阵的数为m，则基可行解的个数最为（ C ）。 Am个 Bn个 C D个2、 在 求 最 大 流 量 的问 题 中，已 知 与 起 点 相 邻 的 三 节 点 单 位 时 间 的 流 量 分 别 为 10,12,15，则 终 点 单 位 时 间 输 出 的 最 大 流 量 为（ D ） A. 等 于 27 B.大 于 或 等 于 37 C.小 于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的最早开始时间，ESj表示结点j的最早开始时间，Ti，j表示活动ij的作业时间，LFi表示结点i的最迟完成时间，LFj表示结点j的最迟完成时间，则下述公式中正确的是（A）A.ESj=B.ESj=C.LFj=D.LFj=二、填空题（共5小题，每题4分）1、求解运输问题时，常用的判断运输方案是否最优的方法，一个是闭合回路，另一个是_位势法_。2、若用三种时间估计法计算作业时间，则应先估计出最乐观时间、_悲观_时间和最可能时间。3、 Max z=3x1+8x2+5x3 4x1+2x215 S.t 3x1+x39 线性规划问题 x1、x2、x30 的标准形式是_ 答案： Max z=3x1+8x2+5x3+0*x4+0*x5 4x1+2x2+x4=15 S.t 3x1+x3+x5=9 x1、x2、x3、x4、x504、写出线性规划问题的对偶问题_ 答案：5、 已知下表是制定生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“”型不等式），其中x4、x5、x6为松弛变量。XBbx 1x 2x 3x4x 5x6x 12110201x 32/3001104x510-20116Cj -Zj000-40-9对偶问题的最优解：_答案：Y=(4,0,9,0,0,0)T3、 计算题（共6小题，每题10分）1、用单纯形法求线性规划问题 max z = 10x1 + 5x23x1 + 4x2 95x1 + 2x2 8x1,x20解：在问题的约束条件中分别加入松弛变量x3，x4，得该线性问题的标准型 max z = 10x1 + 5x23x1 + 4x2 + x3 = 95x1 + 2x2 + x4 = 8x1,x2,x3,x40初始单纯形表x1x2x3x4x393410x485201-z010500 x1为进基变量，min9/3,8/5=8/5 x4为出基变量 以x1代替x4，进行旋转运算，得x1x2x3x4x321/5014/51-3/5x18/512/501/5-z-80/5010-2 x2为进基变量，min 21/5/14/5 , 8/5/2/5 =3/2 x3为出基变量 以x2代替x3，进行旋转运算，得x1x2x3x4x23/2015/14-3/14x1110-1/72/5-z-35/200-5/14-25/14 最优解x = (1,3/2,0,0)T 目标函数的最大值z = 35/22、用动态规划的方法求出AD的最短路径。答案：最短路径为AB3C1D为213、已知线性规划问题 Max z=2x1+x2+5x3+6x4 对偶变量2x1 +x3 +x48 y12x1+2x2 + x3 +2x412 y2Xj0， j=1,2.。4其对偶问题的最优解为y1* =4， y2*=1，试应用对偶问题的性质，求原问题的最优解。4、用标号法求如图下所示网络的最大流和最小截集(割集)，每弧旁的数字是（）。 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,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（V4） 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,+)VS (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) u-=(V1,V2)按=1在u上调整f。 u+上：fs2+=3+1=4 f14+=0+1=1 f4t+=5+1=6 u上：f12-=1-1=0 其余fij不变。调整后得到下图所示可行流 V1 (4,2) V3 (6,6) (6,4) (0,+)VS (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）=fs1+fs2=f3t+f4t=10最小截集： （V1，）=(Vs,V1),(V2,V4)=105、某地区有4个化肥厂，估计每年可供应的数量为A1 -20万吨、A2 -30万吨、A3 -40万吨、 A4-60万吨，销往5个城市，每年每个地区的需求量为B1- 25万吨、B2-15万吨、B3-35万吨、B4-45万吨、B5-30万吨。已知从各化肥厂到各城市的每吨化肥的运价如下表所示（单位：万元）。 销地产地B1B2B3B4B5产量A16948520A2106128730A365920940A4213614360销量2515354530请用伏格尔法求出其运费最少的方案。答案： 销地产地B1B2B3B4B5行差额A1694851A210612871A36592091A421361431列差额41202销地产地B1B2B3B4B5产量(剩)A120A230A340A42560(35)销量2515354530 销地产地B1B2B3B4B5行差额A1694851A210612871A36592094A421361433列差额41202销地产地B1B2B3B4B5产量(剩)A120A230A31540(25)A42560(5)销量2515354530 销地产地B1B2B3B4B5行差额A1694851A210612871A36592090A421361433列差额41202销地产地B1B2B3B4B5产量（剩）A120A230A31540(25)A4253060(5)销量2515354530 销地产地B1B2B3B4B5行差额A1694854A210612874A365920911A421361438列差额41202销地产地B1B2B3B4B5产量（剩）A120A230A3152540(0)A4253060(5)销量2515354530 销地产地B1B2B3B4B5行差额A1694854A210612874A365920911A421361438列差额41202销地产地B1B2B3B4B5产量（剩）A120A230A3152540(0)A42553060(0)销量2515354530 销地产地B1B2B3B4B5行差额A1694854A210612874A365920911A421361438列差额41802销地产地B1B2B3B4B5产量（剩）A1520(15)A230A3152540(0)A42553060(0)销量2515354530 销地产地B1B2B3B4B5行差额A1694858A210612878A365920911A421361438列差额41802销地产地B1B2B3B4B5产量（剩）A151520(0)A23030(0)A3152540(0)A42553060(0)销量2515354530 令u1=0，则u2=0、u3=5、u4=2、v1=0、v2=0、v3=4、v4=8、v5=1销地产地B1B2B3B4B5uiA148u1=0A28u2=0A359u3=5A4263u4=2vjv1=0v2=0v3=4v4=8v5=1得出(ui+vj):销地产地B1B2B3B4B5uiA100481u1=0A200481u2=0A3559136u3=5A4226103u4=2vjv1=0v2=0v3=4v4=8v5=1检验数Cij - (ui+vj)都大于0，所以为最优解。 Cij - (ui+vj)：销地产地B1B2B3B4B5uiA169004u1=0A210