lesson42線性規(guī)劃問題案例建模及討論

1、五、線性規(guī)劃問題案例建模及討論案例1.工業(yè)原料的合理利用案例2.農(nóng)場發(fā)展規(guī)劃問題案例3.最優(yōu)的貨輪裝載方案案例4.合理的倉庫租借合同案例5.招工方案的制定案例6.配料問題案例7.人員分配問題案例8.最佳項目投資方案案例9.客觀評價學(xué)生的學(xué)習(xí)情況1案例1.工業(yè)原料的合理利用要制作100套鋼筋架子，每套有長2.9米、2.1米和1.5米的鋼筋各一根。已知原材料長7.4米，應(yīng)如何切割使用原材料最省。解 下面幾種方案都是能節(jié)省材料的好方案（見下表）。080302010料頭（米）6671727374合計（米）131222211329米21米15米 下料數(shù) 方案長度 2設(shè)方案用 x1 根，方案用 x2 根，

2、方案用 x3 根，方案用 x4 根，方案用 x5 根。則線性規(guī)劃模型為：080302010料頭（米）6671727374合計（米）131222211329米21米15米 下料數(shù) 方案長度 3添加人工變量后，模型變?yōu)椋悍桨?0根，方案10根，方案50根。即只需90根原材料，就可以制造出100套鋼筋架子。余料16米。用單純形法求得的最優(yōu)下料方案為：用Lingo求解4約束條件不變，利用LINGO軟件計算，最優(yōu)解為：方案下40根，方案下30根，方案下20根。進(jìn)一步討論：用Lingo求解1.將目標(biāo)函數(shù)變?yōu)樗迷牧稀案鶖?shù)最少”，即2.約束條件的改進(jìn)及完善 在求解線性規(guī)劃問題時，若約束條件為等式約束， 則

3、容易產(chǎn)生無可行解。 因此在建模的時候，盡量避免使用等式約束。 對于此例，如果條件改為“要求制作29套”鋼筋架子， 目標(biāo)函數(shù)仍然用“余料最少”，則相應(yīng)的模型為：無可行解用Lingo求解5進(jìn)一步討論：2.約束條件的改進(jìn)及完善 在求解線性規(guī)劃問題時，若約束條件為等式約束， 則容易產(chǎn)生無可行解。 對于本問題，可行的做法是 將所有約束條件改為“”，則相應(yīng)的模型為：用Lingo求解結(jié)果為：方案下100根，方案下50根，余料為10米！ 目標(biāo)函數(shù)應(yīng)該為 或者 用Lingo求解返回首頁6進(jìn)一步討論：3. 引進(jìn)整數(shù)限制 對于此例，如果條件改為“要求制作111套”鋼筋架子， 目標(biāo)函數(shù)用“所用原材料根數(shù)最少”，則相應(yīng)

4、的模型為： 結(jié)果為：方案下33.3根，方案下11.1根，方案下55.5根. 改為 返回首頁結(jié)果為：方案下32根，方案下12根，方案下55根，方案下1根.7案例2.農(nóng)場發(fā)展規(guī)劃問題8實例2.某農(nóng)場有100公頃土地及15000元資金可用于發(fā)展生產(chǎn)。 農(nóng)場勞動力情況為秋冬季3500人天，春夏季4000人天。 如勞動力用不了時可外出干活。其凈收入為: 春夏季為2.1元/人.天，秋冬季為1.8元/人.天。 該農(nóng)場種植三種作物：大豆、玉米、小麥，并飼養(yǎng)奶牛和雞。 種作物不需專門投資，而每頭奶牛投資400元，每只雞投資3元。 養(yǎng)奶牛時每頭需撥出1.5公頃土地種飼草，并占用人工: 秋冬季100人天，春夏季50

