第二章線性規(guī)劃問(wèn)題的對(duì)偶與靈敏度分析

第二章線性規(guī)劃的對(duì)偶與靈敏度分析§1線性規(guī)劃的對(duì)偶問(wèn)題§2對(duì)偶問(wèn)題的基本性質(zhì)§4對(duì)偶單純形法§5靈敏度分析2/4/20231線性規(guī)劃的對(duì)偶問(wèn)題概念、理論及經(jīng)濟(jì)意義線性規(guī)劃的對(duì)偶單純形法線性規(guī)劃的靈敏度分析本章內(nèi)容重點(diǎn)2/4/20232§1線性規(guī)劃的對(duì)偶問(wèn)題提出問(wèn)題(LP1)maxz=2x1+x2

st.5x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0一個(gè)公司要收購(gòu)美佳公司的資源(設(shè)備)，問(wèn)它至少要付出多大的代價(jià)？設(shè)備A設(shè)備B調(diào)試工序假設(shè)y1、y2、y3分別代表單位時(shí)間設(shè)備A、設(shè)備B、調(diào)試工序的出讓價(jià)y1y2y32/4/20233美佳出價(jià)：出讓價(jià)應(yīng)不低于用同等數(shù)量的資源由自己組織生產(chǎn)活動(dòng)時(shí)所獲得的利潤(rùn)6y2+y3≥25y1+2y2+y3≥1y1,y2,y3≥0買家還價(jià)：買家在滿足上述條件的前提下，希望用最小的代價(jià)獲得美佳公司的全部資源Minω＝15y1+24y2+5y32/4/20234(LP2)Minω＝15y1+24y2+5y3st.6y2+y3≥25y1+2y2+y3≥1y1,y2,y3

≥0一個(gè)新的線性規(guī)劃稱(LP1)為原問(wèn)題，(LP2)為對(duì)偶問(wèn)題當(dāng)LP中的變量均具有非負(fù)約束，其約束條件當(dāng)目標(biāo)函數(shù)求極大時(shí)均取“≤”號(hào)，而當(dāng)目標(biāo)函數(shù)求極小時(shí)均取“≥”時(shí)，則稱這樣的LP問(wèn)題具有對(duì)稱形式2/4/20235一般規(guī)律(1)

原問(wèn)題有n個(gè)變量，m個(gè)約束，對(duì)偶問(wèn)題有m個(gè)變量，n個(gè)約束。原問(wèn)題的目標(biāo)函數(shù)求極大，對(duì)偶問(wèn)題的目標(biāo)函數(shù)求極小(2)

原問(wèn)題的目標(biāo)函數(shù)中變量的系數(shù)為對(duì)偶問(wèn)題的約束條件的常數(shù)項(xiàng)，反之亦然(3)

原問(wèn)題與對(duì)偶問(wèn)題的約束方程的系數(shù)矩陣互為轉(zhuǎn)置2/4/20236(LP1)Maxz=CX

s.t.

AX≤b

X≥0(LP2)Minω=

bT

Ys.t.AT

Y≥CTY≥0

非對(duì)稱形式的對(duì)偶問(wèn)題一般稱不具有對(duì)稱形式的一對(duì)線性規(guī)劃為非對(duì)稱形式的對(duì)偶規(guī)劃。對(duì)于非對(duì)稱形式的規(guī)劃，一般事先轉(zhuǎn)換成對(duì)稱形式，然后按對(duì)應(yīng)規(guī)則寫出其對(duì)偶問(wèn)題2/4/20237Maxz=x1

+4x2

+3x3St.2x1+3x2－5x3

≤23x1－x2+6x3

≥1

x1+x2+x3=4x1≥0,x2≤0,x3無(wú)約束y1y3’y2’Maxz=x1

+4x2

+3x3St.2x1+3x2－5x3

≤2

－3x1＋x2－

6x3

≤－1

x1+x2+x3≤

4

－x1－x2－x3≤－4x1≥0,x2≤0,x3無(wú)約束Maxz=x1

－4x’2

+3x’3－3x’’3St.2x1－3x’2－5x’3+5x’’3≤2

－3x1－x2－

6’x3＋6x’’3

≤－1

x1－x2+x’3－x’’3≤

4

