清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)課件

第一章習(xí)題解答

1.1用圖解法求解下列線性規(guī)劃問題。并指出問題具有惟一最優(yōu)解、無窮多最優(yōu)解、無界解還是無可行解。

1第一章習(xí)題解答1.1用圖解法求解下列2233

1.2將下述線性規(guī)劃問題化成標(biāo)準(zhǔn)形式。41.2將下述線性規(guī)劃問題化成標(biāo)準(zhǔn)形5566

1.3對下述線性規(guī)劃問題找出所有基解，指出哪些是基可行解，并確定最優(yōu)解。71.3對下述線性規(guī)劃問題找出所有基88x1x2x3x4x5x6是否基可行解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,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)Tx1x2x3x4x5x6是否基可行解Z(x1,x2,x3)09x1x2x3x4是否基可行解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是5所有基可行解中最優(yōu)解為X=(0,1/2,2,0)T和X=(0,0,1,1)T10x1x2x3x4是否基可行解Z(x1,x2)-411/200

1.4分別用圖解法和單純形法求解下述線性規(guī)劃問題，并對照指出單純形表中的各基可行解對應(yīng)圖解法中可行域的哪一頂點。

111.4分別用圖解法和單純形法求解下1050009341008[5]20110500021/50[14/5]1-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)T1050009341008[5]20110500021/50121313清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件14清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件15l.5上題(1)中，若目標(biāo)函數(shù)變?yōu)閙axZ=cx1+dx2，討論c,d的值如何變化，使該問題可行域的每個頂點依次使目標(biāo)函數(shù)達(dá)到最優(yōu)。

最優(yōu)值1)c<0d<0d=0d>0O點OA3線段A3點2)c=0d<0d>0OA1線段A3點3)c>0d<0d=0d>0A1點A1點A3點A2A3線段A2點A1A2線段A1點l.5上題(1)中，若目標(biāo)函數(shù)16

式中，1≤c1≤3,4≤c2≤6,-1≤a11≤3,2≤a12≤5,8≤b1≤12,2≤a21≤5,4≤a22≤6,10≤b2≤14,試確定目標(biāo)函數(shù)最優(yōu)值的下界和上界。

l.6考慮下述線性規(guī)劃問題：

17式中，1≤c1≤3,4≤c2≤6,-1≤a1

目標(biāo)函數(shù)最優(yōu)值的上界為：21

解：上界對應(yīng)的模型如下（c,b取大，a取小）18目標(biāo)函數(shù)最優(yōu)值的上界為：21

目標(biāo)函數(shù)最優(yōu)值（下界）為：6.4

解：下界對應(yīng)的模型如下（c,b取小，a取大）19目標(biāo)函數(shù)最優(yōu)值（下界）為：6.4

l.7分別用單純形法中的大M法和兩階段法求解下列線性規(guī)劃問題，并指出屬哪—類解。20l.7分別用單純形法中的大M法和兩清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件21清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件22清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件23清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件24清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件252626清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件27清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件28見下表。見下表。29清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件303131方法一：大M法引入人工變量x6和x7,線性規(guī)劃問題變?yōu)椋悍椒ㄒ唬捍驧法3200-M4M-17M-4010214000-1346-M1001[3]3-M-M00-1-401013/240-7M/3+4/30-M5M/3+1/30-1/3105/3030-4/30-1[5/3]02-M1/3001/311-4106/59/5003-M00-M4M-17M-4010214000-1346-M1033-M+8/501/50011[1]0010-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ù)都小于等于零(且非基變量檢驗數(shù)都小于0)，因此已經(jīng)得到唯一最優(yōu)解，最優(yōu)解為：-M+8/501/50011[1]0010-4/50-3/534方法二：兩階段法第一階段：方法二：兩階段法第一階段：3500-147010214000-1346-11001[3]3-1-1000001013/240-7/30-15/30-1/3105/3030-4/30-1[5/3]02-11/3001/3110106/59/5003-100-147010214000-1346-11001[3]336-1000011[1]0010-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)入第二階段。-1000011[1]0010-4/50-3/5106/503701/5001[1]00100-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)解為：101/5001[1]00100-3/5106/5-101/5383939清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件40清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件41清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件42

1.8已知某線性規(guī)劃問題的初始單純形表和用單純形法迭代后得到下面表格，試求括弧中未知數(shù)a～l值。項目X1X2X3X4X5X46(b)(c)(d)10X51-13(e)01Cj－Zja-1200X1(f)(g)2-11/20X54(h)(i)1

1/21Cj－Zj0-7(j)(k)(l)

b=2,c=4,d=-2,g=1,h=0,f=3,i=5,e=2,l=0,431.8已知某線性規(guī)劃問題的初始單純

-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

-7=-1-(c/b)*a441.9若X(1)、X(2)均為某線性規(guī)劃問題的最優(yōu)解，證明在這兩點連線上的所有點也是該問題的最優(yōu)解。

451.9若X(1)、X(2)均為清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件46

