數(shù)據(jù)模型及決策

1、數(shù)據(jù)模型與決策“數(shù)據(jù)模型與決策”原來(lái)的名稱是“運(yùn)籌學(xué)”?！皵?shù)據(jù)模型與決策”包括線性規(guī)劃、對(duì)偶、整數(shù)規(guī)劃、運(yùn)輸問(wèn)題和網(wǎng)絡(luò)優(yōu)化。前言數(shù)據(jù)模型與決策和運(yùn)籌學(xué)運(yùn)籌學(xué)是管理科學(xué)的重要理論基礎(chǔ)和應(yīng)用手段，是管理專業(yè)的重要專業(yè)基礎(chǔ)課程之一。運(yùn)籌學(xué)根據(jù)管理問(wèn)題的環(huán)境條件和決策要求，建立相應(yīng)的數(shù)學(xué)模型，利用數(shù)學(xué)模型對(duì)實(shí)際問(wèn)題進(jìn)行分析和求解，經(jīng)過(guò)分析和比較，得到適合實(shí)際問(wèn)題的方案。運(yùn)籌學(xué)是在第二次世界大戰(zhàn)中誕生和發(fā)展起來(lái)的。由于戰(zhàn)爭(zhēng)的需要，英國(guó)和美國(guó)招募了一批年輕的科學(xué)家和工程師，在軍隊(duì)將軍的領(lǐng)導(dǎo)下研究戰(zhàn)爭(zhēng)中的問(wèn)題，例如大規(guī)模轟炸的效果，搜索和攻擊敵軍潛水艇的策略，兵力和軍需物質(zhì)的調(diào)運(yùn)等等。這些研究在戰(zhàn)爭(zhēng)中取得了

2、很好的效果。當(dāng)時(shí)英國(guó)把這些研究成為“作戰(zhàn)研究”，英文是Operational Research，在美國(guó)稱為Operations Research。戰(zhàn)后這些研究成果逐漸公開發(fā)表，這些理論和方法被應(yīng)用到經(jīng)濟(jì)計(jì)劃，生產(chǎn)管理領(lǐng)域，也產(chǎn)生了很好的效果。這樣，Operations Research就轉(zhuǎn)義成為“作業(yè)研究”。我國(guó)把Operations Research譯成“運(yùn)籌學(xué)”，非常貼切地涵蓋了這個(gè)詞作戰(zhàn)研究和作業(yè)研究?jī)煞矫娴暮x。運(yùn)籌學(xué)的內(nèi)容十分廣泛，包括線性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、非線性規(guī)劃、圖論與網(wǎng)絡(luò)優(yōu)化、排隊(duì)論、決策理論、庫(kù)存理論等。在本課程中，結(jié)合管理學(xué)科的特點(diǎn)，主要介紹線性規(guī)劃、整數(shù)規(guī)劃、運(yùn)

