1、20052006運籌學（I）課程試卷A一、辨析題（詳細說明理由）。（每小題3分，本題共15分）1.一個極小化線性規劃的某輪表格中有=(-1，-2，0，0，0)，請問是否可以選擇作為進基變量？為什么？2.線性規劃原問題和對偶問題都有可行解，則原問題的目標函數值一定不小于對偶問題的目標函數值？為什么？3.有一個線性規劃，它有8個變量、4個獨立的約束。請問(1，2，3，4，5，0，0，0)是否可以是它的一個基本可行解？為什么？4. m個發點，n個收點的產銷平衡運輸問題數學模型約束條件中，獨立約束條件有多少個？為什么？5.一個賦權圖的最小生成樹是否唯一？為什么？二、求極小化線性規劃問題的一個單純形表如

2、下表。問a1、a2、a3、a4、a5 、a6分別為何值時：（本題共13分） -3 0 1 0 -1a1 1 0 0 2a2 0 0 1 a32a44 a5 0 0 0 a6(1) (1) 表中給出線性規劃是唯一解；(2)表中給出線性規劃有無窮多解； (3)表中給出線性規劃的可行解無界； (4)表中給出線性規劃為換入變量，為換出變量； 三、給出線性規劃：（本題共10分） （1）寫出對偶問題；（2）已知，是上述線性規劃的最優解，用互補松弛定理求對偶問題的最優解。四、已知線性規劃：（本題共12分） 標準化后的初始表和最優表如下（）CjCB XB7 12 10 0 0X1 X2 X3 X4 X5b0

3、X40 X5 1 1 1 1 0 2 2 1 0 120307 12 10 0 010 X312 X2 0 0 1 2 11 1 0 1 1 10 10 5 0 0 8 2（1）求對偶問題的最優解。（2）若該LP問題原目標函數中X1 的系數由7變為9，問最優解有什么變化？（3） 若右端常數由變為，問最優解有什么變化？ 五、若發點，及收點，的有關數據如下表所示。假定，處允許物資存儲，問怎樣調配以使總的支付費用最少？試建立運輸模型再進行求解。（本題共10分） 供應量存儲費4 6 86 2 420020054需求量50 100 100六、用分支定界法求解整數規劃問題：（本題共10分） s.t. 七、

4、已知4個人做4件事情的收益如下表，問如何分配任務使得收益最大化。（本題共10分） 11 8 9 12 6 7 8 10 14 12 10 7 7 5 8 6八、用Dijkstra法求到各頂點的最短路。（本題共10分） 九、下圖中弧旁的數字（，）（表示容量，表示流量）：（本題共10分）（1）驗證圖中的流是可行流； （2）求網絡的最大流；（3）證明（2）中求出的流是最大流。20052006運籌學（I）課程試卷A參考答案一、辨析題（本題共5小題，每小題3分，共15分）1.答：可以。（1分）因為所對應的檢驗數為“-1”，把作為進基變量，仍然可以改進目標函數值。（2分）2.答：對。（1分）因為原問題和對

5、偶問題都有可行解，則兩問題必有最優解，則依照對偶問題的性質可知，原問題的目標函數值一定大于等于對偶問題的目標函數值。（2分）3.答：不可以。（1分）因為該線性規劃只有4個獨立約束，則相應基變量只有4個，則的解中最多只有4個是非零。（2分）4.答：獨立約束條件有m+n-1個。（1分）因為，該運輸問題數學模型中雖然有m+n個約束條件，但其中一個是沉余項，約束條件中實際只有m+n-1個條件是獨立的。（2分）5.答：不是唯一。（1分）因為賦權圖中邊的所賦權可能是相同的，在這種情況下得到的最小生成樹就不唯一的。（2分）二、解：(1) , 0，。(3分)(2) 0、0 , =0，0。(3分) (3) ，0

6、，0，0。(3分) (4) ，0，0，0, 0且或，0，0,0。(4分)三、解：(1)其對偶問題如下： ，。(3分) (2)使用互補松弛定理，得到如下結果：(其中為取最優解時約束條件不等號左右兩邊的差值，) (=4)=0 (=6)=0 (=0)=0 ，。 （2分） 由此得到：=0，=0。 （2分） 所以： 得到： （2分） 則對偶問題的最優解為。（1分）四、解：(1)根據對偶問題最優解與原問題最優表的聯系，可以直接得到對偶問題的最優解為： 。 （3分） (2)由題意可知：， 因此可知：該最優表中的最優基不變， 所以：最優解不發生變化。 （3分） (3)由最優表中的信息可得： ，（1分） 則 ，

7、（2分）將代替最優表中的，采用對偶單純形法繼續求解得到最終最優表為：CB XBX1 X2 X3 X4 X5b10 X30 X4 2 2 1 0 1 1 1 0 1 1 30 10 13 8 0 0 10 （2分）由此可知：最優解產生了變化，且最優解為。（1分）五、解：該運輸問題為產銷的問題，虛擬銷地，形成新的問題： 供應量4 6 8 56 2 4 4200200需求量50 100 100 150 （2分）設的運輸量為，則由新的運輸問題可以得到： ， （2分）使用最小元素法得到初始解： 供應量50 100 50 100 100200200需求量50 100 100 150 （2分）使用位勢法，得

8、到檢驗數為： 0 3 0 03 0 -3 00-14 3 8 5增加的運輸量，得到新的解為： 供應量50 0 150 100 100200200需求量50 100 100 150 （2分）使用位勢法，得到檢驗數為： 0 0 0 06 0 0 30-44 6 8 5因此可知： 供應量50 0 150 100 100200200需求量50 100 100 150為該運輸問題的最優解。（2分）六、解：采用分支定界法進行求解，其求解枚舉樹圖如下： 9 （2，3/2） （2分） 8 17/2 （2，1） （3/2，2） （2分） 7 （1，2） （2分） 無可行解 （2分）由分支定界法求解過程可知，最優解為，其對應的最優值為：。（2分）七、解：注意到本題要求求解收益最大化，因此按照極大化問題轉化為極小化問題的原則，并按照匈牙利方法計算如下： （2分） （2分） （2分）