學號: ____________________ 班級: ________ 姓名: ____________
*** 題目卷需填寫姓名學號並繳回 ***
第一題: 請用圖解法解下列 「資源有限; 求最大利潤」 的線性規畫問題:
max: 4 x + 3 y; P: 2 x + y <= 18; Q: 3 x + y <= 24; R: 3 x + 4 y <= 60;
第二題: 請修改 objective function, 讓這題變成具有無窮多組最佳解。 請列出修改後的兩個 corner point optimal solutions。
第三題: 假設第一題當中, x 與 y 的單位為 「箱」; 目標函數的單位為 「元」; 限制條件 P 的單位為 「人時」; 限制條件 Q 的單位為 「公克」; 限制條件 R 的單位為 「平方公分」。 用 lp_solve -S4 解題, 印出的部分結果如下。 請用中文解釋 P,Q,R 的 Dual value 欄位的意義 (1.4, 0, 0.4 這三個數字)。
... (以上省略) ...
Dual values with from - till limits:
Dual value From Till
P 1.4 15 20
Q 0 -1e+30 1e+30
R 0.4 42 72
x 0 -1e+30 1e+30
y 0 -1e+30 1e+30
第四題: 請寫出一個 minimization 問題, 它的最佳解, 恰好是這一組 (三個) 數字。 提示: 對偶...
下表顯示一個運輸問題各出發點的供給量 (公升), 需求量 (公升), 運輸成本 (元/公升):
| D1 | D2 | D3 | D4 | 供給量 | ||
| S1 | 3.5 | 2.7 | 1.8 | 3.9 | 62 | |
| S2 | 2.7 | 4.2 | 3.5 | 2.2 | 81 | |
| S3 | 3.5 | 4.1 | 2.9 | 3.2 | 82 | |
| 需求量 | 54 | 62 | 48 | 76 | ||
第五題: 請用 Vogel's approximation method (VAM) 找一組初始可行解。 注意: 供需不平衡!
第六題: 下面列出上題的某一組可行解。 請用 modified distribution 法找出一個 entering variable, 並用 stepping stone method 找出下一組 (改進過的) 可行解。 (本來應該重複應用此二法持續改進, 直至找到最佳解為止; 但限於時間, 只做一回合就好。)
從 S1 運 62 公升到 D4
從 S2 運 62 公升到 D2, 運 19 公升到 D3
從 S3 運 54 公升到 D1, 運 28 公升到 D3