東南大學(xué)運(yùn)籌學(xué)試卷(共8頁)

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

2、問題的最優(yōu)解，若目標(biāo)函數(shù)中用C* 帶替C后，問題的最優(yōu)解變?yōu)閄* ，求證：(10分)四、求V1到各點(diǎn)的最短路。（10分）五、證明任何有n個(gè)節(jié)點(diǎn)n條邊的簡單圖中必存在圈。（10分）六、求下圖所示的網(wǎng)絡(luò)中，每條弧旁邊的數(shù)字是，（15分）VSV2V1V3Vt(4,3)(1,0)(3,1)(2,2)(2,2)(5,2)(3,3)（1）確定所有的截集；（2）求最小截集的容量；（3）證明指出的流是最大流七、試解二次規(guī)劃（15分）問題答案：1. 解：（1）首先把問題轉(zhuǎn)化成標(biāo)準(zhǔn)型：用單純型法求解最優(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）由互補(bǔ)松弛性可得，其對偶問題最優(yōu)解為：（0，1/4，1）；（3）當(dāng)時(shí)所以因此可得出最優(yōu)基發(fā)生變化，因?yàn)?，需要用對偶單純型法繼續(xù)求解；（4）若保證最優(yōu)基不變，需要滿足以下條件： 從而得出-1<<1/3（5）X3的系數(shù)發(fā)生變化：同時(shí)計(jì)算P3的檢驗(yàn)數(shù)為：，因此可以得出尚未得到最優(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）由單純型表可以看出，由于而所以，則對偶問題的第一、二個(gè)約束是緊的，可解出將代入第三個(gè)約束，滿足約束條件，則（3）5和2（4）（

5、5）如果原問題增加一個(gè)變量，則對偶問題增加一個(gè)約束，因此其可行域要么減小，要不不變，但絕不會(huì)增大。3. 證明：因?yàn)閄0 和X*都滿足 所以X0 和X*都是兩個(gè)問題的可行解。又因?yàn)閄0 是最優(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. 證明：設(shè)有V1，V2，V3，Vn個(gè)點(diǎn)，構(gòu)成簡單圖G(V,E)，假設(shè)圖中不存在圈，若簡單圖為連通圖，由樹的定義無圈的連通圖為樹，并且簡單圖G無環(huán)五多重邊，因此可知G為樹，由樹的定義可得：q(G)=P(G)-1=n-1，與已知圖有n條邊矛盾，因此可得假設(shè)不成立，圖中一定存在圈；若簡單圖為非連通圖，則至少有兩個(gè)連通分圖，由于每個(gè)連通分圖無圈，則可得每個(gè)連通分圖都為一顆樹，設(shè)有k個(gè)連通子圖，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條邊不符，因此，假設(shè)不成立所以問題得證6. 解：（1）首先確定所有的截集與對應(yīng)的容量：若，則其截集為 其容量為若，則其截集為 其容量為若，則其截集為 其容量為若，則其截集為 其容量為若，則其截集為 其容量為若，則其截集為 其容量為若，則其截集為 其容量為若，則其截集為 其容量為（2）由（1）所求，最小截集的容量為 其中。（3）根據(jù)最大流量最小截量定理，最大流量