第4章線性規(guī)劃在工商管理中的應(yīng)用-new

會(huì)計(jì)學(xué)1第4章線性規(guī)劃在工商管理中的應(yīng)用-new§1

人力資源分配的問(wèn)題

2

例1．某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：

設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開(kāi)始時(shí)上班，并連續(xù)工作八小時(shí)，問(wèn)該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?第1頁(yè)/共27頁(yè)§1

人力資源分配的問(wèn)題

解：設(shè)xi

表示第i班次時(shí)開(kāi)始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+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第2頁(yè)/共27頁(yè)§1

人力資源分配的問(wèn)題

例2．一家中型的百貨商場(chǎng)，它對(duì)售貨員的需求經(jīng)過(guò)統(tǒng)計(jì)分析如下表所示。為了保證售貨人員充分休息，售貨人員每周工作5天，休息兩天，并要求休息的兩天是連續(xù)的。問(wèn)應(yīng)該如何安排售貨人員的作息，既滿足工作需要，又使配備的售貨人員的人數(shù)最少？4第3頁(yè)/共27頁(yè)§1

人力資源分配的問(wèn)題

解：設(shè)xi(i=1,2,…,7)表示星期一至日開(kāi)始休息的人數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+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≥25x5+x6+x7+x1+x2≥19x6+x7+x1+x2+x3≥31

x7+x1+x2+x3+x4≥28

x1,x2,x3,x4,x5,x6,x7≥05第4頁(yè)/共27頁(yè)§1

人力資源分配的問(wèn)題往往一些服務(wù)行業(yè)的企業(yè)對(duì)人力資源的需求一周內(nèi)像例2所描述的那樣變化，而每天的個(gè)時(shí)間段的需求又像例1往往描述的那樣變化，在保證工作人員每天工作8h，每周休息兩天的情況下，如何安排能使人員的編制最小呢？6第5頁(yè)/共27頁(yè)§2

生產(chǎn)計(jì)劃的問(wèn)題

例3．某公司面臨一個(gè)是外包協(xié)作還是自行生產(chǎn)的問(wèn)題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過(guò)鑄造、機(jī)加工和裝配三個(gè)車(chē)間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如表。問(wèn)：公司為了獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？7第6頁(yè)/共27頁(yè)§2

生產(chǎn)計(jì)劃的問(wèn)題

解：設(shè)x1,x2,x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4,x5

分別為由外協(xié)鑄造再由本公司加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。求xi的利潤(rùn)：利潤(rùn)=售價(jià)-各成本之和產(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）的利潤(rùn)分別為15元、10元、7元、13元、9元。8第7頁(yè)/共27頁(yè)§2

生產(chǎn)計(jì)劃的問(wèn)題通過(guò)以上分析,可建立如下的數(shù)學(xué)模型:目標(biāo)函數(shù)：Max15x1+10x2+7x3+13x4+9x5

約束條件：5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥09第8頁(yè)/共27頁(yè)§2

生產(chǎn)計(jì)劃的問(wèn)題例4．永久機(jī)械廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，均要經(jīng)過(guò)A、B兩道工序加工。設(shè)有兩種規(guī)格的設(shè)備A1、A2能完成A工序；有三種規(guī)格的設(shè)備B1、B2、B3能完成B工序。Ⅰ可在A、B的任何規(guī)格的設(shè)備上加工；Ⅱ可在任意規(guī)格的A設(shè)備上加工，但對(duì)B工序，只能在B1設(shè)備上加工；Ⅲ只能在A2與B2設(shè)備上加工。數(shù)據(jù)如表。問(wèn)：為使該廠獲得最大利潤(rùn)，應(yīng)如何制定產(chǎn)品加工方案？10第9頁(yè)/共27頁(yè)§2

生產(chǎn)計(jì)劃的問(wèn)題解：設(shè)xijk

表示第i種產(chǎn)品，在第j種工序上的第k種設(shè)備上加工的數(shù)量。建立如下的數(shù)學(xué)模型:

s.t.5x111+10x211≤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ù)量相等）

x312-x322=0（Ⅲ產(chǎn)品在A、B工序加工的數(shù)量相等）

xijk≥0,i=1,2,3;j=1,2;k=1,2,311第10頁(yè)/共27頁(yè)§2

