3線性規(guī)劃的應(yīng)用

1、1,線性規(guī)劃的上機(jī)操作,2,例 某工廠準(zhǔn)備做100套鋼架，每套鋼架均由長為2.9米、2.1米和1.5米的鋼管各一根所組成，已知原料長7.4米，如何下料方能使原料最省？,解：原料的下料方式如下表。,3,設(shè)按照方式 Aj下料的原料有 xj 根（j =1，…，8）；所用原料為 y 根。于是，該下料問題的數(shù)學(xué)模型是：,4,采取單純形法來求解。可知最優(yōu)解（x1，x2，x3，x4，x5，x6，x7，x8）=（40，20，0，0，0，30，0， 0

2、）。這表明，只須采用下料方式A1 、A2 和 A6，而且所用原料分別為40根、20根和30根，可使所用原料最省。,放寬:得到相應(yīng)線性規(guī)劃為：,5,該例還可以采用另外的目標(biāo)函數(shù)，即100套鋼架的料頭總長度為 y 米。數(shù)學(xué)模型是：,注意“>=”要改為“=”,6,,7,,,,8,,輸入數(shù)據(jù),9,,10,第四節(jié)、線性規(guī)劃的應(yīng)用,11,例1 載貨問題：有一艘貨輪，分前、中、后三個艙位，它們的容積與最大允許載重量如下面表所示。,現(xiàn)有三種貨物待

3、運(yùn)，已知有關(guān)數(shù)據(jù)列于下面表。,為了航運(yùn)安全，要求前、中、后艙在實(shí)際載重量上大體保持各艙最大允許載重量的比例關(guān)系。具體要求前、后艙分別與中艙之間載重量比例上偏差不超過 15%，前、后艙之間不超過 10%。問該貨輪應(yīng)裝載 A、B、C各多少件，運(yùn)費(fèi)收入為最大？,12,(2) 確定目標(biāo)函數(shù) 商品 A 的件數(shù)為：x11 + x12 + x13，即裝于貨輪前、中、后艙商品 A 的件數(shù)之和； 商品 B 的件數(shù)為：x21 + x22 +

4、 x23，即裝于貨輪前、中、后艙商品 B 的件數(shù)之和； 商品 C 的件數(shù)為：x31 + x32 + x33，即裝于貨輪前、中、后艙商品 C 的件數(shù)之和。 為使運(yùn)費(fèi)總收入最大，目標(biāo)函數(shù)為 max Z = 1000(x11 + x12 + x13) + 700(x21 + x22 + x23) + 600(x31 + x32 + x33),解：(1) 確定決策變量

5、 因?yàn)锳、B、C三種商品在貨輪的前、中、后艙均可裝載，令 i = 1, 2, 3 分別代表商品 A、B、C，用 j = 1, 2, 3 分別代表前、中、后艙。設(shè)決策變量 xij 為裝于 j 艙位的第 i 種商品的數(shù)量（件）。,13,(3) 確定約束條件,A、B、C 三種商品數(shù)量限制為： x11 + x12 + x13 ? 600 x21 + x22 + x23 ? 1000 x3

6、1 + x32 + x33 ? 800,前、中、后艙位體積限制為： 10x11 + 5x21 + 7x31 ? 4000 10x12 + 5x22 + 7x32 ? 5400 10x13 + 6x23 + 7x33 ? 1500,前、中、后艙位載重量限制為： 8x11 + 6x21 + 5x31 ? 2000 8x12 + 6x22 + 5x32 ? 3000

7、 8x13 + 6x23 + 5x33 ? 1500,14,xij ? 0，i = 1, 2, 3，j = 1, 2, 3。 綜上所述，該問題的線性規(guī)劃模型如下：,,根據(jù)各艙實(shí)際載重量大體應(yīng)保持各艙最大允許載重量的比例關(guān)系，且前、后艙分別與中艙之間載重量比例上偏差不超過 15%，前、后艙之間不超過 10%，可得艙體平衡條件為：,15,,16,最后解得： x11 = 206.7722，x12 = 318.2278，

8、 x13 = 75， x21 = 0， x22 = 0， x23 = 150， x31 = 69.1646， x32 = 90.8354， x33 = 0；總費(fèi)用為：8.01?105。,17,例2：庫存問題 某公司在今后四個月內(nèi)需租用倉庫堆放物資。已知各月所需倉庫面積如下：,該廠根據(jù)需要，在各月初辦理租借合同，可同時簽訂不同面積、不同期限的合同。請制定

9、一個費(fèi)用最小的租借方案。,倉庫租借費(fèi)用，與租借合同期限有關(guān)，越長則折扣越大，具體如下：,18,決策變量Xij: 第i月租借期限為j個月的倉庫面積,19,例3、合金的添加優(yōu)化問題 某特鋼公司煉鋼廠用電爐冶煉特種鋼，其鋼種數(shù)目達(dá)數(shù)百個之多，這些特殊鋼所含的元素少的有六七種，多的達(dá)十一種。這些元素通常是由各種鐵合金提供，即在鋼水中添加適量的各種鐵合金，使煉成的鋼符合各個鋼種的要求，一般說來，在添加各種鐵合金之前，

