清華大學(xué)《運籌學(xué)教程》 主編課后習(xí)題答案(第1章)

1、清華大學(xué)運籌學(xué)教程 主編課后習(xí)題答案(第1章)23 1.2 將下述線性規(guī)劃問題化成標準形式。 456 1.3 對下述線性規(guī)劃問題找出所有基解，指出哪些是基可行解，并確定最優(yōu)解。 78x1x2x3x4x5x6是否基可行解Z(x1,x2,x3)061/3-7/6000否(x1,x2,x4)0100-700否(x1,x2,x5)03007/20是3(x1,x2,x6)7/4-400021/4否(x1,x3,x4)00-5/2800否(x1,x3,x5)001.5080是3(x1,x3,x6)10-0.5003否(x1,x4,x5)000350是0(x1,x4,x6)5/400-2015/4否(x1,

2、x5,x6)3/400029/4是9/4(x2,x3,x6)016/3-7/6000否(x2,x4,x6)0100-700否(x2,x5,x6)03007/20是3(x3,x4,x6)00-5/2800否(x3,x5,x6)003/2080是3(x4,x5,x6)000350是0所有基可行解中最優(yōu)解為X=(0,3,0,0,3.5,0)T和X=(0,0,1.5,0,8,0)Tx1x2x3x4是否基可行解Z(x1,x2)-411/200否(x1,x3)2/5011/50是43/5(x1,x4)-1/30011/6否(x2,x3)01/220是5(x2,x4)0-1/202否(x3,x4)0011是

3、5所有基可行解中最優(yōu)解為X=(0,1/2,2,0)T和X=(0,0,1,1)T10 1.4 分別用圖解法和單純形法求解下述線性規(guī)劃問題，并對照指出單純形表中的各基可行解對應(yīng)圖解法中可行域的哪一頂點。 111050009341008520110500021/5014/51-3/5108/512/501/5010-253/2015/14-3/1410110-1/72/700-5/14-25/140點A1點A2點所以最優(yōu)解為X*=(1,3/2,0,0)T13 l.5 上題(1)中，若目標函數(shù)變?yōu)閙ax Z = cx1 + dx2，討論c,d的值如何變化，使該問題可行域的每個頂點依次使目標函數(shù)達到最優(yōu)

4、。 最優(yōu)值1)c0d0O點OA3線段A3點2)c=0d0OA1線段A3點3)c0d0A1點A1點A3點A2A3線段A2點A1A2線段A1點 式中，1c13, 4c26, -1a113, 2a125, 8b112, 2a215, 4a226, 10b214,試確定目標函數(shù)最優(yōu)值的下界和上界。 l.6 考慮下述線性規(guī)劃問題： 17 目標函數(shù)最優(yōu)值的上界為：21 解：上界對應(yīng)的模型如下（c,b取大，a取小） 18 目標函數(shù)最優(yōu)值（下界）為：6.4 解：下界對應(yīng)的模型如下（ c,b取小，a取大）19 l.7 分別用單純形法中的大M法和兩階段法求解下列線性規(guī)劃問題，并指出屬哪類解。 2026見下表。31

5、方法一：大M法引入人工變量x6和x7,線性規(guī)劃問題變?yōu)椋?0-M4M-17M-4010214000-1346-M100133-M-M00-1-401013/240-7M/3+4/30-M5M/3+1/30-1/3105/3030-4/30-15/302-M1/3001/311-4106/59/5003-M-M+8/501/5001110010-4/50-3/5106/5-13/501/5013/5-4-M00-1-4-1/5-3/5-131-M-1/5-M+7/5-1/50001110010-1/53/50105/9-12/5-1/50012/5-40-1-M0-M 由于上表中所有檢驗數(shù)都小于

6、等于零(且非基變量檢驗數(shù)都小于0)，因此已經(jīng)得到唯一最優(yōu)解，最優(yōu)解為：方法二：兩階段法第一階段：00-147010214000-1346-1100133-1-1000001013/240-7/30-15/30-1/3105/3030-4/30-15/302-11/3001/3110106/59/5003-1-100001110010-4/50-3/5106/503/501/5013/50-M0000-1/5-3/5-1-1-M該模型最優(yōu)解為X=（3/5，6/5，0，1，0，0）T，其基變量不含人工變量，說明原問題的一個基可行解為X=（ 3/5，6/5，0，1 ）T，轉(zhuǎn)入第二階段。01/5001

7、100100-3/5106/5-101/5013/5-400-1-43-1/50001100103/50105/9-1-1/50012/5-4 由于上表中所有檢驗數(shù)都小于等于零(且非基變量檢驗數(shù)都小于0)，因此已經(jīng)得到唯一最優(yōu)解，最優(yōu)解為：139 1.8 已知某線性規(guī)劃問題的初始單純形表和用單純形法迭代后得到下面表格，試求括弧中未知數(shù)al值。 項 目X1X2X3X4X5X46(b)(c)(d)10X51-13(e)01CjZja-1200X1(f)(g)2-11/20X54(h)(i)1 1/21CjZj0-7(j)(k)(l) b=2, c=4, d= -2, g=1, h=0, f=3,

