運籌學模擬卷

1、 運籌學模擬卷一、填空題：1.下面為一線性規(guī)劃模型（Max型）迭代過程中的某一單純形表，表中CB列表示對應基變量的價值系數(shù)。Cj行表示各變量的價值系數(shù)。要求：（ ）（ ）（ ）（ ）（ ）4（ ）11/202-1206（ ）01/21-1130-Z0-30-2-2-260把單純形表中的空格補充完整?；究尚薪鉃椋篨*（ ）T目標函數(shù)值為：Z（ ）。當前基本可行解是否是最優(yōu)解。（ ）注：填是或不是2.已知某線性規(guī)劃問題用單純形法計算時得到的初始單純形表及最終單純形表見下表，請將表中空白處數(shù)字填上。cj 2 -1 1 0 0 0CBXB x1 x2 x3 x4 x5 x6b000x4x5 x6 3

2、 1 1 1 0 0 1 -1 2 0 1 0 1 1 -1 0 0 1601020-Z 2 -1 1 0 0 000x4( ) ( ) 1 ( ) -1 -2( )2x1( ) ( ) 0.5 ( ) 1/2 1/2( )( )x2( ) ( ) -1.5 ( ) -1/2 1/2( )-Z( ) ( ) ( ) ( ) （ ） ( )( )1.（4）（2）（6）（0）（0）4（x1）102-1206(x3)01-1130-Z0-30-2-2-260單純形表填空如上表示?；究尚薪鉃椋篨*（20,0,30,0,0）T目標函數(shù)值為：Z（260）。是2.已知某線性規(guī)劃問題用單純形法計算時得到的初

3、始單純形表及最終單純形表見下表，請將表中空白處數(shù)字填上。cj 2 -1 1 0 0 0CBXB x1 x2 x3 x4 x5 x6b000x4x5 x6 3 1 1 1 0 0 1 -1 2 0 1 0 1 1 -1 0 0 1601020-Z 2 -1 1 0 0 000x4（0） (0) 1 (1) -1 -2(10)2x1（1） (0) 0.5 (0) 1/2 1/2(15)(-1)x2（0） (1) -1.5 (0) -1/2 1/2(5)-Z（0） (0) (-1.5) （0） (-1.5) (-0.5 )(-25)注：計算方法如下：（1）單純形表中基變量的系數(shù)列向量為單位列向量，檢

4、驗數(shù)為0。（2）從最終單純形表中抄出最優(yōu)基的逆矩陣，根據(jù)單純形表的計算公式分別算出單純形表中xj的系數(shù)列向量、檢驗數(shù)和基變量的值。二、計算題：1.對于線性規(guī)劃模型，請先把模型化成標準型，然后用單純形表迭代求其最優(yōu)解。解：添加松馳變量x3,x4,x5把模型化成標準型： （5分）單純形表迭代過程如下:(每一單純形表各占6分,其中正確寫出基變量1分,b列1分,其余計算4分)cj3 5 0 0 0CBXBx1 x2 x3 x4 x5b000x3x4x51 0 1 0 0 0 2 0 1 03 2 0 0 141218 6 9Z3 5 0 0 00050x3x2x51 0 1 0 00 1 0 1/2

5、03 0 0 -1 1 46462Z3 0 0 -5/2 030053x3x2x10 0 1 1/3 -1/30 1 0 1/2 01 0 0 -1/3 1/3262Z0 0 0 -3/2 -1-36最優(yōu)解為：， Z36 2. 某建筑工地每月需求水泥量為1200噸,每噸定價為1500元,不允許缺貨。設每噸每月的存儲費為價格的2，每次訂貨費為1800元,需要提前7天訂貨。試求經(jīng)濟訂購批量、每月總費用和再訂貨點。解：Ch30（元/噸·月），CO1800（元/次），R1200（噸/月） 故 最小費用：， 再訂貨點：LRTL1200×7÷30280噸。 3.已知某運輸問題

6、的供輸關系及單位運價表如下表示：產(chǎn)地 銷地B1B2B3產(chǎn)量A14258A23537A31324需求量4851)列出產(chǎn)銷平衡表，并用行列差值法給出該運輸問題的初始基可行解。2)用位勢法求初始可行解對應的各非基變量的檢驗數(shù)。3)求出該運輸問題的最優(yōu)解。解.產(chǎn)大于銷，增添假想銷地B4，列出產(chǎn)銷平衡表(3分)，用行列差值法給初始解（5分）如下表示：銷地產(chǎn)地B1B2B3B4產(chǎn)量行差值A14（）2（8）5（）0（）82,2,3A23（）5（0）3（5）0（2）73,0,2A31（4）3（）2（0）0（）41,1,-需求量4852列差值2,2,-1,1,31,1,22,-用位勢法求初始可行解對應的各非基變量

7、的檢驗數(shù)：對基變量有：Rij=cij(ui+vj)=0，求出行、列位勢，如表示：銷地產(chǎn)地B1B2B3B4產(chǎn)量行位勢A14（）2（8）5（）0（）8u1=0A23（）5（0）3（5）0（2）7u2=3A31（4）3（）2（0）0（）4u3=2需求量4852列位勢v1=1v2=2v3=0v4=3利用Rij=cij(ui+vj)求出非基變量的檢驗數(shù)：R11=5，R13=5，R14=3，R21=1，R32=1，R34=1。選x32為入基變量，作閉回路調整，調整量為0，如表示：銷地產(chǎn)地B1B2B3B4行位勢A14（）2（8）5（）0（）u1=0A23（）5（）3（5）0（2）u2=2A31（4）3（0）