5、人天，年凈收入400元/頭。 養(yǎng)雞時不占土地，需人工喂每只雞秋冬季需0.6人天， 春夏季0.3人天，年凈收入為2元/每只雞。 農(nóng)場現(xiàn)有雞舍允許最多養(yǎng)3000只雞，牛欄允許最多養(yǎng)32頭奶牛。 三種作物每年需要 的人工及收入情況 如右表所示。 試決定該農(nóng)場的經(jīng)營 方案，使年凈收入為最大。 9x1x7x6x5x4x3x2土地限制：資金限制：勞動力限制：牛欄限制:雞舍限制:用Lingo求解10 x1x7x6x5x4x3x2Global optimal solution found at iteration: 4 Objective value: 20260.87 Variable Value Redu

6、ced Cost X1 0.000000 16.30435 X2 39.13043 0.000000 X3 0.000000 17.39130 X4 21.30435 0.000000 X5 0.000000 0.4000000 X6 0.000000 0.8086957 X7 0.000000 0.6826087用Lingo求解牛的數(shù)量應(yīng)該為整數(shù)11Objective value: 20241.80 Variable Value Reduced Cost X1 0.000000 25.00000 X2 39.31333 0.000000 X3 0.000000 40.00000 X4 21.

7、00000 -200.0000 X5 5.000000 -0.8000000 X6 21.00000 -1.800000 X7 0.000000 1.900000Objective value: 20230.70 Variable Value Reduced Cost X1 0.000000 -175.0000 X2 39.00000 -300.0000 X3 0.000000 -120.0000 X4 21.00000 -400.0000 X5 58.00000 -2.000000 X6 0.000000 -1.800000 X7 7.000000 -2.100000用Lingo求解建議種植

8、玉米為整數(shù)公頃返回首頁12有一艘貨輪，分前、中、后三個艙位，它們的最大允許載重量和容積如右表所示： 現(xiàn)有三種貨物待運，有關(guān)數(shù)據(jù)列于下表： 貨物數(shù)量（件）每件體積（立方米件）每件重量（噸件）運價（元件）ABC600100080010578651000700600為了航運安全，要求前、中、后艙在實際載重量上大體保持各艙最大允許載重量的比例關(guān)系。具體要求：前、后艙分別與中艙之間載重量比例上偏差不超過15%，前、后艙不超過10%。問該貨輪應(yīng)裝載A、B、C各多少件，運費收入為最大？案例3.最優(yōu)的貨輪裝載方案13前、后艙分別與中艙之間載重量比例上偏差不超過15%；前、后艙不超過10%。艙位載重限制:艙位體

9、積限制:商品數(shù)量限制:平衡條件:目標(biāo)函數(shù):貨物數(shù)量體積件重量件運價件ABC60010008001057865100070060014解 用i1，2，3分別代表商品A、B、C，用j1，2，3分別代表 前、中、后艙，設(shè)xij為裝于j 艙位的第i 種貨物的數(shù)量（件）， 則問題的線性規(guī)劃模型為：Lingo求解15貨物數(shù)量體積件重量件運價件ABC600100080010578651000700600 Global optimal solution found at iteration: 10 Objective value: 801000.016進(jìn)一步討論: 1.目標(biāo)為總運費最小。 xj = 0，即不裝

10、運貨物。2.限制B至少裝350件，C至少裝300件，目標(biāo)函數(shù)求最大。Global optimal solution found at iteration: 336158 Objective value: 787400.0 01600C15000B75275250A后中前Global optimal solution found at iteration: 10Objective value: 801000.0Lingo求解Lingo求解17進(jìn)一步討論: 1.目標(biāo)為總運費最小。 xj = 02.限制B至少裝350件，C至少裝300件，目標(biāo)函數(shù)求最大。Global optimal solution

11、 found at iteration: 336158 Objective value: 787400.0 01600C15000B75275250A后中前Global optimal solution found at iteration: 10Objective value: 801000.03.限制B至少裝350件，C至少裝300件，目標(biāo)函數(shù)求最小。 Global optimal solution found at iteration: 10 Objective value: 425000.0Lingo求解返回首頁18案例4.合理的倉庫租借合同 工廠在今后四個月內(nèi)需租用倉 庫堆存物資。已

