1、運籌學教程（第二版）習題解答,第一章習題解答,1.1 用圖解法求解下列線性規(guī)劃問題。并指出問題具有惟一最優(yōu)解、無窮多最優(yōu)解、無界解還是無可行解。,第一章習題解答,第一章習題解答,第一章習題解答,1.2 將下述線性規(guī)劃問題化成標準形式。,第一章習題解答,第一章習題解答,第一章習題解答,1.3 對下述線性規(guī)劃問題找出所有基解，指出哪些是基可行解，并確定最優(yōu)解。,第一章習題解答,第一章習題解答,第一章習題解答,1.4 分別用圖解法和單純形法求解下述線性規(guī)劃問題，并對照指出單純形表中的各基可行解對應圖解法中可行域的哪一頂點。,第一章習題解答,第一章習題解答,l.5 上題(1)中，若目標函數(shù)變?yōu)閙ax

2、Z = cx1 + dx2，討論c,d的值如何變化，使該問題可行域的每個頂點依次使目標函數(shù)達到最優(yōu)。 解：得到最終單純形表如下：,第一章習題解答,當c/d在3/10到5/2之間時最優(yōu)解為圖中的A點；當c/d大于5/2且c大于等于0時最優(yōu)解為圖中的B點；當c/d小于3/10且d大于0時最優(yōu)解為圖中的C點；當c/d大于5/2且c小于等于0時或當c/d小于3/10且d小于0時最優(yōu)解為圖中的原點。,第一章習題解答,式中，1c13, 4c26, -1a113, 2a125, 8b112, 2a215, 4a226, 10b214,試確定目標函數(shù)最優(yōu)值的下界和上界。,l.6 考慮下述線性規(guī)劃問題：,第一章

3、習題解答,最優(yōu)值（上界）為：21,解：上界對應的模型如下（c,b取大，a取小）,第一章習題解答,最優(yōu)值（下界）為：6.4,解：下界對應的模型如下（ c,b取小，a取大）,第一章習題解答,l.7 分別用單純形法中的大M法和兩階段法求解下列線性規(guī)劃問題，并指出屬哪類解。,第一章習題解答,第一章習題解答,第一章習題解答,第一章習題解答,1.8 已知某線性規(guī)劃問題的初始單純形表和用單純形法迭代后得到下面表格，試求括弧中未知數(shù)al值。,b=2, c=4, d=-2, g=1, h=0, f=3, i=5, e=2, l=0, a=3, j=5, k= -1.5,第一章習題解答,1.9 若X(1)、X(2

4、)均為某線性規(guī)劃問題的最優(yōu)解，證明在這兩點連線上的所有點也是該問題的最優(yōu)解。,第一章習題解答,1.10 線性規(guī)劃問題max ZCX,AXb，X0，設X0為問題的最優(yōu)解。若目標函數(shù)中用C*代替C后，問題的最優(yōu)解變?yōu)閄*，求證 (C*-C)(X*-X0)0,第一章習題解答,1.11 考慮線性規(guī)劃問題,模型中，為參數(shù)，要求： (1)組成兩個新的約束(i)(i)+(ii)，(ii)(ii)一2(i)，根據(jù)(i)，(ii)以x1,x2為基變量，列出初始單純形表；,第一章習題解答,第一章習題解答,(2)在表中，假定0，則為何值時，x1, x2為問題的最優(yōu)基變量； 解： 如果=0，則當3a 4時，x1, x

5、2為問題的最優(yōu)基變量； (3)在表中，假定3，則為何值時，x1, x2為問題的最優(yōu)基。 解： 如果a=3，則當-1 1時，x1, x2為問題的最優(yōu)基變量。,第一章習題解答,1.12 線性規(guī)劃問題max ZCX，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/ 。,第一章習題解答,1.13 某飼養(yǎng)場飼養(yǎng)動物出售，設每頭動物每天至

6、少需700g蛋白質、30g礦物質、100mg維生素?，F(xiàn)有五種飼料可供選用，各種飼料每kg營養(yǎng)成分含量及單價如下表所示。,第一章習題解答,要求確定既滿足動物生長的營養(yǎng)需要，又使費用最省的選用飼料的方案。(建立這個問題的線性規(guī)劃模型，不求解),第一章習題解答,1.14 某醫(yī)院護士值班班次、每班工作時間及各班所需護士數(shù)如下頁表格所示。,第一章習題解答,(1)若護士上班后連續(xù)工作8h，該醫(yī)院最少需多少名護士，以滿足輪班需要；,第一章習題解答,(2)若除22：00上班的護士連續(xù)工作8h外(取消第6班)，其他班次護士由醫(yī)院排定上1-4班的其中兩個班，則該醫(yī)院又需多少名護士滿足輪班需要。 解:第5班一定要3