－x1+x2－x’3+x’’3≤－4x1,x’2,x’3,x’’3≥0y3’’每個(gè)約束方程對(duì)應(yīng)一個(gè)對(duì)偶變量。原則：是“≤”的方程直接對(duì)應(yīng)y；是“≥”的對(duì)應(yīng)y’；是“＝”的分別對(duì)應(yīng)y’,y’’2/4/20238Minω=2y1-y’2+4y’3-4y’’3St.2y1-3y’2+y’3-y’’3≥1-3y1-y’2-y’3+y’’3≥-4-5y1-6y’2+y’3-y’’3≥35y1+6y’2-y’3+y’’3≥-3y1,y’2,y’3,y’’3≥0Minω=2y1+y2+4y3St.2y1+3y2+y3≥13y1-y2+y3≤4-5y1+6y2+y3=3y1≥0,y2≤0,y3無(wú)約束令y2=－y’2y3=y’3－y’’3Maxz=x1

+4x2

+3x3St.2x1+3x2－5x3

≤23x1－x2+6x3

≥1

x1+x2+x3=4x1≥0,x2≤0,x3無(wú)約束原問(wèn)題對(duì)偶問(wèn)題2/4/20239也可以直接利用對(duì)應(yīng)關(guān)系寫出線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題Maxz=－5x1

－6x2

－7x3St.－x1+5x2－3x3

≥15

－5x1－6x2+10x3

≤

20

x1－x2－x3=－5x1≤

0,x2≥0,x3無(wú)約束Minω=15y1+20y2－5y3St.－y1－5y2+y3≥－55y1－6y2－y3≤－6

－3y1+10y2－y3=－7y1≤0,y2≥

0,y3無(wú)約束掌握兩者之間的對(duì)應(yīng)系：對(duì)偶問(wèn)題的變量對(duì)應(yīng)原問(wèn)題的約束方程，對(duì)偶問(wèn)題的約束方程對(duì)應(yīng)原問(wèn)題的變量（見表2-2）y1y2y3x1x2x32/4/202310§2對(duì)偶問(wèn)題的基本性質(zhì)一、單純形法計(jì)算的矩陣表示松弛變量m×m單位矩陣單純形法計(jì)算時(shí)，總?cè)為初始基，對(duì)應(yīng)的基變量為Xs。迭代若干步后基變量為XB,XB在初始單純形表中的系數(shù)矩陣為B，將A中去掉B后的剩余部分記為N(具體情況見下表)2/4/202311非基變量基變量0XsbXBXNBNXsIσjcB

cN0初始單純形表迭代若干步基變量非基變量cB

XBB－1bXBIXNXsB－1NB－1

σj0cN－cBB－1N

-cBB－1最終單純形表2/4/202312

21000

x1x2x3x4x5cjCB

基(變量)bx3x4x500015245

05100

62010

11001σj21000cj21000CB

基(變量)b

x1x2x3x4x50x315/2

0015/4－15/22x17/2

1001/4－1/21x23/2

010－1/43/2

σj

000－1/4－1/2B-1B2/4/202313五點(diǎn)結(jié)論（2）初始單純形表中的常數(shù)項(xiàng)是b，最終單純形表中B－1b（3）初始單純形表中系數(shù)矩陣為[A,I]=[B,N,I]，最終單純形表中系數(shù)矩陣

[B－1A,B－1]=[B－1B,B－1N,B－1I]=[I,B－1N,B－1]（1）對(duì)應(yīng)初始單純形表中的單位矩陣I，最終單純形表中為B－1(非常重要的指標(biāo))2/4/202314（4）初始單純形表中變量Xj的系數(shù)向量為Pj，最終單純形表中為

P’j

=B－1Pj(1)（5）當(dāng)B為最優(yōu)基時(shí)，在最終單純形表中應(yīng)有

cN－cBB－1N≤0(2)

－cBB－1≤0(3)因?yàn)閄B的檢驗(yàn)數(shù)可寫為

cB－cBI=cB-

cBB-1B=0(4)故（4）（2）可以合并寫成(5)，(3)直接寫成(6)

c－cBB－1

A≤0(5)

－cBB－1≤0(6)2/4/202315如果令YT=cBB－1(單純形乘子)，則(5)、(6)可寫為(7)原問(wèn)題的對(duì)偶問(wèn)題從(7)式可以看出，此時(shí)原問(wèn)題的最優(yōu)解對(duì)應(yīng)的單純形表中，檢驗(yàn)數(shù)若取相反數(shù)恰好是其對(duì)偶問(wèn)題的一個(gè)可行解！而且有原問(wèn)題的最優(yōu)解當(dāng)原問(wèn)題為最優(yōu)解時(shí)，這時(shí)其對(duì)偶問(wèn)題有可行解，且兩者具有相同的目標(biāo)函數(shù)值2/4/202316項(xiàng)目原問(wèn)題變量原問(wèn)題松弛變量x1x2x3x4x5x3

