運(yùn)籌學(xué)復(fù)習(xí)題

1、運(yùn)籌學(xué)復(fù)習(xí)題及答案一、一個(gè)毛紡廠用羊毛和滌綸生產(chǎn)A、B、C混紡毛料，生產(chǎn)1單位A、B、C分別需要羊毛和滌綸3、2；1、1；4、4單位，三種產(chǎn)品的單位利潤分別為4、1、5。每個(gè)月購進(jìn)的原料限額羊毛為8000單位，滌綸為3000單位，問此毛紡廠怎樣安排生產(chǎn)能獲得最大利潤？（要求：建立該問題的數(shù)學(xué)模型）解：設(shè)生產(chǎn)混紡毛料ABC各x1、x2、x3單位maxz=xi+x2+5x33xi+x2+4x3W80002xi+x2+4x3W3000 xi,x2,x30二、寫出下述線性規(guī)劃問題的對偶問題maxs=2x1+3x2-5x3+x4X1+X2-3X3+X4A52xi+2x3-x4W4x2+x3+x4=6X1

2、,X2,X30；X4無拘束解：先將原問題標(biāo)準(zhǔn)化為：maxs=2x1+3x2-5x3+x4-X1-X2+3X3-X4W-52x1+2x3-X40；X4無拘束則對偶問題為：minz=-5y1+4y2+6y3-yi+2y22-yi+y233yi+2y2+y3-5-y1-y2+y3=1yi,y20,y3無拘束三、求下述線性規(guī)劃問題minS=2x13x25x3,X1+x23x35彳2x1+2x30解：引入廢弛變量x4,x5，原問題化為標(biāo)準(zhǔn)型:maxZ=-S=-2xi-3x2+5x3/xi+X23X3X4=5彳2xi+2X3+X5=4txi,X2,X3,X4,X50對應(yīng)基Bo=(P2,P5)的單純形表為5

3、11-3-10T(B0)=4202011510-4-30 xi的檢驗(yàn)數(shù)為正，xi進(jìn)基，由min5/1,4/2=4/2知，x5出基，迭代得新基對應(yīng)的單純形表為=(P2,P1),301-4-1-1/2T(B1)=210101/21300-5-3-1/2至此，檢驗(yàn)數(shù)全為非正，已為最優(yōu)單純形表。對應(yīng)的最優(yōu)解為:x1=2,x2=3,x3=x4=x5=0,maxz=-13,故原問題的最優(yōu)解為:x1=2,x2=3,x3=0,mins=13。四、利用大M法求解下面線性規(guī)劃問題：解：引入廢弛變量X4和人工變量X5,構(gòu)造以下規(guī)劃:maxsx12x2X3Mx2x1x2x3x4s.t.x12x2x56X1,X2,X3

4、,X4,X5對應(yīng)基B0=(P4,P5)的單純形表為421110T(B。)602001maxsX12x2X32x1X2X34s.t.X12x26X1,x2,X306-1+M2+2M10M0X1的檢驗(yàn)數(shù)為-1+M0X1進(jìn)基，由min6/1=6/1知，X5出基，迭代得新基B=(P4,PI),對應(yīng)的單純形表為160511口2T(B1)=612001604101-MX3的檢驗(yàn)數(shù)為10，x3進(jìn)基,對由min16/1=16/1知，X4出基,迭代得新基B2=(P3,P1),應(yīng)的單純形表為1605112T(B2)120016-10-10-10-1-M至此，檢驗(yàn)數(shù)全為非正，已為最優(yōu)單純形表。對應(yīng)的最優(yōu)解為:X1=

