對偶單純形法詳解

對偶單純形法詳解第1頁，共22頁，2023年，2月20日，星期一

二、對偶單純形法的基本思想

1、對“單純形法”求解過程認識的提升——

從更高的層次理解單純形法

初始可行基（對應(yīng)一個初始基本可行解）

→迭代→另一個可行基（對應(yīng)另一個基本可行解），直至所有檢驗數(shù)≤0為止。第2頁，共22頁，2023年，2月20日，星期一

所有檢驗數(shù)≤0意味著

，說明原始問題的最優(yōu)基也是對偶問題的可行基。換言之，當原始問題的基B既是原始可行基又是對偶可行基時，B成為最優(yōu)基。定理2-5

B是線性規(guī)劃的最優(yōu)基的充要條件是，B是可行基，同時也是對偶可行基。第3頁，共22頁，2023年，2月20日，星期一LP原問題:若B是A中的一個基可行基B對應(yīng)的解是基本可行解，則B是可行基對偶可行基若單純形乘子是對偶問題的可行解，則B是對偶可行基

是對偶問題的可行解檢驗數(shù)等價

第4頁，共22頁，2023年，2月20日，星期一

證明：第5頁，共22頁，2023年，2月20日，星期一單純形法的求解過程就是：

在保持原始可行的前提下(b列保持≥0)，

通過逐步迭代實現(xiàn)對偶可行(檢驗數(shù)行≤0)。

2、

對偶單純形法思想：

換個角度考慮LP求解過程：保持對偶可行的前提下（檢驗數(shù)行保持≤0）

，通過逐步迭代實現(xiàn)原始可行（b列≥0，從非可行解變成可行解）。

第6頁，共22頁，2023年，2月20日，星期一對偶單純形法的思想（圖示）原問題初始基本可行解保持為基本可行解初始對偶可行解保持對偶可行性最優(yōu)解基本可行性對偶可行性始終滿足解的可行性始終滿足對偶可行性第7頁，共22頁，2023年，2月20日，星期一

三、對偶單純形法的實施1、使用條件：

①檢驗數(shù)全部≤0；

②解答列至少一個元素

<0；2、實施對偶單純形法的基本原則：在保持對偶可行的前提下進行基變換——每一次迭代過程中取出基變量中的一個負分量作為換出變量去替換某個非基變量(作為換入變量),使原始問題的非可行解向可行解靠近。

第8頁，共22頁，2023年，2月20日，星期一3、計算步驟：

①建立初始單純形表，計算檢驗數(shù)行。解答列≥0——已得最優(yōu)解；至少一個元素<0,轉(zhuǎn)下步;解答列≥0——原始單純形法；至少一個元素<0,另外處理；

檢驗數(shù)全部≤0（非基變量檢驗數(shù)<0）至少一個檢驗數(shù)>0第9頁，共22頁，2023年，2月20日，星期一

基變換：

先確定換出變量——解答列中的負元素（一般選最小的負元素）對應(yīng)的基變量出基；

即相應(yīng)的行為主元行。第10頁，共22頁，2023年，2月20日，星期一然后確定換入變量——原則是：在保持對偶可行的前提下，減少原始問題的不可行性。如果

(最小比值原則),則選

為換入變量

,相應(yīng)的列為主元列

,主元行和主元列交叉處的元素

為主元素。若,要計算最小比值嗎？為什么？第11頁，共22頁，2023年，2月20日，星期一

按主元素進行換基迭代（旋轉(zhuǎn)運算、樞運算），將主元素變成1，主元列變成單位向量，得到新的單純形表。

循環(huán)以上步驟，直至求出最優(yōu)解。第12頁，共22頁，2023年，2月20日，星期一3、舉例——用對偶單純形法求解LP：

化為標準型

→

將兩個等式約束兩邊分別乘以-1，得第13頁，共22頁，2023年，2月20日，星期一以此形式進行列表求解，滿足對偶單純形法的基本條件，具體如下：第14頁，共22頁，2023年，2月20日，星期一-2/-2----4/-3------

比

值-2-3-4000-Z-1-2-110-21-301-3-4

x4

x5

00

-2-3-400x1x2x3x4x5cjxjbXBCB第15頁，共22頁，2023年，2月20日，星期一----4/-5/2----1/-1/2

比

值0-4-10-10

cj-zj0-5/21/21-1/21-1/23/20-1/2-12

x4

x1

0-2

-2-3-400x1x2x3x4x5cjxjbXBCB第16頁，共22頁，2023年，2月20日，星期一00-3/5-8/5-1/50

cj-zj01-1/5-2/51/5107/5-1/5-2/52/511/5

x2

x1

-3-2

-2-3-400x1x2x3x4x5cjxjbXBCB最優(yōu)解:X*=（11/5，2/5,0,0,0）T，最優(yōu)值:minW=-maxZ*=-[11/5×(-2)+2/5×(-3)]=28/5第17頁，共22頁，2023年，2月20日，星期一4、舉例——用對偶單純形法求解LP：

化為標準型

→

將三個等式約束兩邊分別乘以-1，然后列表求解如下：第18頁，共22頁，2023年，2月20日，星期一-3/-1-9/-1---------

比

值-3-90000-Z-1-1100-1-4010-1-7001-2-3-3y3

y4

y5000-3-9000y1y2y3y4y5cjyjbXBCB第19頁，共22頁，2023年，2月20日，星期一

----6/-3-3/-1------

比

值0-6-3006-Z11-1000-3-1100-6-1012-1-1

y1

y4

y5

-300-3-9000y1y2y3y4y5cjyjbXBCB第20頁，共22頁，2023年，2月20日，星期一00-1-208-Z10-4/31/30011/3-1/30001-215/31/31

y1

y2

y5

-3-90-3-9000y1y2y3y4y5cjyj