作業研究 小考 A (2008/3/11)

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

*** 答案請直接寫在題目卷空白處, 並標清楚題號; 題目卷需繳回 ***

某共同基金公司欲將 100000 美元的資金投資在以下五項可能的標的上:

但有以下限制:

1. 任一產業投資金額不得多於 50000 美元
2. 政府公債不得少於綱鐵業投資額的 25%
3. 高報酬高風險的太平洋石油, 投資額不得多於石油業投資額的 60%
4. 因為契約因素, 投資於大西洋石油與休伯鋼鐵的總金額不得超過 40000 美元

請問應如何分配資金方能獲得最大預期利潤? (改編自 "An Introduction to Management Science", Anderson, Sweeney, Williams, Roan; 中譯版: "作業研究" 滄海圖書 林張群 陳可杰譯)

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

max: 0.073 AtlPet + 0.103 PacPet + 0.064 MWSteel + 0.075 HSteel + 0.045 Gov;

capital:         AtlPet + PacPet + MWSteel + HSteel + Gov  = 100000;
petroleum_upper: AtlPet + PacPet                          <= 50000;
steel_upper:                       MWSteel + HSteel       <= 50000;
gov_lower:              -0.25 MWSteel - 0.25 HSteel + Gov >= 0;
risky_pacific:  -0.6 AtlPet + 0.4 PacPet                  <= 0;
contract:        AtlPet                    + HSteel       <= 40000;

下指令 lp_solve invest.lp 得到如下結果:

        Value of objective function: 7780

        Actual values of the variables:
        AtlPet                      20000
        PacPet                      30000
        MWSteel                     20000
        HSteel                      20000
        Gov                         10000

檔案 invest.lp 當中, "0.073 AltPet + ... + 0.045 Gov" 那一道式子叫做 (1); 而 capital, petroleum_upper, steel_upper, gov_lower, risky_pacific, contract 等六式叫做 (2)。 這一題總共有 AltPet, PacPet, MWSteel, HSteel, Gov 五個 (3)。 想找出最佳的投資方式, 其實並不需要逐一檢視無窮多組 (4), 頂多只需要看其中有限多組 (5), 因為這題是一個線性規劃類的題目, 所以我們有興趣的 (6) (就是 lp_solve 所印出來的這組解) 必然是一個 (5)。 在每一組 (5) 上, 我們經常有興趣瞭解: 那幾條 (2) 是 (7), 也就是說, 這一組解把那幾條 (3) 撐到極限。

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

請用計算機驗算 lp_solve 所寫的答案。 (8) (要寫算式)。

再用 octave 驗算:

        c = [0.073; 0.103; 0.064; 0.075; 0.045];
        b = [100000; 50000; 50000; 0; 0; 40000];
        A = [ ...
            1, 1, 1, 1, 1; ...
            1, 1, 0, 0, 0; ...
            0, 0, 1, 1, 0; ...
            0, 0, -0.25, -0.25, 1; ...
            -0.6, 0.4, 0, 0, 0; ...
            1, 0, 0, 1, 0; ...
        ];
        x = [ 20000; 30000; 20000; 20000; 10000];
        b-A*x

印出這樣的結果:

ans =

   0.0000e+00   0.0000e+00   1.0000e+04   0.0000e+00  -6.6613e-13 0.0000e+00