3、輸問(wèn)題、網(wǎng)絡(luò)優(yōu)化、動(dòng)態(tài)規(guī)劃和排隊(duì)論。線性規(guī)劃模型線性規(guī)劃模型的結(jié)構(gòu)目標(biāo)函數(shù) ：max，min約束條件：,=,變量符號(hào)：0, unr, 0線性規(guī)劃的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：min約束條件：=變量符號(hào)：0unr, 0 )(Xb),(AX. t . sXCzmax(min)T0XbAX. t . sXCzminT可行域目標(biāo)函數(shù)等值線最優(yōu)解64-860 x1x2凸集凸集不是凸集線性規(guī)劃可行域和最優(yōu)解的幾種情況1、可行域封閉 唯一最優(yōu)解2、可行域封閉 多個(gè)最優(yōu)解3、可行域開放 唯一最優(yōu)解4、可行域開放 多個(gè)最優(yōu)解5、可行域開放 目標(biāo)函數(shù)無(wú)界6、無(wú)可行解x3=0 x4=0max z=x1+2x2s.t. x1+

4、x23 x2 1 x1, x2 0max z=x1+2x2s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40 x1=0, x2=0 x3=3, x4=1x1=0, x4=0 x2=1, x3=2x2=0, x3=0 x1=3, x4=1x3=0, x4=0 x1=2, x2=1x1=0, x3=0 x2=3, x4=-2線性規(guī)劃的基本概念基礎(chǔ)解、基礎(chǔ)可行解、極點(diǎn)x2=0 x1=0OABCDq標(biāo)準(zhǔn)化的線性規(guī)劃問(wèn)題，有n個(gè)變量，m個(gè)約束。q令其中n-m個(gè)變量等于零，如果剩下的m個(gè)變量的系數(shù)矩陣的行列式不等于0，這個(gè)mm的矩陣稱為線性規(guī)劃的一個(gè)基。等于0的n-m個(gè)變

5、量稱為非基變量，m個(gè)變量稱為基變量。q求解mm的線性方程組，得到基變量的一組解，連同等于0的非基變量這n個(gè)變量的值稱為線性規(guī)劃的一個(gè)基礎(chǔ)解。q如果一個(gè)基礎(chǔ)解中的所有變量都是非負(fù)的，這個(gè)基礎(chǔ)解稱為基礎(chǔ)可行解。q線性規(guī)劃的基礎(chǔ)可行解就是可行域的極點(diǎn)。線性規(guī)劃的基本概念基礎(chǔ)解、基礎(chǔ)可行解、極點(diǎn)max z=x1+2x2s.t. x1+x23 x2 1 x1, x2 0max z=x1+2x2s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40 x1=0, x2=0 x3=3, x4=1基礎(chǔ)可行解x1=0, x4=0 x2=1, x3=2基礎(chǔ)可行解x2=0, x3=0 x

6、1=3, x4=1基礎(chǔ)可行解x3=0, x4=0 x1=2, x2=1基礎(chǔ)可行解x1=0, x3=0 x2=3, x4=-2是基礎(chǔ)解，但不是可行解OABx3=0 x4=0 x2=0 x1=0CD可行域幾何概念代數(shù)概念約束直線滿足一個(gè)等式約束的解約束半平面滿足一個(gè)不等式約束的解約束半平面的交集：凸多邊形滿足一組不等式約束的解約束直線的交點(diǎn)基礎(chǔ)解可行域的極點(diǎn)基礎(chǔ)可行解目標(biāo)函數(shù)等值：一組平行線 目標(biāo)函數(shù)值等于一個(gè)常數(shù)的解maxz=2x1+3x2+x3s.t.x1+3x2+x3152x1+3x2-x318x1-x2+x33x1,x2,x30min z= -2x1-3x2-x3stx1+3x2+x3+x

7、4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1,x2,x3,x4,x5,x60搜索所有基礎(chǔ)可行解求出最優(yōu)解x1+3x2+x3=152x1+3x2-x3=18x1-x2+x3=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基變量x1、x2、x3，非基變量x4、x5、x6基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為：z=20 x1+3x2+x4=152x1+3x2=18x1-x2=3基變量x1、x2、x4，非基變量x3、x5、x6基礎(chǔ)解為（x1，x2，x

8、3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1+3x2=152x1+3x2+x5=18x1-x2=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基變量x1、x2、x5，非基變量x3、x4、x6基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0）是基礎(chǔ)解，但不是可行解，不是一個(gè)極點(diǎn)。x1+3x2=152x1+3x2=18x1-x2+x6=3基變量x1、x2、x6

9、，非基變量x3、x4、x5基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3+x4=153x2-x3=18-x2+x3=3基變量x2、x3、x4，非基變量x1、x5、x6基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基礎(chǔ)解，但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3+x5=18-x

10、2+x3=3基變量x1、x2、x3，非基變量x4、x5、x6基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為：z=15x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3=18-x2+x3+x6=3基變量x1、x2、x3，非基變量x4、x5、x6基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基礎(chǔ)解但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3 單純形法原理

11、（1）松弛變量的表示max z=x1+2x2s.t. x1+x23 x2 1 x1, x20max z=x1+2x2s.t. x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40 x2=0 x1=0 x3=0 x4=0OABCD 引進(jìn)松弛變量x2=0 x1=0 x3=0 x4=0OABCx1,x2=0為非基變量x3,x40為基變量當(dāng)前基礎(chǔ)可行解：(x1,x2,x3,x4)=(0,0,3,1)z=0 x2進(jìn)基,從0開始增加，x3,x4隨之減少第一次疊代：目標(biāo)函數(shù)和基變量分別用非基變量表示： z=-x1-2x2選擇x2進(jìn)基 x3 =3-x1-x2 x4=1 -x2x2=1成為基

12、變量，x4=0成為離基變量當(dāng)前基礎(chǔ)可行解：(x1,x2,x3,x4)=(0,1,2,0)z=-2單純形法原理(2)第一次疊代確定離基變量的進(jìn)一步討論設(shè)非基變量為x1、x2，基變量為x3、x4、x5，進(jìn)基變量為x2x3 =5- x1-4x2 x4 =4-2x1-3x2 x5 =2-3x1- x25/4=1.254/3=1.332/1=2min5/4,4/3,2/1=5/4當(dāng)x2增加到1.25時(shí)x30離基x3 =5- x1+4x2 x4 =4-2x1-3x2 x5 =2-3x1- x2x3增加4/3=1.332/1=2min4/3,2/1=4/3當(dāng)x2增加到1.33時(shí)x40離基x3 =5- x1+

13、4x2 x4 =4-2x1+3x2 x5 =2-3x1- x2x3增加x4增加2/1=2min2/1=2/1當(dāng)x2增加到2時(shí)x50離基x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1+ x2x3增加x4增加x5增加x2可以無(wú)限增加，可行域是開放區(qū)域，目標(biāo)函數(shù)無(wú)界x2=0 x1=0 x3=0 x4=0OABC第二次疊代：目標(biāo)函數(shù)和基變量分別用非基變量表示： z=-2-x1+2x4選擇x1進(jìn)基 x3 =2-x1+x4 x2=1 -x4當(dāng)前基礎(chǔ)可行解：(x1,x2,x3,x4)=(0,1,2,0)z=-2單純形法原理（3）第二次疊代x1進(jìn)基，從0開始增加，基變量x2保持不變

14、，x3從2開始減少x1=2成為基變量，x3=0成為非基變量當(dāng)前基礎(chǔ)可行解：(x1,x2,x3,x4)=(2,1,0,0)z=-4x2=0 x1=0 x3=0 x4=0OABC第三次疊代：目標(biāo)函數(shù)和基變量分別用非基變量表示： z=-4+x3+x4 x1 =2-x3+x4 x2=1 -x4非基變量在目標(biāo)函數(shù)中的系數(shù)全部大于0，已獲得最優(yōu)解。單純形法原理（4）最優(yōu)解的判定x1=2成為基變量，x3=0成為非基變量當(dāng)前基礎(chǔ)可行解：(x1,x2,x3,x4)=(2,1,0,0)z=-4x2=0 x1=0 x3=0 x4=0OABC單純形法原理(5)疊代過(guò)程回顧第一次疊代x2進(jìn)基，x4離基第二次疊代x1進(jìn)基

15、，x3離基(x1,x2,x3,x4)=(0,0,3,1), z=0(x1,x2,x3,x4)=(0,1,2,0), z=-2(x1,x2,x3,x4)=(2,1,0,0), z=-4最優(yōu)解單純形法原理（6）單純形法總結(jié)STEP 0 找到一個(gè)初始的基礎(chǔ)可行解，確定基變量和非基變量。轉(zhuǎn)STEP 1。STEP 1 將目標(biāo)函數(shù)和基變量分別用非基變量表示。轉(zhuǎn)STEP 2。STEP 2 如果目標(biāo)函數(shù)中所有非基變量的系數(shù)全部為正數(shù)，則已經(jīng)獲得最優(yōu)解。運(yùn)算終止。否則，選取系數(shù)為負(fù)數(shù)并且絕對(duì)值最大的非基變量進(jìn)基。轉(zhuǎn)STEP 3。STEP 3 如果進(jìn)基變量增加時(shí)，基變量都不減少，則可行域開放，目標(biāo)函數(shù)無(wú)界。運(yùn)算終

16、止。否則，隨著進(jìn)基變量的增加，最先下降到0的基變量離基。轉(zhuǎn)STEP 1。線性規(guī)劃基本概念練習(xí)（1）036x1x2OABCEFGHI46-2min z=-x1+2x2s.t. 3x1+2x212(1) x1+2x2 6(2) -2x1+ x2 4(3) x1, x2 01、約束條件（1）對(duì)應(yīng)的直線是（ ），對(duì)應(yīng)的半平面是 約束條件（2）對(duì)應(yīng)的直線是（ ），對(duì)應(yīng)的半平面是 約束條件（3）對(duì)應(yīng)的直線是（ ），對(duì)應(yīng)的半平面是2、這個(gè)線性規(guī)劃的可行域是（ ）。3、對(duì)于z=2和4,分別畫出目標(biāo)函數(shù)等值線。4、這個(gè)線性規(guī)劃的最優(yōu)解位于（ ）。ACEFBCDHEGHICDGEz=2z=4CD4036x1x2O

17、ABCEFGHI46-2D線性規(guī)劃基本概念練習(xí)（2）5、x1等于0的直線是( )， x2等于0的直線是( )， x3等于0的直線是( )， x4等于0的直線是( )， x5等于0的直線是( )。6、A點(diǎn)對(duì)應(yīng)的基變量是( )，非基變量是（ ）； D點(diǎn)對(duì)應(yīng)的基變量是( )，非基變量是（ ）。7、A點(diǎn)不是可行解， 是由于( )0, F點(diǎn)不是可行解， 是由于( )0, I 點(diǎn)不是可行解， 是由于( )0，則原問(wèn)題沒(méi)有可行解。STEP 4 轉(zhuǎn)到第二階段，從原問(wèn)題的初始基礎(chǔ)可行解出發(fā)，求出原問(wèn)題的最優(yōu)解。案例一 食油生產(chǎn)計(jì)劃儲(chǔ)罐1儲(chǔ)罐2儲(chǔ)罐3儲(chǔ)罐4儲(chǔ)罐5硬質(zhì)油1硬質(zhì)油2軟質(zhì)油1軟質(zhì)油2軟質(zhì)油3硬質(zhì)油精煉軟

18、質(zhì)油精煉混合成品油原料加工成品DUAL對(duì)偶問(wèn)題max y=bTWs.t. ATWCW 0minbACTCATbTmaxmnmn二、對(duì)偶問(wèn)題的性質(zhì)1、對(duì)偶的對(duì)偶就是原始問(wèn)題對(duì)偶的定義max y=bTWs.t. ATWCW 0對(duì)偶的定義min y=-bTWs.t. -ATW-CW 02、其他形式問(wèn)題的對(duì)偶原始問(wèn)題約束條件的性質(zhì)，影響對(duì)偶問(wèn)題變量的性質(zhì)。原始問(wèn)題變量的性質(zhì)，影響對(duì)偶問(wèn)題約束條件的性質(zhì)。max y=bTWs.t. ATWC W 0max y=bTWs.t. ATWC W :unrmax y=bTWs.t. ATWC W 0min z= 2x1+4x2-x3s.t. 3x1- x2+2x

19、3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max y=6w1+12w2+8w3+15w4s.t. 3w1- w2+2w3+ w4 2 -w1+2w2+ w3+3w4 4 2w1- 3w2+2w3- w4 -1 w1 0,w2 ,w3 0,w4 0=unr=x10 x20 x3: unrq原始問(wèn)題變量的個(gè)數(shù)(3)等于對(duì)偶問(wèn)題約束條件的個(gè)數(shù)(3)； 原始問(wèn)題約束條件的個(gè)數(shù)(4)等于對(duì)偶問(wèn)題變量的個(gè)數(shù)(4)。q原始問(wèn)題變量的性質(zhì)影響對(duì)偶問(wèn)題約束條件的性質(zhì)。 原始問(wèn)題約束條件的性質(zhì)影響對(duì)偶問(wèn)題變量的性質(zhì)。三、原始對(duì)偶關(guān)系1、可行解的目標(biāo)函數(shù)值之間的關(guān)系 設(shè)

20、XF、WF分別是原始問(wèn)題和對(duì)偶問(wèn)題的可行解z=CTXF WTAXF WTb=y2、最優(yōu)解的目標(biāo)函數(shù)值之間的關(guān)系 設(shè)Xo、Wo分別是原始問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解 z=CTXo=WoTAXo=WoTb=y3、原始問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解之間的互補(bǔ)松弛關(guān)系min z=CTXs.t. AX-XS=b X, XS0max y=bTWs.t. ATW+WS=C W, WS0min z=CTXs.t. AXb X 0max y=bTWs.t. ATWC W0對(duì)偶引進(jìn)松弛變量引進(jìn)松弛變量互補(bǔ)松弛關(guān)系X，XsW，WsXTWS=0 WTXS=0max y=bTWs.t. ATW+WS=CW, WS 0XTWS=0WTX

21、S=0ATWIWsCmn=nXA-IXsb=nmm原始問(wèn)題和對(duì)偶問(wèn)題變量、松弛變量的維數(shù)w1. wi . wm wm+1 . wm+j . wm+n x1 . xj . xn xn+1 xn+i xn+m 對(duì)偶問(wèn)題的變量 對(duì)偶問(wèn)題的松弛變量 原始問(wèn)題的變量 原始問(wèn)題的松弛變量xjwm+j=0wixn+i=0(i=1,2,m; j=1,2,n)在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于03、原始問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解的充分必要條件 AX-XS=b X, XS 0原始可行條件（Primal Feasible Condition, PFC）ATW+WS=C W, WS 0對(duì)偶可行條件（Dual Fe

22、asible Condition, DFC）Kuhn-Tucher 條件 XTWS=0 WTXS=0互補(bǔ)松弛條件（Complementary Slackness Condition, PFC）四、對(duì)偶單純形法1、用單純形表求解原始問(wèn)題的四種形式min z=CTXs.t. AXb X 0min z=CTXs.t. AX b X 0max z=CTXs.t. AX b X 0max z=CTXs.t. AX b X 0（2）（3）（4）（1）單純形表和對(duì)偶(1)min z=CTXs.t. AX-XS=b X, XS0max y=bTWs.t. ATW+WS=C W, WS0max y=bTWs.t

23、. ATWC W0對(duì)偶問(wèn)題min z=CTXs.t. AXb X 0原始問(wèn)題引進(jìn)松弛變量引進(jìn)松弛變量zXXSRHS1-WST-WTCBTB-1b0B-1A-B-1B-1bzXXSRHS1-CT0T00A-Ibmin z=CTXs.t. AX-XS=b X, XS0max y=bTWs.t. ATW+WS=C W, WS0zXXSRHS1CBTB-1A-CT-CBTB-1CBTB-1b0B-1A-B-1B-1bWT=CBTB-1WST=CT-WTAmin z=CTXs.t. AX+XS=b X, XS0max y=bTWs.t. ATW+WS=C W 0, WS0單純形表和對(duì)偶(2)max y=

24、bTWs.t. ATWC W 0對(duì)偶問(wèn)題min z=CTXs.t. AX b X 0原始問(wèn)題引進(jìn)松弛變量引進(jìn)松弛變量zXXSRHS1-WSTWTCBTB-1b0B-1AB-1B-1bzXXSRHS1-CT0T00AIbmin z=CTXs.t. AX+XS=b X, XS0max y=bTWs.t. ATW+WS=C W 0, WS0zXXSRHS1CBTB-1A-CTCBTB-1CBTB-1b0B-1AB-1B-1bWT=CBTB-1WST=CT-WTAmax z=CTXs.t. AX-XS=b X, XS0max y=bTWs.t. ATW-WS=C W 0, WS0單純形表和對(duì)偶(3)m

25、in y=bTWs.t. ATW C W 0對(duì)偶問(wèn)題max z=CTXs.t. AX b X 0原始問(wèn)題引進(jìn)松弛變量引進(jìn)松弛變量zXXSRHS1WST-WTCBTB-1b0B-1A-B-1B-1bzXXSRHS1-CT0T00A-Ibmax z=CTXs.t. AX-XS=b X, XS0min y=bTWs.t. ATW-WS=C W 0, WS0zXXSRHS1CBTB-1A-CT-CBTB-1CBTB-1b0B-1A-B-1B-1bWT=CBTB-1WST=WTA- CTmax z=CTXs.t. AX+XS=b X, XS0max y=bTWs.t. ATW-WS=C W, WS0單純

26、形表和對(duì)偶(4)min y=bTWs.t. ATW C W 0對(duì)偶問(wèn)題max z=CTXs.t. AX b X 0原始問(wèn)題引進(jìn)松弛變量引進(jìn)松弛變量zXXSRHS1WSTWTCBTB-1b0B-1AB-1B-1bzXXSRHS1-CT0T00AIbmax z=CTXs.t. AX+XS=b X, XS0min y=bTWs.t. ATW-WS=C W, WS0zXXSRHS1CBTB-1A-CTCBTB-1CBTB-1b0B-1AB-1B-1bWT=CBTB-1WST=WTA- CTmin z=6x1+8x2+3x3s.t. x1+ x2 1 x1+2x2+x3 -1 x1, x2, x3 0m

27、ax y=w1-w2s.t. w1+ w2 6 w1+2w2 8 w2 3 w1, w20max y=w1-w2s.t. w1+w2+w3 =6 w1+2w2 +w4 =8 w2 +w5=3 w1, w2, w3, w4, w50(w1, w2)=(6,0)(w1,w2,w3,w4,w5)=(6, 0, 0, 2, 3)min z=6x1+8x2+3x3s.t. x1+ x2 -x4 =1 x1+2x2+x3 -x5 =-1 x1, x2, x3 ,x4, x50(x1, x2, x3 | x4, x5)(w1, w2 | w3, w4, w5)x2=x3=x4=0 x1=1, x5=2引進(jìn)松

28、弛變量 求對(duì)偶引進(jìn)松弛變量求解代入約束求出松弛變量互補(bǔ)松弛關(guān)系代入約束求解(x1, x2, x3, x4, x5)=(1, 0, 0, 0, 2)min z=6x1+8x2+3x3s.t. x1+ x2 -x4 =1 x1+2x2+x3 -x5 =-1 x1, x2, x3 ,x4, x50max y=w1-w2s.t. w1+w2+w3 =6 w1+2w2 +w4 =8 w2 +w5=3 w1, w2, w3, w4, w50(w1, w2, w3, w4, w5)=(6, 0, 0, 2, 3)(x1, x2, x3, x4, x5)=(1, 0, 0, 0, 2)-w3 w4 w5 w1

29、 w2如何從最優(yōu)單純形表中讀出對(duì)偶問(wèn)題的解（1）初始單純形表最優(yōu)單純形表如何從最優(yōu)單純形表中讀出對(duì)偶問(wèn)題的解（2）初始單純形表最優(yōu)單純形表2、對(duì)偶單純形法（初始解原始不可行的問(wèn)題）0 xxx2xx2x5xx3x24xxx. t . sxx2x3zmin3213213213213210 xxxxxx2xxx2x5xxx3x24xxxx. t . sxx2x3zmin6543216321532143213210 xxxxxx2xxx2x25xxx3x24xxxx. t . sxx2x3zmin654321632153214321321 z x1 x2 x3 x4 x5 x6 RHS z 1 -3

30、-2 -1 0 0 0 0 x4 0 1 -1 1 1 0 0 4 x5 0 2 -3 1 0 1 0 -5 x6 0 -2 2 -1 0 0 1 -2 z x1 x2 x3 x4 x5 x6 RHS z 1 -1 0 0 0 -4 -5 30 x4 0 -1 0 0 1 1 2 -5 x2 0 0 1 0 0 -1 -1 7 x3 0 2 0 1 0 -2 -3 16 z x1 x2 x3 x4 x5 x6 RHS z 1 -13/3 0 -5/3 0 -2/3 0 10/3 x4 0 1/3 0 2/3 1 -1/3 0 17/3 x2 0 -2/3 1 -1/3 0 -1/3 0 5/3

31、 x6 0 -2/3 0 -1/3 0 2/3 1 -16/3 z x1 x2 x3 x4 x5 x6 R H S z 1 0 0 0 -1 -5 -7 35 x1 0 1 0 0 -1 -1 -2 5 x2 0 0 1 0 0 -1 -1 7 x3 0 0 0 1 2 0 1 6 已獲得最優(yōu)解：（x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35對(duì)偶問(wèn)題的最優(yōu)解為：（w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=353、初始解原始、對(duì)偶都不可行的問(wèn)題0 xxx2xx2x5xx3x24xx

32、x. t . sx2x2x3zmin3213213213213210 xxxxxx2xxx2x5xxx3x24xxxx. t . sx2x2x3zmin6543216321532143213210 xxxxxx2xxx2x25xxx3x24xxxx. t . sx2x2x3zmin654321632153214321321zx1x2x3x4x5x6RHSz1-3-220000 x401-111004x502-31010-5x60-22-1001-2解法1：先解決原始可行性zx1x2x3x4x5x6RHSz1-700024-18x40-100112-5x200100-1-17x302010-2-

33、316zx1x2x3x4x5x6RHSz1-720002-4x40-1101012x500-10011-7x302-2100-12zx1x2x3x4x5x6RHSz1000-7-5-1017x10100-1-1-25x200100-1-17x300012016在得到原始可行解時(shí)同時(shí)得到對(duì)偶可行解，已獲得最優(yōu)解：（x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17對(duì)偶問(wèn)題的最優(yōu)解為：（w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17zx1x2x3x4x5x6RHSz1-3-220000

34、x401-111004x502-31010-5x60-22-1001-2zx1x2x3x4x5x6RHSz1-500-200-8x301-111004x501-20-110-9x60-1101012解法2：先解決對(duì)偶可行性已得到對(duì)偶可行解，再用對(duì)偶單純形法求解zx1x2x3x4x5x6RHSz1000-7-5-1017x300012016x200100-1-17x10100-1-1-25zx1x2x3x4x5x6RHSz1-500-200-8x301/2013/2 -1/2017/2x20-1/2101/2 -1/209/2x60-1/2001/21/21-5/2得到原始可行解，已獲得最優(yōu)解：

35、（x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17對(duì)偶問(wèn)題的最優(yōu)解為：（w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=170 xxxxxxbxxaxaxabxxaxaxabxxaxaxa. t . sxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111nn2211五、對(duì)偶的經(jīng)濟(jì)解釋1、原始問(wèn)題是利潤(rùn)最大化的生產(chǎn)計(jì)劃問(wèn)題單位產(chǎn)品的利潤(rùn)（元/件）產(chǎn)品產(chǎn)量（件）總利潤(rùn)（元）資源限量（噸）單位產(chǎn)品消耗的資源（噸/件）剩余的資源（噸）消耗

36、的資源（噸）2、對(duì)偶問(wèn)題0wwwwwwcwwawawacwwawawacwwawawa. t . swbwbwbyminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm2211資源限量（噸）資源價(jià)格（元/噸）總利潤(rùn)（元）對(duì)偶問(wèn)題是資源定價(jià)問(wèn)題，對(duì)偶問(wèn)題的最優(yōu)解w1、w2、.、wm稱為m種資源的影子價(jià)格（Shadow Price）原始和對(duì)偶問(wèn)題都取得最優(yōu)解時(shí)，最大利潤(rùn) max z=min y3、資源影子價(jià)格的性質(zhì)影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0種資

37、源的邊際利潤(rùn)第種資源的增量第最大利潤(rùn)的增量iibzwiooimmii2211wbwbwbwbyzmmiii2211wbw)bb(wbwbzziiwbzw1w2wm4、產(chǎn)品的機(jī)會(huì)成本機(jī)會(huì)成本表示減少一件產(chǎn)品所節(jié)省的所有資源可以增加的利潤(rùn)mmjiij2j21j1wawawawa增加單位資源可以增加的利潤(rùn)減少一件產(chǎn)品的產(chǎn)量可以節(jié)省的資源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211機(jī)會(huì)成本利潤(rùn)差額成本5、產(chǎn)品的差額成本（Reduced Cost）w

38、m+j=(ai1w1+ai2w2+.aimwm)-cj差額成本機(jī)會(huì)成本利潤(rùn)0wwwwwwcwwawawacwwawawacwwawawa. t . swbwbwbyminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm22115、互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋wixn+i=0如果wi0，則xn+i=0如果xn+i0，則wi=0邊際利潤(rùn)大于0的資源，在最優(yōu)生產(chǎn)計(jì)劃條件下沒(méi)有剩余wm+jxj=0如果wm+j0，則xj=0如果xj0，則wm+j=0最優(yōu)生產(chǎn)計(jì)劃條件下有剩余的資源，其邊際利潤(rùn)等于0差額成本大于0（機(jī)會(huì)成本大于利潤(rùn)）的產(chǎn)品，不安排生產(chǎn)安排生產(chǎn)的產(chǎn)品，

39、差額成本等于0（機(jī)會(huì)成本等于利潤(rùn)）和資源有關(guān)的量q資源限量（噸）q資源占用（噸）q資源剩余（噸） 資源限量資源占用q資源的影子價(jià)格（資源的邊際利潤(rùn)）（元/噸）和產(chǎn)品有關(guān)的量q產(chǎn)品利潤(rùn)（元/件）q產(chǎn)品產(chǎn)量（件）q產(chǎn)品的機(jī)會(huì)成本（元/件）q產(chǎn)品的差額成本（元/件） 機(jī)會(huì)成本利潤(rùn)互補(bǔ)松弛關(guān)系互補(bǔ)松弛關(guān)系max z=32x1+31x2+55x3+32x4+70 x5s.t. x1+2x2+ 3x4+2x54000 2x1+2x2+3x3+ x4+4x52000 x1 +2x3+2x4+2x51800 4x1+3x2+5x3 +3x52400 x1，x2，x3，x4，x50產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4產(chǎn)品5

40、資源限量資源A1.02.03.02.04000資源B2.02.03.01.04.02000資源C1.02.02.02.01800資源D4.03.05.03.02400利潤(rùn)3231553270LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)45850.00 VARIABLEVALUE REDUCED COST X1 0.000000 7.250000 X2550.000000 0.000000 X3 0.000000 8.000000 X4900.000000 0.000000 X5 0.000000 8.500000 ROW SLAC

