對偶問題和運輸問題

對偶問題和運輸問題第1頁，共76頁，2023年，2月20日，星期一例3寫對偶問題Minz=2x1+3x2-5x3+x4

x1+x2-3x3+x4>=52x1+2x3-x4<=4

x2+x3+x4=6x1<=0,x2,x3>=0x4無約束

Maxz’=5y1+4y2+6y3y1+2y2>=0y1+y3<=0-3y1+2y2+y3<=-5y1-y2+y3=1y1>=0,y2<=0,y3無約束第2頁，共76頁，2023年，2月20日，星期一3.對偶定理(原問題與對偶問題解的關系）考慮（LP）和（DP）

定理3-1(弱對偶定理）

若x,y分別為（LP)和（DP）的可行解，那么cTx≤bTy。推論

若（LP）可行，那么（LP）無有限最優(yōu)解的充分必要條件是（LD）無可行解。1.線性規(guī)劃對偶問題第3頁，共76頁，2023年，2月20日，星期一

定理3-2(最優(yōu)性準則定理)

若x,y分別(LP),(DP)的可行解,且cTx=bTy，那么x,y分別為(LP)和(DP)的最優(yōu)解。

定理3-3(主對偶定理)

若(LP)和(DP)均可行那么(LP)和(DP)均有最優(yōu)解,且最優(yōu)值相等。以上定理、推論對任意形式的相應性規(guī)劃的對偶均有效1.線性規(guī)劃對偶問題第4頁，共76頁，2023年，2月20日，星期一4、原始問題和對偶問題最優(yōu)解之間的互補松弛關系minz=CTXs.t.AX-XS=bX,XS≥0maxy=bTWs.t.ATW+WS=CW,WS≥0minz=CTXs.t.AX≥bX≥0maxy=bTWs.t.ATW≤CW≥0對偶引進松弛變量引進松弛變量XTWS=0WTXS=0互補松弛關系X，XsW，Ws第5頁，共76頁，2023年，2月20日，星期一五、對偶的經(jīng)濟解釋1、原始問題是利潤最大化的生產(chǎn)計劃問題單位產(chǎn)品的利潤（元/件）產(chǎn)品產(chǎn)量（件）總利潤（元）資源限量（噸）單位產(chǎn)品消耗的資源（噸/件）剩余的資源（噸）消耗的資源（噸）第6頁，共76頁，2023年，2月20日，星期一2、對偶問題資源限量（噸）資源價格（元/噸）總利潤（元）對偶問題是資源定價問題，對偶問題的最優(yōu)解w1、w2、...、wm稱為m種資源的影子價格（ShadowPrice）原始和對偶問題都取得最優(yōu)解時，最大利潤maxz=miny第7頁，共76頁，2023年，2月20日，星期一3、資源影子價格的性質(zhì)影子價格越大，說明這種資源越是相對緊缺影子價格越小，說明這種資源相對不緊缺如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源的影子價格一定等于0第8頁，共76頁，2023年，2月20日，星期一影子價格的經(jīng)濟含義(1)影子價格是對現(xiàn)有資源實現(xiàn)最大效益時的一種估價企業(yè)可以根據(jù)現(xiàn)有資源的影子價格，對資源的使用有兩種考慮：第一，是否將設備用于外加工或出租，若租費高于某設備的影子價格，可考慮出租該設備，否則不宜出租。第二，是否將投資用于購買設備，以擴大生產(chǎn)能力，若市價低于某設備的影子價格，可考慮買進該設備，否則不宜買進。1.線性規(guī)劃對偶問題第9頁，共76頁，2023年，2月20日，星期一需要指出，影子價格不是固定不變的，當約束條件、產(chǎn)品利潤等發(fā)生變化時，有可能使影子價格發(fā)生變化。另外，影子價格的經(jīng)濟含義（2），是指資源在一定范圍內(nèi)增加時的情況，當某種資源的增加超過了這個“一定的范圍”時，總利潤的增加量則不是按照影子價格給出的數(shù)值線性地增加。這個問題還將在靈敏度分析一節(jié)中討論。1.線性規(guī)劃對偶問題第10頁，共76頁，2023年，2月20日，星期一5.由最優(yōu)單純形表求對偶問題最優(yōu)解標準形式：

Max

z=50x1+100x2

s.t.x1+x2+x3=3002x1+x2+x4=400

x2+x5=250

x1,x2,x3,x4,x5

≥01.線性規(guī)劃對偶問題第11頁，共76頁，2023年，2月20日，星期一maxz=CTXs.t.AX+XS=bX,XS≥0maxy=bTWs.t.ATW-WS=CW,WS≥0maxz=CTXs.t.AX≤bX≥0miny=bTWs.t.ATW≥CW≥0單純形表和對偶對偶問題原始問題引進松弛變量引進松弛變量第12頁，共76頁，2023年，2月20日，星期一maxz=CTXs.t.AX+XS=bX,XS≥0miny=bTWs.t.ATW-WS=CW,WS≥0WT=CBTB-1WST=WTA-CT第13頁，共76頁，2023年，2月20日，星期一-cBTB-1IB=(p1,p4,p2)oTB-1最優(yōu)解

x1=50x2=250x4=50影子價格

y1=50y2=0y3=50,B-1對應的檢驗數(shù)

T=cBTB-1。1.線性規(guī)劃對偶問題第14頁，共76頁，2023年，2月20日，星期一例3.2：求解線性規(guī)劃問題：

標準化：Maxz=-2x1-3x2-4x3s.t.

-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4

x1,x2,x3,x4,x5≥0Minf=2x1+3x2+4x3

S.t.x1+2x2+x3≥32x1-x2+x3≥4

x1,x2,x3≥0

2.對偶單純形法第15頁，共76頁，2023年，2月20日，星期一

對偶單純形法的基本思想對偶單純形法的基本思想是：從原規(guī)劃的一個基本解出發(fā)，此基本解不一定可行，但它對應著一個對偶可行解（檢驗數(shù)非正），所以也可以說是從一個對偶可行解出發(fā)；然后檢驗原規(guī)劃的基本解是否可行，即是否有負的分量，如果有小于零的分量，則進行迭代，求另一個基本解，此基本解對應著另一個對偶可行解（檢驗數(shù)非正）。2.對偶單純形法第16頁，共76頁，2023年，2月20日，星期一

如果得到的基本解的分量皆非負則該基本解為最優(yōu)解。也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性（即檢驗數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚?，當同時得到對偶規(guī)劃與原規(guī)劃的可行解時，便得到原規(guī)劃的最優(yōu)解。2.對偶單純形法第17頁，共76頁，2023年，2月20日，星期一

對偶單純形法在什么情況下使用：

應用前提：有一個基，其對應的基滿足:①單純形表的檢驗數(shù)行全部非正（對偶可行）；②變量取值可有負數(shù)（非可行解）。

注：通過矩陣行變換運算，使所有相應變量取值均為非負數(shù)即得到最優(yōu)單純形表。2.對偶單純形法第18頁，共76頁，2023年，2月20日，星期一

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

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

=min{j’/akj’┃akj’<0}=r’/akr’那么

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

4.以akr’為轉(zhuǎn)軸元,作矩陣行變換使其變?yōu)?,該列其他元變?yōu)?,轉(zhuǎn)2。對偶單純形法求解線性規(guī)劃問題過程：2.對偶單純形法第19頁，共76頁，2023年，2月20日，星期一例3.2：求解線性規(guī)劃問題：

