對(duì)偶單純形法

§2.4.對(duì)偶單純形法一、什麼是對(duì)偶單純形法？

對(duì)偶單純形法是應(yīng)用對(duì)偶原理求解原始線性規(guī)劃的一種方法——在原始問(wèn)題的單純形表格上進(jìn)行對(duì)偶處理。

注意：不是解對(duì)偶問(wèn)題的單純形法！二、對(duì)偶單純形法的基本思想

1、對(duì)“單純形法”求解過(guò)程認(rèn)識(shí)的提升從更高的角度理解單純形法

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

→迭代→另一個(gè)可行基（對(duì)應(yīng)另一個(gè)基本可行解），直至所有檢驗(yàn)數(shù)≤0為止。

所有檢驗(yàn)數(shù)≤0意味著，說(shuō)明原始問(wèn)題的最優(yōu)基也是對(duì)偶問(wèn)題的可行基。換言之，當(dāng)原始問(wèn)題的基B既是原始可行基又是對(duì)偶可行基時(shí)，B成為最優(yōu)基。定理2-5

B是線性規(guī)劃的最優(yōu)基的充要條件是，B是可行基，同時(shí)也是對(duì)偶可行基。單純形法的求解過(guò)程就是：

在保持原始可行的前提下(b列保持≥0)，通過(guò)逐步迭代實(shí)現(xiàn)對(duì)偶可行(檢驗(yàn)數(shù)行≤0)。

2、

對(duì)偶單純形法思想：

換個(gè)角度考慮LP求解過(guò)程：保持對(duì)偶可行的前提下（檢驗(yàn)數(shù)行保持≤0），通過(guò)逐步迭代實(shí)現(xiàn)原始可行（b列≥0，從非可行解變成可行解）。

三、對(duì)偶單純形法的實(shí)施1、使用條件：

①檢驗(yàn)數(shù)全部≤0；②解答列至少一個(gè)元素<0；2、實(shí)施對(duì)偶單純形法的基本原則：在保持對(duì)偶可行的前提下進(jìn)行基變換——每一次迭代過(guò)程中取出基變量中的一個(gè)負(fù)分量作為換出變量去替換某個(gè)非基變量(作為換入變量),使原始問(wèn)題的非可行解向可行解靠近。3、計(jì)算步驟：

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

檢驗(yàn)數(shù)全部≤0（非基變量檢驗(yàn)數(shù)<0）至少一個(gè)檢驗(yàn)數(shù)>0

基變換：

先確定換出變量——解答列中的負(fù)元素（一般選最小的負(fù)元素）對(duì)應(yīng)的基變量出基；即相應(yīng)的行為主元行。然后確定換入變量——原則是：在保持對(duì)偶可行的前提下，減少原始問(wèn)題的不可行性。如果(最小比值原則),則選為換入變量,相應(yīng)的列為主元列,主元行和主元列交叉處的元素為主元素。

按主元素進(jìn)行換基迭代（旋轉(zhuǎn)運(yùn)算、樞運(yùn)算），將主元素變成1，主元列變成單位向量，得到新的單純形表。繼續(xù)以上步驟，直至求出最優(yōu)解。對(duì)偶單純形法舉例(例1-1)例1：用對(duì)偶單純形法解下列線性規(guī)劃解:先將原問(wèn)題化為標(biāo)準(zhǔn)形式再將標(biāo)準(zhǔn)形式改為下列形式：對(duì)偶單純形法舉例(例1-2)則第一個(gè)基為B1=(P4,P5)=I基變量為y4,y5第一個(gè)對(duì)偶可行基對(duì)應(yīng)的單純形表如下

XB

b

Y1Y2Y3Y4Y5

Y4Y5-2-1

0-6-110-5-2-101-w

0

-15-24-500

T(B1)Y2Y5-w1/3011/6-1/60-1/3-50-2/3-1/318-150-1-40

T(B2)對(duì)偶單純形法舉例(例1-3)

T(B2)Y2Y5-w1/3011/6-1/60-1/3-50-2/3-1/318-150-1-40

T(B3)對(duì)偶單純形法舉例(例1-4)XBb

Y1Y2Y3Y4Y5

Y2Y3-w-5/410-1/41/415/2011/2-3/21/41/217/2-15/200-7/2-3/2最優(yōu)解Y*=(0,1/4,1/2,0,0)T

最優(yōu)值W’*=-17/2對(duì)偶單純形法舉例(例2-1)例2：用對(duì)偶單純形法解下列線性規(guī)劃解:先將原問(wèn)題化為下列形式對(duì)偶單純形法舉例(例2-2)則第一個(gè)基為B1=(P3,P4,P5)=I基變量為y3,y4,y5第一個(gè)對(duì)偶可行基對(duì)應(yīng)的單純形表如下

T(B1)Y3Y4w-4-2-1100-6-1-30110-2-3000XBb

Y1Y2Y3Y4Y5

Y5-3-1-1001對(duì)偶單純形法舉例(例2-3)

T(B1)Y3Y4w-4-2-1100-6-1-30110-2-3000XBb

Y1Y2Y3Y4Y5

Y5-3-1-1001Y3Y2Y5w-2-5/301-1/3-1/321/310-1/3-1/3-1-2/300-1/32/36-100-1-1對(duì)偶單純形法舉例(例3-1)例3：用對(duì)偶單純形法解下列線性規(guī)劃解:取B1=(P3，P4，P5)=I為對(duì)偶可行基因此其對(duì)應(yīng)的單純形表如下對(duì)偶單純形法舉例(例3-2)x3x4x5-w-13-1100-2-110104220010-1-1000x3x4x5x1x2

T(B1)x3x1x5-w-70213021-10-1000402120-20-10

T(B2)

由于基變量X3所在行的變量系數(shù)全大于等于0，則原問(wèn)題無(wú)可行解對(duì)偶單純形法適用范圍對(duì)偶單純形法的適