12、知各個月所需 的倉庫面積如右表所示。 月份1234所需倉庫面積（平方百米）15102012倉庫租借費用，當(dāng)租借合同期限越長時，享受的折扣優(yōu)待越大，具體數(shù)字如右表所示。 合同租借期限1個月2個月3個月4個月合同期內(nèi)每平方百米的租借費用（元）2800450060007300租借倉庫的合同每月初都可辦理，每份合同具體規(guī)定租用面積和期限。因此，該廠可根據(jù)需要在任何一個月初辦理租借合同，且每次辦理時可簽一份，也可同時簽若干份租用面積和租借期限不同的合同，目標(biāo)是使所付的租借費用最小。試確定租用方案。 19月份1234所需面積15102012合同租借期限1個月2個月3個月4個月租借費用28004500600

13、07300第1個月的租用面積約束:第2個月的租用面積約束:第3個月的租用面積約束:第4個月的租用面積約束:目標(biāo)函數(shù):xij 為第i個月簽訂租用期限為j個月的合同的面積。Lingo求解20Global optimal solution found at iteration: 4 Objective value: 118400.0月份1234所需面積15102012合同租借期限1個月2個月3個月4個月租借費用2800450060007300詳細(xì)結(jié)果如下。21月份1234所需面積15102012對結(jié)果做如下說明：（1）總租借費用為118400；（2）租借合同為：1月份簽一份租借1個月5平方百米的合同

14、； 1月份簽一份租借4個月10平方百米的合同； 3月份簽一份租借1個月8平方百米的合同； 3月份簽一份租借2個月2平方百米的合同。返回首頁22案例5.招工方案的制定 某公司有三項工作需分別招收技工和力工來完成。 第一項工作可由一個技工單獨完成， 或由一個技工和兩個力工組成的小組來完成。 第二項工作可由一個技工或一個力工單獨完成。 第三項工作可由五個力工組成的小組完成， 或一個技工領(lǐng)著三個力工完成。 已知技工和力工每周工資分別為100元和80元， 每周每人實際的有效工作時間分別為42和36小時。 為完成這三項工作任務(wù)，該公司需要每周總有效工作小時數(shù)為： 第一項工作14000小時，第二項18000

15、小時，第三項24000小時。 又能招收到的工人數(shù)為技工不超過700人，力工不超過1000人。 試確定招收技工和力工的人數(shù)，使總的工資支出為最少。23x11x21x12x22x31x32問題的求解決策變量假設(shè)如下： xij第i項工作的第j個方案 所派的組數(shù) 詳見右表。問題的數(shù)學(xué)模型為： 24x11x21x12x22x31x32Lingo求解詳細(xì)結(jié)果如下：25x11x21x12x22x31x32328138233912510 Global optimal solution found at iteration: 176 Objective value: 127640.0返回首頁26案例6.配料問題

16、 某染料廠用甲、乙、丙三種原料混合配制出 A、B、C三種不同的產(chǎn)品。 原料甲、乙、丙每天的最大供應(yīng)量分別為100、100、60千克， 每千克單價分別為65、25、35元。 由于A、B、C三種產(chǎn)品的質(zhì)量限制，要求 產(chǎn)品A中含原料甲不少于50%，含原料乙不超過25%； 產(chǎn)品B中含原料甲不少于25%，含原料乙不超過50%； 產(chǎn)品C的原料配比無限制，產(chǎn)品A、B含原料丙比例無限制。 產(chǎn)品A、B、C每千克的售價分別為50、35、25元。 問應(yīng)如何安排生產(chǎn)，才能使所獲利潤達(dá)到最大。 表1-4表1-527 原料產(chǎn)品甲乙丙ABCx11x21x31x12x22x32x13x23x33其中xij 表示第i 種產(chǎn)品中

17、含第 j 種原料的數(shù)量。則此問題的數(shù)學(xué)模型為28原料配比約束日供應(yīng)量約束原料產(chǎn)品甲乙丙ABCx11x21x31x12x22x32x13x23x33Lingo求解29Global optimal solution found at iteration: 10Objective value: 500.0000 原料產(chǎn)品甲乙丙ABC1000050005000根源：定價偏低原料過剩利潤太少30Lingo求解Global optimal solution found at iteration: 10Objective value: 500.0000 Global optimal solution fou

