運籌學(xué)第三章對偶單純形法

運籌帷幄之中決勝千里之外對偶理論與靈敏度分析第二章對偶理論與靈敏度分析第一節(jié)對偶問題的提出第二節(jié)線性規(guī)劃的對偶理論第三節(jié)對偶問題的經(jīng)濟解釋第四節(jié)對偶單純形法【例2-1】某家電廠利用現(xiàn)有資源生產(chǎn)兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表：設(shè)備A設(shè)備B調(diào)試工序利潤（元）0612521115時24時5時產(chǎn)品Ⅰ產(chǎn)品ⅡD第一節(jié)對偶問題的提出如何安排生產(chǎn)，使獲利最多？廠家設(shè)

Ⅰ產(chǎn)量––––Ⅱ產(chǎn)量––––

設(shè)：設(shè)備A——

元／時

設(shè)備B––––

元／時

調(diào)試工序––––

元／時承租

付出的代價最小，

且對方能接受。出讓代價應(yīng)不低于用同等數(shù)量的資源自己生產(chǎn)的利潤。設(shè)備A設(shè)備B調(diào)試工序利潤（元）0612521115時24時5時ⅠⅡD廠家能接受的條件：出讓代價應(yīng)不低于用同等數(shù)量的資源自己生產(chǎn)的利潤。收購方的意愿：廠家對偶問題原問題承租廠家一對對偶問題第二節(jié)線性規(guī)劃的對偶理論一﹑原問題與對偶問題的關(guān)系二﹑對偶問題的基本性質(zhì)一﹑原問題與對偶問題的關(guān)系1﹒對稱式的對偶“≤”不等式約束條件的原問題與“≥”不等式約束條件的對偶問題，稱為對稱式的一對對偶問題。原問題：maxz=c1x1+c2x2+…+cnxn

a11

a12…a1n

am1

am2…amn·········x1xn···b1bm···≤

x1，x2，…，xn≥0對偶問題：minω=b1y1+b2y2+…+bmym

a11

a12…a1n

am1

am2…amn·········≥

y1，y2，…，ym≥0(y1,y2,…,ym)(c1,c2,…,cn)maxz=CXAX≤bX≥0minω=YbYA≥CY≥0

n個變量，m個約束條件

m個變量，n個約束條件2﹒約束條件全部為“=”的對偶maxz=CXAX＝bX≥0原問題：maxz=CXAX≤bX≥0AX≥b等價maxz=CXAX≤bX≥0－AX≤－bmaxz=CXX≥0A－AX≤b－bminω=(Y1,Y2)Y1,Y2≥0A－A≥Cb－b(Y1,Y2)其中

Y1=(y1,y2,…ym)，Y2=(ym+1,ym+2,…y2m)等價等價minω=YbY為無約束YA≥Cminω=(Y1－Y2)bY1,Y2≥0(Y1－Y2)A≥C令Y=(Y1－Y2)對偶問題對偶問題3﹒約束條件為“≥”的對偶maxz=CXAX≥bX≥0原問題：maxz=CX－AX≤－

bX≥0minω=Y1(－b)Y1(－A)≥CY1≥0minω=YbYA≥CY≤0等價對偶問題令Y=

－Y1對偶問題4﹒變量≤0的對偶maxz=CXAX≤bX≤0原問題：令X=

－X1maxz=C(－X1)A(－X1)≤bX1≥0maxz=(－C)X1(－A)X1≤bX1≥0等價minω=YbY

(－A)≥－CY≥0minω=YbY

A≤CY≥0對偶問題對偶問題等價5﹒變量無約束的對偶maxz=CXAX≤bX無約束原問題：令X=X1－X2X1，X2≥0maxz=CX1－CX2X1,X2≥0AX1－AX2≤bmaxz=(C,－C)X1,X2≥0≤bX1X2(A,－A)X1X2等價minω=YbY≥0Y(A,－A)≥(C,－C)對偶minω=YbYA≥CY≥0－YA≥－Cminω=YbYA

＝CY≥0minω=YbYA≥CY≥0YA≤C等價等價等價對偶問題6﹒原問題與對偶問題的關(guān)系表原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標函數(shù)maxzn個變量變量≥0變量≤0變量無約束目標函數(shù)minω

