第4章線(xiàn)性規(guī)劃在工商管理中的應(yīng)用-newppt課件

1、管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)第四章第四章 線(xiàn)性規(guī)劃在工商管理中的運(yùn)用線(xiàn)性規(guī)劃在工商管理中的運(yùn)用1 人力資源分配的問(wèn)題2 消費(fèi)方案的問(wèn)題3 套裁下料問(wèn)題4 配料問(wèn)題5 投資問(wèn)題1管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1 1人力資源分配的問(wèn)題人力資源分配的問(wèn)題 2 例1某晝夜效力的公交線(xiàn)路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下： 設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開(kāi)場(chǎng)時(shí)上班，并延續(xù)任務(wù)八小時(shí)，問(wèn)該公交線(xiàn)路怎樣安排司機(jī)和乘務(wù)人員，既能滿(mǎn)足任務(wù)需求，又配備最少司機(jī)和乘務(wù)人員?管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1 1人力資源分配的問(wèn)題人力資源分配的問(wèn)題 解：設(shè) xi 表示第i班次時(shí)開(kāi)場(chǎng)上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立

2、如下的數(shù)學(xué)模型。 目的函數(shù)： Min x1 + x2 + x3 + x4 + x5 + x6 約束條件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 03管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1 1人力資源分配的問(wèn)題人力資源分配的問(wèn)題 例2一家中型的百貨商場(chǎng)，它對(duì)售貨員的需求經(jīng)過(guò)統(tǒng)計(jì)分析如下表所示。為了保證售貨人員充分休憩，售貨人員每周任務(wù)5天，休憩兩天，并要求休憩的兩天是延續(xù)的。問(wèn)應(yīng)該如何安排售貨人員的作息，既滿(mǎn)足任務(wù)需求，又使配備的售貨人員的人數(shù)最少？4時(shí)間所需售貨員人

3、數(shù)星期日28星期一15星期二24星期三25星期四19星期五31星期六28管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1 1人力資源分配的問(wèn)題人力資源分配的問(wèn)題 解：設(shè) xi ( i = 1,2,7)表示星期一至日開(kāi)場(chǎng)休憩的人數(shù),這樣我們建立如下的數(shù)學(xué)模型。 目的函數(shù)： Min x1 + x2 + x3 + x4 + x5 + x6 + x7 約束條件：s.t. x1 + x2 + x3 + x4 + x5 28 x2 + x3 + x4 + x5 + x6 15 x3 + x4 + x5 + x6 + x7 24 x4 + x5 + x6 + x7 + x1 25 x5 + x6 + x7 + x1 + x2

4、 19 x6 + x7 + x1 + x2 + x3 31 x7 + x1 + x2 + x3 + x4 28 x1,x2,x3,x4,x5,x6,x7 05管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1 1人力資源分配的問(wèn)題人力資源分配的問(wèn)題往往一些效力行業(yè)的企業(yè)對(duì)人力資源的需求一周內(nèi)像例2所描畫(huà)的那樣變化，而每天的個(gè)時(shí)間段的需求又像例1往往描畫(huà)的那樣變化，在保證任務(wù)人員每天任務(wù)8h，每周休憩兩天的情況下，如何安排能使人員的編制最小呢？6管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2消費(fèi)方案的問(wèn)題消費(fèi)方案的問(wèn)題 例3某公司面臨一個(gè)是外包協(xié)作還是自行消費(fèi)的問(wèn)題。該公司消費(fèi)甲、乙、丙三種產(chǎn)品，都需求經(jīng)過(guò)鑄造、機(jī)加工和裝配三

5、個(gè)車(chē)間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行消費(fèi)，但產(chǎn)品丙必需本廠鑄造才干保證質(zhì)量。數(shù)據(jù)如表。問(wèn)：公司為了獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品各消費(fèi)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？7甲乙丙資 源 限 制鑄 造 工 時(shí) (小 時(shí) /件 )51078000機(jī) 加 工 工 時(shí) (小 時(shí) /件 )64812000裝 配 工 時(shí) (小 時(shí) /件 )32210000自 產(chǎn) 鑄 件 成 本 (元 /件 )354外 協(xié) 鑄 件 成 本 (元 /件 )56-機(jī) 加 工 成 本 (元 /件 )213裝 配 成 本 (元 /件 )322產(chǎn) 品 售 價(jià) (元 /件 )23181

