2007-2008第二学期试卷A.doc

《2007-2008第二学期试卷A.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、（勤奋、求是、创新、奉献）2007～2008学年第二学期末考查试卷主考教师：___张伯生__学院_________________班级__________姓名__________学号___________《运筹学、运筹学（一）》课程试卷A参考答案及评分标准（本卷考试时间120分钟）题号一二三四五六七八九十总得分题分1510101510151015100得分一、辨析题（本题共5小题，每小题3分，共15分）1、已知网络上某条链如下图，问：x为何值时，该链不是增流链，为什么？x＝0（1分）。此时后向边为零边，不符合增流链定义（2分）。2、线性规

2、划模型中，设系数矩阵A＝，则X＝（0，1，2，3，4，0）T有无可能是A的基可行解？不可能（1分）。基可行解中非零值的个数不超过m，（题中m＝3），而给定解中X有4个非零值分量。（2分）3、极大化线性规划模型的某步单纯形表如下所示（x4、x5为松弛变量）：CBXBx1x2x3x4x5b4（）11/202–1206（）01/21–1130r0–30–2–2（1）表中，基变量：x1,x3（2分）（2）目标函数maxf＝4x1+2x2+6x3（2分）（3）表中的解X＝（20，0，30，0，0，）T（2分）（4）X是否为最优解？为什么？是。对于极

3、大化线性规划模型来说，所有非基变量检验数0，即达到最优。（2分）4、已知一个求极大化线性规划对偶问题无可行解,问原问题是否有可行解?是否有最优解?为什么?不一定（1分）。因为当对偶问题无可行解时，原问题或具有无界解或无可行解。但一定没有最优解。（2分）5、m个发点和n个收点的运输问题中，某一非基变量对应多条闭回路。错（1分）。唯一的一条闭回路（2分）。二、用图解法求解下列线性规划问题：（10分）maxf=10x1+5x2s.t.3x1+4x295x1+2x28x10，x20解：（6分）最优解X*＝（1，3/2）T，最优值f*=17.5（4

4、分）三、已知线性规划问题（10分）MaxZ=+-++2-2+-1，，0试用对偶理论证明上述线性规划问题有无界解。证明：所给问题的对偶问题为MinW=2+--21+1-0--21显然约束条件中--21不成立，即此对偶问题无可行解，因此所给问题无最优解，它只可以是无界解或者无可行解。然而X=（0，0，0）显然是它的可行解，因此它必定有无界解。四、已知线性规划问题（15分）maxf=2x1－x2+x3s.t.x1+x2+x36x1+2x210x10，x20，x30的最优单纯形表如下2－1100CBXBx1x2x3x4x5b2x11111060x

5、501-1-114r0－3－1－20（1）C2由－1变成k时，对最优基、最优解有何影响？(k=考生学号最后一位)（2）当约束条件右侧系数由变成时，对最优基、最优解有何影响？如果有影响请求出最优解。解：（1）由题意可知：当k<=2时，该最优表中的最优基、最优解不变。当k>2时，该最优表中的最优基、最优解发生变化。（5分）(2)由最优表中的信息可得：，（2分）则，（2分）将代替最优表中的，采用对偶单纯形法继续求解得到最终最优表为：CBXBX1X2X3X4X5b2X11X3120010－111－1420-40-1-1（4分）由此可知：最优解产生

6、了变化，且最优解为。（2分）五、用分支定界法求解：（10分）Maxs.t.解：采用分支定界法进行求解，其求解枚举树图如下：9（2，3/2）（2分）817/2（2，1）（3/2，2）（2分）7（1，2）（2分）无可行解（2分）由分支定界法求解过程可知，最优解为，其对应的最优值为：。（2分）六、二个发点和三个收点的运输问题，发量、收量、单位运价和单位缺货费如下表：（15分）运价收点发点123发量128743591525收量单位缺货费201020657（1）写出运输问题的数学模型；（2）用最小元素法找出初始基本可行解；（3）求出初始基本可行解的

7、检验数，找出闭回路，确定调整量；（4）求出最优运输方案和最小总运费。解：（1）（5分）（2）123ai1151522052535510201020（3分）（3）v024u123ai0185⒂1532⒇⑸225333⑸（5）10bj201020（4分）（3分）七、有一份说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四个人，他们将说明书译成不同文字所需的时间如下表。问应指派哪个人完成哪项工作，使所需的总时间最少？（10分）任务人员EJGR甲215134乙1041415丙9141613丁78119用匈牙利法求解过程如下：行列变换C=下

8、找最少覆盖0的直线=德丁英丙乙俄甲日X=从而得最优指派：最少的耗时数z=4+4+9+11=28。八、已知网络如下图，每条有向边上数组为（cij，fij）（15分）.(1)向x为何值时，网路上流