《運籌學》-習題-線性規(guī)劃部分練習題及-答案

1、精選優(yōu)質文檔-傾情為你奉上 運籌學線性規(guī)劃部分練習題一、思考題1 什么是線性規(guī)劃模型，在模型中各系數(shù)的經濟意義是什么？2 線性規(guī)劃問題的一般形式有何特征？3 建立一個實際問題的數(shù)學模型一般要幾步？4 兩個變量的線性規(guī)劃問題的圖解法的一般步驟是什么？5 求解線性規(guī)劃問題時可能出現(xiàn)幾種結果，那種結果反映建模時有錯誤？6 什么是線性規(guī)劃的標準型，如何把一個非標準形式的線性規(guī)劃問題轉化成標準形式。7 試述線性規(guī)劃問題的可行解、基礎解、基礎可行解、最優(yōu)解、最優(yōu)基礎解的概念及它們之間的相互關系。8 試述單純形法的計算步驟，如何在單純形表上判別問題具有唯一最優(yōu)解、有無窮多個最優(yōu)解、無界解或無可行解。9 在什

2、么樣的情況下采用人工變量法，人工變量法包括哪兩種解法？10大M 法中，M 的作用是什么？對最小化問題，在目標函數(shù)中人工變量的系數(shù)取什么？最大化問題呢？11什么是單純形法的兩階段法？兩階段法的第一段是為了解決什么問題？在怎樣的情況下，繼續(xù)第二階段？二、判斷下列說法是否正確。1 線性規(guī)劃問題的最優(yōu)解一定在可行域的頂點達到。2 線性規(guī)劃的可行解集是凸集。3 如果一個線性規(guī)劃問題有兩個不同的最優(yōu)解，則它有無窮多個最優(yōu)解。4 線性規(guī)劃模型中增加一個約束條件，可行域的范圍一般將縮小，減少一個約束條件，可行域的范圍一般將擴大。5 線性規(guī)劃問題的每一個基本解對應可行域的一個頂點。6 如果一個線性規(guī)劃問題有可行

3、解，那么它必有最優(yōu)解。7 用單純形法求解標準形式（求最小值）的線性規(guī)劃問題時，與對應的變量都可以被選作換入變量。8 單純形法計算中，如不按最小非負比值原則選出換出變量，則在下一個解中至少有一個基變量的值是負的。9 單純形法計算中，選取最大正檢驗數(shù)對應的變量作為換入變量，可使目 標函數(shù)值得到最快的減少。10 一旦一個人工變量在迭代中變?yōu)榉腔兞亢?，該變量及相應列的?shù)字可以從單純形表中刪除，而不影響計算結果。三、建立下面問題的數(shù)學模型1 某公司計劃在三年的計劃期內，有四個建設項目可以投資：項目從第一年到第三年年初都可以投資。預計每年年初投資，年末可收回本利120% ，每年又可以重新將所獲本利納入投

4、資計劃；項目需要在第一年初投資，經過兩年可收回本利150% ，又可以重新將所獲本利納入投資計劃，但用于該項目的最大投資額不得超過20萬元；項目需要在第二年年初投資，經過兩年可收回本利160% ，但用于該項目的最大投資額不得超過15萬元；項目需要在第三年年初投資，年末可收回本利140% ，但用于該項目的最大投資額不得超過10萬元。在這個計劃期內，該公司第一年可供投資的資金有30萬元。問怎樣的投資方案，才能使該公司在這個計劃期獲得最大利潤？2某飼養(yǎng)場飼養(yǎng)動物，設每頭動物每天至少需要700克蛋白質、30克礦物質、100克維生素。現(xiàn)有五種飼料可供選用，各種飼料每公斤營養(yǎng)成分含量及單價如下表21所示：

5、表 21飼料蛋白質（克）礦物質（克）維生素（毫克）價格（元/公斤）13105022205100731020204462203512050808 要求確定既滿足動物生長的營養(yǎng)要求，又使費用最省的選擇飼料的方案。設有某種原料的三個產地為，把這種原料經過加工制成成品，再運往銷售地。假設用4噸原料可制成1噸成品，產地年產原料30萬噸，同時需要成品7萬噸；產地年產原料26萬噸，同時需要成品13萬噸；產地年產原料24萬噸，不需要成品。又知與間距離為150公里， 與間距離為100公里，與間距離為200公里。原料運費為3千元 / 萬噸公里，成品運費為2.5千元 / 萬噸公里；在開設工廠加工費為5.5千元 /