生產(chǎn)計(jì)劃的問(wèn)題目標(biāo)函數(shù)為計(jì)算利潤(rùn)最大化，利潤(rùn)的計(jì)算公式為：利潤(rùn)=[（銷(xiāo)售單價(jià)-原料單價(jià)）*產(chǎn)品件數(shù)]之和-（每臺(tái)時(shí)的設(shè)備費(fèi)用*設(shè)備實(shí)際使用的總臺(tái)時(shí)數(shù)）之和。這樣得到目標(biāo)函數(shù)：

Max(1.25-0.25)(x111+x112)+(2-0.35)(x211+x212)+(2.80-0.5)x312

–

300/6000(5x111+10x211)-321/10000(7x112+9x212+12x312)-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第11頁(yè)/共27頁(yè)§3

套裁下料問(wèn)題

13

例5．某工廠要做100套鋼架，每套用長(zhǎng)為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長(zhǎng)7.4m，問(wèn)：應(yīng)如何下料，可使所用原料最省？解：共可設(shè)計(jì)下列8種下料方案，見(jiàn)下表

設(shè)x1,x2,x3,x4,x5,x6,x7,x8分別為上面8種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5+x6+x7+x8

約束條件：s.t.x1+2x2+x4+x6≥1002x3+2x4+x5+x6+3x7≥1003x1+x2+2x3+3x4+x6+4x8≥100x1,x2,x3,x4,x5,x6,x7,x8≥0第12頁(yè)/共27頁(yè)§3

套裁下料問(wèn)題若可能的下料方案太多，可以先設(shè)計(jì)出較好的幾個(gè)下料方案。較好，首先要求每個(gè)方案下料后的料頭較短；其次方案總體能裁下所有各種規(guī)格的圓鋼，且不同方案有著不同的各種所需圓鋼的比。這樣套裁即使不是最優(yōu)解，也是次優(yōu)解，也能滿足要求并達(dá)到省料目的。如我們用前5種下料方案進(jìn)行求解，也可得到上述最優(yōu)解。14第13頁(yè)/共27頁(yè)§3

套裁下料問(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)要好。因?yàn)橛袝r(shí)在套用一些下料方案時(shí)可能會(huì)多出一根某種規(guī)格的圓鋼，但它可能是最優(yōu)方案。如果用等于號(hào)，這一方案就不是可行解了。15第14頁(yè)/共27頁(yè)§4

配料問(wèn)題

16

例6．某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如右表。問(wèn)：該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？

解：設(shè)xij

表示第i種（甲、乙、丙）產(chǎn)品中原料j的含量。這樣我們建立數(shù)學(xué)模型時(shí)，要考慮：對(duì)于甲：x11，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；目標(biāo)函數(shù)：利潤(rùn)最大，利潤(rùn)=收入-原料支出約束條件：規(guī)格要求4個(gè)；供應(yīng)量限制3個(gè)。第15頁(yè)/共27頁(yè)§4

配料問(wèn)題利潤(rùn)=總收入-總成本=甲乙丙三種產(chǎn)品的銷(xiāo)售單價(jià)*產(chǎn)品數(shù)量-甲乙丙使用的原料單價(jià)*原料數(shù)量，故有目標(biāo)函數(shù)Max50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

約束條件：從第1個(gè)表中有：

x11≥0.5(x11+x12+x13)x12≤0.25(x11+x12+x13)x21≥0.25(x21+x22+x23)x22≤0.5(x21+x22+x23)17第16頁(yè)/共27頁(yè)§4

配料問(wèn)題

從第2個(gè)表中，生產(chǎn)甲乙丙的原材料不能超過(guò)原材料的供應(yīng)限額，故有

x11+x21+x31≤100

x12+x22+x32≤100

x13+x23+x33≤60

通過(guò)整理，得到以下模型：18第17頁(yè)/共27頁(yè)§4

配料問(wèn)題例6．（續(xù)）目標(biāo)函數(shù)：Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

約束條件：

s.t.0.5x11-0.5x12-0.5x13≥0（原材料1不少于50%）

-0.25x11+0.75x12-0.25x13≤0（原材料2不超過(guò)25%）

0.75x21-0.25x22-0.25x23≥0（原材料1不少于25%）

-0.5x21+0.5x22-0.5x23≤0（原材料2不超過(guò)50%）