8、2（0）0（）u3=1列位勢v1=0v2=2v3=1v4=2 再次利用Rij=cij(ui+vj)求出非基變量的檢驗數(shù)：R11=4，R13=4，R14=2，R21=1，R22=1，R34=1。當前調運方案為最優(yōu)方案，如上表示，最小運費Z2×83×51×435。4.求下面網(wǎng)絡節(jié)點1到節(jié)點7的最短路徑。v2v3v4v6v7v14655567v541812解：用T、P標號算法：給v1點標P標號，其他點標T標號，為。（1分）從v1點出發(fā)，修改v2、v3、v4點的T標號，并把其中最小者改為P標號。T(v2)=4=P(v2)，T(v3)=6，T(v4)=5= P(v4)。（2

9、分）從剛剛獲得P標號的點v2出發(fā)，可達v3,v5（與其相鄰的且還未獲得P標號的點）,修改其T標號，并把最小T標號v3,v5改為P標號。（2分）T(v3)=min6，p(v2)+d23=min6,4+1=5=P(v3)，T(v5)=11。依此類推，各點的P標號如圖所示。（其余各個P標號點各占2分）從v1到v7的最短路為：v1 v2v3v5v7或v1 v2v3v6v5v7，距離為16。（2分）4v2v3v4v6v7v14655567v541812100516955.已知線性規(guī)劃問題：其對偶問題的最優(yōu)解為：，要求：寫出該問題的對偶問題。應用對偶規(guī)劃的性質，求原問題的最優(yōu)解。（2分）（2分）（1分）（

10、2分）（2分）（1分）解：（1）其對偶問題為：（2）設對偶問題的松馳變量為ys1，ys2，ys3，ys4，把代入對偶問題中的約束方程，知ys10，ys20，由互補松馳性有：x1=x2=0。又由，均不等于0，由互補松馳性知原問題的兩個約束對應的松馳變量xs10，xs20，則原問題約束方程可化為：，解得x34，x44。 即原問題最優(yōu)解為：X*（0,0,4,4）T，Z44。 6.某公司打算在三個不同的地區(qū)設置4個銷售點，根據(jù)市場預測部門估計，在不同的地區(qū)設置不同數(shù)量的銷售店，每月可得到的利潤如表1所示。試問在各個地區(qū)應如何設置銷售點，才能使每月獲得的總利潤最大？其值是多少? 表1銷售店利潤地區(qū)012

11、34101625303220121721223010141617解：設給每一個地區(qū)設置一個銷售點為一個階段，共三個階段。 xk為給第k個地區(qū)設置的銷售點數(shù)。 Sk為第k階段還剩余的銷售點數(shù)，S14 狀態(tài)轉移方程為：Sk+1=Skxk dk(xk)為在第k個地區(qū)設置xk個銷售點增加利潤。 最優(yōu)指標函數(shù)fk(Sk)為第k階段把Sk個銷售點時分給第k、k+1,3個銷售點獲取的最大收益。指標函數(shù)遞推方程：，k=2,1 邊界方程為：。 逆推計算如下：k=3時：S3=x3 x3S3x3012340000110101214142316163417174k=2時：S3= S2x2 x3S3x201234000

12、0101012+012120+1412+1017+022130+1612+1417+1021+027240+1712+1617+1421+1022+0312或3k=1時：S2= S1x1 x1S1x2012344031162725223012320472最優(yōu)決策方案為：第一個地區(qū)設置2個銷售點，第二個地區(qū)設置1個銷售點，第三個地區(qū)設置1個銷售點，每月可獲總利潤為47。 7.設某工廠自國外進口一部精密機器，由機器制造廠至出口港有三個港口可選擇，而進口港又有三個可選擇，進口后可經(jīng)由兩個城市到達目的地，其間的運輸費用如圖所示（單位：百元），試把該問題描述成一個多階段決策問題，并用動態(tài)規(guī)劃方法求解。2

13、040307040203010405603030303040401050AB1B2B3C1C2C3D1D2E解：按決策的過程分為四個階段。狀態(tài)變量Sk為第k階段的起點。xk為第k階段的決策變量，狀態(tài)轉移方程為：SK+1xk(Sk)。k=1,2,3,4。階段指標函數(shù)為Sk到xk(Sk)的距離值，最優(yōu)指標函數(shù)fk(Sk)為第k階段狀態(tài)為Sk時，從Sk到終點E的最短距離值。指標函數(shù)遞推方程：，k=3,2,1 邊界方程為：。 下面列表計算如下：k=4時，出發(fā)點有D1、D2，分別計算由各狀態(tài)到終點的最短路徑值： u4S4d4(S4, u4)f4 (S4)u4ED13030ED24040Ek=3時，出發(fā)點有C1、C2、C3三個，分別計算由各狀態(tài)到終點的最短路徑值，如表示： u3S3d3(S3, u3)+ f4(S4)f3 (S3)u 3D1D2C110+30404040D1C260+3030+4070D2C330+3030+4060D1k=2時，狀態(tài)集合為：S2B1，B2，B3，分別計算由各狀態(tài)到終點的最短路徑值，如表示：u2S2d2(S2, X2)+ f3 (S