15/2x17/2x23/200100115/4-15/201/4-1/20-1/43/2σj000-1/4-1/2對(duì)偶問(wèn)題的松弛變量對(duì)偶問(wèn)題變量y4y5y1y2y3項(xiàng)目對(duì)偶問(wèn)題變量對(duì)偶問(wèn)題松弛變量y1y2y3

y4y5y2

1/4y31/2-5/41015/201-1/41/41/2-3/2σj15/2007/23/2原問(wèn)題松弛變量原問(wèn)題變量x3x4x5x1x22/4/202317定理1(弱對(duì)偶定理）若x,y分別為原問(wèn)題與對(duì)偶問(wèn)題的可行解則恒有

cTx≤bTy二、對(duì)偶問(wèn)題的基本性質(zhì)

定理2(最優(yōu)性定理)

若x,y分別原問(wèn)題與對(duì)偶問(wèn)題的可行解,且cTx=bTy

，那么x,y分別為原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解。2/4/202318

定理3(對(duì)偶定理)

若原問(wèn)題與對(duì)偶問(wèn)題均有可行解，那么它們均有最優(yōu)解,且最優(yōu)解的函數(shù)值相等。

定理4(互補(bǔ)松弛性定理)(比較重要)

若在線性規(guī)劃問(wèn)題的最優(yōu)解中,若對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則約束方程取嚴(yán)格等式；反之若約束方程取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。2/4/202319對(duì)偶單純形法的基本思想從對(duì)偶問(wèn)題的可行解出發(fā)，去尋求原問(wèn)題的最優(yōu)解，此時(shí)根據(jù)對(duì)偶定理，原—對(duì)偶問(wèn)題均有最優(yōu)解§4對(duì)偶單純形法2/4/202320

對(duì)偶單純形法的基本思路從原問(wèn)題的一個(gè)基解出發(fā)，此基解不一定可行，但它對(duì)應(yīng)著一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正），所以也可以說(shuō)是從一個(gè)對(duì)偶可行解出發(fā)；然后檢驗(yàn)原問(wèn)題的基解是否可行，即是否有負(fù)的分量？如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)基解，此基解又對(duì)應(yīng)著另一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正）。如果得到的基解的分量皆非負(fù)，則該基解為最優(yōu)解。也就是說(shuō)，對(duì)偶單純形法在迭代過(guò)程中始終保持對(duì)偶解的可行性（即檢驗(yàn)數(shù)非正），使原問(wèn)題的基解由不可行逐步變?yōu)榭尚?。?dāng)同時(shí)得到對(duì)偶問(wèn)題與原問(wèn)題的可行解時(shí)，便得到原問(wèn)題的最優(yōu)解。2/4/202321對(duì)偶單純形法在什么情況下使用：

應(yīng)用前提：有一個(gè)基，其對(duì)應(yīng)的基滿足:

①單純形表的檢驗(yàn)數(shù)全部非正（對(duì)偶可行）

②變量取值可有負(fù)數(shù)（非可行解）。

注：通過(guò)矩陣行變換運(yùn)算，使所有相應(yīng)變量取值均為非負(fù)數(shù)即得到最優(yōu)單純型表。2/4/202322

1.建立初始對(duì)偶單純形表,對(duì)應(yīng)一個(gè)基解,所有檢驗(yàn)數(shù)均非正,轉(zhuǎn)2；

2.若b’≥0,則得到最優(yōu)解,停止;否則,若有bk<0則選k行的基變量為出基變量,轉(zhuǎn)33.若所有akj’≥0(j=1,2,…,n)，則原問(wèn)題無(wú)可行解,停止;否則,若有akj’<0則選

=min{j’/

akj’┃akj’<0，j=1,2,…,n}=r’/akr’那么

xr為進(jìn)基變量,轉(zhuǎn)4；

4.以akr’為主元素,作矩陣初等行變換使其變?yōu)?,該列其他元變?yōu)?,轉(zhuǎn)2。對(duì)偶單純形法求解線性規(guī)劃問(wèn)題計(jì)算過(guò)程2/4/202323例3.2：用對(duì)偶單純形法求解線性規(guī)劃問(wèn)題：

Minf=15y1+24y2+5y3

S.t.

6y2+y3≥25y1+2y2+y3≥1

y1,y2,y3≥0Maxz=－15y1－24y2－

5y3

S.t.

6y2+y3

－y4=25y1+2y2+y3

－y5=1

y1,y2,y3,y4,y5≥0Maxz=－15y1－24y2－

5y3

S.t.－6y2

－y3

＋y4=－2

－5y1－2y2－y3＋y5=－1

y1,y2,y3,y4,y5≥02/4/202324cj－15－24－500CB

基

by1y2y3y4y50y4

