东南大学运筹学试卷.docx

一、已知线性规划问题（25分） （1）求线性规划问题的最优解；5 （2）求对偶问题的最优解；5 （3）当时最优基是否发生变化？为什么？5 （4）求C2 的灵敏度范围；5 （5）如果X3的系数由[1，3，5]变为[1，3，2]最优解是否改变，若改变求新的最优解；5 二、考虑线性规划问题，（15） 用单纯型法求解，得其终表如下： X4为松弛变量，X5为人工变量。 （1）上述模型的对偶模型为？ （2）对偶模型的最优解为？ （3）当两种资源分别单独增加一单位时，目标函数值分别增加？ （4）最优基的逆矩阵B-1=? （5）如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？ 三、线性规划问题 设X0 为该问题的最优解，若目标函数中用C* 带替C后，问题的最优解变为X* ，求证： (10分) 四、求V1到各点的最短路。（10分） 五、证明任何有n个节点n条边的简单图中必存在圈。（10分） 六、求下图所示的网络中，每条弧旁边的数字是，（15分） V VS V2 V1 V3 Vt (4,3) (1,0) (3,1) (2,2) (2,2) (5,2) (3,3) （1）确定所有的截集； （2）求最小截集的容量； （3）证明指出的流是最大流 七、试解二次规划（15分） 问题答案： 1. 解： （1）首先把问题转化成标准型： 用单纯型法求解最优解： 初始单纯型表 1 5 3 4 0 0 0 CB XB b X1 X2 X3 X4 X5 X6 X7 0 X5 800 2 3 1 2 1 0 0 0 X6 1200 5 4 3 4 0 1 0 0 X7 1000 3 4 5 3 0 0 1 Cj-Zj 1 5 3 4 0 0 0 最终单纯型表 0 X5 100 1/4 0 -13/4 0 1 1/4 -1 4 X4 200 2 0 -2 1 0 1 -1 5 X2 100 -3/4 1 11/4 0 0 -3/4 1 Cj-Zj -13/4 0 -11/4 0 0 -1/4 -1 最优解为（0，100，0，200）； （2）由互补松弛性可得，其对偶问题最优解为：（0，1/4，1）； （3）当时 所以 因此可得出最优基发生变化，因为，需要用对偶单纯型法继续求解； （4）若保证最优基不变，需要满足以下条件： 从而得出-11/3 （5）X3的系数发生变化： 同时计算P3的检验数为：，因此可以得出尚未得到最优解，用单纯型法继续求解： 初始单纯型表 1 5 3 4 0 0 0 CB XB b X1 X2 X3 X4 X5 X6 X7 0 X5 100 1/4 0 -1/4 0 1 1/4 -1 4 X4 200 2 0 1 1 0 1 -1 5 X2 100 -3/4 1 -1/4 0 0 -3/4 1 Cj-Zj -13/4 0 1/4 0 0 -1/4 -1 最终单纯型表 0 X5 150 3/4 0 0 1/4 1 1/2 -5/4 3 X3 200 2 0 1 1 0 1 -1 5 X2 150 -1/4 1 0 1/4 0 -1/2 3/4 Cj-Zj -15/4 0 0 -1/4 0 -1/2 -3/4 最优解为（0，150，200，0）； 2. 解： （1）上述模型的对偶模型为： （2）由单纯型表可以看出，，由于 而 所以， 则对偶问题的第一、二个约束是紧的，可解出 将代入第三个约束，满足约束条件，则 （3）5和2 （4） （5）如果原问题增加一个变量，则对偶问题增加一个约束，因此其可行域要么减小，要不不变，但绝不会增大。 3. 证明： 因为X0 和X*都满足 所以X0 和X*都是两个问题的可行解。 又因为X0 是最优解，而且原问题求最大， 因此可得出： 同理可得出： 所以可以得出： 因此得证： 4. 解：用Dijkstra算法求解可得 V1到V2的最短路为V1-V2，最短距离11， V1到V3的最短路为V1-V3，最短距离9， V1到V4的最短路为V1-V4，最短距离10， V1到V5的最短路为V1-V4-V5，最短距离21， V1到V6的最短路为V1-V3-V6，最短距离20， V1到V7的最短路为V1-V4-V5-V7，最短距离25， 具体步骤省略。 5. 证明：设有V1，V2，V3，…Vn个点，构成简单图G(V,E)，假设图中不存在圈， 若简单图为连通图，由树的定义无圈的连通图为树，并且简单图G无环五多重边，因此可知G为树，由树的定义可得：q(G)=P(G)-1=n-1，与已知图有n条边矛盾，因此可得假设不成立，图中一定存在圈； 若简单图为非连通图，则至少有两个连通分图，由于每个连通分图无圈，则可得每个连通分图都为一颗树，设有k个连通子图，k≥2；T1,T2,T3，…Tk， 由树定义可得：q(G1)=P(G1)-1