41、K OR SURPLUS DUAL PRICES 2)200.000000 0.000000 3) 0.00000015.500000 4) 0.000000 8.250000 5) 750.000000 0.000000 NO. ITERATIONS= 2產(chǎn)品產(chǎn)品編號(hào)12345資源利潤(rùn)（元/件）3231553270產(chǎn)量（件）055009000機(jī)會(huì)成本(元/件)限量（噸）占用（噸）剩余（噸）影子價(jià)格（元/噸）差額成本(元/件)設(shè)備設(shè)備A1.02.03.02.040000設(shè)備B2.02.03.01.04.0200015.5設(shè)備C1.02.02.02.018008.25設(shè)備D4.03.05.03.

42、0240002000075038002000180016507.2508.008.539.253163.03278.52312341d1=22d2=13d3=12d4=13s2=27s3=19s1=14供應(yīng)地運(yùn)價(jià)需求地6753482759106供應(yīng)量需求量總供應(yīng)量60噸總需求量60噸供求平衡的運(yùn)輸問(wèn)題0 xxxxxxxxxxxx13=x+x+x12=x+x+x13=x+x+x22=x+x+x19=x+x+x+x27=x+x+x+x14=x+x+x+xs.t.x6+x10+x9+x5+x7+x2+x4+x8+x3+x5+x7+x6=zmin3433323124232221141312113424