n個約束條件約束≥約束≤約束=m個約束條件約束≥約束≤約束=約束條件右端項目標函數(shù)變量系數(shù)m個變量變量≤0變量≥0變量無約束目標函數(shù)變量系數(shù)約束條件右端項【例2-2】試求下述線性規(guī)劃問題的對偶問題（P）與(D)的關(guān)系對應(yīng)表：原(對偶)問題對偶(原)問題目標函數(shù)max目標函數(shù)min目標函數(shù)系數(shù)約束方程常數(shù)列約束方程常數(shù)列目標函數(shù)系數(shù)變量個數(shù)n約束方程個數(shù)n約束方程個數(shù)m變量個數(shù)m約束方程≤變量≥0≥≤0=無符號約束變量≥0約束方程≥≤0≤無符號約束=系數(shù)矩陣A解：

（P）與(D)的關(guān)系對應(yīng)表：原(對偶)問題對偶(原)問題目標函數(shù)max目標函數(shù)min目標函數(shù)系數(shù)約束方程常數(shù)列約束方程常數(shù)列目標函數(shù)系數(shù)變量個數(shù)n約束方程個數(shù)n約束方程個數(shù)m變量個數(shù)m約束方程≤變量≥0≥≤0=無符號約束變量≥0約束方程≥≤0≤無符號約束=系數(shù)矩陣A【例2-3】

試求下述線性規(guī)劃原問題的對偶問題解：原問題的對偶問題【課堂練習(xí)】（P）與(D)的關(guān)系對應(yīng)表：原問題對偶問題目標函數(shù)max目標函數(shù)min目標函數(shù)系數(shù)約束方程常數(shù)列約束方程常數(shù)列目標函數(shù)系數(shù)變量個數(shù)n約束方程個數(shù)n約束方程個數(shù)m變量個數(shù)m約束方程≤變量≥0≥≤0=無符號約束變量≥0約束方程≥≤0≤無符號約束=系數(shù)矩陣A構(gòu)建對偶問題的規(guī)則原始問題的目標對偶問題目標約束類型變量符號最大化極小化>=無限制最小化極大化<=無限制要求：1、將所有約束轉(zhuǎn)換成等式；2、將所有決策變量轉(zhuǎn)換成大于等于?；仡櫍涸瓎栴}與對偶問題的關(guān)系表原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標函數(shù)maxzn個變量變量≥0變量≤0變量無約束目標函數(shù)minω

n個約束條件約束≥約束≤約束=m個約束條件約束≥約束≤約束=約束條件右端項目標函數(shù)變量系數(shù)m個變量變量≤0變量≥0變量無約束目標函數(shù)變量系數(shù)約束條件右端項二﹑對偶問題的基本性質(zhì)1﹒對稱性：對偶問題的對偶問題是原問題。2﹒弱對偶性：若X(0)是原問題的可行解，Y(0)是對偶問題的可行解，則存在CX(0)≤Y(0)b。3﹒無界性：若原問題無界解，則其對偶問題無可行解。4﹒最優(yōu)性：若X(0)是原問題的可行解，Y(0)是對偶問題的可行解，且CX(0)=Y(0)b，則X(0)，Y(0)是最優(yōu)解。5﹒對偶定理：若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解；且目標函數(shù)值相等。6﹒互補松弛性：若X(0)是原問題的可行解，Y(0)是對偶問題的可行解，則YsX(0)=0和Y(0)Xs=0當且僅當X(0)，Y(0)是最優(yōu)解。其中Xs和Ys分別為原問題和對偶問題的松弛變量的可行解.【例2-4】已知線性規(guī)劃問題minw=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x5≥42x1-x2+3x3+x4+x5≥3xj≥0，j=1，2，…，5已知其對偶問題的最優(yōu)解為y1*=4/5，y2*=3/5；z=5。試用對偶理論找出原問題的最優(yōu)解。【例2-4】已知線性規(guī)劃問題解：先寫出它的對偶問題maxz=4y1+3y2y1+2y2≤2①y1-y2≤3②2y1+3y2≤5③y1+y2≤2④3y1+y2≤3⑤y1，y2≥0【例2-4】已知線性規(guī)劃問題將y1*=4/5,y2*=3/5的值代入約束條件，得②=1/5<3，③=17/5<5，④=7/5<2