標準化：Maxz=-2x1-3x2-4x3s.t.

-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4

x1,x2,x3,x4,x5≥0Minf=2x1+3x2+4x3

S.t.x1+2x2+x3≥32x1-x2+x3≥4

x1,x2,x3≥0

2.對偶單純形法第20頁，共76頁，2023年，2月20日，星期一表格對偶單純形法2.對偶單純形法第21頁，共76頁，2023年，2月20日，星期一單純形法和對偶單純形法步驟是是是是否否否否所有所有得到最優(yōu)解計算計算典式對應原規(guī)劃的基本解是可行的典式對應原規(guī)劃的基本解的檢驗數(shù)所有所有計算計算以為中心元素進行迭代以為中心元素進行迭代停沒有最優(yōu)解沒有最優(yōu)解單純形法對偶單純形法<第22頁，共76頁，2023年，2月20日，星期一

對偶單純形法的適用范圍對偶單純形法適合于解如下形式的線性規(guī)劃問題2.對偶單純形法第23頁，共76頁，2023年，2月20日，星期一在引入松弛變量化為標準型之后，約束等式兩側(cè)同乘-1，能夠立即得到檢驗數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對偶單純形表進行求解，非常方便。對于有些線性規(guī)劃模型，如果在開始求解時不能很快使所有檢驗數(shù)非正，最好還是采用單純形法求解。因為，這樣可以免去為使檢驗數(shù)全部非正而作的許多工作。從這個意義上看，可以說，對偶單純形法是單純形法的一個補充。除此之外，在對線性規(guī)劃進行靈敏度分析中有時也要用到對偶單純形方法，可以簡化計算。2.對偶單純形法第24頁，共76頁，2023年，2月20日，星期一單純形表的理解（例題）上表中6個常數(shù)a1,a2

