學號: ____________________ 班級: ________ 姓名: ____________
*** 題目卷需填寫姓名學號並繳回 ***
第一題: 請用圖解法解下列 「資源有限; 求最大利潤」 的線性規畫問題:
max: 5 x + 6 y;
A: 4 x + 12 y <= 84;
B: 3 x + 4 y <= 30;
C: 9 x + 4 y <= 54;
第二題: 請修改 objective function, 讓這題變成具有無窮多組最佳解。 請列出修改後的兩個 corner point optimal solutions。
第三題: 假設第一題當中, x 與 y 的單位為 「桶」; 目標函數的單位為 「元」; 限制條件 A 的單位為 「公斤」; 限制條件 B 的單位為 「毫升」; 限制條件 C 的單位為 「分鐘」。 用 lp_solve -S4 解題, 印出的部分結果如下:
... (以上省略) ...
Dual values with from - till limits:
Dual value From Till
A 0 -1e+30 1e+30
B 1.416667 18 33.65217
C 0.08333333 37.2 90
x 0 -1e+30 1e+30
y 0 -1e+30 1e+30
請用中文解釋 A,B,C 的 Dual value 欄位的意義 (0, 1.416667, 0.08333333 這三個數字)。
第四題: 請寫出一個 minimization 問題, 它的最佳解, 恰好是這一組 (三個) 數字。 提示: 對偶...
下表顯示一個運輸問題各出發點的供給量 (桶), 需求量 (桶), 運輸成本 (元/桶):
| D1 | D2 | D3 | D4 | 供給量 | ||
| S1 | 6.7 | 8.2 | 3.5 | 9.4 | 98 | |
| S2 | 7.4 | 4.5 | 6.2 | 8.0 | 65 | |
| S3 | 5.5 | 6.3 | 6.1 | 7.9 | 72 | |
| 需求量 | 43 | 67 | 57 | 48 | ||
第五題: 請用 Vogel's approximation method (VAM) 找一組初始可行解。 注意: 供需不平衡!
下面列出上題的某一組可行解。 請用 modified distribution 法找出一個 entering variable, 並用 stepping stone method 找出下一組 (改進過的) 可行解。 (本來應該重複應用此二法持續改進, 直至找到最佳解為止; 但限於時間, 只做一回合就好。)
從 S1 運 45 桶到 D2, 運 48 桶到 D4
從 S2 運 43 桶到 D1, 運 22 桶到 D2
從 S3 運 57 桶到 D3