1.10線性規(guī)劃問題maxZ＝CX,AX＝b，X≥0，設(shè)X0為問題的最優(yōu)解。若目標(biāo)函數(shù)中用C*代替C后，問題的最優(yōu)解變?yōu)閄*，求證(C*-C)(X*-X0)≥0的可行解一定是問題的最優(yōu)解，則是問題12**X*X*的可行解一定是問題的最優(yōu)解，則是問題2100XX471.10線性規(guī)劃問題maxZ＝C清華大學(xué)《運籌學(xué)教程》胡運權(quán)主編課后習(xí)題答案(第一章)ppt課件48

1.11考慮線性規(guī)劃問題

模型中α，β為參數(shù)，要求：

(1)組成兩個新的約束(i)’＝(i)+(ii)，(ii)’＝(ii)一2(i)，根據(jù)(i)’，(ii)’以x1,x2為基變量，列出初始單純形表；491.11考慮線性規(guī)劃問題模型中α，β為參Cj→a21-4CBxBbx1x2x3x4ax13+3

011-12x21-

10-10

j003-aa-4解:50Cj→a21-4CBxBbx1x2x3x4ax13+301

(2)在表中，假定β＝0，則α為何值時，x1,x2為問題的最優(yōu)基變量；解：

如果

=0，則當(dāng)3-a≥0且a-4≥0時，即3≤a≤4時，x1,x2為問題的最優(yōu)基變量；

(3)在表中，假定α＝3，則β為何值時，x1,x2為問題的最優(yōu)基。解：如果a=3，則當(dāng)3+3

≥0且1-

≥0時，即

-1≤≤1時，x1,x2為問題的最優(yōu)基變量。51(2)在表中，假定β＝0，則α為何值時，

1.12線性規(guī)劃問題maxZ＝CX，AX＝b，X≥0，如X*是該問題的最優(yōu)解，又λ>0為某一常數(shù)，分別討論下列情況時最優(yōu)解的變化。

(1)目標(biāo)函數(shù)變?yōu)閙axZ＝λCX；

(2)目標(biāo)函數(shù)變?yōu)閙axZ＝(C+λ)X；

(3)目標(biāo)函數(shù)變?yōu)閙axZ＝C/λ*X，約束條件變?yōu)锳X＝λb。

解:(1)最優(yōu)解不變;(2)C為常數(shù)時最優(yōu)解不變，否則可能發(fā)生變化。

(3)最優(yōu)解變?yōu)?λX*。521.12線性規(guī)劃問題maxZ＝C

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.7310.20.20.446220.35180.50.80.8531.13某飼養(yǎng)場飼養(yǎng)動物出售，設(shè)每

要求確定既滿足動物生長的營養(yǎng)需要，又使費用最省的選用飼料的方案。(建立這個問題的線性規(guī)劃模型，不求解)54要求確定既滿足動物生長的營養(yǎng)需要，又使費用最省的

1.14某醫(yī)院護(hù)士值班班次、每班工作時間及各班所需護(hù)士數(shù)如下頁表格所示。班次工作時間所需護(hù)士數(shù)（人）16:00

10:0060210:00

14:0070314:00

18:0060418:00

22:0050522:00

2:002062:00

6:0030551.14某醫(yī)院護(hù)士值班班次、每班工

(1)若護(hù)士上班后連續(xù)工作8h，該醫(yī)院最少需多少名護(hù)士，以滿足輪班需要；解：

56(1)若護(hù)士上班后連續(xù)工作8h，該醫(yī)院

(2)若除22：00上班的護(hù)士連續(xù)工作8h外(取消第6班)，其他班次護(hù)士由醫(yī)院排定上1-4班的其中兩個班，則該醫(yī)院又需多少名護(hù)士滿足輪班需要。

解:57(2)若除22：00上班的護(hù)士連續(xù)工作

1.15—艘貨輪分前、中、后三個艙位，它們的容積與最大允許載重量見后面的表格?，F(xiàn)有3種貨物待運，已知有關(guān)數(shù)據(jù)列于后面的表格。又為了航運安全，前、中、后艙的實際載重量大體保持各艙最大允許載重量的比例關(guān)系。具體要求：前、后艙分別與中艙之間載重量比例的偏差不超過15％，前、后艙之間不超過10％。問該貨輪應(yīng)裝載A，B，C各多少件運費收入才最大?試建立這個問題的線性規(guī)劃模型。581.15—艘貨輪分前、中、后三個艙商品數(shù)量（件）每件體積(m3/件)每件重量(t/件)運價（元/件）A6001081000B100056700C80075600項目前艙中艙后艙最大允許載重量（t）200030001500容積（m3）400054001500解：設(shè)xij表示第i種商品在第j艙的數(shù)量。59商品數(shù)量每件體積每件重量運價A6001081000B10006060

1-16時代服裝公司生產(chǎn)—款新的時裝，據(jù)預(yù)測今后6個月的需求量如下表所示。每件時裝用工2h和10元原材料費，售價40元。該公司1月初有4名工人，每人每月可工作200h，月薪2000元。該公司可于任何—個月初新雇工人，但每雇1人需—次性額外支出1500元，也可辭退工人，但每辭退1人需補償1000元。如當(dāng)月生產(chǎn)數(shù)超過需求，可留到后面月份