對(duì)偶問題和運(yùn)輸問題

對(duì)偶問題和運(yùn)輸問題第一頁(yè)，共七十六頁(yè)，編輯于2023年，星期日例3寫對(duì)偶問題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無約束第二頁(yè)，共七十六頁(yè)，編輯于2023年，星期日3.對(duì)偶定理(原問題與對(duì)偶問題解的關(guān)系）考慮（LP）和（DP）

定理3-1(弱對(duì)偶定理）

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

若（LP）可行，那么（LP）無有限最優(yōu)解的充分必要條件是（LD）無可行解。1.線性規(guī)劃對(duì)偶問題第三頁(yè)，共七十六頁(yè)，編輯于2023年，星期日

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

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

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

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

Max

z=50x1+100x2

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

x2+x5=250

x1,x2,x3,x4,x5

≥01.線性規(guī)劃對(duì)偶問題第十一頁(yè)，共七十六頁(yè)，編輯于2023年，星期日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單純形表和對(duì)偶對(duì)偶問題原始問題引進(jìn)松弛變量引進(jìn)松弛變量第十二頁(yè)，共七十六頁(yè)，編輯于2023年，星期日maxz=CTXs.t.AX+XS=bX,XS≥0miny=bTWs.t.ATW-WS=CW,WS≥0WT=CBTB-1WST=WTA-CT第十三頁(yè)，共七十六頁(yè)，編輯于2023年，星期日-cBTB-1IB=(p1,p4,p2)oTB-1最優(yōu)解

x1=50x2=250x4=50影子價(jià)格

y1=50y2=0y3=50,B-1對(duì)應(yīng)的檢驗(yàn)數(shù)

T=cBTB-1。1.線性規(guī)劃對(duì)偶問題第十四頁(yè)，共七十六頁(yè)，編輯于2023年，星期日例3.2：求解線性規(guī)劃問題：

標(biāo)準(zhǔn)化：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.對(duì)偶單純形法第十五頁(yè)，共七十六頁(yè)，編輯于2023年，星期日

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

如果得到的基本解的分量皆非負(fù)則該基本解為最優(yōu)解。也就是說，對(duì)偶單純形法在迭代過程中始終保持對(duì)偶解的可行性（即檢驗(yàn)數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚?，?dāng)同時(shí)得到對(duì)偶規(guī)劃與原規(guī)劃的可行解時(shí)，便得到原規(guī)劃的最優(yōu)解。2.對(duì)偶單純形法第十七頁(yè)，共七十六頁(yè)，編輯于2023年，星期日

對(duì)偶單純形法在什么情況下使用：

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

注：通過矩陣行變換運(yùn)算，使所有相應(yīng)變量取值均為非負(fù)數(shù)即得到最優(yōu)單純形表。2.對(duì)偶單純形法第十八頁(yè)，共七十六頁(yè)，編輯于2023年，星期日

1.建立初始對(duì)偶單純形表,對(duì)應(yīng)一個(gè)基本解,所有檢驗(yàn)數(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為進(jìn)基變量,轉(zhuǎn)4；

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

標(biāo)準(zhǔn)化：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.對(duì)偶單純形法第二十頁(yè)，共七十六頁(yè)，編輯于2023年，星期日表格對(duì)偶單純形法2.對(duì)偶單純形法第二十一頁(yè)，共七十六頁(yè)，編輯于2023年，星期日單純形法和對(duì)偶單純形法步驟是是是是否否否否所有所有得到最優(yōu)解計(jì)算計(jì)算典式對(duì)應(yīng)原規(guī)劃的基本解是可行的典式對(duì)應(yīng)原規(guī)劃的基本解的檢驗(yàn)數(shù)所有所有計(jì)算計(jì)算以為中心元素進(jìn)行迭代以為中心元素進(jìn)行迭代停沒有最優(yōu)解沒有最優(yōu)解單純形法對(duì)偶單純形法<第二十二頁(yè)，共七十六頁(yè)，編輯于2023年，星期日

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

,a3,b,

1,

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

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

第二十五頁(yè)，共七十六頁(yè)，編輯于2023年，星期日進(jìn)一步理解最優(yōu)單純性表中各元素的含義考慮問題Maxz

=c1x1+c2x2+

…

+cnxn

s.t.a11x1+a12x2+

…

+a1nxn

=b1

a21x1+a22x2+

…

+a2nxn

=b2...

am1x1+am2x2+

…

+amnxn

=bm

x1，x2，…，xn≥03.靈敏度分析第二十六頁(yè)，共七十六頁(yè)，編輯于2023年，星期日3、靈敏度分析無防設(shè)，xj=0j=m+1,…,n;

xi=bi’

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

mm其中：f=-∑cibi’

j=cj-∑ciaij’

為檢驗(yàn)數(shù)。向量b’=B-1bi=1i=1A=[p1,p2,…,pn],pj’=B-1pj,pj’=(a1j’,a2j’,…,amj’)T，j=m+1,…,n第二十七頁(yè)，共七十六頁(yè)，編輯于2023年，星期日ci

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

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

等。3.靈敏度分析第二十八頁(yè)，共七十六頁(yè)，編輯于2023年，星期日

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

m考慮檢驗(yàn)數(shù)

j=cj-∑criarij

j=1,2,……,n

i=1

1.

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

+

ck

k’=ck

+ck-∑criarik

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

ck

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

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

3.靈敏度分析第二十九頁(yè)，共七十六頁(yè)，編輯于2023年，星期日例3.3:Maxz=-2x1-3x2-4x3S.t.

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

x1,x2,x3,x4,x5≥03.靈敏度分析第三十頁(yè)，共七十六頁(yè)，編輯于2023年，星期日例：最優(yōu)單純形表

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

設(shè)cs變化為cs

+cs

，那么

j’=cj-∑criarij

-(

cs+cs)asj

=j

-csasj

，

i≠s

對(duì)所有非基變量，只要對(duì)所有非基變量

j’≤0，即j

≤csasj

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

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

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

3.靈敏度分析第三十二頁(yè)，共七十六頁(yè)，編輯于2023年，星期日例3.4:

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

s.t.

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

12

x1,x2,x3,x4,x5

≥03.靈敏度分析第三十三頁(yè)，共七十六頁(yè)，編輯于2023年，星期日例:

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

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

-3≤Δc2≤1時(shí)，原最優(yōu)解不變。3.靈敏度分析第三十四頁(yè)，共七十六頁(yè)，編輯于2023年，星期日

右端項(xiàng)b發(fā)生變化設(shè)分量br

變化為br+br

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

對(duì)于問題

(LP)Maxz=cT

xs.t.

Ax≤b

x≥03.靈敏度分析第三十五頁(yè)，共七十六頁(yè)，編輯于2023年，星期日最優(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.靈敏度分析第三十六頁(yè)，共七十六頁(yè)，編輯于2023年，星期日例3.5:

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

3.靈敏度分析第三十七頁(yè)，共七十六頁(yè)，編輯于2023年，星期日00.250這里B-1=-20.510.5-0.1250各列分別對(duì)應(yīng)b1、b2、b3的單一變化因此，設(shè)b1增加4，則x1,x5,x2分別變?yōu)椋?+0×4=4,4+(-2)×4=-4<0,2+0.5×4=4用對(duì)偶單純形法進(jìn)一步求解，可得：x*=(4,3,2,0,0)Tf*=173.靈敏度分析第三十八頁(yè)，共七十六頁(yè)，編輯于2023年，星期日

增加一個(gè)變量增加變量xn+1則有相應(yīng)的pn+1,cn+1。那么計(jì)算出B-1pn+1,

n+1=cn+1-∑criari

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

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

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

變化。那么，重新計(jì)算出

B-1pj

j=cj-∑criarij

填入最優(yōu)單純形表，若j≤0則最優(yōu)解不變；否則，進(jìn)一步用單純形法求解。（例子從略）3.靈敏度分析第四十三頁(yè)，共七十六頁(yè)，編輯于2023年，星期日第四章運(yùn)輸問題

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

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

非基變量的檢驗(yàn)數(shù) 閉回路法、對(duì)偶變量法

確定進(jìn)基變量，調(diào)整運(yùn)量，確定離基 變量第四十四頁(yè)，共七十六頁(yè)，編輯于2023年，星期日2321341運(yùn)輸問題網(wǎng)絡(luò)圖s2=27s3=19d1=22d2=13d3=12d4=13s1=14供應(yīng)量供應(yīng)地運(yùn)價(jià)需求量需求地6753842759106第四十五頁(yè)，共七十六頁(yè)，編輯于2023年，星期日運(yùn)輸問題線性規(guī)劃模型供應(yīng)地約束需求地約束第四十六頁(yè)，共七十六頁(yè)，編輯于2023年，星期日運(yùn)輸問題的表格表示第四十七頁(yè)，共七十六頁(yè)，編輯于2023年，星期日初始基礎(chǔ)可行解—西北角法813131466第四十八頁(yè)，共七十六頁(yè)，編輯于2023年，星期日初始基礎(chǔ)可行解—最小元素法（1）第四十九頁(yè)，共七十六頁(yè)，編輯于2023年，星期日最小元素法（2）第五十頁(yè)，共七十六頁(yè)，編輯于2023年，星期日最小元素法（3）第五十一頁(yè)，共七十六頁(yè)，編輯于2023年，星期日最小元素法（4）第五十二頁(yè)，共七十六頁(yè)，編輯于2023年，星期日最小元素法（5）第五十三頁(yè)，共七十六頁(yè)，編輯于2023年，星期日最小元素法（6）第五十四頁(yè)，共七十六頁(yè)，編輯于2023年，星期日-5非基變量xij的檢驗(yàn)數(shù)zij-cij—閉回路法(1)z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5第五十五頁(yè)，共七十六頁(yè)，編輯于2023年，星期日-5閉回路法(2)z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5-5第五十六頁(yè)，共七十六頁(yè)，編輯于2023年，星期日-5閉回路法(3)z14-c14=(c11-c21+c21-c23+c33-c14)-c13=(6-8+2-10+6)-3=-7-7-5第五十七頁(yè)，共七十六頁(yè)，編輯于2023年，星期日-5閉回路法(4)z24-c24=(c23-c33+c34)-c24=(2-10+6)-7=-9-9-5-7第五十八頁(yè)，共七十六頁(yè)，編輯于2023年，星期日-5閉回路法(5)z31-c31=(c21-c23+c33)-c31=(8-2+10)-5=+11+11-5-7-9第五十九頁(yè)，共七十六頁(yè)，編輯于2023年，星期日-5閉回路法(6)z32-c32=(c22-c23+c33)-c32=(4-2+10)-9=+3+3-5-7-9+11第六十頁(yè)，共七十六頁(yè)，編輯于2023年，星期日非基變量