作業研究 補考

學號: ____________________ 班級: ________ 姓名: ____________

*** 題目卷需填寫姓名學號並繳回 ***

齒留香調味醬公司專精於生產各種美食調味醬。 本季斗六廠計畫生產的產品有甜味醬及辣味醬。 兩種醬料所採用的原料包含 A, B, C 三種原料, 水, 及其他無限供應的原料。 此外, 兩種醬料共用一條生產線, 但生產線的運作時間有限。 每生產一公斤醬料, 所需要的 A,B,C 三種原料的量, 及需要使用生產線的運作時間, 如下表。

每一公斤的甜味醬可賣得 79 元的淨利潤; 每一公斤的辣味醬可賣得 81 元的淨利潤。 假設產品可全數賣出, 請問應如何分配資源, 生產這兩種產品, 才能獲得最高利潤?

解: 將題目寫成線性規畫數學式如下, 並存檔叫做 sauce.lp:

        max:  79 sweet + 81 spicy;
        A:  0.27 sweet + 0.19 spicy <= 450;
        B:  0.15 sweet + 0.43 spicy <= 620;
        C:  0.32 sweet + 0.12 spicy <= 480;
        pl:  2.4 sweet +  2.6 spicy <= 4800;
  

下指令 lp_solve -S4 sauce.lp 得到如下結果:

        Value of objective function: 153976

        Actual values of the variables:
        sweet                     1048.78
        spicy                     878.049

        Actual values of the constraints:
        A                             450
        B                         534.878
        C                         440.976
        pl                           4800

        Objective function limits:
                                         From            Till       FromValue
        sweet                        74.76923        115.1053          -1e+30
        spicy                        55.59259        85.58333          -1e+30

        Dual values with from - till limits:
                                   Dual value            From            Till
        A                            44.71545        417.3832        467.6471
        B                                   0          -1e+30           1e+30
        C                                   0          -1e+30           1e+30
        pl                           27.88618        4461.972        5039.041
        sweet                               0          -1e+30           1e+30
        spicy                               0          -1e+30           1e+30

第一部分

這一個問題有 sweet 與 spicy 兩個 (1); 有 A,B,C,pl 共四個 (2); "79 sweet + 81 spicy" 這一式是此題的 (3)。 每一個滿足 A,B,C,pl 所有 (2) 的解, 叫做一個 (4)。 能讓 (3) 得到最大值的 (4), 叫做 (5)。

提示: basic variable, binding constraint, constraint, corner point solution, data structure, dual problem, entering variable, feasible solution, floating point arithmetic, Gaussian elimination, gradient, Hessian matrix, Horner's rule, interior point method, inverse, linear programming, leaving variable, objective function, optimal solution, pivoting, primal solution, variable, vertex,

第二部分

把 lp_solve 印出的結果, 翻譯成常人聽得懂的中文, 就是說: 應生產 (6), 則可獲得最高利潤 (7); 如此將用掉 (8)。 若辣味醬的利潤降為每公斤 75 元, 則最佳利潤將變成 (9)。 又可看出 A 與 pl 兩式是 (10), 也就是說: 最吃緊的資源是原料 A 與生產線。 若將 A 的庫存量提高為 460 公斤, 則最高利潤將變成 (11)。

注意: (6) 與 (8) 要寫品名/數量/單位; (10) 要填英文, 請見第一部分提示; (11) 要寫算式與單位。

第三部分

(12) 請寫出 sauce.lp 的對偶。

第四部分

齒留香調味醬公司有三個工廠: 斗六廠, 豐原廠, 沙鹿廠; 有四個配銷中心: 臺北, 臺中, 臺南, 高雄。 各廠的產量 (箱), 各配銷中心的需求量 (箱), 及各廠到各中心的運送成本 (元/箱) 如下表:

(13) 請用 northwest corner rule 為這個運輸問題找一組初始可行解

(14) 請用 least cost rule 為這個運輸問題找一組初始可行解