（勤奋、求是、创新、奉献） 2007～ 2008学年第二学期末考查试卷 主考教师：__ _ 张伯生_ _ 学院 _________________ 班级 __________ 姓名 __________ 学
号 ___________
《运筹学、运筹学（一）》课程试卷A参考答案及评分标准 （本卷考试时间 120 分钟） 题号 一 二 三 四 五 六 七 八 九 十 总得分 题分 15 10 10 15 10 15 10 15 100 得分 一、辨析题（本题共5小题，每小题3分，共15分） 1、已知网络上某条链如下图，问：x为何值时，该链不是增流链，为v(3,1)v(1,x)v(4,2)vs13t什么？ x＝0（1分）。此时后向边为零边，不符合增流链定义（2分）。 2、线性规划模型中，设系数矩阵A＝(aij)3?6，则X＝（0，1，2，3，4，0）T有无可能是A的基可行解？ 不可能（1分）。基可行解中非零值的个数不超过m，（题中m＝3），而给定解中X有4个非零值分量。（2分） 3、极大化线性规划模型的某步单纯形表如下所示（x4、x5为松弛变量）： CB XB x1 x2 x3 x4 x5 b 4 （ ） 1 1/2 0 2 –1 20 6 （ ） 0 1/2 1 –1 1 30 r 0 –3 0 –2 –2 （1）表中，基变量： x1 , x3 （2分） （2）目标函数 max f ＝ 4x1+2x2+6x3 （2分） （3）表中的解X＝ （20，0，30，0，0，）T （2分） （4）X是否为最优解？为什么？ 是。对于极大化线性规划模型来说，所有非基变量检验数?0，即达到最优。（2分） 4、已知一个求极大化线性规划对偶问题无可行解,问原问题是否有可行解?是否有最优解?为什么? 不一定（1分）。因为当对偶问题无可行解时，原问题或具有无界解或无可行解。但一定没有最优解。（2分） 5、m个发点和n个收点的运输问题中，某一非基变量对应多条闭回路。 错（1分）。唯一的一条闭回路（2分）。 二、用图解法求解下列线性规划问题：（10分） max f =10x1+5x2 s.t. 3x1+4x2?9 5x1+2x2?8 x1?0，x2?0 解： x2（6分） 最优解X*＝（1，3/2）T，最优值f*=17.5（4分） 三、已知线性规划问题（10分）
Max Z =X1+X2 -X1+X2+X3?2
-2X1+X2-X3?1 X1，X2，X3?0
试用对偶理论证明上述线性规划问题有无界解。 证明：所给问题的对偶问题为 Min W=2Y1+Y2 -Y1-2Y2?1
Y1+Y2?1 Y1-Y2?0 -Y1-2Y2?1
显然约束条件中-Y1-2Y2?1不成立，即此对偶问题无可行解，因此所给问题无最优解，它只可以是无界解或者无可行解。然而X=（0，0，0）显然是它的可行解，因此它必定有无界解。
四、已知线性规划问题（15分）
max f =2x1－x2+x3 s.t. x1+x2+x3?6 x1+2x2?10 x1?0，x2?0，x3?0
的最优单纯形表如下
0x1 2 －1 1 0 0 CB XB x1 x2 x3 x4 x5 b 2 x1 1 1 1 1 0 6 0 x5 0 1 -1 -1 1 4 r 0 －3 －1 －2 0 （1）C2由－1变成k时，对最优基、最优解有何影响？(k=考生学号最后一位) ?6??6??10??4???（2）当约束条件右侧系数由变成??时，对最优基、最优解有何影响？如果有影响请求出最优解。 解：（1）由题意可知：当k<=2时，该最优表中的最优基、最优解不变。 当k>2时，该最优表中的最优基、最优解发生变化。 （5分） (2)由最优表中的信息可得： ?10??1B????11???? ， （2分） 则 将为： 代替最优表中的，（2分） ，采用对偶单纯形法继续求解得到最终最优表CB XB 2 X1 1 X3 r X1 X2 X3 X4 X5 b 1 2 0 0 1 4 0 －1 1 1 －1 2 0 -4 0 -1 -1 （4分）
*T由此可知：最优解产生了变化，且最优解为X?(4,0,3,0,0)。（2分）
六、 二个发点和三个收点的运输问题，发量、收量、单位运价和单位缺货费如下表：（15分） 运价 收点 1 2 3 发量 发点 1 2 收量 单位缺货费 8 7 4 3 5 9 20 10 20 6 5 7 15 25 （1） 写出运输问题的数学模型；
（2） 用最小元素法找出初始基本可行解；
（3） 求出初始基本可行解的检验数，找出闭回路，确定调整量；
（4） 求出最优运输方案和最小总运费。 解：（1） minf???cijxijx11?x12?x13?15x21?x22?x23?25x11?x21?20x12?x22?10x13?x23?20xij?0,i?1,2,j?1,2,3（5分） （2） 1 2 3 （3） u 0 3 3 bj v 1 2 3 0 1 8 ⒇ 3 20 2 2 5 ⑸ ⑸ 10 4 3 ⒂ 2 （5） 20 ai 15 25 10 （4分）
?0015???X??2050??055???f*?2051 20 20 2 5 5 10 3 15 5 20 （3分） ai 15 25 10 （3分）
七、有一份说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四个人，他们将说明书译成不同文字所需的时间如下表。问应指派哪个人完成哪项工作，使所需的总时间最少？（10分） 任E J G R 务 人员 甲 2 15 13 4 乙 10 4 14 15 丙 丁 9 7 14 8 16 11 13 9 用匈牙利法求解过程如下： ?215134????1041415?行列变换 ?9141613????78119?? C=??01370????6069??0532????0100??? 下找最少覆盖0的直线 ?01370???6069???0532?????C=?0100?? ?0001???0100???1000????0010?? X=?甲 乙 丙 丁
俄 日 英 德
从而得最优指派：
最少的耗时数z=4+4+9+11=28。
八、已知网络如下图，每条有向边上数组为（cij，fij）（15分）
.
(1)向x为何值时，网路上流为可行流？（2）求网络的最大流、最大流量。（3）证明（2）中得到的结论。(题中k=考生学号最后一位.0号写成10)
???f?f22（1）
?1?x?4. ?x?3（3分）
（2）网路上增流链Ⅰ：（令k=1）
vs(6,3)v1(1,0)v3(4,2)vt； 调整量θ＝1，调整后，
vs(6,4)v1(1,1)v3(4,3)vt 网络上增流链Ⅱ：
（2分）
vs(6,4)v1(1,1)v2(5,3)v3(4,3)vt调整量θ＝1。调整后，
；
vs(6,5)v1(1,0)v2(5,4)v3(4,4)vt最终网络图如下图： （2分） （2分） 最大流量＝9，?fij?如图。（2分） （3）由标号法求出，V1??vs,v1?，V1??v2,v3,v4,vt? 求出截线如图所示。 而网络上的割C=9，即fij?Cij 所以网络上流为最大流。（4分）