43、14332313322212312111343332312423222114131211343332312423222114131211供應(yīng)地約束需求地約束由于前m個(gè)供應(yīng)地約束和后n個(gè)需求地約束是線性相關(guān)的，因此運(yùn)輸問(wèn)題系數(shù)矩陣的秩m+n。可以證明，運(yùn)輸問(wèn)題系數(shù)矩陣的秩為m+n-1。即運(yùn)輸問(wèn)題有m+n-1個(gè)基變量，mn-(m+n-1)個(gè)非基變量。例如以上問(wèn)題m=3，n=4，基變量為3416個(gè)，非基變量為1266個(gè)。123467531x11x12x13x141484272x21x22x23x2427591063x31x32x33x341922131213 m個(gè)供應(yīng)地、n個(gè)需求地的運(yùn)輸問(wèn)題，任何一

44、個(gè)基要滿足以下三個(gè)條件：q基變量的個(gè)數(shù)為m+n-1；q同行同列的基變量不能形成回路；q運(yùn)輸表的每一行和每一列中至少有一個(gè)基變量?；谶\(yùn)輸表中的表示運(yùn)輸表中同行同列的變量組成回路 1 2 3 4 6 7 5 3 1 14 8 4 2 7 2 27 5 9 10 6 3 19 22 13 12 13 813131466123467531148427212271559106319221312130初始基礎(chǔ)可行解最小元素法（1）1234675311314184272122715591063192213121300初始基礎(chǔ)可行解最小元素法（2）123467531131418427213122725910