7、0個人，,第一章習題解答,第一章習題解答,1.15 艘貨輪分前、中、后三個艙位，它們的容積與最大允許載重量見后面的表格?，F(xiàn)有3種貨物待運，已知有關數(shù)據(jù)列于后面的表格。 又為了航運安全，前、中、后艙的實際載重量大體保持各艙最大允許載重量的比例關系。具體要求：前、后艙分別與中艙之間載重量比例的偏差不超過15，前、后艙之間不超過10。問該貨輪應裝載A，B，C各多少件運費收入才最大?試建立這個問題的線性規(guī)劃模型。,第一章習題解答,第一章習題解答,MAX= 1000（X(1,1)+X(1,2)+X(1,3)） +700 （X(2,1)+X(2,2)+X(2,3)） +600 （X(3,1)+X(3,2)

8、+X(3,3)） SUBJECT TO X(i,j)表示第商品i在艙j的裝載量，i,j=1,2,3 商品數(shù)量約束： 1 X(1,1)+X(1,2)+X(1,3) = 600 2 X(2,1)+X(2,2)+X(2,3) = 1000 3 X(3,1)+X(3,2)+X(3,3) = 800,第一章習題解答,商品容積約束： 4 10X(1,1)+5X(2,1)+7X(3,1) = 4000 5 10X(1,2)+5X(2,2)+7X(3,2) = 5400 6 10X(1,3)+5X(2,3)+7X(3,3) = 1500 最大載重量約束： 7 8 X(1,1)+6X(2,1)+5X(3,1)

9、= 2000 8 8 X(1,2)+6X(2,2)+5X(3,2) = 3000 9 8 X(1,3)+6X(2,3)+5X(3,3) = 1500,第一章習題解答,重量比例偏差約束： 10 8X(1,1)+6X(2,1)+5X(3,1)=2/3（1-0.15） 8X(1,2)+6X(2,2)+5X(3,2) 12 8X(1,3)+6X(2,3)+5X(3,3)=1/2（1-0.15） 8X(1,2)+6X(2,2)+5X(3,2) 14 8X(1,3)+6X(2,3)+5X(3,3)=3/4（1-0.1） 8X(1,1)+6X(2,1)+5X(3,1),第一章習題解答,1.16 某廠生產I，

10、兩種食品，現(xiàn)有50名熟練工人，每名熟練工人每h可生產食品110kg或食品6kg。由于需求量將不斷增長(見下頁表格)，該廠計劃到第8周末前培訓出50名新工人，組織兩班生產。已知一名工人每周工作40h，一名熟練工人用2周時間可培訓出不多于3名新工人(培訓期間熟練工人和被培訓人員均不參加生產)。熟練工人每周工資360元，新工人培訓期間工資每周120元，新工人培訓結束后工作每周工資240元，且生產效率同熟練工人。培訓過渡期，工廠將安排部分熟練工人加班，加班1h另加付12元。又生產食品不能滿足訂貨需求，推遲交貨的賠償費分別為：食品I為0.50元(kg周)；食品為0.60元(kg周)。工廠應如何全面安排，

11、使各項費用總和最小，試建立線性規(guī)劃模型。,第一章習題解答,設x(i)，y(i)表示從事兩個產品生產的人數(shù)，xx(i)，yy(i)表示從事生產兩個產品的加班小時數(shù)，f1(i),f2(i)表示兩個產品推遲交貨的數(shù)量，r1(i),r2(i)表示兩個產品的需求數(shù)量，w(i),n(i)分別表示開始從事培訓工作的人數(shù)和新接受培訓的工人人數(shù)。,第一章習題解答,MIN= 360X(i)+360Y(i)+360W(i) +12XX(i)+12yy(i) +0.5f1(i)+0.6f2(i) +(120+120)n(i) +240(7-i)n(i) n(i)=nx(i)+ny(i) N(8)=0 - 3 W(i)

