同濟(jì)運(yùn)籌學(xué)2005到2006期末試卷A

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

2、下表。問(wèn)a1、a2、a3、a4、a5 、a6分別為何值時(shí)：（本題共13分） -3 0 1 0 -1a1 1 0 0 2a2 0 0 1 a32a44 a5 0 0 0 a6(1) (1) 表中給出線性規(guī)劃是唯一解；(2)表中給出線性規(guī)劃有無(wú)窮多解； (3)表中給出線性規(guī)劃的可行解無(wú)界； (4)表中給出線性規(guī)劃為換入變量，為換出變量； 三、給出線性規(guī)劃：（本題共10分） （1）寫出對(duì)偶問(wèn)題；（2）已知，是上述線性規(guī)劃的最優(yōu)解，用互補(bǔ)松弛定理求對(duì)偶問(wèn)題的最優(yōu)解。四、已知線性規(guī)劃：（本題共12分） 標(biāo)準(zhǔn)化后的初始表和最優(yōu)表如下（）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）求對(duì)偶問(wèn)題的最優(yōu)解。（2）若該LP問(wèn)題原目標(biāo)函數(shù)中X1 的系數(shù)由7變?yōu)?，問(wèn)最優(yōu)解有什么變化？（3） 若右端常數(shù)由變?yōu)?，?wèn)最優(yōu)解有什么變化？ 五、若發(fā)點(diǎn)，及收點(diǎn)，的有關(guān)數(shù)據(jù)如下表所示。假定，處允許物資存儲(chǔ)，問(wèn)怎樣調(diào)配以使總的支付費(fèi)用最少？試建立運(yùn)輸模型再進(jìn)行求解。（本題共10分） 供應(yīng)量存儲(chǔ)費(fèi)4 6 86 2 420020054需求量50 100 100六、用分支定界法求解整數(shù)規(guī)劃問(wèn)題：（本題共10分） s.t. 七、

4、已知4個(gè)人做4件事情的收益如下表，問(wèn)如何分配任務(wù)使得收益最大化。（本題共10分） 11 8 9 12 6 7 8 10 14 12 10 7 7 5 8 6八、用Dijkstra法求到各頂點(diǎn)的最短路。（本題共10分） 九、下圖中弧旁的數(shù)字（，）（表示容量，表示流量）：（本題共10分）（1）驗(yàn)證圖中的流是可行流； （2）求網(wǎng)絡(luò)的最大流；（3）證明（2）中求出的流是最大流。20052006運(yùn)籌學(xué)（I）課程試卷A參考答案一、辨析題（本題共5小題，每小題3分，共15分）1.答：可以。（1分）因?yàn)樗鶎?duì)應(yīng)的檢驗(yàn)數(shù)為“-1”，把作為進(jìn)基變量，仍然可以改進(jìn)目標(biāo)函數(shù)值。（2分）2.答：對(duì)。（1分）因?yàn)樵瓎?wèn)題和對(duì)

5、偶問(wèn)題都有可行解，則兩問(wèn)題必有最優(yōu)解，則依照對(duì)偶問(wèn)題的性質(zhì)可知，原問(wèn)題的目標(biāo)函數(shù)值一定大于等于對(duì)偶問(wèn)題的目標(biāo)函數(shù)值。（2分）3.答：不可以。（1分）因?yàn)樵摼€性規(guī)劃只有4個(gè)獨(dú)立約束，則相應(yīng)基變量只有4個(gè)，則的解中最多只有4個(gè)是非零。（2分）4.答：獨(dú)立約束條件有m+n-1個(gè)。（1分）因?yàn)?，該運(yùn)輸問(wèn)題數(shù)學(xué)模型中雖然有m+n個(gè)約束條件，但其中一個(gè)是沉余項(xiàng)，約束條件中實(shí)際只有m+n-1個(gè)條件是獨(dú)立的。（2分）5.答：不是唯一。（1分）因?yàn)橘x權(quán)圖中邊的所賦權(quán)可能是相同的，在這種情況下得到的最小生成樹(shù)就不唯一的。（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)其對(duì)偶問(wèn)題如下： ，。(3分) (2)使用互補(bǔ)松弛定理，得到如下結(jié)果：(其中為取最優(yōu)解時(shí)約束條件不等號(hào)左右兩邊的差值，) (=4)=0 (=6)=0 (=0)=0 ，。 （2分） 由此得到：=0，=0。 （2分） 所以： 得到： （2分） 則對(duì)偶問(wèn)題的最優(yōu)解為。（1分）四、解：(1)根據(jù)對(duì)偶問(wèn)題最優(yōu)解與原問(wèn)題最優(yōu)表的聯(lián)系，可以直接得到對(duì)偶問(wèn)題的最優(yōu)解為： 。 （3分） (2)由題意可知：， 因此可知：該最優(yōu)表中的最優(yōu)基不變， 所以：最優(yōu)解不發(fā)生變化。 （3分） (3)由最優(yōu)表中的信息可得： ，（1分） 則 ，

7、（2分）將代替最優(yōu)表中的，采用對(duì)偶單純形法繼續(xù)求解得到最終最優(yōu)表為：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分）由此可知：最優(yōu)解產(chǎn)生了變化，且最優(yōu)解為。（1分）五、解：該運(yùn)輸問(wèn)題為產(chǎn)銷的問(wèn)題，虛擬銷地，形成新的問(wèn)題： 供應(yīng)量4 6 8 56 2 4 4200200需求量50 100 100 150 （2分）設(shè)的運(yùn)輸量為，則由新的運(yùn)輸問(wèn)題可以得到： ， （2分）使用最小元素法得到初始解： 供應(yīng)量50 100 50 100 100200200需求量50 100 100 150 （2分）使用位勢(shì)法，得

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