6、6管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2消費(fèi)方案的問(wèn)題消費(fèi)方案的問(wèn)題 解：設(shè) x1,x2,x3 分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4,x5 分別為由外協(xié)鑄造再由本公司加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。 求 xi 的利潤(rùn)：利潤(rùn) = 售價(jià) - 各本錢(qián)之和 產(chǎn)品甲全部自制的利潤(rùn) =23-(3+2+3)=15 元 產(chǎn)品甲鑄造外協(xié)，其他自制的利潤(rùn) =23-(5+2+3)=13 元 產(chǎn)品乙全部自制的利潤(rùn) =18-(5+1+2)=10 元 產(chǎn)品乙鑄造外協(xié)，其他自制的利潤(rùn) =18-(6+1+2)=9 元 產(chǎn)品丙的利潤(rùn) =16-(4+3+2)=7 元 可得到 xi i = 1,2,3,4,5

7、 的利潤(rùn)分別為 15元、10元、7元、13元、9元。8管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2消費(fèi)方案的問(wèn)題消費(fèi)方案的問(wèn)題經(jīng)過(guò)以上分析,可建立如下的數(shù)學(xué)模型:目的函數(shù)： Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 約束條件： 5x1 + 10 x2 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 09管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2消費(fèi)方案的問(wèn)題消費(fèi)方案的問(wèn)題例4永久機(jī)械廠消費(fèi)、三種產(chǎn)品，均要經(jīng)過(guò)A、B兩 道工序加工。設(shè)有兩種規(guī)格的

8、設(shè)備A1、A2能完成 A 工序；有三種規(guī)格的設(shè)備B1、B2、B3能完成 B 工序?？稍贏、B的任何規(guī)格的設(shè)備上加工； 可在恣意規(guī)格的A設(shè)備上加工，但對(duì)B工序，只能在B1設(shè)備上加工；只能在A2與B2設(shè)備上加工。數(shù)據(jù)如表。問(wèn)：為使該廠獲得最大利潤(rùn)，應(yīng)如何制定產(chǎn)品加工方案？10產(chǎn)品單件工時(shí) 設(shè)備 設(shè)備的 有效臺(tái)時(shí) 滿(mǎn)負(fù)荷時(shí)的設(shè)備費(fèi)用 A1 5 10 6000 300 A2 7 9 12 10000 321 B1 6 8 4000 250 B2 4 11 7000 783 B3 7 4000 200 原料（元/件） 0.25 0.35 0.50 售價(jià)（元/件） 1.25 2.00 2.80 管管 理理

9、 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2消費(fèi)方案的問(wèn)題消費(fèi)方案的問(wèn)題解：設(shè) xijk 表示第 i 種產(chǎn)品，在第 j 種工序上的第 k 種設(shè)備上加工的數(shù)量。建立如下的數(shù)學(xué)模型: s.t. 5x111 + 10 x211 6000 設(shè)備 A1 7x112 + 9x212 + 12x312 10000 設(shè)備 A2 6x121 + 8x221 4000 設(shè)備 B1 4x122 + 11x322 7000 設(shè)備 B2 7x123 4000 設(shè)備 B3 x111+ x112- x121- x122- x123 = 0 產(chǎn)品在A、B工序加工的數(shù)量相等 x211+ x212- x221 = 0 產(chǎn)品在A、B工序加工的數(shù)量相等

10、 x312 - x322 = 0 產(chǎn)品在A、B工序加工的數(shù)量相等 xijk 0 , i = 1,2,3; j = 1,2; k = 1,2,311管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2消費(fèi)方案的問(wèn)題消費(fèi)方案的問(wèn)題目的函數(shù)為計(jì)算利潤(rùn)最大化，利潤(rùn)的計(jì)算公式為： 利潤(rùn) = 銷(xiāo)售單價(jià) - 原料單價(jià)* 產(chǎn)品件數(shù)之和 -每臺(tái)時(shí)的設(shè)備費(fèi)用*設(shè)備實(shí)踐運(yùn)用的總臺(tái)時(shí)數(shù)之和。這樣得到目的函數(shù)： Max(1.25-0.25)(x111+x112)+(2-0.35)(x211+x212)+(2.80-0.5)x312 300/6000(5x111+10 x211)-321/10000(7x112+9x212+12x312)

