運籌學(xué)-第一章 線性規(guī)劃

習(xí)題一1.1用圖解法求解下列線性規(guī)劃問題，并指出各問題是具有唯一最優(yōu)解、無窮多最優(yōu)解、無界解或無可行解。min無窮多最優(yōu)解、無界解或無可行解。minz=6x1+代st.2x1+x孑13x1+4x231.5x1,x230(3)maxz=x1+x2st.8x+6x324124x1+6x23~122x34

2x1,x230(5)maxz=3x1+9x2st.x+3xW22

12—x1+x2<4xW622x—5xW012x1,x2301.2.在下列線性規(guī)劃問題中，:fmaxz=4x1+8x2st.2x+2xW1012—x1+x238x,x3012(4)maxz=3x1—2x2st.x1+x2W12x+2x3412x,x30

12(6)maxz=3x1+4x2st.—x+2xW812x1+2x2W122x1+x2W16x1,x230毒本解，指出哪些是基本可行解并分別代入目標(biāo)函數(shù)，比較找出最優(yōu)解。st.maxzst.maxz=3x1+5x2x1+x3=42x2+x4=123x1+2x2+x5=18x,30(j'=1,…,5)minz=4x1+12x2+18x3st.x1+3x3—x4=32x2+2x3—x5=5x,30(j■=1,…,5)分別用圖解法和單純形法求解下列線性規(guī)劃問題，并對照指出單純形法迭代的每一步相當(dāng)于圖解法可行域中的哪一個頂點。maxz=10x1+5x2st.3x+4xW9125x+2xM812x1,x230maxz=100x1+200x2st.x1+x2W500x1<2002x1+6x2<1200x1,x230分別用大M法和兩階段法求解下列線性規(guī)劃問題，并指出問題的解屬于哪一類：

(1)maxz=4x1^5x2+x3(1)maxz=4x1^5x2+x3st.3x1~b2x2^x3^182x1+x2W4x1+x2—x3=5x.No(=1,2,3)(3)maxz=x1+x2st.8x^6xN24124x1^6xN-—122xN4

2x1,x2N0(5)maxz=4x1^6x2st.2x^4xW180

123x1~^2x2W150

x1+x2=57xN222x.x?No

121.5線性規(guī)劃問題maxz=CX,st.4x~h2x~h2xN41232x~h4xW20124x+8x~h2xW16123x.N0(=1,2,3)(4)maxz=x1+2x2+3x3—x4st.x1+2x2+3x3=152x1+x2+5x3=20x1+2x2+x3+x4=10x.N0(j'=1,??,,4)(6)maxz=5x1+3x2+6x3st.x1+2x2+x3W182x1+x2+3x3^16x1+x2+x3=10x1,x2N0,x3無約束AX=b,XN0,如X*是該問題的最優(yōu)解，又4>0為某一常數(shù)，分別討論下列情況時最優(yōu)解的變化:目標(biāo)函數(shù)變?yōu)閙axz=ACX；目標(biāo)函數(shù)變?yōu)閙axz=(C+人)X；目標(biāo)函數(shù)變?yōu)閙axz=CX,約束條件變?yōu)锳X=Ab。1.6下表中給出某求極大化問題的單純形表，問表中a1,a2c1,c2,d為何值時以及表中變量屬于哪一種類型時有：表中解為唯一最優(yōu)解；表中解為無窮多最優(yōu)解之一；表中解為退化的可行解；下一步迭代將以x1替換基變量x5；該線性規(guī)劃問題具有無界解；1.7戰(zhàn)斗機是一種重要的作戰(zhàn)工具，但要使戰(zhàn)斗機發(fā)揮作用必須有足夠的駕駛該線性規(guī)劃問題無可行解。1.7戰(zhàn)斗機是一種重要的作戰(zhàn)工具，但要使戰(zhàn)斗機發(fā)揮作用必須有足夠的駕駛員。因此生產(chǎn)出來的戰(zhàn)斗機除一部分直接用于戰(zhàn)斗外，需抽一部分用于培訓(xùn)駕駛員。已知每年生產(chǎn)的戰(zhàn)斗機數(shù)量為a.(j=1,…,n)，又每架戰(zhàn)斗機每年能培訓(xùn)出k名駕駛

員，問應(yīng)如何分配每年生產(chǎn)出來的戰(zhàn)斗機，使在n年內(nèi)生產(chǎn)出來的戰(zhàn)斗機為空防作出最大貢獻？1.8.某石油管道公司希望知道，在下圖所示的管道網(wǎng)絡(luò)中可以流過的最大流量是多少及怎樣輸送，弧上數(shù)字是容量限制。請建立此問題的線性規(guī)劃模型，不必求解。1.9.某晝夜服務(wù)的公交線路每天各時間區(qū)段內(nèi)所需司機和乘務(wù)人員數(shù)如下:班次時間所需人數(shù)16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030設(shè)司機和乘務(wù)人員分別在各時間區(qū)段一開始時上班，并連續(xù)工作八小時，問該公交線路至少配備多少名司機和乘務(wù)人員。列出此問題的線性規(guī)劃模型。1.10某班有男生30人，女生20人，周日去植樹。根據(jù)經(jīng)驗，一天男生平均每人挖坑20個，或栽樹30棵，或給25棵樹澆水；女生平均每人挖坑10個，或栽樹20棵，或給15棵樹澆水。問應(yīng)怎樣安排，才能使植樹（包括挖坑、栽樹、澆水）最多？請建立此問題的線性規(guī)劃模型，不必求解。1.11某糖果廠用原料A、B、C加工成三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果中A、B、C含量，原料成本，各種原料的每月限制用量，三種牌號糖果的單位加工費及售價如下表所示。問該廠每月應(yīng)生產(chǎn)這三種牌號糖果各多少千克，使該廠獲利最大？試建立此問題的線性規(guī)劃的數(shù)學(xué)模型。甲乙丙原料成本元/千克）每月限量（千克）A>60%>15%2.002000B1.502500C<20%<60%<50%1.001200加工費（元/千克）0.500.400.30售價3.402.852.251.12.某商店制定7-12月進貨售貨計劃，已知商店倉庫容量不得超過500件，6月底已存貨200件，以后每月初進貨一次，假設(shè)各月份此商品買進售出單價如下表所示，問各月進貨售貨各多少，才能使總收入最多？請建立此問題的線性規(guī)劃模

型，不必求解。月份789101112買進單價282425272323售出單價2924262822251.13.某農(nóng)場有100公頃土地及15000元資金可用于發(fā)展生產(chǎn)。農(nóng)場勞動力情況為秋冬季3500人日，春夏季4000人日，如勞動力本身用不了時可外出干活，春夏季收入為2.1元/人日，秋冬季收入為1.8元/人日。該農(nóng)場種植三種作物：大豆、玉米、小麥，并飼養(yǎng)奶牛和雞。種作物時不需要專門投資，而飼養(yǎng)動物時每頭奶牛投資400元，每只雞投資3元。養(yǎng)奶牛時每頭需撥出1.5公頃土地種飼草，并占用人工秋冬季為100人日，春夏季為50人日，年凈收入400元/每頭奶牛。養(yǎng)雞時不占土地，需人工為每只雞秋冬季需0.6人日，春夏季為0.3人日，年凈收人為2元/每只雞。農(nóng)場現(xiàn)有雞舍允許最多養(yǎng)3000只雞，牛欄允許最多養(yǎng)32頭奶牛。三種作物每年需要的人工及收人情況如下表所示。大豆玉米麥子秋冬季需人日數(shù)203510春夏季需人日數(shù)507540年凈收入（元/公頃）175300120試決定該農(nóng)場的經(jīng)營方案，使年凈收人為最大。（建立線性規(guī)劃模型，不需求解）1.14某廠接到生產(chǎn)A、B兩種產(chǎn)品的合同，產(chǎn)品A需200件，產(chǎn)品B需300件。這兩種產(chǎn)品的生產(chǎn)都經(jīng)過毛坯制造與機械加工兩個工藝階段。在毛坯制造階段，產(chǎn)品A每件需要2小時，產(chǎn)品B每件需要4小時。機械加工階段又分粗加工和精加工兩道工序，每件產(chǎn)品A需粗加工4小時，精加工10小時；每件產(chǎn)品B需粗加工7小時，精加工12小時。若毛坯生產(chǎn)階段能力為1700小時，粗加工設(shè)備擁有能力為1000小時，精加工設(shè)備擁有能力為3000小時。又加工費用在毛坯、粗加工、精加工時分別為每小時3元、3元、2元。此外在粗加工階段允許設(shè)備可進行500小時的加班生產(chǎn)，但加班生產(chǎn)時間內(nèi)每小時增加額外成本4.,5元。試根據(jù)以上資料，為該廠制訂一個成本最低的生產(chǎn)計劃。1.15對某廠i，ii，m三種產(chǎn)品下一年各季度的合同預(yù)訂數(shù)如下表所示。口產(chǎn)品季度1234I1500100020001200II1500150012001500III1000200015002500該三種產(chǎn)品l季度初無庫存，要求在4季度末各庫存150件。已知該廠每季度生產(chǎn)工時為15000小時，生產(chǎn)I、II、m產(chǎn)品每件分別需時2、4、3小時。因更換工藝裝備，產(chǎn)品I在2季度無法生產(chǎn)。規(guī)定當(dāng)產(chǎn)品不能按期交貨時，產(chǎn)品LII每件每遲交一個季度賠償20元，產(chǎn)品m賠償10元；又生產(chǎn)出來產(chǎn)品不在本季度交貨的，每件每季度的庫存費用為5元。問：該廠應(yīng)如何安排生產(chǎn)，使總的賠償加庫存的費用為最?。ㄒ蠼?shù)學(xué)模型，不需求解）。1.16某公司有三項工作需分別招收技工和力工來完成。第一項工作可由一個技工單獨完成，或由一個技工和兩個力工組成的小組來完成。第二項工作可由一個技工或一個力工單獨去完成。第三項工作可由五個力工組成的小組完成，或由一個技工領(lǐng)著三個力工來完成。已知技工和力工每周工資分別為100