東南大學運籌學試卷(共8頁)

1、精選優(yōu)質文檔-傾情為你奉上一、已知線性規(guī)劃問題（25分）（1）求線性規(guī)劃問題的最優(yōu)解；5（2）求對偶問題的最優(yōu)解；5（3）當時最優(yōu)基是否發(fā)生變化？為什么？5（4）求C2 的靈敏度范圍；5（5）如果X3的系數由1，3，5變?yōu)?，3，2最優(yōu)解是否改變，若改變求新的最優(yōu)解；5二、考慮線性規(guī)劃問題，（15）用單純型法求解，得其終表如下：X4為松弛變量，X5為人工變量。（1）上述模型的對偶模型為？（2）對偶模型的最優(yōu)解為？（3）當兩種資源分別單獨增加一單位時，目標函數值分別增加？（4）最優(yōu)基的逆矩陣B-1=?（5）如果原問題增加一個變量，則對偶問題的可行域將可能變大還是變小？三、線性規(guī)劃問題設X0 為該

2、問題的最優(yōu)解，若目標函數中用C* 帶替C后，問題的最優(yōu)解變?yōu)閄* ，求證：(10分)四、求V1到各點的最短路。（10分）五、證明任何有n個節(jié)點n條邊的簡單圖中必存在圈。（10分）六、求下圖所示的網絡中，每條弧旁邊的數字是，（15分）VSV2V1V3Vt(4,3)(1,0)(3,1)(2,2)(2,2)(5,2)(3,3)（1）確定所有的截集；（2）求最小截集的容量；（3）證明指出的流是最大流七、試解二次規(guī)劃（15分）問題答案：1. 解：（1）首先把問題轉化成標準型：用單純型法求解最優(yōu)解：初始單純型表1534000CBXBbX1X2X3X4X5X6X70X580023121000X6120054

3、340100X710003453001Cj-Zj1534000最終單純型表0X51001/40-13/4011/4-14X420020-2101-15X2100-3/4111/400-3/41Cj-Zj-13/40-11/400-1/4-1最優(yōu)解為（0，100，0，200）；（2）由互補松弛性可得，其對偶問題最優(yōu)解為：（0，1/4，1）；（3）當時所以因此可得出最優(yōu)基發(fā)生變化，因為，需要用對偶單純型法繼續(xù)求解；（4）若保證最優(yōu)基不變，需要滿足以下條件： 從而得出-1<<1/3（5）X3的系數發(fā)生變化：同時計算P3的檢驗數為：，因此可以得出尚未得到最優(yōu)解，用單純型法繼續(xù)求解：初始單純

4、型表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最優(yōu)解為（0，150，200，0）；2. 解：（1）上述模型的對偶模型為：（2）由單純型表可以看出，由于而所以，則對偶問題的第一、二個約束是緊的，可解出將代入第三個約束，滿足約束條件，則（3）5和2（4）（

5、5）如果原問題增加一個變量，則對偶問題增加一個約束，因此其可行域要么減小，要不不變，但絕不會增大。3. 證明：因為X0 和X*都滿足 所以X0 和X*都是兩個問題的可行解。又因為X0 是最優(yōu)解，而且原問題求最大，因此可得出：同理可得出：所以可以得出：因此得證：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，具

6、體步驟省略。5. 證明：設有V1，V2，V3，Vn個點，構成簡單圖G(V,E)，假設圖中不存在圈，若簡單圖為連通圖，由樹的定義無圈的連通圖為樹，并且簡單圖G無環(huán)五多重邊，因此可知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）根據最大流量最小截量定理，最大流量