它們?yōu)閲栏癫坏仁?；由互補松弛性得

x2*=x3*=x4*=0。因y1，y2≥0；原問題的兩個約束條件應(yīng)取等式，故有

x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原問題的最優(yōu)解為

X*=(1，0，0，0，1)T；w*=51、原始問題是利潤最大化的生產(chǎn)計劃問題單位產(chǎn)品的利潤（元/件）產(chǎn)品產(chǎn)量（件）總利潤（元）資源限量（噸）單位產(chǎn)品消耗的資源（噸/件）剩余的資源（噸）消耗的資源（噸）第三節(jié)對偶問題的經(jīng)濟解釋2、對偶問題資源限量（噸）資源價格（元/噸）總利潤（元）對偶問題是資源定價問題，對偶問題的最優(yōu)解y1、y2、...、ym稱為m種資源的影子價格（ShadowPrice）原始和對偶問題都取得最優(yōu)解時，最大利潤maxz=minw3、資源影子價格的性質(zhì)從對偶定理可知，當達到最優(yōu)解時，原問題和對偶問題的目標函數(shù)值相等，即z=CX(0)=Y(0)b=CBB-1b.也即z=CX(0)=Y(0)b=CBB-1b=y1(0)b1+y2(0)b2

+…+ym(0)bm

其中X(0),Y(0)分別是原問題和對偶問題的最優(yōu)解?，F(xiàn)在考慮在最優(yōu)解處，常數(shù)項bi的微小變動對目標函數(shù)值的影響(不改變原來的最優(yōu)基).求z對bi的偏導(dǎo)數(shù)，可得：y1(0)

＝?z—?b1,y2(0)

＝?z—?b2,ym(0)

＝?z—?bm,…這說明，若原問題的某一約束條件的右端常數(shù)項bi增加一個單位，則由此引起的最優(yōu)目標函值的增加量，就等于該約束條件相對應(yīng)的對偶變量的最優(yōu)值。最優(yōu)變量yi(0)的值，就相當于對單位第I種資源在實現(xiàn)最大利潤時的一種估價。這種估價是針對具體企業(yè)具體產(chǎn)品而存在的一種特殊價格，稱它為“影子價格”?！纠?-3】

求下列問題的最優(yōu)解。

影價格及其經(jīng)濟解釋

第四節(jié)對偶單純形法6﹒(LP)的檢驗數(shù)的相反數(shù)對應(yīng)于(DP)的一個基解，其中第j個決策變量xj的檢驗數(shù)的相反數(shù)對應(yīng)于(DP)中第j個松弛變量ysj的解，第i個松弛變量xsi的檢驗數(shù)的相反數(shù)對應(yīng)于第i個對偶變量yi的解。ＸＢＸＮＸs0Ys1CN1－CBB-1N1﹣Ys2－CBB-1﹣Y二﹑對偶問題的基本性質(zhì)【例2-4】線性規(guī)劃（1）用單純形方法求最優(yōu)解；（2）求每步迭代對應(yīng)對偶問題的基本解。cj6-2100CBXBbx1x2x3x4x500x4x524[2]1﹣10241001

δj

6-210060x1x51310﹣1/2[1/2]131/2-1/201

δj

01-5-306-2x1x2461001460-112

δj

00-11-2-2123解：原問題與對偶問題解之間的對應(yīng)關(guān)系指出：在單純形表中進行迭代時，在b列中得到的是原問題的基可行解，而在檢驗數(shù)行得到的是對偶問題的基解。通過逐步迭代，當在檢驗數(shù)行得到對偶問題的解也是基可行解時，已得到最優(yōu)解。即原問題與對偶問題都是最優(yōu)解。根據(jù)對偶問題的對稱性，可以這樣考慮：若保持對偶問題的解是基可行解，即cj?CBB-1Pj≤0，而原問題在非可行解的基礎(chǔ)上，通過逐步迭代達到基可行解，這樣也得到了最優(yōu)解。其優(yōu)點是原問題的初始解不一定是基可行解，可從非基可行解開始迭代。設(shè)原問題為

