管理運籌學(xué)第二章-線性規(guī)劃應(yīng)用(建模)

1、LOGO.第二章第二章 線性規(guī)劃的應(yīng)用線性規(guī)劃的應(yīng)用國際醫(yī)藥商學(xué)院國際醫(yī)藥商學(xué)院LOGO.人力資源分配的問題1套裁下料問題2配料問題4生產(chǎn)計劃的問題3投資問題5LOGO.線性規(guī)劃應(yīng)用 合理利用線材問題：合理利用線材問題：如何下料使如何下料使用材最少。用材最少。 配料問題：配料問題：在原料供應(yīng)量的限制在原料供應(yīng)量的限制下如何獲取最大利潤。下如何獲取最大利潤。 投資問題：投資問題：從投資項目中選取方從投資項目中選取方案，使投資回報最大。案，使投資回報最大。線性規(guī)劃線性規(guī)劃-LOGO. 產(chǎn)品生產(chǎn)計劃：產(chǎn)品生產(chǎn)計劃：合理利用人力、物力、財力等，合理利用人力、物力、財力等，使獲利最大。使獲利最大。 勞動

2、力安排：勞動力安排：用最少的勞動力來滿足工作的用最少的勞動力來滿足工作的需要。需要。 運輸問題：運輸問題：如何制定調(diào)運方案，使總運費最如何制定調(diào)運方案，使總運費最小。小。線性規(guī)劃應(yīng)用LOGO. 數(shù)學(xué)規(guī)劃的建模有許多共同點，要遵循下列原則： (1)容易理解。建立的模型不但要求建模者理解，還應(yīng)當(dāng)讓有關(guān)人員理解。這樣便于考察實際問題與模型的關(guān)系，使得到的結(jié)論能夠更好地應(yīng)用于解決實際問題。 (2)容易查找模型中的錯誤。這個原則的目的顯然與(1)相關(guān)。常出現(xiàn)的錯誤有：書寫錯誤和公式錯誤。線性規(guī)劃應(yīng)用 (3)容易求解。對線性規(guī)劃來說，容易求解問題主要是控制問題的規(guī)模，包括決策變量的個數(shù)和約束條件的個數(shù)。這

3、條原則的實現(xiàn)往往會與(1)發(fā)生矛盾，在實現(xiàn)時需要對兩條原則進(jìn)行統(tǒng)籌考慮。LOGO. 建立線性規(guī)劃模型的過程可以分為四個步驟： (1)設(shè)立決策變量； (2)明確約束條件并用決策變量的線性等式或不等式表示； (3)用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大（Max）還是極?。∕in）； (4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。線性規(guī)劃應(yīng)用LOGO. 例1 某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下： 班 次時 間所 需 人 數(shù)16 ： 0 0 1 0 ： 0 06 021 0 ： 0 0 1 4 ： 0 07 031 4 ： 0 0 1 8 ： 0 06 041 8 ：

4、 0 0 2 2 ： 0 05 052 2 ： 2 ： 0 02 062 ： 0 0 6 ： 0 03 0一、人力資源分配的問題設(shè)司機(jī)和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作8h，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?LOGO. 解：設(shè) xi 表示第i班次時開始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：目標(biāo)函數(shù)：MinMin z= z= x x1 1 + + x x2 2 + + x x3 3 + + x x4 4 + + x x5 5 + + x x6 6 約束條件：約束條件：s.t.s.t. x x1 1 + + x x

5、6 6 60 60 x x1 1 + + x x2 2 70 70 x x2 2 + + x x3 3 60 60 x x3 3 + + x x4 4 50 50 x x4 4 + + x x5 5 20 20 x x5 5 + + x x6 6 30 30 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5, ,x x6 6 0 0一、人力資源分配的問題LOGO.例2 某工廠要做100套鋼架，每套用長為2.9 m, 2.1m, 1.5m的圓鋼各一根。已知原料每根長7.4 m，問：應(yīng)如何下料，可使所用原料最??？方案 1方案 2方案 3方案 4方案 5方案 6方

6、案 7方案 82.9 m120101002.1 m002211301.5 m31203104合計7.47.37.27.16.66.56.36.0剩余料頭00.10.20.30.80.91.11.4二、套裁下料問題解:考慮下列各種下料方案（按一種邏輯順序給出）方案 1方案 2方案 3方案 4方案 5方案 6方案 7方案 82.9 m211100002.1 m021032101.5 m10130234合計7.37.16.57.46.37.26.66.0剩余料頭0.10.30.901.10.20.81.4把各種下料方案按剩余料頭從小到大順序列出LOGO. 假設(shè) x1,x2,x3,x4,x5 分別為上

7、面前 5 種方案下料的原材料根數(shù)。我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)： Min z= x1 +x2 +x3 +x4 +x5 約束條件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3+ 3x5 100 x1,x2,x3,x4,x5 0方案 1方案 2方案 3方案 4方案 52.9 m120102.1 m002211.5 m31203合計7.47.37.27.16.6剩余料頭00.10.20.30.8二、套裁下料問題LOGO. 約束條件用大于等于號時，目標(biāo)函數(shù)本來求所用原料最少和求料頭最少是一樣的。 但由于第一個下料的方案中料頭為

