線性規劃實務應用 應用領域(例如): 決定每期最佳產品生產組合 多重期間的生產規劃 行銷管理(如選擇媒體) 財務管理(如選擇投資組合)

Presentation on theme: "線性規劃實務應用 應用領域(例如): 決定每期最佳產品生產組合 多重期間的生產規劃 行銷管理(如選擇媒體) 財務管理(如選擇投資組合)"— Presentation transcript:

1 線性規劃實務應用 應用領域(例如): 決定每期最佳產品生產組合 多重期間的生產規劃 行銷管理(如選擇媒體) 財務管理(如選擇投資組合)
人員排班(人力規劃) 人力調度問題 運輸與轉運問題（物流系統設計） 產品混合問題 最佳切割(裁剪)問題 9-1

2 建構線性規劃模型之步驟 徹底了解問題 以口語方式描述目標方程式與限制式 定義決策變數 以決策變數表示出目標方程式 以決策變數表示出限制式
9-2

3 每單位所需人工時數 部門 A產品 B產品 可利用 總時數 1 0.65 0.95 6500 2 0.45 0.85 6000
單位的利潤分別為$10與$9 9-3

4 最佳產品生產組合(1/2) 題目請見課本p205<最佳產品生產組合> A產品與B產品分別需要生產多少數量，方能使得總利潤為最大？
【解答】 決策變數： XA = A產品生產的數量 XB = B產品生產的數量 9-4

5 最佳產品生產組合(2/2) 模式： Max Z = 10XA + 9XB 總利潤 s.t. 0.65XA + 0.95XB  6500
使用LINDO軟體求得最佳解： XA=5,744，XB=1,795，Z = $73,590 9-5

6 LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 73589.74
1) VARIABLE VALUE REDUCED COST XA XB ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 4) 5) NO. ITERATIONS= RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE XA XB RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE INFINITY INFINITY 9-6

7 1. 工廠的每月產能為2,200單位 2. 單位生產成本分別為$30與$35 3. 單位儲存成本皆為生產成本的1%
4. 每月最低總產量至少要為1,900單位 3月 4月 5月 總需求 AV7型 800 1,000 1,200 3,000 AV9型 900 1,400 3,300 1,700 2,000 2,600 9-7

8 多重期間的生產規劃(1/6) 題目請見課本p206<多重期間的生產規劃> 決策變數定義： Xij = 產品i在j月的產量
Iij = 產品i在j月的存貨 i = 1 為AV7型產品， 2 為AV9型產品 j = 1 為 3月， 2 為 4月， 3 為 5月 目標函數：最小化總成本 = 30X11+30X12+30X13+35X21+35X22+ 35X23+0.3I11+0.3I12+0.3I I21+ 0.35I I23 9-8

9 多重期間的生產規劃(2/6) 存貨平衡方程式： 以變數表示即為， Iij-1 + Xij = Dij + Iij Dij為產品i在j月的需求
上個月的存貨 + 本月產量 = 本月需求 + 本月月底存貨 以變數表示即為， Iij-1 + Xij = Dij + Iij Dij為產品i在j月的需求 9-9

10 多重期間的生產規劃(3/6) 若3月初無存貨，則可得以下的限制式： 0 + X11 = 800 + I11 AV7型產品3月的需求
I11 + X12 = 1,000 + I12 AV7型產品4月的需求 I21 + X22 = 1,000 + I22 AV9型產品4月的需求 I12 + X13 = 1,200 + I13 AV7型產品5月的需求 I22 + X23 = 1,400 + I23 AV9型產品5月的需求 9-10

11 多重期間的生產規劃(4/6) 決策變數必須在限制式的左邊，才能以電腦求解，將以上限制式重新整理，則得：
X11 – I11 = AV7型產品3月的需求 X21 - I21 = AV9型產品3月的需求 I11 + X12 - I12 = 1, AV7型產品4月的需求 I21 + X22 - I22 = 1, AV9型產品4月的需求 I12 + X13 - I13 = 1, AV7型產品5月的需求 I22 + X23 - I23 = 1, AV9型產品5月的需求 9-11

12 多重期間的生產規劃(5/6) 另外，每月最高與最低產量的限制式： X11 + X21 ≦ 2,200 3月的最高產量
X11, X12,…X23, I11, I12,…I23 ≧ 0 非負限制式 9-12

13 多重期間的生產規劃(6/6) 使用LINDO軟體求得最佳解，整理得下表： 9-13

14 刊登在報紙與週刊上的廣告總數至少要有20則。
廣告形式 成本 可傳播人數 最多可刊登次數 電視 $900 10,000 12 電台 $200 2,600 15 報紙 $700 5,500 25 週刊 $400 4,200 10 其他限制: 廣告的總花費不得超過$12,000。 刊登在報紙與週刊上的廣告總數至少要有20則。 9-14