11、- 250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).經(jīng)整理可得： Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4474x122-1.2304x322-0.35x12312管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)3 3套裁下料問(wèn)題套裁下料問(wèn)題 13 例5某工廠要做100套鋼架，每套用長(zhǎng)為2.9 m,2.1 m,1.5 m的圓鋼各一根。知原料每根長(zhǎng)7.4 m，問(wèn)：應(yīng)如何下料，可使所用原料最?。?解： 共可設(shè)計(jì)以下8 種下料方案，見(jiàn)下表

12、 設(shè) x1,x2,x3,x4,x5,x6 ,x7 ,x8分別為上面 8 種方案下料的原資料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。 目的函數(shù)： Min x1 + x2 + x3 + x4+ x5 + x6 + x7 + x8 約束條件： s.t. x1 + 2x2 + x4 + x6 100 2x3+2x4 + x5+ x6 +3x7 100 3x1+ x2 +2x3 +3x4 +x6 + 4x8 100 x1,x2,x3,x4,x5,x6 ,x7 ,x8 0管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)3套裁下料問(wèn)題套裁下料問(wèn)題假設(shè)能夠的下料方案太多，可以先設(shè)計(jì)出較好的幾個(gè)下料方案。較好，首先要求每個(gè)方案下料后的料

13、頭較短；其次方案總體能裁下一切各種規(guī)格的圓鋼，且不同方案有著不同的各種所需圓鋼的比。這樣套裁即使不是最優(yōu)解，也是次優(yōu)解，也能滿(mǎn)足要求并到達(dá)省料目的。如我們用前5種下料方案進(jìn)展求解，也可得到上述最優(yōu)解。14管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)3 3套裁下料問(wèn)題套裁下料問(wèn)題用“管理運(yùn)籌學(xué)軟件計(jì)算得出最優(yōu)下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。 即 x1=30; x2=10； x3=0； x4=50； x5=0； x6= x7= x8=0 只需90根原資料就可制造出100套鋼架。留意：在建立此類(lèi)型數(shù)學(xué)模型時(shí)，約束條件用大于等于號(hào)比用等于號(hào)要好。由于有時(shí)在套用一些下料方案時(shí)能夠會(huì)

14、多出一根某種規(guī)格的圓鋼，但它能夠是最優(yōu)方案。假設(shè)用等于號(hào)，這一方案就不是可行解了。15管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4配料問(wèn)題配料問(wèn)題 16 例6某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如右表。問(wèn)：該廠應(yīng)如何安排消費(fèi)，使利潤(rùn)收入為最大？產(chǎn)品名稱(chēng)規(guī)格要求單價(jià)（元/kg）甲原材料1不少于50%，原材料2不超過(guò)25%50乙原材料1不少于25%，原材料2不超過(guò)50%35丙不限25原材料名稱(chēng)每天最多供應(yīng)量單價(jià)（元/kg）11006521002536035 解：設(shè) xij 表示第 i 種甲、乙、丙產(chǎn)品中原料 j 的含量。這樣我們建立數(shù)學(xué)模型時(shí)，要思索： 對(duì)于甲： x11，

15、x12，x13； 對(duì)于乙： x21，x22，x23； 對(duì)于丙： x31，x32，x33； 對(duì)于原料1： x11，x21，x31； 對(duì)于原料2： x12，x22，x32； 對(duì)于原料3： x13，x23，x33； 目的函數(shù)： 利潤(rùn)最大，利潤(rùn) = 收入 - 原料支出 約束條件： 規(guī)格要求 4 個(gè)； 供應(yīng)量限制 3 個(gè)。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4配料問(wèn)題配料問(wèn)題利潤(rùn)=總收入-總本錢(qián)=甲乙丙三種產(chǎn)品的銷(xiāo)售單價(jià)*產(chǎn)品數(shù)量-甲乙丙運(yùn)用的原料單價(jià)*原料數(shù)量，故有目的函數(shù)Max 50 x11+x12+x13+35x21+x22+x23+25x31+x32+x33-65x11+x21+x31-25x12+