x11+x21+x31≤100(供應(yīng)量限制）

x12+x22+x32≤100(供應(yīng)量限制）

x13+x23+x33≤60(供應(yīng)量限制）

xij≥0,(i=1,2,3;j=1,2,3)19第18頁(yè)/共27頁(yè)§4

配料問(wèn)題例6．（續(xù)）

此線性規(guī)劃的計(jì)算機(jī)解為x11=100，x12=50，x13=50，其余的xij=0，也就是說(shuō)每天只生產(chǎn)產(chǎn)品甲200kg，分別需要用第1種原料100kg，第2種原料50kg，第3種原料50kg。20第19頁(yè)/共27頁(yè)§4

配料問(wèn)題

標(biāo)準(zhǔn)汽油辛烷數(shù)蒸汽壓力(g/cm2)庫(kù)存量(L)1107.57.11×10-2380000293.011.38×10-2265200387.05.69×10-24081004108.028.45×10-2130100飛機(jī)汽油辛烷數(shù)蒸汽壓力(g/cm2)產(chǎn)量需求1不小于91不大于9.96×10-2越多越好2不小于100不大于9.96×10-2不少于25000021例7.汽油混合問(wèn)題。一種汽油的特性可用兩種指標(biāo)描述，用“辛烷數(shù)”來(lái)定量描述其點(diǎn)火特性，用“蒸汽壓力”來(lái)定量描述其揮發(fā)性。某煉油廠有1、2、3、4的4種標(biāo)準(zhǔn)汽油，其特性和庫(kù)存量列于表4-8中，將這四種標(biāo)準(zhǔn)汽油混合，可得到標(biāo)號(hào)為1，2的2種飛機(jī)汽油，這兩種汽油的性能指標(biāo)及產(chǎn)量需求列于表4-9中。問(wèn)應(yīng)如何根據(jù)庫(kù)存情況適量混合各種標(biāo)準(zhǔn)汽油，既滿足飛機(jī)汽油的性能指標(biāo)，又使2號(hào)汽油滿足需求，并使得1號(hào)汽油產(chǎn)量最高？表4---8表4---9第20頁(yè)/共27頁(yè)§4

配料問(wèn)題

22解：設(shè)xij為飛機(jī)汽油i中所用標(biāo)準(zhǔn)汽油j的數(shù)量(L)。目標(biāo)函數(shù)為飛機(jī)汽油1的總產(chǎn)量：

庫(kù)存量約束為：產(chǎn)量約束為飛機(jī)汽油2的產(chǎn)量：由物理中的分壓定律，可得有關(guān)蒸汽壓力的約束條件：同樣可得有關(guān)辛烷數(shù)的約束條件為：第21頁(yè)/共27頁(yè)§4

配料問(wèn)題

23綜上所述，得該問(wèn)題的數(shù)學(xué)模型為：第22頁(yè)/共27頁(yè)§4

配料問(wèn)題

24由管理運(yùn)籌學(xué)軟件求解得：第23頁(yè)/共27頁(yè)§5

投資問(wèn)題

25例8．某部門(mén)現(xiàn)有資金200萬(wàn)元，今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；項(xiàng)目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過(guò)30萬(wàn)元；項(xiàng)目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過(guò)80萬(wàn)元；項(xiàng)目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過(guò)100萬(wàn)元。據(jù)測(cè)定每萬(wàn)元每次投資的風(fēng)險(xiǎn)指數(shù)如右表：?jiǎn)枺?）應(yīng)如何確定這些項(xiàng)目每年的投資額，使得第五年年末擁有資金的本利金額為最大？2）應(yīng)如何確定這些項(xiàng)目每年的投資額，使得第五年年末擁有資金的本利在330萬(wàn)元的基礎(chǔ)上使得其投資的總的風(fēng)險(xiǎn)系數(shù)為最??？

解：1）確定決策變量：連續(xù)投資問(wèn)題設(shè)xij(i=1～5，j=1～4)表示第i年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項(xiàng)目的金額。這樣我們建立如下的決策變量：

Ax11

x21

x31

x41

x51

Bx12

x22

x32

x42Cx33

Dx24第24頁(yè)/共27頁(yè)§5

投資問(wèn)題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，于是x51=1.1x41+1.25x32；

B、C、D的投資限制：xi2≤30(i=1、2、3、4)，x33≤80，x24≤1003）目標(biāo)函數(shù)及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200

x21+x22+x24=1.1x11