15 行銷上的應用—媒體選擇(1/3) 目標函數：（最大可傳播的人數） 題目請見課本p211<媒體選擇> 【解答】 定義決策變數：
 定義決策變數： X1 = 電視廣播的則數 X2 = 電台廣播的則數 X3 = 報紙廣告的則數 X4 = 週刊廣告的則數 目標函數：（最大可傳播的人數） Max Z= 10000X1+2600X2+5500X3+4200X4 9-15

16 行銷上的應用—媒體選擇(2/3) 受限於： X1 ≦ 12 電視廣告限制 X2 ≦ 15 電台廣告限制 X3 ≦ 25 報紙廣告限制
900X1+200X2+700X3+400X4 ≦ 總預算 X3+X4 ≧ 報紙與週刊廣告限制 X1, X2, X3, X4 ≧ 非負限制式 9-16

17 行銷上的應用—媒體選擇(3/3) 使用LINDO軟體求得最佳解： x2* = 5，x3*=10，x4*=10，Z*=110,000
即，電台廣播5則數， 報紙廣告10則數， 週刊廣告10則數， 可傳播最多的人數為110,000人。 9-17

18 投資於石油股票的額度需小於等於投資於政府債 券的額度。 投資於石油股票及電腦股票的總額度，需小於等 於投資於政府債券及公營事業股票的60%。
投資項目 收益 投資最大額度 政府債券 $130,000 石油股票 ,000 電腦股票 ,000 公營事業股票 ,000 投資於石油股票的額度需小於等於投資於政府債 券的額度。 投資於石油股票及電腦股票的總額度，需小於等 於投資於政府債券及公營事業股票的60%。 總投資額不得超過$200,000。 9-18

19 選擇最佳投資組合(1/3) 題目請見課本p213<選擇投資最佳組合> 決策變數： X1 = 投資於政府債券的額度(元)
目標函數： 最大化 總收益 =0.045X X X X4 9-19

20 選擇最佳投資組合(2/3) 受限於： X1 ≦ 130,000 X2 ≦ 100,000 X3 ≦ 100,000 X4 ≦ 120,000
9-20

21 選擇最佳投資組合(3/3) X2 ≦ X1 必須轉成 - X1 + X2 ≦ 0 X2 + X3 ≦ 0.6(X1+X4)
求得最佳解： X1 = 0，為投資於政府債券的額度(元) X2 = 0，為投資於石油股票的額度(元) X3 = 75,000，為投資於電腦股票的額度(元) X4=125,000，為投資於公營事業股票的額度(元) 而總收益為 $12,875。 9-21

22 人力規劃問題(1/4) 題目請見課本p215<人力規劃問題> 目標函數為僱用的接線生人數達到最少受限於： 每一位接線生執勤8小時
早上8:00到中午12:00工作的接線生至少23人 中午12:00到下午4:00工作的接線生至少18人 下午4:00到晚上8:00工作的接線生至少32人 晚上8:00到凌晨12:00工作的接線生至少16人 凌晨12:00到凌晨4:00工作的接線生至少8人 凌晨4:00到早上8:00工作的接線生至少10人 每一位接線生執勤8小時 9-22

23 人力規劃問題(2/4) 考慮每一班的工作人數，決策變數定義： X1 = 第一班(8:00~16:00)工作的接線生人數
9-23

24 人力規劃問題(3/4) 最少接線生人數 = X1 + X2 + X3 + X4 + X5 + X6 受限於： X1 + X6 ≧ 23
9-24

25 人力規劃問題(4/4) 使用LINDO軟體求得最佳解： X1=18，第一班(8:00~16:00)工作的接線生人數
僱用員工總數 Z = 63 (人) 9-25

26 每單位所需人工時數 部門 A產品 B產品 可利 用總時數 1 0.65 0.95 6500 2 0.45 0.85 6000
單位的利潤分別為$10與$9 9-26

27 部門間之人力轉換 轉入部門 轉出部門 1 2 3 4 可轉換上限 1 -- yes yes -- 400
轉出部門 可轉換上限 yes yes yes yes yes yes yes 9-27

28 人力調度問題(1/3) 題目請見課本p217<人力調度問題> 決策變數： X1 = A產品生產的數量 X2 = B產品生產的數量
Hj = 部門j配置的人力時數， j = 1, 2, 3, 4 Tij = 從部門i轉至部門j的人力時數  人力平衡方程式： （Hj=部門j現有人數）+（轉入部門j的人數）-（從部門j轉出的人數） 9-28

29 人力調度問題(2/3) 目標函數： 最大化 總利潤 Z = 10X1 + 9X2 受限於： 0.65X1 + 0.95X2 ≦ H1
H1 = T41 – (T12 + T13) H2 = (T12 + T42) – (T23 + T24) H3 = (T13 + T23) – T34 H4 = (T24 + T34) – (T41 + T42) 9-29