45、631922131213000初始基礎(chǔ)可行解最小元素法（3）1234675311314184272131227259106319190221312133000初始基礎(chǔ)可行解最小元素法（4）12346753111314084272131227259106319190221312132000初始基礎(chǔ)可行解最小元素法（5）123467531113140842722131227059106319190221312130000初始基礎(chǔ)可行解最小元素法（6）1234675311414842728136275910636131922131213-5非基變量xij的檢驗(yàn)數(shù)zij-cij閉回路法(1)z12-c

46、12=(c11-c21+c22)-c12=6-8+4-7=-51234675311414842728136275910636131922131213-5z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5-5非基變量xij的檢驗(yàn)數(shù)zij-cij閉回路法(2)1234675311414842728136275910636131922131213-5z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7-7-5非基變量xij的檢驗(yàn)數(shù)zij-cij閉回路法(3)12346753114148427281362759

47、10636131922131213-5z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9-9-5-7非基變量xij的檢驗(yàn)數(shù)zij-cij閉回路法(4)1234675311414842728136275910636131922131213-5z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11+11-5-7-9非基變量xij的檢驗(yàn)數(shù)zij-cij閉回路法(5)1234675311414842728136275910636131922131213-5z32-c32=(c22-c23+ c33)-c32=(4-2+10)-9=+3+3-5-

