簡介

例題一: 種什麼才好?

請見 lpsolve 手冊的這一篇: "Formulation of an lp model in lpsolve"。摘要: 農夫有 75 畝地, 可種 w 或 b。 w 的成本每畝 $120, b 的成本每畝 $210。農夫資本額 $15000。 w 產量每畝 110 單位, b 產量每畝 30 單位, 農夫的倉庫共可儲存 4000 單位。 w 的淨利是每單位 $1.3 而 b 的淨利是每單位 $2.0。請問這 75 畝應該如何分配給這兩種作物以獲得最高利潤?

暫停往下看, 請先思考並寫出數學模型。數學模型在 farmer.lp 檔案裡 (別急著點進去!)

用 lpsolve 解題

請安裝 lpsolve (ubuntu 底下: sudo apt-get install lp-solve) 並執行 lp_solve farmer.lp 印出以下結果:

        Value of objective function: 6315.62

        Actual values of the variables:
        wheat                           21.875
        barley                          53.125

用 octave 驗證

先複習一下矩陣定義及矩陣乘法。進入 octave, 逐列剪貼以下指令, 觀察列印結果並思考其輸出的意義:

        A = [120,210; 110,30; 1,1]
        b = [15000; 4000; 75]
        c = [143; 60]
        x = [21.875; 53.125]
        c'*x
        A*x
        b-A*x

上面的 A,b,c 都是題目抄來的參數。 x 是從 lp_solve 解出的最佳解 (兩種作物各種多少) 抄來的。 c'*x 得到最佳利潤, 當然與 lp_solve 的答案要一樣。 A*x 是實際使用的資金, 倉儲, 與耕地。 b-A*x 則是未用完的資金, 倉儲, 與耕地。從 b-A*x 的零值可看出: 在 optimal solution 處, binding constraints 為 storage (倉儲) 與 land (耕地)。

用 gnumeric 解題

安裝 gnumeric 並用它開啟這個範例。注意底下的分頁標籤。請切換到 farmer 分頁。從 tools 選單打開 solver 對話框。

(Solver 對話框的) parameters 分頁: 點一下 Set Target Cell, 再到試算表點選 D4 那一格。 (隨便一個沒用到的空格都可以; gnumeric 會在這一格填答案) 確認一下 Equal to 選定的是 Max。點一下 By Changing Cells, 再到試算表選取 B3:C3 (不是 143 與 60, 是它們上面那兩個空白格)。

Model 分頁: 應該都不需要改。確認一下已選取 Linear Model 並已勾選 Assume Non-Negative。

使用 gnumeric 解 farmer 這題

Constraint 分頁: 點一下 Left Hand Side, 再到試算表選取 D7 到 D9 (total LHS 那一行, 共三格); 中間的 Type 則選 <= ; 最後點一下右邊的 Right Hand Side, 再到試算表選取 F7 到 F9 (就是 total RHS 那一行, 共三格)。記得要點選 Add (新增), 才會真的加入這一組 (共三個) 限制條件。

其他分頁應該都不需要更動。按下 solve 之後, 注意 B3 與 C3 出現最佳耕地分配; D4 出現預期獲利; D7:D9 出現各種資源的實際使用情形。

例題二: 汽車子廠分工

改編自 Michael Trick 教授的講義。摘要: Tucker 汽車公司將生產 1000 輛汽車。 Tucker 汽車公司有四個子廠, 每個廠生產一部汽車的成本不同; 所需使用的人時及原物料也各不相同, 如附表:

子廠	成本	原物料	工時
1	15	3	2
2	7	6	5
3	9	5	4
4	10	4	3

又因為契約因素, 這 1000 輛汽車當中, 至少有 400 輛必須交由 3 廠生產。今共有 4000 原物料及 3300 人時可供支配, 請問應如何分配方能使成本降至最低? 模型請見 tucker.lp。

gnumeric 試作: 一樣請用 gnumeric 打開 intro.gnumeric, 並切換到 auto-company 分頁。試著完成此表格。可從 farmer 分頁把數學式剪貼過來, 但「滑鼠右鍵-copy」之後, 一定要先按 ENTER 或 Escape, 以免 gnumeric 以為你要替此格選新的範圍。設定 solver 時, 除了敲入 constraint 之外, 還要記得此題與上題的目標相反...。

問題與討論: 「成本」是否包含薪資及原物料? 「降低成本」是否為最重要的目標? 算出數字很重要; 但檢討數學式是否精確反應現實, 更重要。

名詞 & 圖解

objective function (目標函數): 例如「種什麼才好?」當中的利潤函數; 又如「汽車公司的子廠分工」當中的成本函數。
variable (決策變數): 例如「種什麼才好?」當中的 wheat (要拿多大的面積種 w?) 與 barley (要拿多大的面積種 b?) 兩個變數; 又如「汽車公司的子廠分工」當中的 f1, f2, f3, f4 (每個子廠各要生產幾部汽車?)。這些變數到底要調整/設定到什麼值, 才會得到最佳利潤或最低成本? 這就是線性規畫要討論的問題。
constraint (限制條件): 就是依據題目所列出來的等式與不等式。這些等式與不等式限制了決策變數能夠調整/設定的範圍。
variable bound
feasible solution (可行解): (決策變數的) 一組滿足所有限制的設定值。例如 (wheat, barley) = (10, 30)
feasible region (可行區域): 所有 feasible solutions 所成的集合, 例如右圖紅色部分。
corner point solution: 座落於 feasible region 頂點的解。例如右圖的 A,B,C,D,E 五個解都是。
optimal solution: 例如右圖的 D。
active constraints (binding constraints) (tight constraints): (在某一解處的) 等號成立的那些限制條件。例如在 B 點的 binding constraint 只有一個: capital (資金); 而在 C 點的 binding constraints 則有 capital (資金) 與 land (耕地) 兩項。

作業

請用 lp_solve 解這題: steel.lp, 並分別用計算機與 octave 驗證 lp_solve 算出來的 optimal solution 確實是一個 feasible solution。在此處, 那些限制條件是 binding constraints? 參考解答在本頁原始碼某處。

附錄: 筆記

(此節可忽略)

轉檔

取得 netlib 的測試資料集, 並先備份! (因為等一下要原地轉檔, 萬一失敗...)
編譯第一支轉檔程式 emps: gcc -o emps data/emps.c (ubuntu: 要先安裝 build-essential 套件才能編譯)
安裝 lp-solve 套件並閱讀 README.txt.gz, 搜尋 mps2lp, 瞭解如何使用第二支轉檔程式
列出所有資料檔名於 ~/listing 當中: perl -000 -ne 'print if /MPS/' index | perl -ne 'print "$1\n" if m#file\s+lp/data/(.*)#' > ~/listing
還有 kennington/ 子目錄底下的資料檔, 也解壓縮, 並且列出檔名: gunzip kennington/*.gz ; find kennington/ -name '*-*' >> ~/listing
批次轉檔: for f in $(cat ~/listing ) ; do ~/emps < $f > ~/tmp.txt ; lp_solve -parse_only -mps ~/tmp.txt -wlp $f ; done

製圖

farmer.gpt

簡介