30 人力調度問題(3/3) T12 + T13 ≦ 400 T23 + T24 ≦ 800 T34 ≦ 100 T41 + T42 ≦ 200
X1, X2 ≧ 0 最佳解：X1=6825，X2=1751，Z* = $84,011、B1=6100，B2=5200，B3=8051，B4=1549， T13=400，T23=651，T24=149， 增加利潤 = $84,011 - $73,590 = $10,421 增加百分率 = $10,421/ $73,590 = 14.16% 9-30

31 9-31

32 9-32

33 運輸問題(1/3) 決策變數定義： 題目請見課本p224<運輸問題> X11 = 從德州廠運送至佛羅里達配銷點的數量
9-33

34 運輸問題(2/3) 最小化運輸成本 6X11+2X12+5X13+3X21+8X22+4X23+7X31+6X32+7X33 受限於：
9-34

35 運輸問題(3/3) 求得最佳解： 總運輸成本 Z = $1890 X12=100，從德州廠運送至德州配銷點的數量
9-35

36 9-36

37 物流系統設計(1/3) 題目請見課本p226<物流系統設計> 決策變數
Xij = 由產製來源i (= 1, 2, 3, 4, 5)至需求地點j (=1, 2, 3)的配送數量 Yk = 1 若產製來源k (=3, 4, 5)處將設廠；否則為0 模式： Min Z = 5X11+7X12+8X13+10X21+8X22+6X23+9X31+4X32+3X33+12X41+6X42+2X43+4X51+10X52+11X Y Y Y5 9-37

38 物流系統設計(2/3) s.t. X11 + X12 + X13  2500 從San Diego工廠送出 的量不得超過其產能
X21 + X22 + X23  從Houston工廠送出的 量不得超過其產能 X31 + X32 + X33  10000Y3 若在Tulsa有設廠則送出 的量不得超過其產能 X41 + X42 + X43  10000Y4 若在St. Louis有設廠則 送出量不得超過其產能 X51 + X52 + X53  10000Y5 若在Portland有設廠則 送出量不得超過其產能 9-38

39 物流系統設計(3/3) X11 + X21 + X31 + X41 + X51 = 3000 X12 + X22 + X32 + X42 + X52 = 8000 X13 + X23 + X33 + X43 + X53 = 9000 Xij  0  i, j 非負限制式 Yk = 0, 1  k 0, 1整數限制式 最佳解：Y3=Y4=1, X11= 2,500, X31= 500, X32= 8,000, X43= 9,000目標函數值：Z = 617,000 9-39

40 泰山化學公司生產三種化學溶劑—A級、B級與C級，這三種溶劑都是由原油1與原油2混合而成。
A級溶劑至少要有42%的成份P，B級溶劑至少要有48%，C級溶劑至少要有52% 公司至少必須生產12,000加侖的A級溶劑，至少20,000加侖的B級溶劑，至少15,000加侖的C級溶劑 9-40

41 混合問題(1/2) 題目請見課本p230<混合問題> 決策變數：
Xij = 用於i(=A, B, C)級溶劑的原油j(=1, 2)數量 模式： Min Z =0.52XA1+0.52XB1+0.52XC1+0.45XA2+0.45XB2+0.45XC2 s.t. 0.60XA1+0.41XA2  0.42(XA1+XA2) 0.60XB1+0.41XB2  0.48(XB1+XB2) 0.60XC1+0.41XC2  0.52(XC1+XC2) 9-41

42 混合問題(2/2) XA1+XA2  12000 XB1+XB2  20000 XC1+XC2  15000
Xij  0  i, j 目標函數值：Z = 。最佳解：XA1= ，XB1= ，XC1= ，XA2= ，XB2= ，XC2= 9-42

43 吾人欲以最少的標準板數來切成上表A, B, C三種規格所需的數量，請問最少需要幾塊標準板，以及該如何來切割
標準板規格：150 x 225 x 0.2 cm 吾人欲以最少的標準板數來切成上表A, B, C三種規格所需的數量，請問最少需要幾塊標準板，以及該如何來切割 9-43

44 9-44

45 最佳切割問題(1/2) 題目請見課本p232<最佳切割問題> 下頁是其切割四種方式 變數定義： 目標函數：最小化所需的總板數
X1 = 裁剪方案一所需要標準板的個數 X2 = 裁剪方案二所需要標準板的個數 X3 = 裁剪方案三所需要標準板的個數 X4 = 裁剪方案四所需要標準板的個數 目標函數：最小化所需的總板數 Z = X1 + X2 + X3 + X4 9-45

46 最佳切割問題(2/2) 受限於： 2X1 + X4 ≧ 250 3X2 ≧ 1000 3X2 + 10X3 + 6X4 ≧ 750
使用LINDO軟體求得最佳解： X1=125，X2=333.33，Z* = (個) 亦即，切割方案一125塊，方案二334塊，最少總共需用459塊 9-46

47 Ch9 HW 1, 2, 3, 4, 7, 9, 10, 11 9-47