16、x22+x32-35x13+x23+x33= -15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 約束條件： 從第1個(gè)表中有： x110.5(x11+x12+x13) x120.25(x11+x12+x13) x210.25(x21+x22+x23) x220.5(x21+x22+x23)17管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4配料問(wèn)題配料問(wèn)題 從第2個(gè)表中，消費(fèi)甲乙丙的原資料不能超越原資料的供應(yīng)限額，故有 x11+x21+x31100 x12+x22+x32100 x13+x23+x3360 經(jīng)過(guò)整理，得到以下模型：18管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4

17、4配料問(wèn)題配料問(wèn)題例6續(xù)目的函數(shù)：Max z = -15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 約束條件： s.t. 0.5 x11-0.5 x12 -0.5 x13 0 原資料1不少于50% -0.25x11+0.75x12 -0.25x13 0 原資料2不超越25% 0.75x21-0.25x22 -0.25x23 0 原資料1不少于25% -0.5 x21+0.5 x22 -0.5 x23 0 原資料2不超越50% x11+ x21 + x31 100 (供應(yīng)量限制 x12+ x22 + x32 100 (供應(yīng)量限制 x13+ x23 +

18、x33 60 (供應(yīng)量限制 xij 0 , (i = 1,2,3; j = 1,2,3)19管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4配料問(wèn)題配料問(wèn)題例6續(xù) 此線(xiàn)性規(guī)劃的計(jì)算機(jī)解為x11 = 100，x12 = 50，x13 = 50，其他的xij = 0，也就是說(shuō)每天只消費(fèi)產(chǎn)品甲200kg，分別需求用第1種原料100kg，第2種原料50kg，第3種原料50kg。20管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4配料問(wèn)題配料問(wèn)題 標(biāo)準(zhǔn)汽油標(biāo)準(zhǔn)汽油辛烷數(shù)辛烷數(shù)蒸汽壓力蒸汽壓力(g/cm2)庫(kù)存量庫(kù)存量(L)1107.57.1110-2380000293.011.38 10-2265200387.05.6910-24

19、081004108.028.45 10-2130100飛機(jī)汽油飛機(jī)汽油辛烷數(shù)辛烷數(shù)蒸汽壓力蒸汽壓力(g/cm2)產(chǎn)量需求產(chǎn)量需求1不小于不小于91不大于不大于9.96 10-2越多越好越多越好2不小于不小于100不大于不大于9.96 10-2不少于不少于25000021例7.汽油混合問(wèn)題。一種汽油的特性可用兩種目的描畫(huà)，用“辛烷數(shù)來(lái)定量描畫(huà)其點(diǎn)火特性，用“蒸汽壓力來(lái)定量描畫(huà)其揮發(fā)性。某煉油廠有1、2、3、4的4種規(guī)范汽油，其特性和庫(kù)存量列于表4-8中，將這四種規(guī)范汽油混合，可得到標(biāo)號(hào)為1，2的2種飛機(jī)汽油，這兩種汽油的性能目的及產(chǎn)量需求列于表4-9中。問(wèn)應(yīng)如何根據(jù)庫(kù)存情況適量混合各種規(guī)范汽油，

20、既滿(mǎn)足飛機(jī)汽油的性能目的，又使2號(hào)汽油滿(mǎn)足需求，并使得1號(hào)汽油產(chǎn)量最高？表表4-8表表4-9管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4配料問(wèn)題配料問(wèn)題 11121314xxxx1121122213231424380000265200408100130100 xxxxxxxx22解：設(shè)xij為飛機(jī)汽油i中所用規(guī)范汽油j的數(shù)量(L)。 目的函數(shù)為飛機(jī)汽油1的總產(chǎn)量： 庫(kù)存量約束為：產(chǎn)量約束為飛機(jī)汽油2的產(chǎn)量：21222324250000 xxxx由物理中的分壓定律， 可得有關(guān)蒸汽壓力的約束條件：1njjjPVp v11121314212223242.851.424.2718.4902.851.424.27

21、18.490 xxxxxxxx同樣可得有關(guān)辛烷數(shù)的約束條件為：111213142122232416.52.04.017.007.57.013.08.00 xxxxxxxx管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4配料問(wèn)題配料問(wèn)題 23綜上所述，得該問(wèn)題的數(shù)學(xué)模型為：111213142122232411211222132314241112131421222324111213142122max2500003800002652004081001301002.851.424.2718.4902.851.424.2718.49016.5241707.57xxxxxxxxxxxxxxxxxxxxxxxxxxxxx

22、x232413800,(1,2;1,2,3,4)ijxxxij管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)4 4配料問(wèn)題配料問(wèn)題 24由管理運(yùn)籌學(xué)軟件求解得：111213141112131421222324max()933399.938261966.078265200315672.21990561.688118033.906092427.75839538.309xxxxxxxxxxxx管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)5 5投資問(wèn)題投資問(wèn)題 25例8某部門(mén)現(xiàn)有資金200萬(wàn)元，今后五年內(nèi)思索給以下的工程投資。知：項(xiàng)目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；工程B：從第一年到第四年每年年初都可投

23、資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超越30萬(wàn)元；工程C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超越80萬(wàn)元；工程D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超越100萬(wàn)元。 據(jù)測(cè)定每萬(wàn)元每次投資的風(fēng)險(xiǎn)指數(shù)如右表：?jiǎn)枺?應(yīng)如何確定這些工程每年的投資額，使得第五年年末擁有資金的本利金額為最大？2應(yīng)如何確定這些工程每年的投資額，使得第五年年末擁有資金的本利在330萬(wàn)元的根底上使得其投資的總的風(fēng)險(xiǎn)系數(shù)為最?。宽?xiàng)目風(fēng)險(xiǎn)指數(shù)（次/萬(wàn)元）A1B3C4D5.5 解：1確定決策變量：延續(xù)投資問(wèn)題 設(shè) xij ( i = 15，j =

24、14)表示第 i 年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)工程的金額。這樣我們建立如下的決策變量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)5 5投資問(wèn)題投資問(wèn)題2 2約束條件：約束條件：第一年：第一年：A A當(dāng)年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是當(dāng)年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是 x11+ x11+ x12 = 200 x12 = 200；第二年：第二年：B B次年末才可收回投資，故第二年年初有資金次年末才可收回投資，故第二年年初有資金1.1

