對偶單純形法

1954年C.萊姆基提出的方法

對偶單純形法是指從對偶可行性逐步搜索出原始問題最優解的方法。由線性規劃問題的對偶理論，原始問題的檢驗數對應於對偶問題的一組基本可行解或最優解；原始問題的一組基本可行解或最優解對應於對偶問題的檢驗數；原始問題約束方程的係數矩陣的轉置是對偶問題約束條件方程的係數矩陣。所以，在求解常數項小於零的線性規劃問題時，可以把原始問題的常數項視為對偶問題的檢驗數，原始問題的檢驗數視為對偶問題的常數項。

1定律定義 2方法思路 3計算步驟

4推導過程 5優缺點

定律定義

偶單純形（）純形稱形．單純形言，迭程始終保持題，斷改善對偶問題解（即判別係數）的可行性，直至可行．而對偶單純形方法則是始終保持對偶問題的解的可行性，並不斷改善原問題解的可行性，直至滿足原問題。

方法思路

謂足偶，即指檢驗足優件。保持檢驗足優件提，旦基，偶題題均，強偶證，二均優。

設始題標準形式，則其對偶問題(Dual Problem)為。當原問題的一個基解滿足最優性條件時，其檢驗數小於等於0，當時，既有或，即知單純形運算元為對偶問題的可行解。換而言之，只要保證檢驗數，則對偶問題一定存在可行基B。

在初始單純形表中，一般此可行基B都為單位矩陣I，這時候只要能夠保持檢驗數持續小於等於0迭代下去，通過變換到一個相鄰的目標函數值較小的基可行解（因為對偶問題是求目標函數極小化），並循環進行，一到時，原問題也為可行解。這時，對偶問題和原問題均為可行解，而且兩者的可行解就是最優解，這就是對偶單純形法求解線性規劃的基本思路。

一旦最終基變數XB≥0，原問題也滿足最優解條件的原因是：對偶問題的最終單純形表中的基變數和原問題的最終單純形表中的檢驗數的相反數CBB取值相等，不難觀察到原問題的檢驗數，其檢驗數滿足最優性條件。（註：這裡的B並不是同一個矩陣，它們是各自問題的初始可行基，但CB和b在本質上是同一個向量。）

雖然，本方法借鑒了對偶理論的思路，但是它是求解原問題而非對偶問題的一個方法。而且，一般用對偶單純形法解決的是原始問題是極小化問題，，但是只要先標準化為即於上面一致。

計算步驟

設對某標準形式的線性規劃問題

1.做出單純形表

存在一個對偶問題的可行基B，不妨設，列出它的初始單純形表。

CB	基	b	x1	···	xr	···	xm	xm+1	···	xs	···	xn
c1	x1	b1	1	···		···		a1,m+1	···	a1s	···	a1n
...	...	...	...		...		...	...		...		...
cr	xr	br		...	1	...		ar,m+1	...	ars	...	arm
...	...	...	...		...		...	...		...		...
cm	xm	bm		...		...	1	am,m+1	...	ams	...	amn
cj-zj				...		...		cm+1-zm+1		cs-zs	...	cn-zn

表中必須有的最後一行的檢驗數的值要求為部分為負數。當對有時，即表中原問題和對偶問題均為最優解。否則，通過變化一個基變數，找出原問題的一個目標函數值較小的相鄰基解。

2.確定換出基的變數（離基變數）

因為總存在的bi，選取數值最小的作為為第r行，令，其對應變數xr為換出基的變數。

3.確定換入基的變數（入基變數）

（1）為了使下個表中第r行基變數為正值，只有對應的的非基變數才可以考慮作為換入基的變數。為了消除原問題的基解不可行性，變換后的b應該變成正數，故能夠成為主元素arj的應該小於零，意味著這第r行的凡是為非負的元素在判別的是否為主元素時不必考慮。

（2）為了使下一個表中的對偶問題的解仍為可行解，選取檢驗數與對應變數arj中的比值最小的那個變數作為主元素，令。如果有多個值時任選其一。

其中，稱為ars為主元素，主元素對應的那一列的變數xs為換入基的變數。如果對於所有的非基變數xj成立，則問題沒有可行解。

3.用換入變數替換換出變數，得到一個新的基。

對新的基再檢查是否所有。如是，則找到了兩者的最優解，如為否，則返回到第一步再循環進行。

推導過程

分為兩者情況討論滿足最小比值法時選取主元素時，可以保證一個表中的檢驗數為（對）

設下一個表中的檢驗數為，有：

(a)對，因，故，主元素，，由此可知方括弧內的值，故有。

(b)對，因，故有。

優缺點

對偶單純形法的優點：不需要人工變數；

當變數多於約束時，用對偶單純形法可減少迭代次數；

在靈敏度分析中，有時需要用對偶單純形法處理簡化。

對偶單純形法缺點：在初始單純形表中對偶問題是基可行解，這點對多數線性規劃問題很難做到。因此，對偶單純形法一般不單獨使用。