作業研究 補考

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

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

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

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

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

        max:  48 sweet + 51 spicy;
        P:  0.16 sweet + 0.29 spicy <= 73;
        Q:    27 sweet +   38 spicy <= 9600;
        R:  0.25 sweet + 0.18 spicy <= 48;
        pl: 0.15 sweet + 0.23 spicy <= 58;
  

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

	Value of objective function: 13127.6

	Actual values of the variables:
	sweet                     20.6897
	spicy                     237.931

	Actual values of the constraints:
	P                         72.3103
	Q                            9600
	R                              48
	pl                        57.8276

	Objective function limits:
					 From            Till       FromValue
	sweet                        36.23684        70.83333          -1e+30
	spicy                           34.56        67.55556          -1e+30

	Dual values with from - till limits:
				   Dual value            From            Till
	P                                   0          -1e+30           1e+30
	Q                           0.8857759            5184         9626.23
	R                            96.33621        46.43137        88.88889
	pl                                  0          -1e+30           1e+30
	sweet                               0          -1e+30           1e+30
	spicy                               0          -1e+30           1e+30

第一部分

在這個問題中, 有 P,Q,R,pl 四個 (1); "max: 48 sweet + 51 spicy;" 是這一題的 (2)。 sweet 和 spicy, 是此題的兩個 (3)。 每一組 sweet 和 spicy 的值 (兩個數字) 若滿足所有 (1), 就叫做一個 (4)。 能讓 (2) 得到最大值的 (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)。 若辣味醬的利潤升高為每公斤 50 元, 則最佳利潤將變成 (9)。 又可看出 Q 與 R 兩式是 (10), 也就是說: 最吃緊的資源是原料 Q 與 R。 若 Q 的庫存量減少為 9000 公克, 則最高利潤將變成 (11)。

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

第三部分

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

第四部分

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

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

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