運(yùn)籌學(xué)模擬卷

1、 運(yùn)籌學(xué)模擬卷一、填空題：1.下面為一線性規(guī)劃模型（Max型）迭代過程中的某一單純形表，表中CB列表示對應(yīng)基變量的價(jià)值系數(shù)。Cj行表示各變量的價(jià)值系數(shù)。要求：（ ）（ ）（ ）（ ）（ ）4（ ）11/202-1206（ ）01/21-1130-Z0-30-2-2-260把單純形表中的空格補(bǔ)充完整?；究尚薪鉃椋篨*（ ）T目標(biāo)函數(shù)值為：Z（ ）。當(dāng)前基本可行解是否是最優(yōu)解。（ ）注：填是或不是2.已知某線性規(guī)劃問題用單純形法計(jì)算時(shí)得到的初始單純形表及最終單純形表見下表，請將表中空白處數(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目標(biāo)函數(shù)值為：Z（260）。是2.已知某線性規(guī)劃問題用單純形法計(jì)算時(shí)得到的初

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)注：計(jì)算方法如下：（1）單純形表中基變量的系數(shù)列向量為單位列向量，檢

4、驗(yàn)數(shù)為0。（2）從最終單純形表中抄出最優(yōu)基的逆矩陣，根據(jù)單純形表的計(jì)算公式分別算出單純形表中xj的系數(shù)列向量、檢驗(yàn)數(shù)和基變量的值。二、計(jì)算題：1.對于線性規(guī)劃模型，請先把模型化成標(biāo)準(zhǔn)型，然后用單純形表迭代求其最優(yōu)解。解：添加松馳變量x3,x4,x5把模型化成標(biāo)準(zhǔn)型： （5分）單純形表迭代過程如下:(每一單純形表各占6分,其中正確寫出基變量1分,b列1分,其余計(jì)算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噸,每噸定價(jià)為1500元,不允許缺貨。設(shè)每噸每月的存儲(chǔ)費(fèi)為價(jià)格的2，每次訂貨費(fèi)為1800元,需要提前7天訂貨。試求經(jīng)濟(jì)訂購批量、每月總費(fèi)用和再訂貨點(diǎn)。解：Ch30（元/噸·月），CO1800（元/次），R1200（噸/月） 故 最小費(fèi)用：， 再訂貨點(diǎn)：LRTL1200×7÷30280噸。 3.已知某運(yùn)輸問題

6、的供輸關(guān)系及單位運(yùn)價(jià)表如下表示：產(chǎn)地 銷地B1B2B3產(chǎn)量A14258A23537A31324需求量4851)列出產(chǎn)銷平衡表，并用行列差值法給出該運(yùn)輸問題的初始基可行解。2)用位勢法求初始可行解對應(yīng)的各非基變量的檢驗(yàn)數(shù)。3)求出該運(yùn)輸問題的最優(yōu)解。解.產(chǎn)大于銷，增添假想銷地B4，列出產(chǎn)銷平衡表(3分)，用行列差值法給初始解（5分）如下表示：銷地產(chǎn)地B1B2B3B4產(chǎn)量行差值A(chǔ)14（）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,-用位勢法求初始可行解對應(yīng)的各非基變量

7、的檢驗(yàn)數(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)求出非基變量的檢驗(yàn)數(shù)：R11=5，R13=5，R14=3，R21=1，R32=1，R34=1。選x32為入基變量，作閉回路調(diào)整，調(diào)整量為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)求出非基變量的檢驗(yàn)數(shù)：R11=4，R13=4，R14=2，R21=1，R22=1，R34=1。當(dāng)前調(diào)運(yùn)方案為最優(yōu)方案，如上表示，最小運(yùn)費(fèi)Z2×83×51×435。4.求下面網(wǎng)絡(luò)節(jié)點(diǎn)1到節(jié)點(diǎn)7的最短路徑。v2v3v4v6v7v14655567v541812解：用T、P標(biāo)號算法：給v1點(diǎn)標(biāo)P標(biāo)號，其他點(diǎn)標(biāo)T標(biāo)號，為。（1分）從v1點(diǎn)出發(fā)，修改v2、v3、v4點(diǎn)的T標(biāo)號，并把其中最小者改為P標(biāo)號。T(v2)=4=P(v2)，T(v3)=6，T(v4)=5= P(v4)。（2

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

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

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

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

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