6、萬噸，在開設工廠加工費為4千元 / 萬噸，在開設工廠加工費為3千元 / 萬噸；又因條件限制，在設廠規(guī)模不能超過年產成品5萬噸，與可以不限制（見表22），問應在何地設廠，生產多少成品，才使生產費用（包括原料運費、成品運費和加工費）最少？ 表2 2距 產 離 地產地產原料數(shù)（萬噸）加工費（千元/萬噸）0150100305515002002641002000243需成品數(shù)（萬噸）71304某旅館每日至少需要下列數(shù)量的服務員（見表23）每班服務員從開始上班到下班連續(xù)工作八小時，為滿足每班所需要的最少服務員數(shù)，這個旅館至少需要多少服務員。 表 2 3班 次時 間 （日 夜 服 務）最少服務員人數(shù)1上午

7、6 點 上午10點802上午10點 下午2 點903下午 2 點 下午 6 點804下午 6 點 夜間10點705夜間10點 夜間 2 點406夜間 2 點 上午 6 點305 某農場有100公頃土地及15000元資金可用于發(fā)展生產。農場勞動力情況為秋冬季3500人日；春夏季4000人日。如勞動力本身用不了時可外出打工，春秋季收入為25元 / 人日，秋冬季收入為20元 / 人日。該農場種植三種作物：大豆、玉米、小麥，并飼養(yǎng)奶牛和雞。種作物時不需要專門投資，而飼養(yǎng)每頭奶牛需投資800元，每只雞投資3元。養(yǎng)奶牛時每頭需撥出1.5公頃土地種飼料，并占用人工秋冬季為100人日，春夏季為50人日，年凈收

8、入900元 / 每頭奶牛。養(yǎng)雞時不占用土地，需人工為每只雞秋冬季0.6人日，春夏季為0.3人日，年凈收入2元 / 每只雞。農場現(xiàn)有雞舍允許最多養(yǎng)1500只雞，牛欄允許最多養(yǎng)200頭。三種作物每年需要的人工及收入情況如表2 4所示 表 2 4大豆玉米麥子秋冬季需人日數(shù)春夏季需人日數(shù)年凈收入（元/公頃）205030003575410010404600 試決定該農場的經營方案，使年凈收入為最大。6市場對、兩種產品的需求量為：產品在1 4月份每月需1萬件，59月份每月需3萬件，10 12月份每月需10萬0件；產品在3 9月份每月需1.5萬件，其它每月需5萬件。某廠生產這兩種產品的成本為：產品在1 5月

9、份內生產時每件5元，6 12月份內生產時每件4.50元；產品在在1 5月份內生產時每件8元，6 12月份內生產時每件7元；該廠每月生產兩種產品能力總和不超過12萬件。產品容積每件0.2立方米，產品容積每件0.4立方米。該廠倉庫容積為1萬5千立方米，要求：（1）說明上述問題無可行解；（2）若該廠倉庫不足時，可從外廠租借。若占用本廠倉庫每月每立方米需1元，而租用外廠倉庫時上述費用增加為1.5元，試問在滿足市場需求情況下，該廠應如何安排生產，使總的生產加庫存費用最少？（建立模型，不求解）7某工廠、三種產品在下一年個季度的合同預定數(shù)如表 2 5所示，該三種產品第一季度初無庫存，要求在在第四季度末每種產

10、品的庫存為150件。已知該廠每季度生產工時為15000小時，生產產品、每件需3，4，3小時。因更換工藝裝備，產品在第二季度無法生產。規(guī)定當產品不能按期交貨時，產品、每件每遲交一個季度賠償20元，產品賠償15元，又生產出來的產品不在本季度交貨的，每件每季度的庫存費為5元。問應如何安排生產，使總的賠償加庫存費用最小。 表 2 5產 品季 度12341500100020001200150015001200150015002000150025008某玩具廠生產、三種玩具，這三種玩具需在、三種機器上加工，每60個為一箱。每箱玩具在不同的機器上加工所需的時間（天）如表2 6 所示，本月可供使用的機器的時間