－2

0[－6]－1100y5

－1

－5－2－101

σj－15－24－500－24y21/3

011/6－1/60

0y5

－1/3

－50[－2／3]－1／31

σj－150－1－40－24y21／4－5／410－1／41／4－5y31／2

15／2011／2－3／2

σj－15／200－7／2－3／2對(duì)偶問(wèn)題的最優(yōu)解X=(7/2,3/2,15/2,0,0)T原問(wèn)題的最優(yōu)解Y=(0,1/4,1/2,0,0)Tx1x2x3x4x52/4/202325對(duì)偶單純形法的適用范圍對(duì)偶單純形法適合于解如下形式的線性規(guī)劃問(wèn)題2/4/202326是是是是否否否否所有所有得到最優(yōu)解計(jì)算計(jì)算對(duì)應(yīng)原規(guī)劃的基本解是可行的對(duì)應(yīng)原規(guī)劃的檢驗(yàn)數(shù)為非正所有所有計(jì)算計(jì)算以主元素為中心進(jìn)行迭代以主元素為中心進(jìn)行迭代停沒(méi)有最優(yōu)解沒(méi)有最優(yōu)解單純形法對(duì)偶單純形法2/4/202327進(jìn)一步理解最優(yōu)單純性表中各元素的含義考慮問(wèn)題

Maxz=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn

≤b1a21x1+a22x2+…+a2nxn

≤b2

….

am1x1+am2x2+…+amnxn

≤bmx1，x2，…，xn≥0§5靈敏度分析cj,bi,aij,m,n參數(shù)2/4/202328當(dāng)這些參數(shù)中的一個(gè)或幾個(gè)發(fā)生變化時(shí)，線性規(guī)劃問(wèn)題的最優(yōu)解會(huì)發(fā)生什么變化，或者這些參數(shù)在一個(gè)多大范圍內(nèi)變化時(shí)，問(wèn)題的最優(yōu)解不變？所要解決的問(wèn)題重要公式1、將參數(shù)的改變通過(guò)下面的公式計(jì)算后直接反映到最終單純形表上2、檢查原問(wèn)題是否仍有可行解2/4/2023294、按下表所列情況得出結(jié)論或決定繼續(xù)計(jì)算的步驟原問(wèn)題對(duì)偶問(wèn)題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解非可行解非可行解可行解非可行解可行解非可行解問(wèn)題的最優(yōu)解或最優(yōu)基不變用單純形法繼續(xù)迭代求最優(yōu)解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解引進(jìn)人工變量，重新計(jì)算3、檢查對(duì)偶問(wèn)題是否仍有可行解2/4/202330一、價(jià)值系數(shù)cj發(fā)生變化線性規(guī)劃問(wèn)題中變量系數(shù)cj

的變化僅僅影響到檢驗(yàn)數(shù)的變化，所以將cj

的變化直接反映到最終單純形表中，此時(shí)只會(huì)出現(xiàn)如上表中的前兩種情況cj21000CB

基(變量)b

x1x2x3x4x50x315/2

0015/4－15/22x17/2

1001/4－1/21x23/2

010－1/43/2

σj

000－1/4－1/21.521/8-4/91.522/4/202331cj21000CB

基(變量)b

x1x2x3x4x50x46

005/41－61.5x12

10－1/5012x23011/500

σj

00－1/100－2/3因?yàn)樽兞縳4對(duì)應(yīng)的檢驗(yàn)數(shù)大于零，屬于第二種情況，所以用單純形法繼續(xù)迭代最優(yōu)解XT=(2,3)T2/4/202332二、常數(shù)項(xiàng)b發(fā)生變化常數(shù)項(xiàng)的變化反映到最終單純形表中將引起b列數(shù)字的變化，所以可能出現(xiàn)第一或第三兩種情況。若是第一種情況，問(wèn)題的最優(yōu)基不變，變化后的b列值為最優(yōu)解；出現(xiàn)第三種情況時(shí)，用對(duì)偶單純形法繼續(xù)找出最優(yōu)解2/4/202333cj21000CB

基(變量)b

x1x2x3x4x50x315/2

0015/4－15/22x17/2

1001/4－1/21x23/2

010－1/43/2

σj

000－1/4－1/21524515325轉(zhuǎn)下頁(yè)2/4/202334cj21000CB

基(變量)b

x1x2x3x4x50x335/2

0015/4－15/22x111/2

1001/4－1/21x2

－1/2

010[－1/4]3/2

σj

000－1/4－1/2用對(duì)偶單純形法cj21000CB

基(變量)b

x1x2x3x4x50x315051002x15110010x42

0－401－6

σj

