習(xí)題答案肖勇波 2 第10章非線性規(guī)劃 第11章動態(tài)規(guī)劃 第12章排隊(duì)論基礎(chǔ) 第2章線性規(guī)劃1.用圖解法求解下列線性規(guī)劃問題：對應(yīng)的目標(biāo)函數(shù)值數(shù)的值達(dá)到最大，對應(yīng)的目標(biāo)函數(shù)值為z*=8。2.分別考慮下面的兩個線性規(guī)劃問題，其中c為一個參數(shù)：請問：在兩個線性規(guī)劃問題中，當(dāng)參數(shù)c在什么范圍內(nèi)取值時，最優(yōu)解分別在可行域的A、B、C、D、0點(diǎn)處獲得?3.將下列線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式：minz=2x?-3x?型如下：maxz=2x?-3x?+3x?-4x4-10maxw=-2x?+2x1+初始單純形表需要引入人工變量x?和xg:C13400基b08111100024500001021011001還需要引入m個人工變量z?,Zm。C000基b1110000010000…00001110001010010010000…000…000010010100初始單純形表與(2)同理。初始單純形表與(2)同理。6.利用單純形法求解下列線性規(guī)劃問題，要求求出每個問題的所有最優(yōu)解。C41100θ基b096491031240821011541100 x?入基，x?出基：C41100基b00141151080150x?入基，x4出基：C41100基b10141000最優(yōu)解為(2,0,),z=2。C45000基b032100905100100601001645000 X2入基，x?出基：C45000基b063010205100105560100140000x?入基，x?出基：C45000θ基b42100030015601001000最優(yōu)解為(2,6)T,z=38。C00基b211012031201000x?入基、x4出基，換基迭代后：C00基b12120113121-210120300x?入基、x?出基，換基迭代后：C00基b11021011100C0000基b211012031201031100令x?入基，對應(yīng)xs出基：C0000θC基b0211010101110000C00基bX211020101111010x?入基，x4出基：C00基b1101011100C43000基b21001203301001031000101000x2入基，x4出基：C43000基b1001311000031000105000C00000基b21001203301001031000101000C00000基b10010110000310001000所有非基變量檢驗(yàn)系數(shù)為負(fù)，但x?仍在基內(nèi)，則可行域?yàn)榭占?.考慮下面的線性規(guī)劃問題，其中c為一個參數(shù)：naxX?+CX?請結(jié)合單純形法，探討當(dāng)參數(shù)c在什么范圍內(nèi)取值時，最優(yōu)解分別在可行域的A、B、C、D點(diǎn)處獲得?標(biāo)準(zhǔn)化得：C1C000基b0811100041010040100101C000a)當(dāng)c<1時，x?入基，x4出基C1C000基b0801101611400040100146000iii)1<c<1時，x?入基，x?出基C1C000基bC0101101300001000b)當(dāng)c>1時，x?入基，xs出基C1C000基b0410104040015C4010011000x?入基，x?出基C1C000基401001000C1000基b080108316114000403130014601400??1000基b10101100000080000對應(yīng)點(diǎn)Cii)x2入基，x?出基C1000基b04101040400115140100141000x?入基，x?出基C1000基b14101004001140100180000對應(yīng)點(diǎn)B。所以c=1時，為退化解情形，BC上任一點(diǎn)均為最優(yōu)解。時，最優(yōu)解時，最優(yōu)解9.考慮下面的線性規(guī)劃問題，其中a為一個參數(shù)：請結(jié)合單純形法，探討當(dāng)參數(shù)a在什么范圍內(nèi)取值時，最優(yōu)解由如下方程組聯(lián)立得到?聯(lián)立得到；即最優(yōu)解在C點(diǎn)取得。(若三線交于一點(diǎn)，則為B)C12000基b0811100804a010b04010014812000a)當(dāng)a<6時，x?出基，x?入基C12000基b041010404001a2401001181000i)當(dāng)a<2,x?入基，x?出基C12000基b14101000012401001000若x?入基，x?出基C12000基b00001141002401001000符合iii)當(dāng)2<a<6,x?入基，x4出基C12000基b00011100al42401001000最優(yōu)解為(6-a,4,a-2,0,0)T。聯(lián)立交點(diǎn)不在可行域內(nèi)，不符合題意。b)當(dāng)a=8時，為退化解(0,3,5,0,1)T,不符合題意。綜上所述：a=2時，最優(yōu)解聯(lián)立得到。10.考慮如下線性規(guī)劃問題：C→00基b810401100請問：原始線性規(guī)劃問題的目標(biāo)函數(shù)系數(shù)、系數(shù)矩陣和約束右邊項(xiàng)的取值分別是多少?11.給定某求極大化線性規(guī)劃問題的最終單純形表，其中(a)~J)為待定常C→基bθ241000103001000(3)該線性規(guī)劃問題無有界最優(yōu)解?β,8+r)”。Ca1100基bθα11001300假設(shè)所有現(xiàn)金流都發(fā)生在月中。為了應(yīng)付現(xiàn)金流的需求，該廠可能需要借助于銀行借款。有度1月起每月末償還1%的利息，于12月底償還本金和最后一期；x:為期一年的長期借款金目標(biāo)函數(shù)：定義z為第12月末資金去掉第12月現(xiàn)金流(由于第12月現(xiàn)金流給定，因此目標(biāo)函數(shù)里是否體現(xiàn)均可)。maxz=-1.015y?2+1.005s?2第1月初：(2≤i≤12)min(D?-1,0)-0.01x-1.015y?-1+1.005s?-1+y?-S且保證所有決策變量非負(fù)。14.已知某銀行每個月初發(fā)行若干款理財產(chǎn)品，每款產(chǎn)品對應(yīng)的預(yù)期收益率和投資時間(投資時間都以月來計(jì)算)不同。某人在2019年年底持有資金10萬元，計(jì)劃在2020年年底利用這筆資金。請建立規(guī)劃模型幫助他決策應(yīng)該在2020年如何購買理財產(chǎn)品。有理即可。15.馬上進(jìn)入期末考試周了，本學(xué)期趙同學(xué)有四門課程需要期末考試：運(yùn)籌學(xué)、經(jīng)濟(jì)學(xué)原理、管理學(xué)原理、高等數(shù)學(xué)。趙同學(xué)掐指一算，總共只有40個小時的復(fù)習(xí)時間來備考了；他希望對復(fù)習(xí)時間進(jìn)行合理安排，盡可能提升考試成績。趙同學(xué)感覺壓力最大的是高等數(shù)學(xué)，他決定至少投入三分之一的時間用于高等數(shù)學(xué)的復(fù)習(xí)。趙同學(xué)平時運(yùn)籌學(xué)學(xué)習(xí)很好，他決定用于運(yùn)籌學(xué)的復(fù)習(xí)時間最多不超過5小時。根據(jù)以往經(jīng)驗(yàn)，在定量的課程(運(yùn)籌學(xué)、高等數(shù)學(xué))上每投入1小時能提升1.5%的成績；在定量和定性相結(jié)合的課程(經(jīng)濟(jì)學(xué)原理)上每投入1小時能提升2%的成績；在定性課程上每投入1小時只能提高1%的成績。請構(gòu)造一個線性規(guī)劃模型，幫助趙同學(xué)合理規(guī)劃復(fù)習(xí)時間。決策變量：設(shè)投入運(yùn)籌學(xué)、經(jīng)濟(jì)學(xué)原理、管理學(xué)原理、高等數(shù)學(xué)的時間分別為x?,X?,X?,x?小時。maxz=1.5%x?+2%x?+1%x?+16.考慮某玩具廠現(xiàn)金流的管理問題。已知該玩具廠未來一年每月都有需要支出的應(yīng)付賬款，同時也會回收應(yīng)收賬款；相關(guān)數(shù)據(jù)如下表所示(單位：萬元月份123456789應(yīng)付賬款85645432應(yīng)收賬款564866632為了應(yīng)付現(xiàn)金流的需求，該廠可能需要借助于銀行借款。有兩種方式：(1)為期一年的長期借款，即于上一年年末借一年期貸款，一次得到全部貸款額，從下一年度1月起每月末償還1%的利息，于12月底償還本金和最后一期；(1)為期一個月的短期借款，即可以每月初獲得短期貸款，于當(dāng)月底償還本金和利息，假設(shè)月利率為1.5%。當(dāng)該廠有多余現(xiàn)金時，也可以以短期存款的方式獲取部分利息收入。假設(shè)該廠只能每月初存入，月末取出，月息0.5%。x:為期一年的長期借款金第1月：x+y?-S?=10-5第2月：-0.01x-1.015y?+1.005s?+y?-S?=8-6第3月：-0.01x-1.015y?+1.005s?+y?-S?=5-4第4月：-0.01x-1.015y?+1.005s?+y?-S?=0第5月：8-6-0.01x-1.015y?+1.005s?+y?-S?=10-6第6月：-0.01x-1.015y?+1.005ss+y?-s?=0第7月：18-12-0.01x-1.015y?+1.005s?+y?-S?=20-6第8月：-0.01x-1.015y?+1.005s?+yg-Sg=0第9月：6-4-0.01x-1.015yg+1.005sg+yg-Sg=5-3第10月：-0.01x-1.015y?+1.005sg+y?o-S?0=4-2第11月：-0.01x-1.015y?0+1.005s?o+y??-S?1=0第12月：18-3-0.01x-1.015y??+1.005s?1+y?2-S?2=0銷售都集中在農(nóng)歷8月10日—8月15之間),而且月餅保質(zhì)期比較短，所以老王每年7月價格是20元/個，原材料成本是10元/個；即每塊月餅毛利是10元。如果需要，老王也可是2元。為z。則原問題等價于：其中M為一個很大的正數(shù)。Excel求解，能實(shí)現(xiàn)265000元的利潤。18.繼續(xù)第17題。如果今年的市場情況比較復(fù)雜，沒法準(zhǔn)確預(yù)測月餅的銷售價格。經(jīng)過分析，老王認(rèn)為今年月餅有可能漲價，也可能跌價；漲跌可能性各50%,幅度都為2元。在漲價(即銷售價格22元/個)的情況下，產(chǎn)品的保底銷量將變?yōu)?0000個；在跌價(即銷售價格18元/個)的情況下，產(chǎn)品的保底銷量將變?yōu)?3000個。中秋節(jié)過后，如果有月餅剩余，每個月餅還能以2元/個的價格清倉銷售。請問：老王應(yīng)該怎樣安排月餅的生產(chǎn)和廣告活動?他能實(shí)現(xiàn)多少利潤?解：設(shè)自己生產(chǎn)的月餅為x?個，增產(chǎn)x?個。廣告除固定投入外的投入為100y元，是否做廣告為z。則原問題等價于：maxz=22*(10000+180y)*0.5+18*(13000+180y)*0.5-100y-5000其中M為一個很大的正數(shù)?？赏ㄟ^Excel求解。19.考慮某資源配置問題：其中，x?表示產(chǎn)品A的產(chǎn)量，x?表示產(chǎn)品B的產(chǎn)量。通過單純形表計(jì)算得到的最終結(jié)果如下：C→基b0001100010000請?jiān)谏鲜霰砀竦幕A(chǔ)上回答如下問題：(1)產(chǎn)品A的單位利潤有可能發(fā)生變化，請問它在什么范圍內(nèi)變化時，最優(yōu)解保持不變?(2)上述結(jié)果表明資源2和資源3是瓶頸資源。假設(shè)可以以10元的單位價格購買部分第3章對偶理論與敏感性分析maxz=7x?+3x?+5x2.考慮下列兩個線性規(guī)劃問題：3.給出線性規(guī)劃問題minz=4x?+6x?+1乙(1)寫出其對偶問題；(2)用圖解法求解對偶問題；(3)根據(jù)(2)的結(jié)果計(jì)算原問題的最優(yōu)解。答案：,最優(yōu),最優(yōu)maxz=2x?+4x?+X?(1)用單純形法求解該問題；(2)寫出其對偶問題；(3)直接給出對偶問題的最終單純形表。maxz=2x?+4x?C→24110000基bθ08101100006210001006060111001060912141101000000109可知應(yīng)該將x?出基。因此，進(jìn)行換基迭代，得到如下單純形表。C→24110000基bθ410000000010000001000100101000可知應(yīng)該將x?出基。因此，進(jìn)行換基迭代，得到如下單純形表。C,→24110000基bθ4100008000100210101003100001310000該將x?出基。因此，進(jìn)行換基迭代，得到如下單純形表。C→24110000基bθ4201000822100002140011001000130000(2)對偶問題為minw=8y?+6y?+6y?+9y?(3)原問題的最優(yōu)解對應(yīng)與對偶問題最終單純形表的檢驗(yàn)系數(shù)，而原問題單純形表檢驗(yàn)系數(shù)*(-1)是對偶問題最優(yōu)解。5.給出線性規(guī)劃問題先用單純形法求出最優(yōu)解，再回答下列問題：(2)如果約束右邊項(xiàng)變?yōu)榱?15,12)',請問最優(yōu)解是多少?答案：引入松弛變量，將原問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式：首先確定初始基可行解，建立初始單純形表。很顯然，可以取變量(x?,x?)為初始基變量，因?yàn)樗鼈兯鶎?yīng)的系數(shù)矩陣中的列向量剛好構(gòu)成一個單位陣。對應(yīng)的初始單純形表如下表所示。C,→2100基bθ1111010820010100Cj→2100基bθ2111101003111000最優(yōu)解為X*=(12,0,0)',對應(yīng)的原問題最優(yōu)目標(biāo)函數(shù)值z°=-24。(1)如果目標(biāo)函數(shù)變?yōu)閙axz=2x?+3x?+x?對上述最終單純形表做進(jìn)一步優(yōu)化，C,→23100基bθ21111000111010C→基b2101301000最優(yōu)解為X?=(6,9,0)',對應(yīng)的最優(yōu)目標(biāo)函數(shù)值z*=。,。(3)最優(yōu)解為,。6.給出線性規(guī)劃問題請回答下列問題：maxz=3x?+x?+C?X?+C?X?(1)考慮λ=0的情形，以(x?,x?)為基變量列出相應(yīng)的單純形表。(2)若(x?,x?)為最優(yōu)基，請問(C?,C?)在什么范圍內(nèi)變化時，最優(yōu)解保持不變?(3)若(x?,x?)為最優(yōu)基，請問λ在什么范圍內(nèi)變化時，影子價格保持不變?(1)引入松弛變量，將原問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式：取變量(x?,x?)為初始基變量，對應(yīng)的初始單純形表如下表所示。C,→3100基bX3λ0110101λ0033(2),最優(yōu)解不變。(3)λ≤300時，影子價格不變。(4)引入松弛變量，將原問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式：取變量(x?,x?)為初始基變量，對應(yīng)的初始單純形表如下表所示。C→31000基bθ3λ01101λ100顯然，c4，3最優(yōu)解變化。03minz(λ)=x?+x?-(1+λ)x?+3λx?8.考慮下列線性規(guī)劃問題，其中λ是一個非負(fù)參數(shù)。當(dāng)λ在不同范圍取值時，最優(yōu)解如何發(fā)生變化?畫出最優(yōu)目標(biāo)函數(shù)值z(λ)隨λ的變化關(guān)系。maxz(λ9.某廠生產(chǎn)甲、乙、丙、丁四種產(chǎn)品，其所需勞動力、設(shè)備和原材料等相關(guān)數(shù)據(jù)如下表所甲乙丙丁資源限制勞動力6354設(shè)備1122原材料3452產(chǎn)品利潤(元/件)請回答下列問題：價格是4元呢?引入松弛變量，將原問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式：b變量。對應(yīng)的初始單純形表如下表所示。b000基b06354100011220100342001000C→000基bθ002100001010064Cj→000θ1000001011000最優(yōu)解為X*=(50,0,30,0)',對應(yīng)的最優(yōu)目標(biāo)函數(shù)值z*=2700。(2)假設(shè)丙的利潤為40+a,最終單純形表變化為C1→000基bθx610010010-0.2010a0顯然，若-15≤a≤10時，最優(yōu)解不變。(3)假設(shè)乙的利潤為40+c,最終單純形表變化為C;→C000基bθ1000001011000若最優(yōu)生產(chǎn)計(jì)劃中生產(chǎn)乙，要求c>30。解，可以得到最優(yōu)解',對應(yīng)的最優(yōu)目標(biāo)函數(shù)值z*=2666.67。利用單純形法求解可得可以得到最優(yōu)解為',所以最多購單位原材10.勝利家具廠生產(chǎn)桌子和椅子兩種家具；相關(guān)數(shù)據(jù)如下表所示。桌子椅子可用工時木工43油工21單位利潤為了使得銷售利潤最大，家具廠經(jīng)理建立了一個線性規(guī)劃模型來幫助安排生產(chǎn)。利用Excel優(yōu)化求解，得到的敏感性報告如下所SE$4椅子產(chǎn)量200307.55終陰影約束允許的允許的 請問：如果桌子價格上漲10%而椅子價格下降10%,最優(yōu)解是否發(fā)生變化?如果價格變化趨勢相反呢?答案：如果桌子價格上漲10%而椅子價格下降10%,那么桌子和椅子的價格分別為55和27,此時目標(biāo)函數(shù)系數(shù)變化的相對百分比之和。根據(jù)100%規(guī)則，最優(yōu)解有可能發(fā)生