12、 + N(i) = 0 XX(i) = 1000 YY(i) = 1000,第一章習題解答,400X(i)+10XX(i)=116000 240y(i)+6 yy(i)= 79200 400*x(1)+10*xx(1)+f1(1)=10000; 400*(x(1)+x(2)+10*(xx(1)+xx(2) +f1(2)=20000; for(a(i)|i#ge#3#and#i#le#s: 400*x(1)+400*x(2)+10*xx(1)+10*xx(2) +sum(a(j)|j#le#i#and#j#gt#2: 400*(x(j)+nx(j-2)+10*xx(j)+f1(i) =sum(a

13、(j)|j#le#i:r1(j); f1(s)=0;,第一章習題解答,240*y(1)+6*yy(1)+f2(1)=6000; 240*(y(1)+y(2)+6*(yy(1)+yy(2) +f2(2)=13200; for(a(i)|i#ge#3#and#i#le#s: 240*y(1)+240*y(2)+6*yy(1)+6*yy(2) +sum(a(j)|j#le#i#and#j#gt#2: 240*(y(j)+ny(j-2)+6*yy(j)+f2(i) =sum(a(j)|j#le#i:r2(j); f2(s)=0;,第一章習題解答,x(1)+y(1)+w(1)=50; x(2)+y(2)

14、+w(1)+w(2)=50; for(a(i)|i#gt#2: x(i)+y(i)+w(i-1)+w(i)=50); sum(a(i)|i#le#s:n(i)=50; for(a(i):gin(x(i); for(a(i):gin(y(i); for(a(i):gin(w(i); for(a(i):gin(n(i);,第一章習題解答,1-17 時代服裝公司生產款新的時裝，據(jù)預測今后6個月的需求量如下表所示。每件時裝用工2h和10元原材料費，售價40元。該公司1月初有4名工人，每人每月可工作200h，月薪2000元。該公司可于任何個月初新雇工人，但每雇1人需次性額外支出1500元，也可辭退工人，

15、但每辭退1人需補償1000元。如當月生產數(shù)超過需求，可留到后面月份銷售，但需付庫存費每件每月5元。當供不應求時，短缺數(shù)不需補上。試幫助該公司決策，如何使6個月的總利潤達到最大。,第一章習題解答,max = 30(y1+y2+y3+y4+y5+y6) -1500(p1+p2+p3+p4+p5+p6) -1000(d1+d2+d3+d4+d5+d6) -5(pp1+pp2+pp3+pp4+pp5+pp6) -2000(x1+x2+x3+x4+x5+x6) -1000 x6; x0=4; x表示工人人數(shù)，y表示產品產量， p表示新工人人數(shù) d表示辭退工人人數(shù) p1-d1=x1-x0;p2-d2=x2

16、-x1; p3-d3=x3-x2;p4-d4=x4-x3; p5-d5=x5-x4;p6-d6=x6-x5;,第一章習題解答,pp0=0;pp表示庫存量,dd表示缺損額 pp1-dd1=y1+pp0-500; pp2-dd2=y2+pp1-600; pp3-dd3=y3+pp2-300; pp4-dd4=y4+pp3-400; pp5-dd5=y5+pp4-500; pp6-dd6=y6+pp5-800; 生產能力約束： y1=100*x1; y2=100*x2; y3=100*x3; y4=100*x4; y5=100*x5; y6=100*x6; 總產量約束：y1+y2+y3+y4+y5+

17、y6=3100; gin(y1);gin(y2);gin(y3);gin(y4); gin(y5);gin(y6);gin(x1);gin(x2); gin(x3);gin(x4);gin(x5);gin(x6);,第一章習題解答,1.18 童心玩具廠下一年度的現(xiàn)金流(萬元)如下表所示，表中負號表示該月現(xiàn)金流出大于流人，為此該廠需借款。借款有兩種方式：一是于上一年末借一年期貸款，一次得全部貸款額，從1月底起每月還息1，于12月歸還本金和最后一次利息；二是得到短期貸款，每月初獲得，于月底歸還，月息1.5。當該廠有多余現(xiàn)金時，可短期存款，月初存人，月末取出，月息0.4。問該廠應如何進行存貸款操作，

18、既能彌補可能出現(xiàn)的負現(xiàn)金流，又可使年末現(xiàn)金總量為最大?,第一章習題解答,MAX= 1.004 Z(12) - 1.01y - 1.015 W(12) SUBJECT TO 1 Y -Z(1)+W(1) =12 2 -.01Y+1.004Z(1) -.1015W(1) -Z(2)+W(2) =10 3 -.01Y+1.004Z(2) -.1015W(2) -Z(3)+W(3) = 8 4 -.01Y+1.004Z(3) -.1015W(3) -Z(4)+W(4) =10 5 -.01Y+1.004Z(4) -.1015W(4) -Z(5)+W(5) = 4 6 -.01Y+1.004Z(5) -1.015W(5