一、已知线性规划问题（25 分） 12341234123412341234max53423280054341200. 34531000,,,0zxxxxxxxxxxxxstxxxxx x x x （1）求线性规划问题的最优解；5 （2）求对偶问题的最优解；5 （3）当3150b 时最优基是否发生变化？为什么？5 （4）求 C2 的灵敏度范围；5 （5）如果 X3 的系数由[1，3，5]变为[1，3，2]最优解是否改变，若改变求新的最优解；5 二、考虑线性规划问题，（15） 123123123123max512425. 2432,,0zxxxxxxstxxxx x x 用单纯型法求解，得其终表如下： X4 为松弛变量，X5 为人工变量。 （1）上述模型的对偶模型为？ （2）对偶模型的最优解为？ （3）当两种资源分别单独增加一单位时，目标函数值分别增加？ （4）最优基的逆矩阵 B-1=? （5）如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？ 三、线性规划问题max ( ),,0,Tf xC x Axb x 设 X0 为该问题的最优解，若目标函数中用 C* 带替 C 后，问题的最优解变为 X* ，求证： **0() ()0TCCXX(10 分) 四、求 V1 到各点的最短路。（10 分） 五、证明任何有 n 个节点 n 条边的简单图中必存在圈。（10 分） 六、求下图所示的网络中，每条弧旁边的数字是(,)ijijcf，（15 分） （1）确定所有的截集； （2）求最小截集的容量； （3）证明指出的流是最大流 七、试解二次规划（15 分） 22112212121212min ( )244633. 49,0f xxx xxxxxxstxxxx VS V2 V1 V3 Vt (4,3) (1,0) (3,1) (2,2) (2,2) (5,2) (3,3) 问题答案： 1. 解： （1）首先把问题转化成标准型： 12341234512346123471234567max53423280054341200. 34531000,,,,,,0zxxxxxxxxxxxxxxstxxxxxx x x x x x x 用单纯型法求解最优解： 初始单纯型表 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/...