48、7-9+11非基變量xij的檢驗(yàn)數(shù)zij-cij閉回路法(6)12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0選擇進(jìn)基變量,確定離基變量x31進(jìn)基, minx21,x33=min8,6=6, x33離基+3-5-5-7-91112346753114148427221312275910636131922131213調(diào)整運(yùn)量,重新計(jì)算檢驗(yàn)數(shù),確定進(jìn)基、離基變量x14進(jìn)基, minx11,x34=min14,13=13, x34離基-11-5-5+4+2-8123467531113148427221312275910631919

49、22131213調(diào)整運(yùn)量, 重新計(jì)算檢驗(yàn)數(shù)所有zij-cij0時(shí)，相應(yīng)的wij=0，同時(shí)由單純形表的結(jié)構(gòu)可以知道，對(duì)偶問(wèn)題的松弛變量的相反數(shù)就是非基變量的檢驗(yàn)數(shù)，因此，運(yùn)輸問(wèn)題非基變量的檢驗(yàn)數(shù)可以通過(guò)下列步驟得到：v對(duì)于m+n-1個(gè)基變量，可以得到對(duì)偶問(wèn)題的m+n-1個(gè)等式約束v令一個(gè)對(duì)偶變量vm0，就可以由m+n-1個(gè)等式，求出m個(gè)對(duì)偶變量ui和vj的值v已知ui，vj和cij的值，可以求出對(duì)偶問(wèn)題松弛變量，即非基變量檢驗(yàn)數(shù)的值令v3=0，得到以下等式方程組v3=0u2=7v2=-5u1=10v1=-7-w13=u1+v3-c13=+4-w21=u2+v1-c21=-4+4-4對(duì)于基變量x2