8、零，無論按但由于第一個下料的方案中料頭為零，無論按第一下料方案下多少根料，料頭都為零，所以第一下料方案下多少根料，料頭都為零，所以目標(biāo)函數(shù)就一定要求是原料最少。目標(biāo)函數(shù)就一定要求是原料最少。LOGO. 例3 明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機(jī)加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？三、生產(chǎn)計劃的問題LOGO.甲乙丙資 源 限 制鑄 造 工 時 (小 時 /件 )51078000機(jī) 加 工

9、 工 時 (小 時 /件 )64812000裝 配 工 時 (小 時 /件 )32210000自 產(chǎn) 鑄 件 成 本 (元 /件 )354外 協(xié) 鑄 件 成 本 (元 /件 )56-機(jī) 加 工 成 本 (元 /件 )213裝 配 成 本 (元 /件 )322產(chǎn) 品 售 價 (元 /件 )231816解：解：設(shè) x1 ,x2 ,x3 分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4, x5 分別為由外協(xié)鑄造再由本公司機(jī)加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。三、生產(chǎn)計劃的問題LOGO. 求 xi 的利潤:利潤利潤 = = 售價售價 - - 各成本之和各成本之和可得到 xi（i=1,2,3,

10、4,5）的利潤分別為15、10、7、13、9元。 這樣我們建立如下數(shù)學(xué)模型： 目標(biāo)函數(shù)目標(biāo)函數(shù): : Max 15x1+10 x2+7x3+13x4+9x5 約束條件約束條件： s.t. 5x1+10 x2+7x3 8000 6x1+4x2+8x3+6x4+4x5 12000 3x1+2x2+2x3+3x4+2x5 10000 x1,x2,x3,x4,x5 0三、生產(chǎn)計劃的問題LOGO. 例2.14 某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。問：該廠應(yīng)如何安排生產(chǎn)，使利潤收入為最大？四、配料問題LOGO. 解：設(shè)解：設(shè) x xijij 表示第表示第 i i

11、 種（甲、乙、丙）產(chǎn)品中原料種（甲、乙、丙）產(chǎn)品中原料 j j 的含量。這樣我們建立數(shù)學(xué)模型時，要考慮：的含量。這樣我們建立數(shù)學(xué)模型時，要考慮： 對于甲： x11，x12，x13； 對于乙： x21，x22，x23； 對于丙： x31，x32，x33； 對于原料1： x11，x21，x31； 對于原料2： x12，x22，x32； 對于原料3： x13，x23，x33；四、配料問題LOGO.目標(biāo)函數(shù)：目標(biāo)函數(shù)： 利潤最大，利潤利潤最大，利潤 = = 收入收入 - - 原料支出原料支出 約束條件：約束條件：規(guī)格要求規(guī)格要求 4 4 個；個； 供應(yīng)量限制供應(yīng)量限制 3 3 個。個。 Max z z

12、 =150(=150(x11+x12+x13)+85()+85(x21+x22+x23) ) +65( +65(x31+x32+x33)-65()-65(x11+x21+x31) ) -25( -25(x12+x22+x32)-35()-35(x13+x23+x33) ) =85 =85x x1111+125+125x x1212+115+115x x1313+20+20 x x2121+60+60 x x2222+50+50 x x2323 +40+40 x x3232+30+30 x x3333四、配料問題LOGO.s.t.s.t. 0.5 x11-0.5 x12 -0.5 x13 0 （