,a3,b,

1,

2取值在什么范圍可使1、現(xiàn)可行解最優(yōu)，且唯一？何時不唯一？2、現(xiàn)基本解不可行；3、問題無可行解；4、無有限最優(yōu)解；5、現(xiàn)基本解可行，由x1取代x6

目標函數(shù)可改善。

第25頁，共76頁，2023年，2月20日，星期一進一步理解最優(yōu)單純性表中各元素的含義考慮問題Maxz

=c1x1+c2x2+

…

+cnxn

s.t.a11x1+a12x2+

…

+a1nxn

=b1

a21x1+a22x2+

…

+a2nxn

=b2...

am1x1+am2x2+

…

+amnxn

=bm

x1，x2，…，xn≥03.靈敏度分析第26頁，共76頁，2023年，2月20日，星期一3、靈敏度分析無防設，xj=0j=m+1,…,n;

xi=bi’

i=1,…,m是基本可行解,對應的目標函數(shù)典式為：z=-f+m+1xm+1+…+nxn以下是初始單純形表：

mm其中：f=-∑cibi’

j=cj-∑ciaij’

為檢驗數(shù)。向量b’=B-1bi=1i=1A=[p1,p2,…,pn],pj’=B-1pj,pj’=(a1j’,a2j’,…,amj’)T，j=m+1,…,n第27頁，共76頁，2023年，2月20日，星期一ci

,bj發(fā)生變化增加一約束或變量及A中元素發(fā)生變化—通過例題學會處理對于表格單純形法，通過計算得到最優(yōu)單純形表。應能夠找到最優(yōu)基B的逆矩陣B-1

，B-1b以及B-1N，檢驗數(shù)j

等。3.靈敏度分析第28頁，共76頁，2023年，2月20日，星期一

價值系數(shù)c發(fā)生變化：

m考慮檢驗數(shù)

j=cj-∑criarij

j=1,2,……,n

i=1

1.

若ck是非基變量的系數(shù)：設ck變化為ck

+

ck

k’=ck

+ck-∑criarik

=k+ck只要k’≤0,即

ck

≤-k，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗數(shù)

k用k’取代，繼續(xù)單純形法的表格計算。

3.靈敏度分析第29頁，共76頁，2023年，2月20日，星期一例3.3:Maxz=-2x1-3x2-4x3S.t.

-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4

x1,x2,x3,x4,x5≥03.靈敏度分析第30頁，共76頁，2023年，2月20日，星期一例：最優(yōu)單純形表

從表中看到σ3=c3+Δc3-(c2×a13+c1×a23)可得到Δc3≤9/5時，原最優(yōu)解不變。3.靈敏度分析第31頁，共76頁，2023年，2月20日，星期一2、若cs是基變量的系數(shù)：

設cs變化為cs

+cs

，那么

j’=cj-∑criarij

-(

cs+cs)asj

=j

-csasj

，

i≠s

對所有非基變量，只要對所有非基變量

j’≤0，即j

≤csasj

，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗數(shù)

j用j’取代，繼續(xù)單純形法的表格計算。

Max{j/asjasj>0}≤cs≤Min{j/asjasj<0}

3.靈敏度分析第32頁，共76頁，2023年，2月20日，星期一例3.4:

Maxz=2x1+3x2+0x3+0x4+0x5

s.t.

x1+2x2+x3=84x1+x4=164x2+x5=

12

x1,x2,x3,x4,x5

≥03.靈敏度分析第33頁，共76頁，2023年，2月20日，星期一例:

下表為最優(yōu)單純形表,考慮基變量系數(shù)c2發(fā)生變化從表中看到σj=cj-(c1×a1j+c5×

a5j+(c2+Δc2)×a2j)j=3,4可得到

-3≤Δc2≤1時，原最優(yōu)解不變。3.靈敏度分析第34頁，共76頁，2023年，2月20日，星期一

右端項b發(fā)生變化設分量br

變化為br+br

，根據(jù)第1章的討論，最優(yōu)解的基變量xB=B-1b，那么只要保持B-1(b+b)≥0，則最優(yōu)基不變，即基變量保持，只有值的變化；否則，需要利用對偶單純形法繼續(xù)計算。

對于問題

(LP)Maxz=cT

xs.t.

Ax≤b