50、3=11，有u2+v3=c23=7，令v3=0，得到u2=7v3=0u2=7u1=10v2=-5v1=-7對(duì)于基變量x22=7，有u2+v2=c22=2，由u2=7，得到v2=-5對(duì)于基變量x12=10，有u1+v2=c12=5，由v2=-5，得到u1=10對(duì)于基變量x11=12，有u1+v1=c11=3，由u1=10，得到v1=-7對(duì)于非基變量x13， 有檢驗(yàn)數(shù)為：u1+v3-c13=10+0-6=+4對(duì)于非基變量x21， 有檢驗(yàn)數(shù)為：u2+v1-c21=7+(-7)-4=-4+4-4總結(jié)：求運(yùn)輸問(wèn)題單純形法非基變量檢驗(yàn)數(shù)的對(duì)偶變量法：v對(duì)于基變量xij0，有ui+vj=cijv對(duì)于m+n-

51、1個(gè)基變量以及vn=0，可以列出m+n個(gè)等式方程，求解m+n個(gè)對(duì)偶變量ui和vjv非基變量xij的檢驗(yàn)數(shù)，等于ui+vj-cij+4-412346753114u1842728136u2591063613u3v1v2v3v4=0非基變量xij的檢驗(yàn)數(shù)zij-cij對(duì)偶變量法(1)v4=012346753114u1842728136u2591063613u3=6v1v2v3v4=0u3+v4=c34u3=6非基變量xij的檢驗(yàn)數(shù)zij-cij對(duì)偶變量法(1)12346753114u1842728136u2591063613u3=6v1v2v3=4v4=0u3+v3=c33v3=4非基變量xij的檢

52、驗(yàn)數(shù)zij-cij對(duì)偶變量法(1)12346753114u1842728136u2=-2591063613u3=6v1v2v3=4v4=0u2+v3=c23u2=-2非基變量xij的檢驗(yàn)數(shù)zij-cij對(duì)偶變量法(1)12346753114u1842728136u2=-2591063613u3=6v1v2=6v3=4v4=0u2+v2=c22v2=6非基變量xij的檢驗(yàn)數(shù)zij-cij對(duì)偶變量法(1)12346753114u1842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0u2+v1=c21v1=10非基變量xij的檢驗(yàn)數(shù)zij-cij對(duì)偶變量法(1)1

53、2346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0u1+v1=c11u1=-4非基變量xij的檢驗(yàn)數(shù)zij-cij對(duì)偶變量法(1)12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0z12-c12=u1+v2-c12=(-4)+6-7=-5-5非基變量xij的檢驗(yàn)數(shù)zij-cij對(duì)偶變量法(1)12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0z13-c13=u1+v3-c13=(-4)+4

