同济运筹学2007到2008期末试卷A.doc

0708运筹学（一）课程试卷A一、辨析题（本题共5小题，每小题3分，共15分）1、已知网络上某条链如下图，问：x为何值时，该链不是增流链，为什么？ 2、线性规划模型中，设系数矩阵A，则X（0，1，2，3，4，0）T有无可能是A的基可行解？3、极大化线性规划模型的某步单纯形表如下所示（x4、x5为松弛变量）：CBXBx1x2x3x4x5b4（ ）11/2021206（ ）01/211130r03022（1）表中，基变量： （2）表中的解X （3）X是否为最优解？为什么?4、已知一个求极大化线性规划对偶问题无可行解,问原问题是否有可行解?是否有最优解?为什么?5、m个发点和n个收点的运输问题中，某一非基变量对应多条闭回路。二、用图解法求解下列线性规划问题：（10分）max f =10x1+5x2s.t. 3x1+4x29 5x1+2x28x10，x20三、已知线性规划问题（10分）Max Z =+-+2-2+-1，0试用对偶理论证明上述线性规划问题有无界解。四、已知线性规划问题（15分）max f =2x1x2+x3s.t. x1+x2+x36 x1+2x210x10，x20，x30的最优单纯形表如下21100CBXBx1x2x3x4x5b2x11111060x501-1-114r03120（1）C2由1变成k时，对最优基、最优解有何影响？(k=考生学号最后一位)（2）当约束条件右侧系数由变成时，对最优基、最优解有何影响？如果有影响请求出最优解。五、 用分支定界法求解：（10分） Max s.t. 六、 二个发点和三个收点的运输问题，发量、收量、单位运价和单位缺货费如下表：（15分）运价 收点发点 1 2 3发 量 1 2 8 7 4 3 5 9 15 25 收量单位缺货费 20 10 20 6 5 7（1） 写出运输问题的数学模型；（2） 用最小元素法找出初始基本可行解；（3） 求出初始基本可行解的检验数，找出闭回路，确定调整量；（4） 求出最优运输方案和最小总运费。七、有一份说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四个人，他们将说明书译成不同文字所需的时间如下表。问应指派哪个人完成哪项工作，使所需的总时间最少？（10分） 任务人员EJGR甲215134乙1041415丙9141613丁78119八、已知网络如下图，每条有向边上数组为（cij，fij）（15分）. (1)向x为何值时，网路上流为可行流？（2）求网络的最大流、最大流量。（3）证明（2）中得到的结论。(题中k=考生学号最后一位，0号写成10)0708运筹学（一）课程试卷A参考答案一、辨析题（本题共5小题，每小题3分，共15分）1、已知网络上某条链如下图，问：x为何值时，该链不是增流链，为什么？ x0（1分）。此时后向边为零边，不符合增流链定义（2分）。2、线性规划模型中，设系数矩阵A，则X（0，1，2，3，4，0）T有无可能是A的基可行解？不可能（1分）。基可行解中非零值的个数不超过m，（题中m3），而给定解中X有4个非零值分量。（2分）3、极大化线性规划模型的某步单纯形表如下所示（x4、x5为松弛变量）：CBXBx1x2x3x4x5b4（ ）11/2021206（ ）01/211130r03022（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+5x2s.t. 3x1+4x29 5x1+2x28x10，x20解：（6分）最优解X*（1，3/2）T，最优值f*=17.5（4分）三、已知线性规划问题（10分）Max Z =+-+2-2+-1，0试用对偶理论证明上述线性规划问题有无界解。 证明：所给问题的对偶问题为 Min W=2+ -21 +1 -0 -21显然约束条件中-21不成立，即此对偶问题无可行解，因此所给问题无最优解，它只可以是无界解或者无可行解。然而X=（0，0，0）显然是它的可行解，因此它必定有无界解。四、已知线性规划问题（15分）max f =2x1x2+x3s.t. x1+x2+x36 x1+2x210x10，x20，x30的最优单纯形表如下21100CBXBx1x2x3x4x5b2x11111060x501-1-114r03120（1）C2由1变成k时，对最优基、最优解有何影响？(k=考生学号最后一位)（2）当约束条件右侧系数由变成时，对最优基、最优解有何影响？如果有影响请求出最优解。解：（1）由题意可知：当k2时，该最优表中的最优基、最优解发生变化。 （5分） (2)由最优表中的信息可得： ，（2分） 则 ，（2分）将代替最优表中的，采用对偶单纯形法继续求解得到最终最优表为：CB XBX1 X2 X3 X4 X5b2 X11 X3 1 2 0 0 1 0 1 1 1 1 4 2 0 -4 0 -1 -1（4分） 由此可知：最优解产生了变化，且最优解为。（2分）五、用分支定界法求解：（10分） Max s.t. 解：采用分支定界法进行求解，其求解枚举树图如下： 9 （2，3/2） （2分） 8 17/2 （2，1） （3/2，2） （2分） 7 （1，2） （2分） 无可行解 （2分）由分支定界法求解过程可知，最优解为，其对应的最优值为：。（2分）六、 二个发点和三个收点的运输问题，发量、收量、单位运价和单位缺货费如下表：（15分）运价 收点发点 1 2 3发量 1 2 8 7 4 3 5 9 15 25 收量单位缺货费 20 10 20 6 5 7（5） 写出运输问题的数学模型；（6） 用最小元素法找出初始基本可行解；（7） 求出初始基本可行解的检验数，找出闭回路，确定调整量；（8） 求出最优运输方案和最小总运费。 解：（1）（5分） （2）123ai1151522052535510201020（3分）（3） v024u123ai01851532225333（5）10bj201020（4分）（3分）七、有一份说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四个人，他们将说明书译成不同文字所需的时间如下表。问应指派哪个人完成哪项工作，使所需的总时间最少？（10分） 任务人员EJGR甲215134乙1041415丙9141613丁78119用匈牙利法求解过程如下：行列变换C= 下找最少覆盖0的直线=德丁英丙乙俄甲日X= 从而得最优指派：最少的耗时数z=4+4+9+11=28。八、已知网络如下图，每条有向边上数组为（cij，fij）（15分）. (1)向x为何值时，网路上流为可行流？（2）求网络的最大流、最大流量。（3）证明（2）中得