11、為：為15天，為20天，為天。每箱玩具的價格為：1500元；：1700元； ：2400元。問怎樣安排生產，使總的產值最大。 表 2 6加工天數(shù)機器玩具玩具玩具某線帶廠生產、兩種紗線和、兩種紗帶，紗帶由紗線加工而成。這四種產品的產值，可變成本（即材料、人工等隨產品數(shù)量變化的直接費用），加工工時等由表給出，工廠有供紡紗的總工時7200h，織帶的總工時1200h（1） 列出線性規(guī)劃模型，以便確定產品數(shù)量，使總的利潤最大。（2） 如果組織這次生產的固定成本（即與產品數(shù)量無關的間接費用）為20萬元，線性規(guī)劃模型有何變化？ 表 2 7 產品項目單位產值（元）1681401050406單位可變成本（元）42

12、28350140單位紡紗工時（h）32104單位織帶工時（h）0020510 某制衣廠生產4種規(guī)格的出口服裝，有三種制衣機可以加工這4種服裝，他們的生產效率（每天制作的服裝件數(shù)）等有關數(shù)據(jù)如表28所示，試確定各種服裝的生產數(shù)量，使總的加工費用最小。 表 28衣服規(guī)格制 衣 機需要生產 數(shù)量（件）ABC30060080010000280450700900020035068070001504104508000每天加工費（元）8010015011某制衣廠生產兩種服裝，現(xiàn)有100名熟練工人。已知一名熟練工人每小時生產10件服裝或6件服裝。據(jù)銷售部門消息，從本周開始，這兩種服裝的需求量將持續(xù)上升。見表2

13、 9，為此，該廠決定到第8周末需培訓出100名新工人，兩班生產。已知一名工人一周工作40小時，一名熟練工人每周時間可培訓出不多余5名的新工人（培訓期間熟練工人和培訓人員不參加生產）熟練工人每周工資400元，新工人在培訓期間工資每周80元，培訓合格后參加生產每周工資260元，生產效率同熟練工人。在培訓期間，為按期交貨，工廠安排部分工人加班生產每周工作50小時，工資每周600元。又若所定的服裝不能按期交貨，每推遲交貨一周的賠償費為：服裝每件10元，服裝每件20元。工廠應如何安排生產，使各項費用總和最少。 表 2 9 （單位：千件/周） 周次服裝123456782020242533344042121

14、417222225252512某家具制造廠生產五種不同規(guī)格的家具。每種家具都要經過機械成型、打磨、上漆幾種主要工序。每種家具的每道工序所用時間及每道工序的可用時間，每種家具的利潤由表210給出。問工廠應如何安排生產，使總的利潤最大？ 表 210生產工序所需時間 （小時）每道工序可用時間一二三四五成型346233600打磨435643950上漆2800利潤（百元）.7.52.5313某混合飼料場飼養(yǎng)為某種動物配置。已知此動物的生長速度和飼料中的三種營養(yǎng)成分甲、乙、丙有關，且每頭動物每天需要營養(yǎng)甲85克，乙5克，丙18克?，F(xiàn)有五種飼料都含有這三種營養(yǎng)成分，每種飼料每公斤所含營養(yǎng)成分及每種飼料成本如

15、表 211所示，求即滿足動物成長需要又使成本最低的飼料配方。 表 211飼料營養(yǎng)甲（克）營養(yǎng)乙（克）營養(yǎng)丙（克）成本（元）105001000822200006070633000040355415001502545080020002314某食品廠在第一車間用1單位原料N可加工3單位產品A及2單位產品B，產品A可以按單位售價8元出售，也可以在第二車間繼續(xù)加工，單位生產費用要增加6元，加工后單位售價增加9元。產品B可以按單位售價7元出售，也可以在第三車間繼續(xù)加工，單位生產費用要增加4元，加工后單位費用可增加6元。原料N的單位購入價為2元，上述生產費用不包括工資在內。3個車間每月最多有20萬工時，每工

16、時工資0.5元，每加工1單位N需1.5個工時，如A繼續(xù)加工,每單位需3工時，如B繼續(xù)加工，每單位需2個工時。原料N每月最多能得到10萬單位。問如何安排生產，使工廠獲利最大。15某公司有30萬元可用于投資，投資方案有下列幾種：方案：年初投資1元，第二年年底可收回12元。5年內都可以投資，但投資額不能超過萬元。方案：年初投資1元，第三年年底可收回13元。5年內都可以投資。方案：年初投資1元，第四年年底可收回14元。5年內都可以投資。方案：只在第二年年初有一次投資機會，每投資1元，四年后可收回1.7元。但最多投資額不能超過10萬元。方案：只在第四年年初有一次投資機會，每投資1元，年底可收回1.4元。