54、-5=-5-5-5非基變量xij的檢驗(yàn)數(shù)zij-cij對(duì)偶變量法(1)12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0z14-c14=u1+v4-c14=(-4)+0-3=-7-7-5-5非基變量xij的檢驗(yàn)數(shù)zij-cij對(duì)偶變量法(1)12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0z24-c24=u2+v4-c24=(-2)+0-7=-9-9-5-5-7非基變量xij的檢驗(yàn)數(shù)zij-cij對(duì)偶變量法(1)12346753114u1=-484272

55、8136u2=-2591063613u3=6v1=10v2=6v3=4v4=0z31-c31=u3+v1-c31=6+10-5=1111-5-5-7-9非基變量xij的檢驗(yàn)數(shù)zij-cij對(duì)偶變量法(1)12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0z32-c32=u3+v2-c32=6+6-9=+3+3-5-5-7-911非基變量xij的檢驗(yàn)數(shù)zij-cij對(duì)偶變量法(1)12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0選擇進(jìn)基變量,確定離基變量x

56、31進(jìn)基, minx21,x33=min8,6=6, x33離基+3-5-5-7-91112346753114148427221312275910636131922131213調(diào)整運(yùn)量,重新計(jì)算檢驗(yàn)數(shù),確定進(jìn)基、離基變量x14進(jìn)基, minx11,x34=min14,13=13, x34離基-11-5-5+4+2-812346753111314842722131227591063191922131213調(diào)整運(yùn)量, 重新計(jì)算檢驗(yàn)數(shù)所有zij-cij0，由互補(bǔ)松弛關(guān)系得到，相應(yīng)的對(duì)偶變量滿足wi-wj=cij加上wm=0，可以依次計(jì)算各對(duì)偶變量的值。w2=3w60w3=6w5=4w1=9c24=5

57、c46=1c13=3c35=2c56=4c34=4c12=6234561w4=1對(duì)于非基變量xij，檢驗(yàn)數(shù)為：wi-wj-cij非基變量x24的檢驗(yàn)數(shù)為：w2-w4-c24=3-1-5=-3非基變量x34的檢驗(yàn)數(shù)為：w3-w4-c34=6-1-4=+1計(jì)算結(jié)果與圈法相同。最小費(fèi)用流問(wèn)題的單純形法總結(jié)1. 確定網(wǎng)絡(luò)的一個(gè)初始基礎(chǔ)可行解生成樹；2. 求出各非基邊（生成樹的弦）的檢驗(yàn)數(shù)圈法對(duì)偶變量法3. 確定進(jìn)基變量：檢驗(yàn)數(shù)為正數(shù)，數(shù)值最大的非基邊4. 確定離基變量：在圈中與圈方向相反的邊中流量最小的邊離基。52134b1=8b2=-3b3=-4b4=5b5=-6c14=2c12=3c13=5c43

58、=4c54=7c23=6c35=8c25=152134b1=8b2=-3b3=-4b4=5b5=-6x14=5x12=3x43=10 x35=6c14=2c12=3c13=5c43=4c54=7c23=6c35=8c25=1z=c12x12+c14x14+c43x43+c35x35=33+2 5+4 10+8 610752134b1=8b2=-3b3=-4b4=5b5=-6x14=5x12=3x43=10 x35=6minx35,x43,x14=5，x14離基，調(diào)整流量c14=2c12=3c13=5c43=4c54=7c23=6c35=8c25=152134b1=8b2=-3b3=-4b4=5

59、b5=-6x34=5x12=8x35=1x25=5最優(yōu)解。x12=8, x25=5, x43=5, x35=1, min z=57c14=2c12=3c13=5c43=4c54=7c23=6c35=8c25=1檢驗(yàn)數(shù)-8+1+3-5=-9檢驗(yàn)數(shù)-8+1-6=-13檢驗(yàn)數(shù)-4-8+1+3-2=-10檢驗(yàn)數(shù)-4-8-7=-192345671ff624374317988以下網(wǎng)絡(luò)中，節(jié)點(diǎn)稱為源點(diǎn)(Source)，是供應(yīng)流量的節(jié)點(diǎn)，節(jié)點(diǎn)稱為匯點(diǎn)（Sink），是消耗流量的節(jié)點(diǎn)。其他節(jié)點(diǎn)都是中轉(zhuǎn)節(jié)點(diǎn)，既不產(chǎn)生流量，也不消耗流量。每一條邊都有相應(yīng)的流量上限uij，稱為邊的容量（Capacity）。每一條邊流量

60、的下限都是0。網(wǎng)絡(luò)最大流問(wèn)題：對(duì)于給定的網(wǎng)絡(luò)，求從源點(diǎn)到匯點(diǎn)的最大流量。uij網(wǎng)絡(luò)最大流問(wèn)題的基本概念q鏈的方向，同向邊，反向邊v從源點(diǎn)到匯點(diǎn)的一條鏈，鏈的方向?yàn)閺脑袋c(diǎn)到匯點(diǎn)v鏈上與鏈的方向相同的邊稱為同向邊，方向相反的稱為反向邊。2345671624374317988同向邊反向邊同向邊同向邊q飽和邊，不飽和邊，不飽和邊流量的間隙，不飽和鏈，不飽和鏈的間隙v從源點(diǎn)到匯點(diǎn)的一條鏈，鏈的方向?yàn)閺脑袋c(diǎn)到匯點(diǎn)v如果同向邊（i, j）的流量xij0，稱為邊(i, j)是不飽和的，間隙ij=xij。如果反向邊(i, j)的流量xij0，則稱邊(i, j)是飽和的。v如果從源點(diǎn)到匯點(diǎn)的一條鏈的邊（同向邊和反