0－100－22/4/202335三、增加一個(gè)變量xj的分析增加一個(gè)變量x’j在實(shí)際問(wèn)題中反映為增加一個(gè)新的產(chǎn)品。其分析步驟為例如，美佳公司計(jì)劃推出新產(chǎn)品III，生產(chǎn)每件產(chǎn)品所需設(shè)備A、B及調(diào)試工序的時(shí)間分別為3、4、2小時(shí)，該產(chǎn)品的盈利為3元／件。試分析新的生產(chǎn)計(jì)劃2/4/202336設(shè)該公司生產(chǎn)新產(chǎn)品x6，則有c6=3P6=(3,4,2)Tcj210003CB

基(變量)b

x1x2x3x4x5x60x315/2

0015/4－15/2－72x17/2

1001/4－1/201x23/2

010－1/43/22

σj

000－1/4－1/212/4/202337cj210003CB

基(變量)b

x1x2x3x4x5x60x315/2

0015/4－15/2－72x17/2

1001/4－1/201x23/2

010－1/43/2［2］

σj

000－1/4－1/21cj210003CB

基(變量)b

x1x2x3x4x5x60x351/4

07/213/8－9/402x17/2

1001/4－1/203x63/4

01/20－1/83/41

σj

0－1／20－1/8－5/40用單純形法繼續(xù)迭代2/4/202338四、分析參數(shù)aij的變化1、變量xj在最終單純行表中為非基變量，參照上一段算法2、變量xj在最終單純行表中為基變量，則相應(yīng)的B和B-1會(huì)發(fā)生變化例如，在美佳公司，若產(chǎn)品II每件所需設(shè)備A、B及調(diào)試工序的時(shí)間分別為8、4、1小時(shí)，該產(chǎn)品的盈利為3元／件。試分析新的生產(chǎn)計(jì)劃先將生產(chǎn)工時(shí)變化后的新產(chǎn)品II看成是一種新產(chǎn)品，生產(chǎn)量記為x’2，計(jì)算步驟與上一段一樣2/4/202339cj210003CB

基(變量)b

x1x2x3x4x5x’20x315/2

0015/4－15/211/22x17/2

1001/4－1/21/21x23/2

010－1/43/2[1/2]

σj

000－1/4－1/23/2因?yàn)閤2已經(jīng)變換為x’2，故用x’2替換出x2，并在下一個(gè)表中不保留x22/4/202340cj23000CB

基(變量)b

x1x’2x3x4x50x3

-9

0014－242x12

1001/2－23x’23

010－1/23

σj

0001/2－5cj23000-MCB

基(變量)b

x1x’2x3x4x5x6-Mx6900-1-4[24]12x12

1001/2－203x’23

010－1/230

σj

00-M1/2-4M－5+24M0添加人工變量原、對(duì)偶問(wèn)題均為非可行解2/4/202341cj23000-MCB

基(變量)b

x1x’2x3x4x5x60x53/800-1/24-1/611/242x111/410-1/121/601/123x’215/8011/800-1/8

σj

00-5/24-1/30－M+5/24結(jié)論：最優(yōu)生產(chǎn)計(jì)劃為生產(chǎn)家電I11/4件,家電II15/8件2/4/202342增加約束一個(gè)之后，應(yīng)把最優(yōu)解帶入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入1個(gè)新的非負(fù)變量（原約束若是小于等于形式可引入非負(fù)松弛變量，否則引入非負(fù)人工變量），并通過(guò)矩陣行變換把對(duì)應(yīng)基變量的元素變?yōu)?，進(jìn)一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼?。五、增加一個(gè)約束條件的分析2/4/202343例如，美佳公司生產(chǎn)的產(chǎn)品還須一道實(shí)驗(yàn)工序，家電I:3小時(shí)，家電II：2小時(shí)，又實(shí)驗(yàn)工序的生產(chǎn)能力為12小時(shí)。問(wèn)如何安排最優(yōu)生產(chǎn)計(jì)劃？增加的約束條件為3x1+2x2≤12將原最優(yōu)解代入，得3×7/2+2×3/2=27/2>12故原問(wèn)題的最優(yōu)解不是現(xiàn)在的最優(yōu)解假設(shè)≤12，則原問(wèn)題的最優(yōu)解是現(xiàn)在的最優(yōu)解，問(wèn)題結(jié)束2/4/202344將新的約束條件添加松弛變量3x1+2x2+x6=12以x6為基變量，將上式反映到最終單純形表中cj210000CB

基(變量)b

x1x2x3x4x5x60x315/2

0015/4－15/202x17/2

1001/4－1/201x23/2

010－1/43/200x612320001