x≥03.靈敏度分析第35頁，共76頁，2023年，2月20日，星期一最優(yōu)單純形表中含有B-1=(aij）i=1,…,m;j=n+1,…,n+m

那么新的xi=(B-1b)i+brair

i=1,…,m。由此可得，最優(yōu)基不變的條件是Max{-bi/airair>0}≤br≤Min{-bi/airair<0}3.靈敏度分析第36頁，共76頁，2023年，2月20日，星期一例3.5:

上例最優(yōu)單純形表如下

3.靈敏度分析第37頁，共76頁，2023年，2月20日，星期一00.250這里B-1=-20.510.5-0.1250各列分別對應b1、b2、b3的單一變化因此，設b1增加4，則x1,x5,x2分別變?yōu)椋?+0×4=4,4+(-2)×4=-4<0,2+0.5×4=4用對偶單純形法進一步求解，可得：x*=(4,3,2,0,0)Tf*=173.靈敏度分析第38頁，共76頁，2023年，2月20日，星期一

增加一個變量增加變量xn+1則有相應的pn+1,cn+1。那么計算出B-1pn+1,

n+1=cn+1-∑criari

n+1填入最優(yōu)單純形表,若n+1≤0則最優(yōu)解不變；否則，進一步用單純形法求解。3.靈敏度分析第39頁，共76頁，2023年，2月20日，星期一例3.6:例3.4增加x6,p6=(2,6,3)T,c6=5計算得到用單純形法進一步求解，可得：x*=(1,1.5,0,0,0,2)Tf*=16.53.靈敏度分析第40頁，共76頁，2023年，2月20日，星期一

增加一個約束增加約束一個之后，應把最優(yōu)解帶入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入一個新的非負變量（原約束若是小于等于形式可引入非負松弛變量，否則引入非負人工變量），并通過矩陣行變換把對應基變量的元素變?yōu)?，進一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼狻?.靈敏度分析第41頁，共76頁，2023年，2月20日，星期一例3.7:例3.4增加3x1+2x2≤15，原最優(yōu)解不滿足這個約束。于是3.靈敏度分析經(jīng)對偶單純形法一步，可得最優(yōu)解為（3.5,2.25,0,0,3,2)T，最優(yōu)值為13.75第42頁，共76頁，2023年，2月20日，星期一

A中元素發(fā)生變化(只討論N中某一列變化情況）與增加變量xn+1的情況類似，假設pj

變化。那么，重新計算出

B-1pj

j=cj-∑criarij

填入最優(yōu)單純形表，若j≤0則最優(yōu)解不變；否則，進一步用單純形法求解。（例子從略）3.靈敏度分析第43頁，共76頁，2023年，2月20日，星期一第四章運輸問題

運輸問題的表示 網(wǎng)絡圖、線性規(guī)劃模型、運輸表

初始基礎可行解 西北角法、最小元素法

非基變量的檢驗數(shù) 閉回路法、對偶變量法

確定進基變量，調(diào)整運量，確定離基 變量第44頁，共76頁，2023年，2月20日，星期一2321341運輸問題網(wǎng)絡圖s2=27s3=19d1=22d2=13d3=12d4=13s1=14供應量供應地運價需求量需求地6753842759106第45頁，共76頁，2023年，2月20日，星期一運輸問題線性規(guī)劃模型供應地約束需求地約束第46頁，共76頁，2023年，2月20日，星期一運輸問題的表格表示第47頁，共76頁，2023年，2月20日，星期一初始基礎可行解—西北角法813131466第48頁，共76頁，2023年，2月20日，星期一初始基礎可行解—最小元素法（1）第49頁，共76頁，2023年，2月20日，星期一最小元素法（2）第50頁，共76頁，2023年，2月20日，星期一最小元素法（3）第51頁，共76頁，2023年，2月20日，星期一最小元素法（4）第52頁，共76頁，2023年，2月20日，星期一最小元素法（5）第53頁，共76頁，2023年，2月20日，星期一最小元素法（6）第54頁，共76頁，2023年，2月20日，星期一-5非基變量xij的檢驗數(shù)zij-cij—閉回路法(1)z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5第55頁，共76頁，2023年，2月20日，星期一-5閉回路法(2)z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5-5第56頁，共76頁，2023年，2月20日，星期一-5閉回路法(3)z14-c14=(c11-c21+c21-c23+c33-c14)-c13=(6-8+2-10+6)-3=-7-7-5第57頁，共76頁，2023年，2月20日，星期一-5閉回路法(4)z24-c24=(c23-c33+c34)-c24=(2-10+6)-7=-9-9-5-7第58頁，共76頁，2023年，2月20日，星期一-5閉回路法(5)z31-c31=(c21-c23+c33)-c31=(8-2+10)-5=+11+11-5-7-9第59頁，共76頁，2023年，2月20日，星期一-5閉回路法(6)z32-c32=(c22-c23+c33)-c32=(4-2+10)-9=+3+3-5-7-9+11第60頁，共76頁，2023年，2月20日，星期一非基變量xij的