Chap. 3 線性規劃導論
Linear Programming 是20世紀中葉最重要的科學進步之一。LP 處理的典型問題是將有限的資源(limited resource)以最佳的(optimal)方法，分配至相競爭的活動(competing activities)中。
3.1 範例
|
工廠 |
產品1 |
產品2 |
每週可用時間 |
|
1 |
1 |
0 |
4 |
|
2 |
0 |
2 |
12 |
|
3 |
3 |
2 |
18 |
|
單位利潤 |
$3 |
$5 |
|
Maximize
Z = 3 X1 + 5 X2
s.t.
|
X1
|
|
<=4 |
|
|
2
X2 |
<=12 |
|
3
X1+ |
2
X2 |
<=18 |
|
X1
>=0 |
X2
>=0 |
|
X2
術語
可行解 (feasible solution)：如 (2,3), (4,1)
非可行解 (infeasible solution)：如 (6,0), (4,6)
可行域 (feasible region)： collection of all feasible
solutions
角點可行解 (corner-point feasible
solution)：如 (0,0) , (4,0) , (4,3), (2,6), (0,6)
相鄰的角點可行解：如 (2,6) 與 (0,6)，(4,0)與(4,3)
最優解 (optimal solution)：如 (2,6)
可能只有一個最優解、不只一個最優解、無最優解
3.2 線性規劃模式
基本特徵
1. 目標函數必需為線性 (The Objective Function (O.F.) is linear)
2. 限制式（不論是等式 or 不等式）必需為線性 (The constraints are linear (equality and/or inequality))
3. 所有參數均為 非負之實數 (The variables are nonnegative variables)
4. 標準模式如下所示：
最佳化 （Optimize: MAX or MIN）
Z = C1 X1 + C2 X2 + ... + Cn Xn
限制在 （Subject to， s.t.）
A11 X1 + A12 X2 + .... + A1n Xn < B1
A21 X1 + A22 X2 + .... + A2n Xn < B2
...
Am1 X1 + Am2 X2 + .... + Amn Xn < Bm
且 X1, X2,.... Xn ≧ 0,
其中
m ≧ n or m < n,
m : number of constraints, n : number of unknowns
計算的複雜度一般可採 ㎡n 為指標
Table 3.3 (p.33)
|
Resource |
Resource usage per unit of
acitivity |
Amount
of resource available |
|||
|
1 |
2 |
…….. |
n |
||
|
1 |
a11 |
a12 |
……. |
a1n |
b1 |
|
2 |
a21 |
a22 |
……. |
a2n |
b2 |
|
|
……. |
……. |
……. |
……. |
…….. |
|
m |
am1 |
am2 |
……. |
amn |
bm |
|
Contribution
to Z per unit of activity |
C1 |
C2 |
……. |
Cn |
|
3.3 線性規劃之假設
|
比例性 (Proportionality) |
O.F.中的CkXk, 限制式中的 AikXk，均與第k種活動單獨從事的水準成正比。 |
|
可加性 (Additivity) |
各種活動之間彼此沒有交叉影響，在(X1, X2, …., Xn)之下，每一資源的總用量和效果總量，各等於每一活動單獨從事時的資源用量和效果量的總合。 |
|
可分性 (Divisibility) |
各活動的水準可隨意分割，使得決策變數值可以是非整數。 |
|
確定性 (Certainty) |
所有參數值 (包括O.F.與限制式中的係數與後者的rhs)都是已知數。 |
3.4 範例數則
放射線治療 p.45
南方社區聯盟 (S.C.K) p.48
空氣污染管制 p.50
固態廢棄物回收 p.53
排程 p.57
配送 p.60
3.5 一些應用實例
請自行研讀教科書之內容
