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

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

人力資源分配的問題

2

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

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

人力資源分配的問題

解：設(shè)xi

表示第i班次時開始上班的司機和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學模型。目標函數(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頁/共27頁§1

人力資源分配的問題

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

人力資源分配的問題

解：設(shè)xi(i=1,2,…,7)表示星期一至日開始休息的人數(shù),這樣我們建立如下的數(shù)學模型。目標函數(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頁/共27頁§1

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

生產(chǎn)計劃的問題

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

生產(chǎn)計劃的問題

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

分別為由外協(xié)鑄造再由本公司加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。求xi的利潤：利潤=售價-各成本之和產(chǎn)品甲全部自制的利潤=23-(3+2+3)=15元

產(chǎn)品甲鑄造外協(xié)，其余自制的利潤=23-(5+2+3)=13元

產(chǎn)品乙全部自制的利潤=18-(5+1+2)=10元

產(chǎn)品乙鑄造外協(xié)，其余自制的利潤=18-(6+1+2)=9元

產(chǎn)品丙的利潤=16-(4+3+2)=7元

可得到xi

（i=1,2,3,4,5）的利潤分別為15元、10元、7元、13元、9元。8第7頁/共27頁§2

生產(chǎn)計劃的問題通過以上分析,可建立如下的數(shù)學模型:目標函數(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頁/共27頁§2

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

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

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

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頁/共27頁§2

生產(chǎn)計劃的問題目標函數(shù)為計算利潤最大化，利潤的計算公式為：利潤=[（銷售單價-原料單價）*產(chǎn)品件數(shù)]之和-（每臺時的設(shè)備費用*設(shè)備實際使用的總臺時數(shù)）之和。這樣得到目標函數(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頁/共27頁§3

套裁下料問題

13

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

設(shè)x1,x2,x3,x4,x5,x6,x7,x8分別為上面8種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學模型。目標函數(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頁/共27頁§3

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

套裁下料問題用“管理運籌學”軟件計算得出最優(yōu)下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。即x1=30;x2=10；

x3=0；

x4=50；

x5=0；x6=x7=x8=0只需90根原材料就可制造出100套鋼架。注意：在建立此類型數(shù)學模型時，約束條件用大于等于號比用等于號要好。因為有時在套用一些下料方案時可能會多出一根某種規(guī)格的圓鋼，但它可能是最優(yōu)方案。如果用等于號，這一方案就不是可行解了。15第14頁/共27頁§4

配料問題

16

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

解：設(shè)xij

表示第i種（甲、乙、丙）產(chǎn)品中原料j的含量。這樣我們建立數(shù)學模型時，要考慮：對于甲：x11，x12，x13；對于乙：x21，x22，x23；對于丙：x31，x32，x33；對于原料1：x11，x21，x31；對于原料2：x12，x22，x32；對于原料3：x13，x23，x33；目標函數(shù)：利潤最大，利潤=收入-原料支出約束條件：規(guī)格要求4個；供應(yīng)量限制3個。第15頁/共27頁§4

配料問題利潤=總收入-總成本=甲乙丙三種產(chǎn)品的銷售單價*產(chǎn)品數(shù)量-甲乙丙使用的原料單價*原料數(shù)量，故有目標函數(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個表中有：

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頁/共27頁§4

配料問題

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

x11+x21+x31≤100

x12+x22+x32≤100

x13+x23+x33≤60

通過整理，得到以下模型：18第17頁/共27頁§4

配料問題例6．（續(xù)）目標函數(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不超過25%）

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

-0.5x21+0.5x22-0.5x23≤0（原材料2不超過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頁/共27頁§4

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

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

配料問題

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

配料問題

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

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

配料問題

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

配料問題

24由管理運籌學軟件求解得：第23頁/共27頁§5

投資問題

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

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

Ax11

x21

x31

x41

x51

Bx12

x22

x32

x42Cx33

Dx24第24頁/共27頁§5

投資問題2）約束條件：第一年：A當年末可收回投資，故第一年年初應(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）目標函數(shù)及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200

x21+x22+x24=1.1x11