10、鋼水中的各種元素的含量低于規(guī)格要求，因此添加各種鐵合金多少，向來是工程技術(shù)人員的一個難題。 該廠過去一直沿用“經(jīng)驗(yàn)估計(jì)法”來調(diào)整各種元素的含量，質(zhì)量不穩(wěn)定，還經(jīng)常發(fā)生報(bào)廢現(xiàn)象；而且為了某些主要元素含量偏低，往往將某些元素加到上限，而鐵合金是一種價格昂貴的材料，這無形提高了鋼的成本。 為了提高鋼的質(zhì)量，降低生產(chǎn)成本，我們必須采用線性規(guī)劃模型來解決這類問題。 已知下列數(shù)據(jù)： (1)鋼水的重量：W (2

11、)鋼水中各種受控元素為 M 個，目前，在鋼水的含量為：b1,…,bm（%） (3)鋼的規(guī)格要求：各種元素最低不得低于：a1,…,am 不得高于：c1,…,cm (4)現(xiàn)有 n 種鐵合金，它們各種元素的含量及價格如下表：,20,21,例4、生產(chǎn)存貯問題 一個合資食品企業(yè)面臨某種食品一至四月的生產(chǎn)計(jì)劃問題。四個月的需求分別為4500噸、3000噸、55

12、00噸、4000噸。目前（一月初）該企業(yè)有100個熟練工人，正常工作時每人每月可以完成40噸，每噸成本200元。由于市場需求浮動較大，該企業(yè)可通過以下方法調(diào)節(jié)生產(chǎn)： （1）利用加班增加生產(chǎn)，但加班生產(chǎn)每人每月不能超過10噸，其成本為300元/噸。 （2）利用庫存來調(diào)節(jié)，庫存費(fèi)用為60元/噸/月，最大庫存能力為1000噸。 請為該企業(yè)構(gòu)造一個線性規(guī)劃模型，在滿足需求的前提下使四個月總費(fèi)用為最小。 假定該企業(yè)

13、在一月初的庫存為0，要求四月底庫存為500噸。,22,23,例5、配料問題 綠色飼料公司生產(chǎn)雛雞、蛋雞、肉雞三種飼料，三種飼料由A、B、C三種原料混合而成，產(chǎn)品規(guī)格要求、產(chǎn)品單價、產(chǎn)品日銷售量、原料單價見下表：,受資金及生產(chǎn)能力限制，每天只能生產(chǎn)30噸，問如何安排生產(chǎn)，獲利最大？,24,例6、工廠選址問題 有A、B、C三個原料產(chǎn)地，其原料要在工廠加工，制成成品，再在銷售地出售，A、B兩地又是銷售地，已知有關(guān)數(shù)據(jù)如下：,其

14、中：4噸原料制成1噸成品，原料運(yùn)費(fèi)每百公里300元，成品運(yùn)費(fèi)每百公里200元。如在B地設(shè)加工廠，每年產(chǎn)成品不能超過5萬噸，A、C設(shè)廠，則不受限制。問應(yīng)在哪建廠，總費(fèi)用（為簡化問題，在這只包括產(chǎn)品加工費(fèi)、運(yùn)費(fèi)）最低？,25,表中出現(xiàn)了X12、X21是否矛盾？,26,Min Z =5.5*(Y11+Y12)+ 4*(Y21+Y22)+ 3*(Y31+Y32) +0.3*[1.5*(X12+X21)+ 1.0*(X13

15、+X31) +2.0*(X23+X32)] +0.2*[1.5*(Y12+Y21) +1.0* Y31+ 2.0* Y32],第一類約束條件：原材料的運(yùn)輸數(shù)量是成品數(shù)量的4倍A：30+X21+X31-X12-X13 = 4*（Y11+Y12）B：26+X12+X32-X21-X23 = 4*（Y21+Y22）C：24+X13+X23-X31-X32 = 4*（Y31+Y32）,

16、27,28,例7、培訓(xùn)問題 某工廠舉辦“技工”培訓(xùn)班，由受過培訓(xùn)合格的技師負(fù)責(zé)培訓(xùn)，每名技師負(fù)責(zé)培訓(xùn)10名學(xué)員，培訓(xùn)一個月為一期，根據(jù)以往經(jīng)驗(yàn)，每10名學(xué)員有7名能成為合格技工。合格技工全部留用，不合格不予留用。在今后三個月內(nèi)，廠方需要技工人數(shù)為：1月份100人，2月份150人，3月份200人，已知年初有合格技工130人。工資支付標(biāo)準(zhǔn)如下：正受訓(xùn)的學(xué)員，每人每月400，合格技工中上班的每人每月1200，部份留用但暫時還不需要上班

17、的每人每月800。制訂一個工資總額最小的培訓(xùn)方案。 假定4月份至少需要250名技工。,29,決策變量：,30,例8：投資計(jì)劃問題,某投資機(jī)構(gòu)在今后3年內(nèi)有4種投資機(jī)會：1、在3年內(nèi)每年年初投資，年底可獲利潤20%，并可將本金 收回。2、在第一年年初投資，第二年年底可獲利50%，并可將本金 收回，但該項(xiàng)投資金額不超過200萬元。3、在第二年年初投資，第三年年底收回本金，可獲利60%， 但該項(xiàng)投資金額不