17、但最多投資額不能超過20萬元。方案：存入銀行，每年年初存入1元，年底可收回1.02元.投資所得的收益及銀行所得利息也可用于投資.求使公司在第五年底收回資金最多的投資方案.16.某工廠生產、四種產品，產品需依次經過A、B兩種機器加工，產品需依次經過A、C兩種機器加工，產品需依次經過B、C兩種機器加工，產品需依次經過A、B機器加工。有關數(shù)據(jù)如表212所示，請為該廠制定一個最優(yōu)生產計劃。 表 212產 品機器生產率（件/小時）原料成本（元）產品價格（元）10201665201025801015125020101870機器成本（元小時）200150225每 周 可 用 小時 數(shù)15012070四、用圖

18、解法解下列線性規(guī)劃1 2 3 4 5 6 五、用單純形法解下列線性規(guī)劃問題。（可用大M法或兩階段法）。（1） （2） (3) (4) (5)（6） (7) (8) (9) (10) (11) (12) 六、表213中給出求極大化問題的單純形表，問表中為何值時以及表中變量屬于哪一種類型時有：（1） 表中解為唯一最優(yōu)解； （2）表中解為無窮多最優(yōu)解之一；（3）表中解為退化的可行解；（4）下一步迭代將以代替基變量；（5）該線性規(guī)劃問題具有無界解；（6）該線性規(guī)劃問題無可行解。 表213 34153100010001000七、某醫(yī)院的護士分四個班次，每班工作12 h 。報到的時間分別是早上 6點 ，中

19、午12點,下午 6 點，夜間 12點。每班需要的人數(shù)分別為19人，21人，18人，16人。問：（1） 每天最少需要派多少護士值班？（2） 如果早上6點上班和中午12點上班的人每月有120元加班費，下午6點和夜間12點上班的人每月分別有100元和150元加班費，如何安排上班人數(shù)，使醫(yī)院支付的加班費最少？八、某石油公司有兩個冶煉廠。甲廠每天可生產高級、中級和低級的石油分別為200，300和200桶，乙廠每天可生產高級、中級和低級的石油分別為100，200和100桶。公司需要這三種油的數(shù)量分別為 14000，24000和14000桶。甲廠每天的運行費是5000元，乙廠是4000元。問：（1） 公司應

20、安排這兩個廠各生產多少天最經濟？（2） 如甲廠的運行費是2000元，乙廠是5000元。公司應如何安排兩個廠的生產。列出線性規(guī)劃模型并求解。 運籌學習題解答第二章 線性規(guī)劃模型及其單純形法二、(1) X (2) (3) (4) (5) X (6) X (7) (8) (9) X (10) 三、1 解：設決策變量分別表示第一年投資到項目、的資金額；分別表示第二年投資到項目、的資金額；分別表示第三年投資到項目、的資金額。則得線性規(guī)劃模型如下： 2 解：設五種飼料分別選取公斤，則得下面的數(shù)學模型： ；3 解：設表示由運往的原料數(shù)（單位：萬噸）（。其中時，表示留用數(shù)；表示由運往的成品數(shù)（單位：萬噸）（。

21、其中時，表示留用數(shù)；表示在設廠的年產成品數(shù)（單位：萬噸）（。則這一問題的數(shù)學模型為： 4 解：設1，2，3，4，5，6）為第班開始上班的服務員人數(shù)。則數(shù)學模型： 5 用分別表示大豆、玉米、麥子的種植公頃數(shù)；分別表示奶牛和雞的飼養(yǎng)數(shù)；分別表示秋冬季和春夏季的勞動力（人日）數(shù)，則有6 解：（1）因為10 12月份市場需求總計45萬件，這三個月最多生產36萬件，故需10月初有9萬件的庫存，超過該廠的最大倉庫容積，故按上述條件，本題無解。（2）考慮到生產成本、庫存費用和生產能力，該廠月份需求的不足只需在月份生產出來留用即可，故設：為第個月生產的產品的數(shù)量；為第個月生產的產品的數(shù)量；分別為第個月末產品、的庫存數(shù)，分別為用于第（）個月庫存的原有及租用的倉庫容積（立方米），則所求問題的數(shù)學模型為：7 解：設為第個季度生產的產品的數(shù)量；為第個季度末需庫存的產品的數(shù)量；為第個季度不能交貨的產品的數(shù)量；為第個季度對產