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