maxz=CX

AX=b

X≥0又設(shè)B是一個基。不失一般性，令B=(P1，P2，…，Pm)，它對應(yīng)的變量為XB=(x1，x2，…,xm)。當非基變量都為零時，可以得到XB=B-1b。若在B-1b中至少有一個負分量，設(shè)(B-1b)i＜0，并且在單純形表的檢驗數(shù)行中的檢驗數(shù)都為非正，即對偶問題保持可行解。每次迭代是將基變量中的負分量xl取出，去替換非基變量中的xk，經(jīng)基變換，所有檢驗數(shù)仍保持非正。從原問題來看，經(jīng)過每次迭代，原問題由非可行解往可行解靠近。當原問題得到可行解時，便得到了最優(yōu)解。2﹒對偶單純形法的計算步驟⑴列出初始單純形表⑵最優(yōu)性檢驗

根據(jù)線性規(guī)劃問題，確定一個對偶可行的基解，列出初始單純形表。

檢查b列的數(shù)，若都為非負，則已得到最優(yōu)解。停止計算。若b列的數(shù)中，還有分量為負數(shù)，則進行下一步計算。⑶確定換出變量

按min{(B-1b)i|(B-1b)i<0}=(B-1b)l

確定xl為換出變量。⑷確定換入變量①如果xl所在行各系數(shù)alj

(j=1,2,…n).都有alj>0，則無可行解，停止計算。②如果有alj<0(

j=1,2,…n),則計算ck－zkθ＝mincj－zj———

alj|alj<０＝———

alk確定xk為換入變量，且保持得到的對偶問題的解是基可行解。⑸迭代運算

以alk為主元素，對單純形表進行迭代運算，得到新單純表。重復(fù)⑵—⑸【例2-5】用對偶單純形法求解x1+2x2+x3≥32x1－x2+3x3≥4minω=2x1+3x2+4x3x1,x2,x3≥0﹣x1﹣2x2﹣x3+

x4=﹣3﹣2x1+x2﹣3x3+x5=﹣4maxz=﹣2x1﹣3x2﹣4x3x1,x2,x3x4,x5≥0解：cj﹣2﹣3﹣400CBXBbx1x2x3x4x500x4x5﹣3﹣4﹣1[﹣2]﹣21﹣1﹣31001

δj

﹣2﹣3﹣400θ1－4/3其中x4,x5為松弛變量cj﹣2﹣3﹣400CBXBbx1x2x3x4x50﹣2x4x1﹣1201[﹣5/2]﹣1/21/23/210﹣1/2﹣1/2

δj

0﹣4﹣10﹣1θ﹣8/5﹣﹣2cj﹣2﹣3﹣400CBXBbx1x2x3x4x5﹣3﹣2x2x12/511/50110﹣1/57/5﹣2/5﹣1/51/5﹣2/5

δj

00﹣9/5﹣8/5﹣1/5原最優(yōu)X*=(11/5,2/5,0,0,0)T，對偶最優(yōu)Y*=(8/5,1/5)從以上求解過程可以看到對偶單純形法有以下優(yōu)點：(1)初始解可以是非可行解，當檢驗數(shù)都為負數(shù)時就可以進行基的變換，這時不需要加入人工變量，因此可以簡化計算。(2)當變量多于約束條件，對這樣的線性規(guī)劃問題用對偶單純形法計算可以減少計算工作量，因此對變量較少，而約束條件很多的線性規(guī)劃問題，可先將它變換成對偶問題，然后用對偶單純形法求解。(3)在靈敏度分析及求解整數(shù)規(guī)劃的割平面法中，有時需要用對偶單純形法，這樣可使問題的處理簡化。對偶單純形法的局限性主要是，對大多數(shù)線性規(guī)劃問題，很難找到一個對偶問題初始可行基，因而這種方法在求解線性規(guī)劃問題時很少單獨應(yīng)用。對偶單純形法的計算步驟（min）⑴列出初始單純形表⑵最優(yōu)性檢驗

根據(jù)線性規(guī)劃問題，確定一個對偶可行的基解，列出初始單純形表。

檢查b列的數(shù)，