东南大学运筹学试卷.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分）VSV2V1V3Vt(4,3)(1,0)(3,1)(2,2)(2,2)(5,2)(3,3)（1）确定所有的截集；（2）求最小截集的容量；（3）证明指出的流是最大流七、试解二次规划（15分）问题答案：1. 解：（1）首先把问题转化成标准型：用单纯型法求解最优解：初始单纯型表1534000CBXBbX1X2X3X4X5X6X70X580023121000X6120054340100X710003453001Cj-Zj1534000最终单纯型表0X51001/40-13/4011/4-14X420020-2101-15X2100-3/4111/400-3/41Cj-Zj-13/40-11/400-1/4-1最优解为（0，100，0，200）；（2）由互补松弛性可得，其对偶问题最优解为：（0，1/4，1）；（3）当时所以因此可得出最优基发生变化，因为，需要用对偶单纯型法继续求解；（4）若保证最优基不变，需要满足以下条件： 从而得出-11/3（5）X3的系数发生变化：同时计算P3的检验数为：，因此可以得出尚未得到最优解，用单纯型法继续求解：初始单纯型表1534000CBXBbX1X2X3X4X5X6X70X51001/40-1/4011/4-14X4200201101-15X2100-3/41-1/400-3/41Cj-Zj-13/401/400-1/4-1最终单纯型表0X51503/4001/411/2-5/43X3200201101-15X2150-1/4101/40-1/23/4Cj-Zj-15/400-1/40-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个连通子图，k2；T1,T2,T3，Tk，由树定义可得：q(G1)=P(G1)-1； q(G2)=P(G2)-1； q(G3)=P(G3)-1； q(Gk)=P(Gk)-1；等式左右两边相加得：q(G1)+ q(G2)+ q(G3)+ q(Gk)=P(G1)+P(G2)+P(G3)+P(Gk)-k；q(G)=n-k，k2；与已知条件图有n条边不符，因此，假设不成立所以问题得证6. 解：（1）首先确定所有的截集与对应的容量：若，则其截集为 其容量为若，则其截集为 其容量为若，则其截集为 其容量为若，则其截集为 其容量为若，则其截集为 其容量为若，则其截集为 其容量为若，则其截集为 其容量为若，则其截集为 其容量为（2）由（1）所求，最小截集的容量为 其中。（3）根据最大流量最小截量