25、x111.1 x11，于是，于是 x21 + x21 + x22+ x24 = 1.1x11x22+ x24 = 1.1x11；第三年：年初有資金第三年：年初有資金 1.1x21+ 1.25x12 1.1x21+ 1.25x12，于是，于是 x31 + x32+ x33 = 1.1x21+ x31 + x32+ x33 = 1.1x21+ 1.25x121.25x12；第四年：年初有資金第四年：年初有資金 1.1x31+ 1.25x22 1.1x31+ 1.25x22，于是，于是 x41 + x42 = 1.1x31+ 1.25x22 x41 + x42 = 1.1x31+ 1.25x22；第

26、五年：年初有資金第五年：年初有資金 1.1x41+ 1.25x32 1.1x41+ 1.25x32，于是，于是 x51 = 1.1x41+ 1.25x32 x51 = 1.1x41+ 1.25x32； B B、C C、D D的投資限制：的投資限制： xi2 30 ( i =1 xi2 30 ( i =1、2 2、3 3、4 )4 )，x33 80 x33 80，x24 x24 100 100 3 3目的函數(shù)及模型：目的函數(shù)及模型：a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1

27、.55x24 s.t. x11+ x12 = 200 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12 x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22 x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32 x51 = 1.1x41+ 1.25x32； xi2 30 ( i =1 xi2 30 ( i =1、2 2、3 3、4 )4 )，x33 80 x33 80，x24 100 x24 100 xij 0 ( i = 1 xij 0 ( i = 1、2 2