補(bǔ)充線性規(guī)劃問(wèn)題練習(xí)題解答

./補(bǔ)充線性規(guī)劃問(wèn)題習(xí)題及解答1．某銅廠軋制的薄銅板每卷寬度為100cm,現(xiàn)在要在寬度上進(jìn)行切割以完成下列訂貨任務(wù)：24cm寬的75卷,40cm寬的50卷和32cm寬的110卷,長(zhǎng)度是一樣的,試將這個(gè)要解決的切割方案問(wèn)題列成線性規(guī)劃模型,使切余的邊料最少。答：有下面八種切法方方案出品數(shù)〔卷規(guī)格一二三四五六七八需要數(shù)量〔卷24cm40cm32cm4000200031111022102010117550110余料4204412122028設(shè)x1,x2,x3,x4,x5,x6,x7,x8分別表示八種下料方案切割的銅卷數(shù),求解x1,x2,x3,x4,x5,x6,x7,x8使?jié)M足條件：并使余料總數(shù)：Z=4x1+20x2+4x3+4x4+12x5+12x6+20x7+28x8取得最小值。近似最優(yōu)解x1=25/4,x3=20,x4=50其他為0,最優(yōu)值z(mì)*=305。〔不是整數(shù)解2．某養(yǎng)雞場(chǎng)養(yǎng)雞10000只,用大豆和谷物飼料混合喂養(yǎng),每天每只平均吃混合飼料0.5kg,其中應(yīng)至少含有0.1kg蛋白質(zhì)和0.002kg鈣。已知大豆中含50%蛋白質(zhì)和0.5%的鈣,價(jià)格是1.00元/kg,谷物中含有10%的蛋白質(zhì)和0.4%的鈣,價(jià)格是0.30元/kg,糧食部門(mén)每周只保證供應(yīng)谷物飼料25000kg,大豆供應(yīng)量不限,問(wèn)應(yīng)如何搭配兩種飼料,才能使喂養(yǎng)成本最低,建立該問(wèn)題的數(shù)學(xué)模型。50%x1+10%x2≥0.1×7×10000=7000蛋白質(zhì)0.5%x1+0.4%x2≥0.002×7×10000=140鈣x1+x2≤0.5×7×10000=35000總量50%x1+10%x2≥0.1×7×10000=7000蛋白質(zhì)0.5%x1+0.4%x2≥0.002×7×10000=140鈣x1+x2≤0.5×7×10000=35000總量x2≤25000谷物限量x1≥0,x2≥0minz=x1+0.3x2圖解最優(yōu)解x1=9333.33,x2=23333.33,最小值z(mì)*=16333.33。3．一家晝夜服務(wù)的飯店,24小時(shí)需要服務(wù)員的人數(shù)如下每個(gè)服務(wù)員每天連續(xù)工作8小時(shí),且在表中時(shí)段開(kāi)始上班,試求要求滿足以上要求的最少上班人數(shù),建立該問(wèn)題的數(shù)學(xué)模型。解：設(shè)在j鐘點(diǎn)上班的人數(shù)為xj<j=1,2,…,6>,上班之后連續(xù)工作8小時(shí),下班離開(kāi),每班中間不允許交接班離開(kāi)。故有4人8人10人7人12人4人2~6時(shí)x16~10時(shí)x210~14時(shí)x314~18時(shí)x418~22時(shí)x522~2時(shí)x6據(jù)題意有2~6時(shí)x1+x6≥46~10時(shí)x1+x2+≥810~14時(shí)x2+x3≥1014~18時(shí)x3+x4≥718~22時(shí)x4+x5≥1222~2時(shí)x5+x6≥4minz=x1+x2+x3+x4+x5+x6最優(yōu)解x1=4,x2=10,x4=8,x5=4,其他xj=0,最優(yōu)值minz=26〔人4．設(shè)有四個(gè)投資機(jī)會(huì)：甲：在三年,投資人應(yīng)在每年年初投資,每年每元可獲利息0.2元,每年取息后可重新將本息投入生息。乙：在三年,投資人應(yīng)在第一年年初投資,每?jī)赡昝吭色@得利息0.5元,兩年后取息,可重新將本息投入生息。丙：在三年,投資人應(yīng)在第二年年初投資,兩年后每元可獲得利息0.6元,這種投資最多不得超過(guò)15000元。?。和顿Y人應(yīng)在第三年年初投資,一年每元投資可獲利息0.4元,這種投資不得超過(guò)10000元。假定在這三年為期的投資中,開(kāi)始時(shí)有30000元可供投資,投資人應(yīng)怎樣決定投資,才能在第三年底獲得最高的收益,試建立其數(shù)學(xué)模型。解：設(shè)xij為第i年初投放到j(luò)項(xiàng)目的資金數(shù),其數(shù)學(xué)模型為：maxz=1.2x31+1.6x23+1.4x34x11+x12maxz=1.2x31+1.6x23+1.4x34x11+x12≤30000x21+x23≤1.2x11x31+x34≤1.2x21+1.5x12x23≤15000x34≤10000xij≥0,<i=1,2,3,j=1,2,3,4>最優(yōu)解x11=12500,x12=17500,x23=15000,x31=16250,x34=10000,其他為0；最優(yōu)值z(mì)*=575005．某一求目標(biāo)函數(shù)最大值的線性規(guī)劃問(wèn)題,用單純形法求解時(shí)得到的某一步的單純形表如下：?jiǎn)朼1,a2,a3,c,d各為何值及變量xj屬于那一類(lèi)性質(zhì)的變量時(shí)：〔1現(xiàn)有解為唯一最優(yōu)解?！?現(xiàn)有解為最優(yōu),但最優(yōu)解有無(wú)窮多個(gè)。〔3存在可行解,但目標(biāo)函數(shù)無(wú)界。〔4此問(wèn)題無(wú)可行解。答：1.c＜0,d≥0,x3,x4,x5都不是人工變量；2.c=0,d≥0,a1,a2至少一個(gè)大于零,x3,x4,x5都不是人工變量；3.c＞0,d≥0,a1≤0,a2≤0,x3,x4,x5都不是人工變量；4.c≤0,d＞0且x3,x4,x5至少一個(gè)是人工變量。6.某線性規(guī)劃問(wèn)題的初始單純形表及迭代后的表格如下：求a,b,…,k,l各個(gè)值。答：a=3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0,i=5,j=5,k=-3/2,l=07.寫(xiě)出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題：〔1答:〔2答:8．用對(duì)偶單純形法求解下列線性規(guī)劃問(wèn)題:〔1解:化成標(biāo)準(zhǔn)形式,列對(duì)偶單純形表cj-1-100bCBXBx1x2x3x400x3x4-2-110-1-701-4-7λj=cj-zj-1-1000采用對(duì)偶單純形迭代規(guī)則得最優(yōu)表：-1-1x1x2107/131/13011/13-2/1321/1310/13λj=cj-zj00-6/13-1/1331/13最優(yōu)解X=<21/13,10/13,0,0>,最優(yōu)值minZ=31/13<maxZ’=-31/13>?！?解:化成標(biāo)準(zhǔn)形式,列對(duì)偶單純形表cj-4-12-1800bCBXBx1x2x3x4x500X4X5-10-3100<-2>-201-3-5λj=cj-zj-4-12-18000-12X4X2-10<-3>100110-1/2-35/2λj=cj-zj-40-60-6-18-12X3X21/301-1/301/3100-1/213/2λj=cj-zj-200-2-6最優(yōu)解X=<0,3/2,1,0,0>,最優(yōu)值minZ=36<maxZ’=0-<3/2>×12-1×18=-36>。9．設(shè)〔1寫(xiě)出其對(duì)偶問(wèn)題?！?求解對(duì)偶問(wèn)題。〔3從對(duì)偶解中求出原問(wèn)題的解。答：〔1對(duì)偶模型〔2求解對(duì)偶問(wèn)題,圖解法。得Y=<-3,1>,w*=-15。〔3利用互補(bǔ)松弛性求原問(wèn)題解,由y1,y2異于0,知原約束均為等式；又由對(duì)偶約束1,2,4式為嚴(yán)格不等式,故可得x1,x2,x4等于0。代入原約束方程組,解得x3=3,x5=3,即X*=<0,0,3,0,3>T,最優(yōu)值z(mì)*=-1×3-4×3=-15=w*。10．從下面最優(yōu)單純形表中〔最大化問(wèn)題,約束條件均為""連接-5-5Z=-5〔1寫(xiě)出原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解。Z=-5〔2求,,并解釋這兩個(gè)數(shù)值的含義。〔3如果以代價(jià)增添第一種資源一個(gè)單位,是否值得？〔4若有人原向你購(gòu)買(mǎi)第三種資源,應(yīng)要價(jià)多少才合算？〔5是否有其它最優(yōu)解,如果沒(méi)有,說(shuō)明為什么？如果有,則求出另一個(gè)最優(yōu)解。解：<1>原問(wèn)題最優(yōu)解X*=<2,0,3/2,0,1,0>T,對(duì)偶問(wèn)題最優(yōu)解Y*=<4,0,9,0,0,0>。<2>在最優(yōu)表上可以得到最優(yōu)基的逆B-1,根據(jù)最優(yōu)表上Pj’=B-1Pj,可解得Pj=BPj’,從而得A,對(duì)偶解單純形因子再由檢驗(yàn)數(shù),可得解得C=<1,1,2,0,0,0>,最優(yōu)值z(mì)*=1×2+0+2×<3/2>=5。在最優(yōu)方案時(shí),有,因?yàn)閎1影子價(jià)格大于0,是稀缺資源,故在一定圍每增加一個(gè)單位該種資源就會(huì)增加4個(gè)單位總收入〔影子價(jià)格或邊際收入為4。對(duì),x6表示第三種資源剩余數(shù)量,該偏導(dǎo)數(shù)值表示資源剩余量對(duì)總收入的影響率。在初始方案時(shí)其值為0,在最佳方案時(shí)其值為-9,從另外角度說(shuō)明引入該資源有利于減少短缺造成的損失或增加收入〔影子價(jià)格為9。<3>如果以代價(jià)增添第一種資源一個(gè)單位,會(huì)增加4個(gè)單位總收入,值得。<4>若有人愿向你購(gòu)買(mǎi)第三種資源,要價(jià)不低于其影子價(jià)格9才合算。<5>在最優(yōu)表上,非基變量x2的檢驗(yàn)數(shù)為0,故最優(yōu)解不唯一。令x2進(jìn)基,x1出基,換基迭代得新最優(yōu)解X*=<0,2,3/2,0,5>T,最優(yōu)值z(mì)*=0+1×2+2<3/2>=5。11．設(shè)先用單純形法求出最優(yōu)解,再分析在下列各條件單獨(dú)變化的情況下最優(yōu)解的變化。〔1約束條件〔2右端常數(shù)由90變?yōu)?0?！?目標(biāo)函數(shù)中x3的系數(shù)由13變?yōu)??！?增加一個(gè)約束條件：解:先用單純形法求出最優(yōu)解MAX:-5X1+5X2+13X3ST:1]-1X1+1X2+3X3+1X4=202]12X1+4X2+10X3+1X5=90得到了第一個(gè)可行基用最大檢驗(yàn)數(shù)法IBAC-551300bX1X2X3X4X51X2520-113102X5010160-2-41Cj-Zj-10000-2-50迭代次數(shù)=2最優(yōu)解MAXZ=100變量名取值檢驗(yàn)數(shù)X100.000000X220X30-2.000000X40-5.000000X510約束標(biāo)號(hào)對(duì)偶價(jià)格<1>5.000000<2>0.000000在最優(yōu)基不變的條件下,變量在目標(biāo)函數(shù)中的系數(shù)的取值區(qū)間變量名現(xiàn)系數(shù)系數(shù)取值區(qū)間X1-5.0000<-?,-5.0000>X25.0000<4.3333,5.0000>X313.0000<-?,15.0000>X40.0000<-?,5.0000>X50.0000<0.0000,1.0000>在最優(yōu)基不變的條件下,右端常數(shù)項(xiàng)的取值區(qū)間約束序號(hào)現(xiàn)常數(shù)常數(shù)取值區(qū)間<1>20.0000<0.0000,22.5000><2>90.0000<80.0000,?>約束條件〔2右端常數(shù)由90變?yōu)?0,不影響最優(yōu)基,只須驗(yàn)證可行性。由最優(yōu)表找到最優(yōu)基的逆,,x5不可行,采用對(duì)偶單純形迭代,x5出基,x3進(jìn)基,IBAC-551300bX1X2X3X4X51X3135-8012-1/22X2552310-53/2Cj-Zj-90-1600-1-1最優(yōu)解變量名取值檢驗(yàn)數(shù)X10-16.000000X25X35X40-1.000000X50-1.000000MAXZ=90<2>目標(biāo)函數(shù)中非基變量x3的系數(shù)c3由13變?yōu)?。檢查檢驗(yàn)數(shù)λ3=c3-CBB-1P3=8-<5,0><3,10>T=8-15=-7<0,最優(yōu)解,最優(yōu)值不變。<3>增加一個(gè)約束條件：,引進(jìn)松弛變量x6作為一個(gè)基變量,在最優(yōu)表添加一行,迭代出單位矩陣和檢驗(yàn)數(shù)形式,判斷是否最優(yōu)解。IBAC-5513000bX1X2X3X4X5X61X2520-1131002X5010160-2-4103X6050235001Cj-Zj-10000-2-500IBAC-5513000bX1X2X3X4X5X61X2520-1131002X5010160-2-4103X60-1050<-4>-301Cj-Zj-10000-2-500采用對(duì)偶單純形迭代,x6出基,x3進(jìn)基,IBAC-5513000bX1X2X3X4X5X61X2525/211/410-5/403/42X501527/200-5/21-1/23X3135/2-5/4013/40-1/4Cj-Zj-95-5/200-7/20-1/2最優(yōu)解MAXZ=95變量名取值檢驗(yàn)數(shù)X10-2.500000X225/2X35/2X40-3.500000X515X60-0.500000約束標(biāo)號(hào)對(duì)偶價(jià)格<1>3.500000<2>0.000000<3>0.500000在最優(yōu)基不變的條件下,變量在目標(biāo)函數(shù)中的系數(shù)的取值區(qū)間變量名現(xiàn)系數(shù)系數(shù)取值區(qū)間X1-5.0000<-?,-2.5000>X25.0000<4.3333,7.8000>X313.0000<8.3333,15.0000>X40.0000<-?,3.5000>X50.0000<-0.1852,1.0000>X60.0000<-?,0.5000>在最優(yōu)基不變的條件下,右端常數(shù)項(xiàng)的取值區(qū)間約束序號(hào)現(xiàn)常數(shù)常數(shù)取值區(qū)間<1>20.0000<16.6667,26.0000><2>90.0000<75.0000,?><3>50.0000<33.3333,60.0000>12．設(shè)〔1求在不影響最優(yōu)基的條件下各個(gè)cj的允許變化的圍。〔2求在不影響最優(yōu)基的條件下各個(gè)bi的允許變化的圍。解：列單純形表求解得最優(yōu)表,利用最優(yōu)基不變時(shí)求解各系數(shù)區(qū)間MAX:2X1+5X2+8X3ST:1]3X1+2X2-1X3+1X4=6102]-1X1+6X2+3X3+1X5=1253]-1X1+1X2+1/2X3+1X6=420MAX:2X1+5X2+8X3ST:1]3X1+2X2-1X3+1X4=6102]-1X1+6X2+3X3+1X5=1253]-1X1+1X2+1/2X3+1X6=420得到了第一個(gè)可行基用最大檢驗(yàn)數(shù)法IBAC258000bX1X2X3X4X5X61X4061032-11002X50125-163010125/33X60420-111/2001840Cj-Zj0258000旋轉(zhuǎn)元是A[2][3]用最大檢驗(yàn)數(shù)法IBAC258000bX1X2X3X4X5X61X401955/38/34011/301955/82X38125/3-1/32101/303X602395/6-5/6000-1/61Cj-Zj-1000/314/3-1100-8/30旋轉(zhuǎn)元是A[1][1]用最大檢驗(yàn)數(shù)法IBAC258000bX1X2X3X4X5X61X121955/813/203/81/802X38985/805/211/83/803X609645/1605/405/16-1/161Cj-Zj-5895/40-180-7/4-13/40迭代次數(shù)=2最優(yōu)解MAXZ=5895/4=14733/4=1473.750000變量名