5、6,X2=0,X3=16,X4=X5=0,最優(yōu)值maxz=10。Mi/其對偶問題(D)為x1x2x3MaxmaxZ=6y1+8y2123五、已知線性規(guī)劃問題(L):2126y11328y2(2)用對偶單純形法求解問題引入廢弛變量x4、x5,構(gòu)造以下規(guī)劃:?zX1mins2x23X32x1X22X36s.t.X13x22X38X1,X2,X30寫出該問題的對偶表，從而給出其對偶問題(D).用對偶單純形法求解問題?解：(1)該問題的對偶表2y1+y21y1+3y22y1+2y2230maxZSX12x2x1X22xs.t.X13x22x2333xxx34568X1,X2,X3,x4,x50對應(yīng)基B

6、Q=(P4,P5)的單純形表為6-2-1-210T(BQ)=8-1-3-2010-1-2-300檢驗(yàn)數(shù)全為非正，基變量X4=-6,x4出基，利用偶單純形法，由min-1/2,2/-1,-3/-2=1/2知，x1進(jìn)基，迭代得新基B=(P,P),對應(yīng)的單純形表為II5基變量X5=5,X5出基,利用偶單純形法知,純形表X2進(jìn)基，迭代得新基R=(PI,P2),對應(yīng)的單為2104/5-3/51/5T(B2)=2012/51/5-2/5600-7/5-1/5-3/5至此，獲得最優(yōu)解:xI=X2=2,X3=X4=X5=0,最優(yōu)值maxZ=-6,故原問題的最優(yōu)解為：311/21-1/20T(B1)=50-5/

7、2-1-1/2130-3/2-2-1/20XI=X2=2,X3=0,最優(yōu)值minS=6.六、某運(yùn)輸問題的產(chǎn)銷平衡表和運(yùn)價(jià)表以下，試用表上作業(yè)法求最優(yōu)調(diào)運(yùn)方案銷地B1B2B3產(chǎn)量產(chǎn)地A11267A204212A331511銷量10101030解：由最小元素法得初始運(yùn)輸方案12B3產(chǎn)量BBA177A210212A310111銷量10101030總運(yùn)費(fèi)S=0X10+1X10+6X7+2X2+5X1=61經(jīng)計(jì)算入n=(6+0)(2+1)=30,調(diào)整量=min(7,10)=7,經(jīng)調(diào)整，得新運(yùn)輸方案:B12B3產(chǎn)量BA177A23912A310111銷量10101030總運(yùn)費(fèi)S=613X7=40至此，所有

8、檢驗(yàn)數(shù)均以非正，該運(yùn)輸方案已為最優(yōu)。即：A1運(yùn)到B17個(gè)單位；A2運(yùn)到B13個(gè)單位；A2運(yùn)到B39個(gè)單位A3運(yùn)到B210個(gè)單位；A3運(yùn)到B31個(gè)單位；總運(yùn)費(fèi)S=40個(gè)單位七、某極大化整數(shù)規(guī)劃對應(yīng)的線性規(guī)劃的最優(yōu)單純形表以下：5/2011/2-1/213/410-1/43/4-69/400-3/4-3/4試建立割平面方程并求原整數(shù)規(guī)劃的最優(yōu)解。解：由X2=5/2為非整數(shù)，對應(yīng)方程為：5/2=X2+1/2X3-1/2X4即：X2-X4-2=1/2-(1/2X3+1/2X4),得Gomery割平面：1/2-(1/2x3+1/2x4)0引入廢弛變量X5,增加拘束：-1/2X3-1/2X4+X5=1/2

9、,由表5/2011/2-1/2013/410-1/43/40-1/200匝-1/21-69/400-3/4-3/40利用對偶單純形法迭代獲得可新單純?表：2010-117/21001-1/210011-2-33/20000-3/2由7/2=X1+X4-1/2X5,得Gomery割平面：1/2-1/2X5+0用單純形法求最優(yōu)解；資源1的影子價(jià)格；(3)資源2由目前的6變?yōu)?,最優(yōu)值會發(fā)生怎樣的變化,最優(yōu)解是多少？(4)對C2進(jìn)行矯捷度解析。解：(1)引入廢弛變量X3,X4，原問題化為標(biāo)準(zhǔn)型:maxS=-XI+2X2-X1+X2+X3=2X1+2X2+X4=6X1,X2,X3,X402-1110T

