[下载]单纯法简介

haolaoban

線性規劃基本原理

　　系統分析常應用數學規劃（mathematical programming）法以求取優選策略，也就是在所有可行方案中，選取可達到最好目標者。規劃法中的線性規劃是20世紀中期開始發展的科學，線性規劃模式中的所有方程式及函數都是線性的，所以應用最為廣泛。線性規劃有個非常高效率的解題方法，稱為單純法（simplex method），可用來解決任何尺度線性規劃的問題。

　　此下以一水庫為符合供水合約要求之營運分析為例，介紹線性規劃之應用。如圖所示之系統：



　　考慮下游地區的週期性用水需求可以表示成下式：

(8.2.1-1)

式中，

t
= 時段指標；

= 年需水總量；

= 各時段之用水係數。

　　系統營運上的其他限制條件包括：

(1) (8.2.1-2)

(2) (8.2.1-3)

(3) (8.2.1-4)

(4)  已知；

(5) 所有變量均。

上述諸式中，

T
= 分析時段總數；

= 水庫蓄水量；

= 水庫起始蓄水量；

= 營運分析的期末蓄水；

= 水庫入流量；

= 水庫蒸發量，須經疊代計算；
，
= 水庫的最大及最小蓄水量；

= 放水量；

= 缺水量；

= 超供水量；

而且，亦即此二水量僅有一量有值，另一量必定為 0。

　　根據不同的管理目標，水庫營運分析的標的函數可能有下列三種選擇：

1. 標的函數 #1 ： 希望相對於目標供水量的總缺水量為最小。

(8.2.1-5)

2. 標的函數 #2 ： 使總缺水量為最小。

(8.2.1-6)

3. 標的函數 #3 ： 儘量減低最大的供水偏差量

(8.2.1-7)

　　上述之標的函數 #3 具有平均供水偏差的效果，相當於一平滑化 (Smooth) 之標的函數如下式：

(8.2.1-8)

　　此式將「懲罰」較大的缺水量值，但相對於標的函數 #3，需先進行線性化的處理，方能應用線性規劃求解。

　　茲採用標的函數 #3 進行分析，其可行解的限制條件可整理如下：

(8.2.1-9)

(8.2.1-10)

(8.2.1-11)

所有變數 (8.2.1-12)

(8.2.1-11) 式亦可寫成下列二式：

(8.2.1-13)

(8.2.1-14)

　　問題中諸變量在分析上之類別為：

已知變量有：、、、、T、(=0)、。
未知目標函數值：C = 為最大的供水偏差量。
未知的因變量有： 、。
未知的決策變量有：。
對一3時段的營運分析問題，將 (8.2.1-7)、(8.2.1-9)、(8.2.1-10)、(8.2.1-13)、(8.2.1-14) 諸式表成矩陣型式如下表，即可以線性規劃求解：

MIN
0
0
0
0
0
0
1
=
Z
變數:
X1
X2
X3
X4
X5
X6
X7
　 　
　 Q1
V2
Q2
V3
Q3
V4
C
　 b
　 1
1
　 　 　 　 　 =
I1 - EVAP1 + V1
　 　 -1
1
1
　 　 　 =
I2 - EVAP2
　 　 　 　 -1
1
1
　 =
I3 - EVAP3
　 　 1
　 　 　 　 　
Vmax
　 　 　 　 1
　 　 　
Vmax
　 　 　 　 　 　 1
　
Vmax
　 1
　 　 　 　 　 1

D1
　 　 　 1
　 　 　 1

D2
　 　 　 　 　 1
　 1

D3
　 1
　 　 　 　 　 -1

D1
　 　 　 1
　 　 　 -1

D2
　 　 　 　 　 1
　 -1

D3

上表中的已知值均出現在方程式右方 (Right Hand Side, RHS)，線性規劃將求得方程式左方所有未知變量的最佳解與最小之標的函數值。

　　線性規劃法使用簡便，計算效率高，商用的電腦套裝軟體，例如LINDO、MINOS等極為普遍，超過半數以上的水資源規劃與管理問題皆可套用線性規劃求解。但線性規劃的缺點及限制則有：

對隨時段動態演進的問題，上表會形成寬鬆矩陣 (Sparse Matrices) ，而線性規劃若以使用普及的簡繁法 (Simplex Method) 求解，其計算時間隨矩陣之行數與列數乘積成二次方增加，故有計算時效的問題。
方程式中的非線性項必須先經線性化處理，或以連續線性近似法分析，但對非凸型的函數則可能難以求得整體最佳解 (Global Optimum)。
不易明確地納入風險及不確性的分析在內。
對整數值的變量或離散決策型態的問題並不適合，此二類問題宜採用整數規劃或動態規劃分析。
　　線上計算例請參閱附錄一。

8.2.2　線性規劃連續趨近法

　　並非所有規劃的問題都能適用線性規劃模式，當一個或多個線性規劃的假設不成立時，就只好改用其它數學規劃模式，譬如，整數規劃或非線性規劃。惟線性規劃亦可用連續趨近法來處理限制式中的非線性項，線性規劃連續趨近法為疊代法的一種，其求解程序係利用一階泰勒級數展開法，將非線性項近似取為線性項，並定出一起始可行解代入分析，再由分析所得結果疊代至上述起始可行解中，直到分析所得結果與起始可行解近似為止。

　　例如在水庫防洪運轉分析中，主要之非線性函數為溢洪道的放水堰流公式，並不能直接運用於線性規劃分析，因此可運用線性規劃連續趨近法處理。首先將此非線性方程式做一階泰勒級數展開：



(8.2.2-1)

式中為 的假設近似值。

??由於上式將非線性方程式近似為一次的線性方程式，因此可將此式置入線性規劃模式中加以遞迴分析，將分析得出的  值疊代回原式中的  值中，再對整體線性規劃模式加以求解，重覆此步驟直至  為止，此時分析所得的結果即為系統的最佳防洪操作策略。

golden

你就不能转成简体再贴呀，这样看多不方便呀。

DK_slayer

对啊，我真没耐心看下去，拜托你饶了我吧