1、 運籌學模擬卷一、填空題：1.下面為一線性規劃模型（Max型）迭代過程中的某一單純形表，表中CB列表示對應基變量的價值系數。Cj行表示各變量的價值系數。要求：（ ）（ ）（ ）（ ）（ ）4（ ）11/202-1206（ ）01/21-1130-Z0-30-2-2-260把單純形表中的空格補充完整。基本可行解為：X*（ ）T目標函數值為：Z（ ）。當前基本可行解是否是最優解。（ ）注：填是或不是2.已知某線性規劃問題用單純形法計算時得到的初始單純形表及最終單純形表見下表，請將表中空白處數字填上。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單純形表填空如上表示。基本可行解為：X*（20,0,30,0,0）T目標函數值為：Z（260）。是2.已知某線性規劃問題用單純形法計算時得到的初

3、始單純形表及最終單純形表見下表，請將表中空白處數字填上。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）單純形表中基變量的系數列向量為單位列向量，檢

4、驗數為0。（2）從最終單純形表中抄出最優基的逆矩陣，根據單純形表的計算公式分別算出單純形表中xj的系數列向量、檢驗數和基變量的值。二、計算題：1.對于線性規劃模型，請先把模型化成標準型，然后用單純形表迭代求其最優解。解：添加松馳變量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最優解為：， Z36 2. 某建筑工地每月需求水泥量為1200噸,每噸定價為1500元,不允許缺貨。設每噸每月的存儲費為價格的2，每次訂貨費為1800元,需要提前7天訂貨。試求經濟訂購批量、每月總費用和再訂貨點。解：Ch30（元/噸·月），CO1800（元/次），R1200（噸/月） 故 最小費用：， 再訂貨點：LRTL1200×7÷30280噸。 3.已知某運輸問題

6、的供輸關系及單位運價表如下表示：產地 銷地B1B2B3產量A14258A23537A31324需求量4851)列出產銷平衡表，并用行列差值法給出該運輸問題的初始基可行解。2)用位勢法求初始可行解對應的各非基變量的檢驗數。3)求出該運輸問題的最優解。解.產大于銷，增添假想銷地B4，列出產銷平衡表(3分)，用行列差值法給初始解（5分）如下表示：銷地產地B1B2B3B4產量行差值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、的檢驗數：對基變量有：Rij=cij(ui+vj)=0，求出行、列位勢，如表示：銷地產地B1B2B3B4產量行位勢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)求出非基變量的檢驗數：R11=5，R13=5，R14=3，R21=1，R32=1，R34=1。選x32為入基變量，作閉回路調整，調整量為0，如表示：銷地產地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)求出非基變量的檢驗數：R11=4，R13=4，R14=2，R21=1，R22=1，R34=1。當前調運方案為最優方案，如上表示，最小運費Z2×83×51×435。4.求下面網絡節點1到節點7的最短路徑。v2v3v4v6v7v14655567v541812解：用T、P標號算法：給v1點標P標號，其他點標T標號，為。（1分）從v1點出發，修改v2、v3、v4點的T標號，并把其中最小者改為P標號。T(v2)=4=P(v2)，T(v3)=6，T(v4)=5= P(v4)。（2

9、分）從剛剛獲得P標號的點v2出發，可達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.已知線性規劃問題：其對偶問題的最優解為：，要求：寫出該問題的對偶問題。應用對偶規劃的性質，求原問題的最優解。（2分）（2分）（1分）（

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

11、34101625303220121721223010141617解：設給每一個地區設置一個銷售點為一個階段，共三個階段。 xk為給第k個地區設置的銷售點數。 Sk為第k階段還剩余的銷售點數，S14 狀態轉移方程為：Sk+1=Skxk dk(xk)為在第k個地區設置xk個銷售點增加利潤。 最優指標函數fk(Sk)為第k階段把Sk個銷售點時分給第k、k+1,3個銷售點獲取的最大收益。指標函數遞推方程：，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最優決策方案為：第一個地區設置2個銷售點，第二個地區設置1個銷售點，第三個地區設置1個銷售點，每月可獲總利潤為47。 7.設某工廠自國外進口一部精密機器，由機器制造廠至出口港有三個港口可選擇，而進口港又有三個可選擇，進口后可經由兩個城市到達目的地，其間的運輸費用如圖所示（單位：百元），試把該問題描述成一個多階段決策問題，并用動態規劃方法求解。2

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