13、甲對原材料1的規(guī)格要求） -0.25x11+0.75x12 -0.25x13 0 （甲對原材料2的規(guī)格要求） 0.75x21-0.25x22 -0.25x23 0 （乙對原材料1的規(guī)格要求） -0.5 x21+0.5 x22 -0.5 x23 0 （乙對原材料2的規(guī)格要求） x11+x21+x31 100 (供應(yīng)量限制） x12+x22+x32 100 (供應(yīng)量限制） x13+x23+x33 60 (供應(yīng)量限制） xij0 ,i = 1,2,3; j = 1,2,3四、配料問題LOGO. 例5 某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的項目投資。已知：項目A ：從第一年到第五年每年年初都

14、可投資，當(dāng)年末能收回本利110%；項目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過30萬元；項目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過80萬元；項目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過100萬元。 五、投資問題LOGO. 據(jù)測定每萬元每次投資的風(fēng)險指數(shù)如下表：據(jù)測定每萬元每次投資的風(fēng)險指數(shù)如下表：項 目 風(fēng) 險 指 數(shù) （ 次 /萬 元 ） A 1 B 3 C 4 D 5 .5 a a）應(yīng)如何確定這些項目的每年投資額，使得第五年年末擁有資）應(yīng)如何確定這些項目的每年投資額

15、，使得第五年年末擁有資金的本利金額為最大？金的本利金額為最大？ b b）應(yīng)如何確定這些項目的每年投資額，使得第五年年末擁有資）應(yīng)如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利在金的本利在330330萬元的基礎(chǔ)上使得其投資總的風(fēng)險系數(shù)為最小？萬元的基礎(chǔ)上使得其投資總的風(fēng)險系數(shù)為最小？五、投資問題LOGO. 解：解：1 1）確定決策變量：連續(xù)投資問題 設(shè) xij ( i = 15，j = 1、2、3、4)表示第 i 年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項目的金額。這樣我們建立如下決策變量： A x11 x21 x31 x41 x51 B x12 x22 x3

16、2 x42 C x33 D x24五、投資問題LOGO. 2 2）約束條件：）約束條件： 第一年：A當(dāng)年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是： x11+ x12 = 200 第二年：B次年末才可收回投資故第二年年初的資金為1.1x11，于是： x21 + x22+ x24 = 1.1x11 第三年：年初的資金為1.1x21+1.25x12，于是 ： x31 + x32+ x33 = 1.1x21+ 1.25x12 第四年：年初的資金為1.1x31+1.25x22，于是： x41 + x42 = 1.1x31+ 1.25x22 第五年：年初的資金為1.1x41+1.25x32，于是

17、： x51 = 1.1x41+ 1.25x32 B、C、D的投資限制： xi2 30 ( i=1，2，3，4 )，x33 80，x24 100五、投資問題LOGO.a)Max z=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+ x12 = 200 x21 + x22+ x24 = 1.1x11 x31 + x32+ x33 = 1.1x21+ 1.25x12 x41 + x42 = 1.1x31+ 1.25x22 x51 = 1.1x41+ 1.25x32 xi2 30 ( i =1、2、3、4 )， x33 80，x24 100 xij0(i=1,2,3,4,5；

18、j=1,2,3,4）3 3）目標(biāo)函數(shù)及模型：）目標(biāo)函數(shù)及模型：五、投資問題LOGO.b) b) MinMin f f = = （x x1111+ +x x2121+ +x x3131+ +x x4141+ +x x5151)+ )+ 3( 3(x x1212+ +x x2222+ +x x3232+ +x x4242)+4)+4x x3333+5.5+5.5x x24 24 s.t.s.t. x x1111+ + x x12 12 = 200= 200 x x21 21 + + x x2222+ + x x2424 =1.1 =1.1x x1111 x x31 31 + + x x3232+ + x x3333 =1.1 =1.1x x2121+ 1.25+ 1.25x x1212 x x41 41 + + x x4242 =1.1 =1.1x x3131+ 1.25+ 1.25x x2222 x x51 51 =1.1=1.1x x4141+ 1.25+ 1.25x x3232 x xi i2 2 30 ( 30 ( i i =1 =1、2 2、3 3、4 )4 )