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

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

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

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

最佳產品生產組合(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

LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 73589.74 1) 73589.74 VARIABLE VALUE REDUCED COST XA 5743.589844 0.000000 XB 1794.871826 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 1061.538452 0.000000 3) 1889.743530 0.000000 4) 0.000000 8.461538 5) 0.000000 10.256411 NO. ITERATIONS= 2 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE XA 10.000000 2.857143 5.500000 XB 9.000000 11.000000 2.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 6500.000000 INFINITY 1061.538452 3 6000.000000 INFINITY 1889.743530 4 7000.000000 2333.333252 3733.333252 5 1400.000000 418.181824 350.000000 9-6

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

多重期間的生產規劃(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.3I13+0.35I21+ 0.35I22+0.35I23 9-8

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

多重期間的生產規劃(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

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

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

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

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

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

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

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

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

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

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

選擇最佳投資組合(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

人力規劃問題(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

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

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

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

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

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

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

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

人力調度問題(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

9-31

9-32

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

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

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

9-36

物流系統設計(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+11X53+350000Y3+200000Y4+480000Y5 9-37

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

物流系統設計(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

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

混合問題(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

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

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

9-44

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

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

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