8、i=5, e=2, l=0,43 -7=-1-(c/b)*a -7=-1-2a a=3 j=2-(d/b)*a j=2+3=5 k=-(1/b)*a k=-3/2 1.9 若X(1)、X(2)均為某線性規(guī)劃問題的最優(yōu)解，證明在這兩點連線上的所有點也是該問題的最優(yōu)解。 45 1.10 線性規(guī)劃問題max ZCX,AXb，X0，設(shè)X0為問題的最優(yōu)解。若目標函數(shù)中用C*代替C后，問題的最優(yōu)解變?yōu)閄*，求證(C*-C)(X*-X0)0的可行解一定是問題的最優(yōu)解，則是問題12*X*X*的可行解一定是問題的最優(yōu)解，則是問題2100XX47 1.11 考慮線性規(guī)劃問題 模型中，為參數(shù)，要求： (1)組成兩個

9、新的約束(i)(i)+(ii)，(ii)(ii)一2(i)，根據(jù)(i)，(ii)以x1,x2為基變量，列出初始單純形表；49Cja21-4CBxBbx1x2x3x4ax13+3011-12x21- 10-10j003-aa-4解:50 (2)在表中，假定0，則為何值時，x1, x2為問題的最優(yōu)基變量； 解： 如果=0，則當3-a0且 a-4 0時，即3a 4時，x1, x2為問題的最優(yōu)基變量； (3)在表中，假定3，則為何值時，x1, x2為問題的最優(yōu)基。 解： 如果a=3，則當3+3 0 且1- 0時，即 -1 1時，x1, x2為問題的最優(yōu)基變量。51 1.12 線性規(guī)劃問題max ZCX

10、，AXb，X0，如X*是該問題的最優(yōu)解，又0為某一常數(shù)，分別討論下列情況時最優(yōu)解的變化。 (1)目標函數(shù)變?yōu)閙ax ZCX； (2)目標函數(shù)變?yōu)閙ax Z(C+)X； (3)目標函數(shù)變?yōu)閙ax ZC/*X，約束條件變?yōu)锳Xb。 解:(1)最優(yōu)解不變; (2)C為常數(shù)時最優(yōu)解不變，否則可能發(fā)生變化。 (3)最優(yōu)解變?yōu)? X* 。52 1.13 某飼養(yǎng)場飼養(yǎng)動物出售，設(shè)每頭動物每天至少需700g蛋白質(zhì)、30g礦物質(zhì)、100mg維生素。現(xiàn)有五種飼料可供選用，各種飼料每kg營養(yǎng)成分含量及單價如下表所示。飼料蛋白質(zhì)(g)礦物質(zhì)(g)維生素(mg)價格（元/kg）1310.50.2220.51.00.73

11、10.20.20.446220.35180.50.80.853 要求確定既滿足動物生長的營養(yǎng)需要，又使費用最省的選用飼料的方案。(建立這個問題的線性規(guī)劃模型，不求解)54 1.14 某醫(yī)院護士值班班次、每班工作時間及各班所需護士數(shù)如下頁表格所示。班次工作時間所需護士數(shù)（人）16:00 10:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:00 6:003055 (1)若護士上班后連續(xù)工作8h，該醫(yī)院最少需多少名護士，以滿足輪班需要； 解： 56 (2)若除22：00上班的護士連續(xù)工作8h外(取消第6班)，其他班次護士由醫(yī)院排定

12、上1-4班的其中兩個班，則該醫(yī)院又需多少名護士滿足輪班需要。 解:57 1.15 艘貨輪分前、中、后三個艙位，它們的容積與最大允許載重量見后面的表格?，F(xiàn)有3種貨物待運，已知有關(guān)數(shù)據(jù)列于后面的表格。 又為了航運安全，前、中、后艙的實際載重量大體保持各艙最大允許載重量的比例關(guān)系。具體要求：前、后艙分別與中艙之間載重量比例的偏差不超過15，前、后艙之間不超過10。問該貨輪應(yīng)裝載A，B，C各多少件運費收入才最大?試建立這個問題的線性規(guī)劃模型。58商品數(shù)量（件）每件體積(m3/件)每件重量(t/件)運價（元/件）A6001081000B100056700C80075600項目前艙中艙后艙最大允許載重量（

13、t）200030001500容積（m3）400054001500解：設(shè)xij表示第i種商品在第j艙的數(shù)量。5960 1-16 時代服裝公司生產(chǎn)款新的時裝，據(jù)預(yù)測今后6個月的需求量如下表所示。每件時裝用工2h和10元原材料費，售價40元。該公司1月初有4名工人，每人每月可工作200h，月薪2000元。該公司可于任何個月初新雇工人，但每雇1人需次性額外支出1500元，也可辭退工人，但每辭退1人需補償1000元。如當月生產(chǎn)數(shù)超過需求，可留到后面月份銷售，但需付庫存費每件每月5元。當供不應(yīng)求時，短缺數(shù)不需補上。試幫助該公司決策，如何使6個月的總利潤達到最大。 月份123456需求50060030040050080061解：設(shè)xi表示第i個月的工人數(shù)量，yi表示第i個月生產(chǎn)產(chǎn)品的數(shù)量。 pi表示第i個月初新雇工人數(shù)量，di表示第i個月初解雇工人數(shù)量。 ppi表示第i個月月末的庫存量， ddi表示第i個月的短缺量。62 1.17 童心玩具廠下一年度的現(xiàn)金流(萬元)如下表所示，表中負號表示該月現(xiàn)金流出大于流人，為此該廠需借款。借款有兩種方式：一是于上一年末借一年期貸款，一次得全部貸款額，從1月底起每月還息1，