18、nd at iteration: 8 Objective value: 3000.000 原料產(chǎn)品甲乙丙ABC10000400606000原料產(chǎn)品甲乙丙ABC1000050005000適當(dāng)提高定價31原料產(chǎn)品甲乙丙ABC10000400606000原料產(chǎn)品甲乙丙ABC1000050005000規(guī)定:產(chǎn)品B至少生產(chǎn)50千克。Lingo求解不生產(chǎn)B產(chǎn)品！32原料產(chǎn)品甲乙丙ABC10000400606000原料產(chǎn)品甲乙丙ABC1000050005000原料產(chǎn)品甲乙丙ABC8713040263447130返回首頁33案例7. 人員分配問題 某中型商場每周對售貨員的需求如右下表。售貨員每周工資為300元

19、。為了保證售貨員的休息，規(guī)定每人每周工作5天，休息2天，并且休息的2天是連續(xù)的。問應(yīng)該如何安排售貨員的作息時間，使得既滿足工作需要，又使支出最少？時 間所需售貨員人數(shù)星期日12人星期一18人星期二15人星期三12人星期四16人星期五19人星期六14人34時 間所需售貨員人數(shù)星期日12人星期一18人星期二15人星期三12人星期四16人星期五19人星期六14人設(shè)決策變量 xi 表示：星期 i 開始休息的員工人數(shù)，詳見下表。則此問題的數(shù)學(xué)模型為：35時 間所需售貨員人數(shù)星期日12人星期一18人星期二15人星期三12人星期四16人星期五19人星期六14人用Lingo求解36Global optimal

20、 solution found at iteration: 13 Objective value: 22.00000 Variable Value Reduced Cost X1 1.000000 1.000000 X2 5.000000 1.000000 X3 3.000000 1.000000 X4 2.000000 1.000000 X5 1.000000 1.000000 X6 7.000000 1.000000 X7 3.000000 1.000000詳細(xì)結(jié)果見下表。37時 間所需售貨員人數(shù)星期日12人星期一18人星期二15人星期三12人星期四16人星期五19人星期六14人總?cè)藬?shù)22

21、人返回首頁38案例8.最佳項目投資方案某部門在今后五年內(nèi)考慮給下列項目投資，已知：項目1 從第一年到第四年的每年年初投資， 并于次年末回收本利115%；項目2 第三年年初投資，到第五年末能回收本利125%， 但規(guī)定最大投資額不超過40萬元；項目3 第二年年初投資，到第五年末能回收本利140%， 但規(guī)定最大投資額不超過30萬元；項目4 五年內(nèi)每年年初均可投資，并于本年末回收本利106%。 該部門現(xiàn)有資金100萬元， 問如何確定投資方案， 使得到第五年末擁有資金的本利額最大？39設(shè)決策變量xij表示：項目i在第j年初的投資額，詳見下表。40Lingo求解此問題的數(shù)學(xué)模型為：且為整數(shù)41Object

22、ive value: 143.7500 Variable Value X14 0.00000 X23 40.00000 X32 30.00000 X45 48.82075 X11 71.69811 X41 28.30189 X12 0.000000 X42 0.000000 X13 42.45283 X43 0.000000 X44 0.000000詳細(xì)結(jié)果見下表。返回首頁42案例9.客觀評價學(xué)生 的學(xué)習(xí)情況某專業(yè)30名學(xué)生連續(xù)兩個學(xué)期的專業(yè)綜合成績?nèi)缬冶硭?，請對這30人給出客觀、合理并具有激勵、鞭策作用的“綜合排名”。學(xué)生學(xué)期1學(xué)期2學(xué)生學(xué)期1學(xué)期219493167561292951775

23、813908718747248978197373587852071846879021705578669226982885832368709846524667410838625654711827926638012807627625313796428567714777229525715767930496843學(xué)生學(xué)期1（ai）學(xué)期2（bi）學(xué)生學(xué)期1（ai）學(xué)期2（bi）194931675612929517758139087187472489781973735878520718468790217055786692269828858323687098465246674108386256547118279266380128076276253137964285677147772295257157679304968解決思路：將第1學(xué)期成績看做基礎(chǔ)成績，在此基