10、(B0)=612010-1200迭代獲得新基B1=(P2P4)對應(yīng)的單純形表為:,2-1110T(B1)=230-21-410-20迭代獲得新基B2=(P2P1),對應(yīng)的單純形表為:8/3011/31/3T(B2)=2/310-2/31/3-14/300-4/3-1/3至此，檢驗(yàn)數(shù)已經(jīng)請為非正，得原問題得最優(yōu)解：X1=2/3,X2=8/3,最優(yōu)值maxS=14/3.x3的檢驗(yàn)數(shù)的負(fù)數(shù),(2)由最優(yōu)單純形表T(B2)得知資源1的影子價(jià)格為廢弛變量(3)由于最優(yōu)基B=B2的逆矩陣為01/31/31/31/3210/3B-1B-1b=1/3-2/31/3-2/384/3因此,故最優(yōu)基不變，最優(yōu)解改變

11、為:x1=4/3,x2=10/3,對應(yīng)的最優(yōu)值為16/3。(4)設(shè)c2的攝動量為3,最優(yōu)基不變。此時(shí)，C=(-1,2+3,0,0),CB=(2+3,-1),由C-CBB-1A-1,即c2=2+31,故當(dāng)c2在1,+g）變化時(shí)，最優(yōu)基不變，生產(chǎn)計(jì)劃不變?九、某物質(zhì)的產(chǎn)銷平衡表及運(yùn)價(jià)表以下，求總運(yùn)費(fèi)最省的調(diào)運(yùn)方案。平衡表運(yùn)價(jià)表（百元/噸）銷地產(chǎn)量產(chǎn)地、B1B2B3B4（噸）BiB2B3B4A32598A51926A77543銷量（噸）632415解：利用最小元素法獲得初始可行解（運(yùn)輸方案）、銷地產(chǎn)產(chǎn)量地、B1B2B3B4（噸）A3A5T_L.5124A7銷量（噸）632415對應(yīng)的總運(yùn)費(fèi)S0=1X

12、2+2X5+5X1+1X5+2X4+4X3=42(百元)檢驗(yàn)數(shù)?23=C23-（U2+V3）=2-（4-1）=-1,表中不是最優(yōu)運(yùn)輸方案，需調(diào)整，調(diào)整量為=min=2,2,5=2,新運(yùn)輸方案為銷地產(chǎn)量產(chǎn)地、B1B2B3B4（噸）A303A2325A347銷量(噸)632415對應(yīng)的總運(yùn)費(fèi)S1=3X2+0X5+3X1+3X5+2X2+4X3=40(百元)或si=so+也S=42-1X2=40(白兀)利用位勢法計(jì)算檢驗(yàn)數(shù)=Cij-(Ui+Vj),以下:B1B2B3B4UiA550A54-1A520Vj2533此時(shí),檢驗(yàn)數(shù)全為非負(fù)，表中已經(jīng)是最優(yōu)運(yùn)輸方案，總運(yùn)費(fèi)為40百兀十、利用割平面法,求下面冋題：maxs2X1X2X1X26s.t.X14x23X1X20且均為整數(shù)解：引入廢弛變量X3,X4，構(gòu)造輔助LP:maxs2X1X2x1X2X36s.t.x14X2X43x1,x：；,X3,X40對應(yīng)基Bo=的單純形表6111031401T(B)=02100迭代獲得新基Bi=)對應(yīng)的單純形表為(P3P,3051T(B1)=31401609012迭代獲得新基B2=(P2P),對應(yīng)的單純形表為:3/5011/51/5T(B2)=27/5104/51/557/500-9/51/5檢驗(yàn)數(shù)已經(jīng)全為非正，獲得輔助劃LP的最優(yōu)單純形表，由于解不是整數(shù)，因此不是原整數(shù)規(guī)問題的解?對