《運(yùn)籌學(xué)》-習(xí)題-線性規(guī)劃部分練習(xí)題及-答案

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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