1、運籌學教程課件運 籌 學 教 程4.0 版運籌學教程課件運籌學是管理科學的重要理論基礎和應用手段，是管理專業的重要專業基礎課程之一。運籌學根據管理問題的環境條件和決策要求，建立相應的數學模型，利用數學模型對實際問題進行分析和求解，經過分析和比較，得到適合實際問題的方案。前言運籌學簡介運籌學教程課件運籌學是在第二次世界大戰中誕生和發展起來的。由于戰爭的需要，英國和美國招募了一批年輕的科學家和工程師，在軍隊將軍的領導下研究戰爭中的問題，例如大規模轟炸的效果，搜索和攻擊敵軍潛水艇的策略，兵力和軍需物質的調運等等。這些研究在戰爭中取得了很好的效果。當時英國把這些研究成為“作戰研究”，英文是operat

2、ional research，在美國稱為operations research。運籌學教程課件戰后這些研究成果逐漸公開發表，這些理論和方法被應用到經濟計劃，生產管理領域，也產生了很好的效果。這樣，operations research就轉義成為“作業研究”。我國把operations research譯成“運籌學”，非常貼切地涵蓋了這個詞作戰研究和作業研究兩方面的涵義。運籌學的內容十分廣泛，包括線性規劃、整數規劃、動態規劃、非線性規劃、圖論與網絡優化、排隊論、決策理論、庫存理論等。在本課程中，結合管理學科的特點，主要介紹線性規劃、整數規劃、運輸問題、網絡優化、動態規劃和排隊論。運籌學教程課件運

3、籌學教程課件運籌學教程課件線性規劃模型線性規劃模型的結構目標函數 ：max，min約束條件：,=,變量符號：0, unr, 0線性規劃的標準形式目標函數：min約束條件：=變量符號：0unr, 0 )(xb),(ax. t . sxczmax(min)t0xbax. t . sxczmint運籌學教程課件可行域目標函數等值線最優解64-860 x1x2運籌學教程課件凸集凸集不是凸集運籌學教程課件線性規劃可行域和最優解的幾種情況1、可行域封閉 唯一最優解2、可行域封閉 多個最優解3、可行域開放 唯一最優解4、可行域開放 多個最優解5、可行域開放 目標函數無界6、無可行解運籌學教程課件x3=0 x

4、4=0max 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=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線性規劃的基本概念基礎解、基礎可行解、極點x2=0 x1=0oabcd運籌學教程課件q標準化的線性規劃問題，有n個變量，m個約束。q令其中n-m個變量等于零，如果剩下的m個變量的系數矩陣的行列式不等

5、于0，這個mm的矩陣稱為線性規劃的一個基。等于0的n-m個變量稱為非基變量，m個變量稱為基變量。q求解mm的線性方程組，得到基變量的一組解，連同等于0的非基變量這n個變量的值稱為線性規劃的一個基礎解。q如果一個基礎解中的所有變量都是非負的，這個基礎解稱為基礎可行解。q線性規劃的基礎可行解就是可行域的極點。線性規劃的基本概念基礎解、基礎可行解、極點運籌學教程課件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基礎可行解x

6、1=0, x4=0 x2=1, x3=2基礎可行解x2=0, x3=0 x1=3, x4=1基礎可行解x3=0, x4=0 x1=2, x2=1基礎可行解x1=0, x3=0 x2=3, x4=-2是基礎解，但不是可行解oabx3=0 x4=0 x2=0 x1=0cd可行域運籌學教程課件幾何概念代數概念約束直線滿足一個等式約束的解約束半平面滿足一個不等式約束的解約束半平面的交集：凸多邊形滿足一組不等式約束的解約束直線的交點基礎解可行域的極點基礎可行解目標函數等值：一組平行線 目標函數值等于一個常數的解運籌學教程課件maxz=2x1+3x2+x3s.t.x1+3x2+x3152x1+3x2-x3

7、18x1-x2+x33x1,x2,x30min z= -2x1-3x2-x3stx1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1,x2,x3,x4,x5,x60搜索所有基礎可行解求出最優解運籌學教程課件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基礎解為（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基礎可行解，表示可行域的一個極點。目標函數值為：z=20運籌學教程課件x

8、1+3x2+x4=152x1+3x2=18x1-x2=3基變量x1、x2、x4，非基變量x3、x5、x6基礎解為（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基礎可行解，表示可行域的一個極點。目標函數值為：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3運籌學教程課件x1+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基礎解為（x1，x2，x3，x4，x5，x6）=（6

9、，3，0，0，-3，0）是基礎解，但不是可行解，不是一個極點。運籌學教程課件x1+3x2=152x1+3x2=18x1-x2+x6=3基變量x1、x2、x6，非基變量x3、x4、x5基礎解為（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基礎可行解，表示可行域的一個極點。目標函數值為：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3運籌學教程課件3x2+x3+x4=153x2-x3=18-x2+x3=3基變量x2、x3、x4，非基變量x1、x5、x6基礎解為（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-3

10、0，0，0）是基礎解，但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3運籌學教程課件3x2+x3=153x2-x3+x5=18-x2+x3=3基變量x1、x2、x3，非基變量x4、x5、x6基礎解為（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基礎可行解，表示可行域的一個極點。目標函數值為：z=15x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3運籌學教程課件3x2+x3=153x2-x3=18-x2+x3+x6=3基變量x1、x2、x3，非基變量x4、x5、x6基礎解為（x1

11、，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基礎解但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3運籌學教程課件 單純形法原理（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 引進松弛變量運籌學教程課件x2=0 x1=0 x3=0 x4=0oabcx1,x2=0為非基變量x3,x40為基變量當前基礎可行解：(x1

12、,x2,x3,x4)=(0,0,3,1)z=0 x2進基,從0開始增加，x3,x4隨之減少第一次疊代：目標函數和基變量分別用非基變量表示： z=-x1-2x2選擇x2進基 x3 =3-x1-x2 x4=1 -x2x2=1成為基變量，x4=0成為離基變量當前基礎可行解：(x1,x2,x3,x4)=(0,1,2,0)z=-2單純形法原理(2)第一次疊代運籌學教程課件確定離基變量的進一步討論設非基變量為x1、x2，基變量為x3、x4、x5，進基變量為x2x3 =5- x1-4x2 x4 =4-2x1-3x2 x5 =2-3x1- x25/4=1.254/3=1.332/1=2min5/4,4/3,2

13、/1=5/4當x2增加到1.25時x30離基x3 =5- x1+4x2 x4 =4-2x1-3x2 x5 =2-3x1- x2x3增加4/3=1.332/1=2min4/3,2/1=4/3當x2增加到1.33時x40離基x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1- x2x3增加x4增加2/1=2min2/1=2/1當x2增加到2時x50離基x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1+ x2x3增加x4增加x5增加x2可以無限增加，可行域是開放區域，目標函數無界運籌學教程課件x2=0 x1=0 x3=0 x4=0oabc第二次疊代：

14、目標函數和基變量分別用非基變量表示： z=-2-x1+2x4選擇x1進基 x3 =2-x1+x4 x2=1 -x4當前基礎可行解：(x1,x2,x3,x4)=(0,1,2,0)z=-2單純形法原理（3）第二次疊代x1進基，從0開始增加，基變量x2保持不變，x3從2開始減少x1=2成為基變量，x3=0成為非基變量當前基礎可行解：(x1,x2,x3,x4)=(2,1,0,0)z=-4運籌學教程課件x2=0 x1=0 x3=0 x4=0oabc第三次疊代：目標函數和基變量分別用非基變量表示： z=-4+x3+x4 x1 =2-x3+x4 x2=1 -x4非基變量在目標函數中的系數全部大于0，已獲得最

15、優解。單純形法原理（4）最優解的判定x1=2成為基變量，x3=0成為非基變量當前基礎可行解：(x1,x2,x3,x4)=(2,1,0,0)z=-4運籌學教程課件x2=0 x1=0 x3=0 x4=0oabc單純形法原理(5)疊代過程回顧第一次疊代x2進基，x4離基第二次疊代x1進基，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最優解運籌學教程課件單純形法原理（6）單純形法總結step 0 找到一個初始的基礎可行解，確定基變量和非基變量。轉step 1。step

16、 1 將目標函數和基變量分別用非基變量表示。轉step 2。step 2 如果目標函數中所有非基變量的系數全部為正數，則已經獲得最優解。運算終止。否則，選取系數為負數并且絕對值最大的非基變量進基。轉step 3。step 3 如果進基變量增加時，基變量都不減少，則可行域開放，目標函數無界。運算終止。否則，隨著進基變量的增加，最先下降到0的基變量離基。轉step 1。運籌學教程課件=目標函數約束條件基矩陣右邊常數=基變量運籌學教程課件=進基變量離基變量目標函數約束條件右邊常數=運籌學教程課件=目標函數約束條件新的基矩陣右邊常數=運籌學教程課件=進基變量離基變量目標函數約束條件基矩陣=運籌學教程課

17、件=目標函數約束條件新的基矩陣右邊常數=運籌學教程課件線性規劃基本概念練習（1）036x1x2oabcefghi46-2min z=-x1+2x2s.t. 3x1+2x212(1) x1+2x2 6(2) -2x1+ x2 4(3) x1, x2 01、約束條件（1）對應的直線是（ ），對應的半平面是 約束條件（2）對應的直線是（ ），對應的半平面是 約束條件（3）對應的直線是（ ），對應的半平面是2、這個線性規劃的可行域是（ ）。3、對于z=2和4,分別畫出目標函數等值線。4、這個線性規劃的最優解位于（ ）。acefbcdheghicdgez=2z=4cd4運籌學教程課件036x1x2oab

18、cefghi46-2d線性規劃基本概念練習（2）5、x1等于0的直線是( )， x2等于0的直線是( )， x3等于0的直線是( )， x4等于0的直線是( )， x5等于0的直線是( )。6、a點對應的基變量是( )，非基變量是（ ）； d點對應的基變量是( )，非基變量是（ ）。7、a點不是可行解， 是由于( )0, f點不是可行解， 是由于( )0, i 點不是可行解， 是由于( )0，則原問題沒有可行解。step 3 轉到第二階段，從原問題的初始基礎可行解出發，求出原問題的最優解。運籌學教程課件案例一 食油生產計劃儲罐1儲罐2儲罐3儲罐4儲罐5硬質油1硬質油2軟質油1軟質油2軟質油3硬

19、質油精煉軟質油精煉混合成品油原料加工成品運籌學教程課件dual運籌學教程課件對偶問題max y=btws.t. atwcw 0minbactcatbtmaxmnmn運籌學教程課件二、對偶問題的性質1、對偶的對偶就是原始問題對偶的定義max y=btws.t. atwcw 0對偶的定義min y=-btws.t. -atw-cw 0運籌學教程課件2、其他形式問題的對偶原始問題約束條件的性質，影響對偶問題變量的性質。原始問題變量的性質，影響對偶問題約束條件的性質。max y=btws.t. atwc w 0max y=btws.t. atwc w :unrmax y=btws.t. atwc w

20、0運籌學教程課件min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 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原始問題變量的個數(3)等于對偶問題約束條件的個數(3)； 原始問題約束條件的個數(4)等于對偶問題變量的個數(4)。q原始問題變量的性質影響對偶問題約束條件的性質。 原始問題約束條件的

21、性質影響對偶問題變量的性質。運籌學教程課件三、原始對偶關系1、可行解的目標函數值之間的關系 設xf、wf分別是原始問題和對偶問題的可行解z=ctxf wtaxf wtb=y2、最優解的目標函數值之間的關系 設xo、wo分別是原始問題和對偶問題的最優解 z=ctxo=wotaxo=wotb=y運籌學教程課件3、原始問題和對偶問題最優解之間的互補松弛關系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對偶引進松弛變量引進松弛變量互補松弛關系x，xsw

22、，wsxtws=0 wtxs=0運籌學教程課件max y=btws.t. atw+ws=cw, ws 0xtws=0wtxs=0atwiwscmn=nxa-ixsb=nmm原始問題和對偶問題變量、松弛變量的維數運籌學教程課件w1. wi . wm wm+1 . wm+j . wn+m x1 . xj . xn xn+1 xn+i xn+m 對偶問題的變量 對偶問題的松弛變量 原始問題的變量 原始問題的松弛變量xjwm+j=0wixn+i=0(i=1,2,m; j=1,2,n)在一對變量中，其中一個大于0，另一個一定等于0運籌學教程課件3、原始問題和對偶問題最優解的充分必要條件 ax-xs=b

23、x, xs 0原始可行條件（primal feasible condition, pfc）atw+ws=c w, ws 0對偶可行條件（dual feasible condition, dfc）kuhn-tucher 條件 xtws=0 wtxs=0互補松弛條件（complementary slackness condition, pfc）運籌學教程課件四、對偶單純形法運籌學教程課件對偶問題的解（w1, w2, w3, w4, w5,w6）=(0, 0, 0, -1, -2, -1)不是對偶問題的可行解運籌學教程課件對偶問題的解（w1, w2, w3, w4, w5,w6）=(0, 2/3,

24、0, 1/3, 0, -1/3)不是對偶問題的可行解運籌學教程課件對偶問題的解（w1, w2, w3, w4, w5,w6）=(1/2, 1/2, 0, 1/2, 0, 0)是對偶問題的可行解運籌學教程課件結論 單純形法求解的過程，從對偶的觀點來看，是在始終保持原始可行解的條件下，不斷改進對偶可行性的過程。一個從對偶不可行的解，經過幾次疊代，逐步向對偶可行解靠攏，一旦得到的解既是原始可行的，又是對偶可行的，這個解就分別是原始問題和對偶問題的最優解。運籌學教程課件1、用單純形表求解原始問題的四種形式min z=ctxs.t. axb x 0min z=ctxs.t. ax b x 0max z=

25、ctxs.t. ax b x 0max z=ctxs.t. ax b x 0（2）（3）（4）（1）運籌學教程課件單純形表和對偶(1)min z=ctxs.t. ax-xs=b x, xs0max y=btws.t. atw+ws=c w, ws0max y=btws.t. atwc w0對偶問題min z=ctxs.t. axb x 0原始問題引進松弛變量引進松弛變量運籌學教程課件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,

26、 ws0zxxsrhs1cbtb-1a-ct-cbtb-1cbtb-1b0b-1a-b-1b-1bwt=cbtb-1wst=ct-wta運籌學教程課件min z=ctxs.t. ax+xs=b x, xs0max y=btws.t. atw+ws=c w 0, ws0單純形表和對偶(2)max y=btws.t. atwc w 0對偶問題min z=ctxs.t. ax b x 0原始問題引進松弛變量引進松弛變量運籌學教程課件zxxsrhs1-wstwtcbtb-1b0b-1ab-1b-1bzxxsrhs1-ct0t00aibmin z=ctxs.t. ax+xs=b x, xs0max y=

27、btws.t. atw+ws=c w 0, ws0zxxsrhs1cbtb-1a-ctcbtb-1cbtb-1b0b-1ab-1b-1bwt=cbtb-1wst=ct-wta運籌學教程課件max z=ctxs.t. ax-xs=b x, xs0max y=btws.t. atw-ws=c w 0, ws0單純形表和對偶(3)min y=btws.t. atw c w 0對偶問題max z=ctxs.t. ax b x 0原始問題引進松弛變量引進松弛變量運籌學教程課件zxxsrhs1wst-wtcbtb-1b0b-1a-b-1b-1bzxxsrhs1-ct0t00a-ibmax z=ctxs.t

28、. 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- ct運籌學教程課件max z=ctxs.t. ax+xs=b x, xs0max y=btws.t. atw-ws=c w, ws0單純形表和對偶(4)min y=btws.t. atw c w 0對偶問題max z=ctxs.t. ax b x 0原始問題引進松弛變量引進松弛變量運籌學教程課件zxxsrhs1wstwtcbtb-1b0b-1ab-1b-1bzxxsrhs1-c

29、t0t00aibmax 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- ct運籌學教程課件min z=6x1+8x2+3x3s.t. x1+ x2 1 x1+2x2+x3 -1 x1, x2, x3 0max 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,

30、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引進松弛變量 求對偶引進松弛變量求解代入約束求出松弛變量互補松弛關系代入約束求解(x1, x2, x3, x4, x5)=(1, 0, 0, 0, 2)運籌學教程課件min z=6x1+8x2+3x3s.t. x1+ x2

31、 -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 w2運籌學教程課件如何從最優單純形表中讀出對偶問題的解（1）初始單純形表最優單純形表運籌學教程課件如何從最優單純形表中讀出對偶問題的解（2）初始單純形表最優單純形表運籌學教程課件2、對偶單純形法（初始

32、解原始不可行的問題）0 xxx2xx2x5xx3x24xxx. t . sxx2x3zmin3213213213213210 xxxxxx2xxx2x5xxx3x24xxxx. t . sxx2x3zmin654321632153214321321運籌學教程課件0 xxxxxx2xxx2x25xxx3x24xxxx. t . sxx2x3zmin654321632153214321321 z x1 x2 x3 x4 x5 x6 rhs z 1 -3 -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

33、 -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 x6 0 -2/3 0 -1/3 0 2/3 1 -16/3 運籌學教程課件 z x1 x2 x3 x4 x5 x6 r h s

34、 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 已獲得最優解：（x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35對偶問題的最優解為：（w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=35運籌學教程課件3、初始解原始、對偶都不可行的問題0 xxx2xx2x5xx3x24xxx. t . sx2x2x3zmin3213213213213210 xxxxxx2xxx2x5xx

35、x3x24xxxx. t . sx2x2x3zmin654321632153214321321運籌學教程課件0 xxxxxx2xxx2x25xxx3x24xxxx. t . sx2x2x3zmin654321632153214321321zx1x2x3x4x5x6rhsz1-3-220000 x401-111004x502-31010-5x60-22-1001-2解法1：先解決原始可行性運籌學教程課件zx1x2x3x4x5x6rhsz1-700024-18x40-100112-5x200100-1-17x302010-2-316zx1x2x3x4x5x6rhsz1-720002-4x40-11

36、01012x500-10011-7x302-2100-12運籌學教程課件zx1x2x3x4x5x6rhsz1000-7-5-1017x10100-1-1-25x200100-1-17x300012016在得到原始可行解時同時得到對偶可行解，已獲得最優解：（x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17對偶問題的最優解為：（w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17運籌學教程課件zx1x2x3x4x5x6rhsz1-3-220000 x401-111004x502-31010-

37、5x60-22-1001-2zx1x2x3x4x5x6rhsz1-500-200-8x301-111004x501-20-110-9x60-1101012解法2：先解決對偶可行性已得到對偶可行解，再用對偶單純形法求解運籌學教程課件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運籌學教程課件得到原始可行解，已獲得最優解：（x1, x2,

38、 x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17對偶問題的最優解為：（w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17運籌學教程課件0 xxxxxxbxxaxaxabxxaxaxabxxaxaxa. t . sxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111nn2211五、對偶的經濟解釋1、原始問題是利潤最大化的生產計劃問題單位產品的利潤（元/件）產品產量（件）總利潤（元）資源限量（噸）單位產品消耗的資源（噸/件）剩余的資源（噸）消耗的

39、資源（噸）運籌學教程課件2、對偶問題0wwwwwwcwwawawacwwawawacwwawawa. t . swbwbwbyminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm2211資源限量（噸）資源價格（元/噸）總利潤（元）對偶問題是資源定價問題，對偶問題的最優解w1、w2、.、wm稱為m種資源的影子價格（shadow price）原始和對偶問題都取得最優解時，最大利潤 max z=min y運籌學教程課件3、資源影子價格的性質影子價格越大，說明這種資源越是相對緊缺影子價格越小，說明這種資源相對不緊缺如果最優生產計劃下某種資源有剩余，這種資

40、源的影子價格一定等于0種資源的邊際利潤第種資源的增量第最大利潤的增量iibzwiooimmii2211wbwbwbwbyzmmiii2211wbw)bb(wbwbzziiwbz運籌學教程課件w1w2wm4、產品的機會成本機會成本表示減少一件產品所節省的所有資源可以增加的利潤mmjiij2j21j1wawawawa增加單位資源可以增加的利潤減少一件產品的產量可以節省的資源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211運籌學教程課件機會成本利潤差

41、額成本5、產品的差額成本（reduced cost）wm+j=(ai1w1+ai2w2+.aimwm)-cj差額成本機會成本利潤0wwwwwwcwwawawacwwawawacwwawawa. t . swbwbwbyminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm2211運籌學教程課件5、互補松弛關系的經濟解釋wixn+i=0如果wi0，則xn+i=0如果xn+i0，則wi=0邊際利潤大于0的資源，在最優生產計劃條件下沒有剩余wm+jxj=0如果wm+j0，則xj=0如果xj0，則wm+j=0最優生產計劃條件下有剩余的資源，其邊際利潤等于0

42、差額成本大于0（機會成本大于利潤）的產品，不安排生產安排生產的產品，差額成本等于0（機會成本等于利潤）運籌學教程課件和資源有關的量q資源限量（噸）q資源占用（噸）q資源剩余（噸） 資源限量資源占用q資源的影子價格（資源的邊際利潤）（元/噸）和產品有關的量q產品利潤（元/件）q產品產量（件）q產品的機會成本（元/件）q產品的差額成本（元/件） 機會成本利潤互補松弛關系互補松弛關系運籌學教程課件max z=32x1+31x2+55x3+32x4+70 x5s.t. x1+2x2+ 3x4+2x54000 2x1+2x2+3x3+ x4+4x52000 x1 +2x3+2x4+2x51800 4x1

43、+3x2+5x3 +3x52400 x1，x2，x3，x4，x50運籌學教程課件lp 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 slack or surplus dual prices 2)200.000000 0.000000 3) 0.000

44、00015.500000 4) 0.000000 8.250000 5) 750.000000 0.000000 no. iterations= 2運籌學教程課件2000075038002000180016507.2508.008.539.253163.03278.5產品的機會成本產品對設備的消耗設備的影子價格資源的占用 產品產量產品對設備的消耗資源的剩余資源限量資源占用產品的差額成本產品的機會成本產品利潤產品產量和產品的機會差額成本互補松弛資源剩余和資源的影子價格互補松弛運籌學教程課件運籌學教程課件2312341d1=22d2=13d3=12d4=13s2=27s3=19s1=14供應地運價

45、需求地6753482759106供應量需求量總供應量60噸總需求量60噸供求平衡的運輸問題運籌學教程課件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=zmin343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211供應地約束需求地約束由于前m個供應地約束和后n個需求地約束是線

46、性相關的，因此運輸問題系數矩陣的秩m+n。可以證明，運輸問題系數矩陣的秩為m+n-1。即運輸問題有m+n-1個基變量，mn-(m+n-1)個非基變量。例如以上問題m=3，n=4，基變量為3416個，非基變量為1266個。運籌學教程課件123467531x11x12x13x141484272x21x22x23x2427591063x31x32x33x341922131213運籌學教程課件 m個供應地、n個需求地的運輸問題，任何一個基要滿足以下三個條件：q基變量的個數為m+n-1；q同行同列的基變量不能形成回路；q運輸表的每一行和每一列中至少有一個基變量。運籌學教程課件基在運輸表中的表示運籌學教程

47、課件運輸表中同行同列的變量組成回路運籌學教程課件 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 813131466運籌學教程課件初始基礎可行解最小元素法（1）運籌學教程課件1234675311314184272122715591063192213121300初始基礎可行解最小元素法（2）運籌學教程課件123467531131418427213122725910631922131213000初始基礎可行解最小元素法（3）運籌學教程課件123467531131418427213122725910631919022131213

48、3000初始基礎可行解最小元素法（4）運籌學教程課件12346753111314084272131227259106319190221312132000初始基礎可行解最小元素法（5）運籌學教程課件123467531113140842722131227059106319190221312130000初始基礎可行解最小元素法（6）運籌學教程課件1234675311414842728136275910636131922131213-5非基變量xij的檢驗數zij-cij閉回路法(1)z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5運籌學教程課件1234675311414842

49、728136275910636131922131213-5z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5-5非基變量xij的檢驗數zij-cij閉回路法(2)運籌學教程課件1234675311414842728136275910636131922131213-5z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7-7-5非基變量xij的檢驗數zij-cij閉回路法(3)運籌學教程課件1234675311414842728136275910636131922131213-5z24-c24=(c23-c

50、33+ c34)-c24=(2-10+6)-7=-9-9-5-7非基變量xij的檢驗數zij-cij閉回路法(4)運籌學教程課件1234675311414842728136275910636131922131213-5z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11+11-5-7-9非基變量xij的檢驗數zij-cij閉回路法(5)運籌學教程課件1234675311414842728136275910636131922131213-5z32-c32=(c22-c23+ c33)-c32=(4-2+10)-9=+3+3-5-7-9+11非基變量xij的檢驗數zi

51、j-cij閉回路法(6)運籌學教程課件12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0選擇進基變量,確定離基變量x31進基, minx21,x33=min8,6=6, x33離基+3-5-5-7-911運籌學教程課件12346753114148427221312275910636131922131213調整運量,重新計算檢驗數,確定進基、離基變量x14進基, minx11,x34=min14,13=13, x34離基-11-5-5+4+2-8運籌學教程課件1234675311131484272213122759106319

52、1922131213調整運量, 重新計算檢驗數所有zij-cij0時，相應的wij=0，同時由單純形表的結構可以知道，對偶問題的松弛變量的相反數就是非基變量的檢驗數，因此，運輸問題非基變量的檢驗數可以通過下列步驟得到：v對于m+n-1個基變量，可以得到對偶問題的m+n-1個等式約束v令一個對偶變量vm0，就可以由m+n-1個等式，求出m個對偶變量ui和vj的值v已知ui，vj和cij的值，可以求出對偶問題松弛變量，即非基變量檢驗數的值運籌學教程課件令v3=0，得到以下等式方程組v3=0u2=7v2=-5u1=10v1=-7-w13=u1+v3-c13=+4-w21=u2+v1-c21=-4運籌

53、學教程課件+4-4運籌學教程課件對于基變量x23=11，有u2+v3=c23=7，令v3=0，得到u2=7v3=0u2=7u1=10v2=-5v1=-7對于基變量x22=7，有u2+v2=c22=2，由u2=7，得到v2=-5對于基變量x12=10，有u1+v2=c12=5，由v2=-5，得到u1=10對于基變量x11=12，有u1+v1=c11=3，由u1=10，得到v1=-7對于非基變量x13， 有檢驗數為：u1+v3-c13=10+0-6=+4對于非基變量x21， 有檢驗數為：u2+v1-c21=7+(-7)-4=-4+4-4運籌學教程課件總結：求運輸問題單純形法非基變量檢驗數的對偶變量

54、法：v對于基變量xij0，有ui+vj=cijv對于m+n-1個基變量以及vn=0，可以列出m+n個等式方程，求解m+n個對偶變量ui和vjv非基變量xij的檢驗數，等于ui+vj-cij+4-4運籌學教程課件12346753114u1842728136u2591063613u3v1v2v3v4=0非基變量xij的檢驗數zij-cij對偶變量法(1)v4=0運籌學教程課件12346753114u1842728136u2591063613u3=6v1v2v3v4=0u3+v4=c34u3=6非基變量xij的檢驗數zij-cij對偶變量法(1)運籌學教程課件12346753114u18427281

55、36u2591063613u3=6v1v2v3=4v4=0u3+v3=c33v3=4非基變量xij的檢驗數zij-cij對偶變量法(1)運籌學教程課件12346753114u1842728136u2=-2591063613u3=6v1v2v3=4v4=0u2+v3=c23u2=-2非基變量xij的檢驗數zij-cij對偶變量法(1)運籌學教程課件12346753114u1842728136u2=-2591063613u3=6v1v2=6v3=4v4=0u2+v2=c22v2=6非基變量xij的檢驗數zij-cij對偶變量法(1)運籌學教程課件12346753114u1842728136u2=-

56、2591063613u3=6v1=10v2=6v3=4v4=0u2+v1=c21v1=10非基變量xij的檢驗數zij-cij對偶變量法(1)運籌學教程課件12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0u1+v1=c11u1=-4非基變量xij的檢驗數zij-cij對偶變量法(1)運籌學教程課件12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0z12-c12=u1+v2-c12=(-4)+6-7=-5-5非基變量xij的檢驗數zij-cij對偶變量法(

57、1)運籌學教程課件12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0z13-c13=u1+v3-c13=(-4)+4-5=-5-5-5非基變量xij的檢驗數zij-cij對偶變量法(1)運籌學教程課件12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0z14-c14=u1+v4-c14=(-4)+0-3=-7-7-5-5非基變量xij的檢驗數zij-cij對偶變量法(1)運籌學教程課件12346753114u1=-4842728136u2=-25910636

58、13u3=6v1=10v2=6v3=4v4=0z24-c24=u2+v4-c24=(-2)+0-7=-9-9-5-5-7非基變量xij的檢驗數zij-cij對偶變量法(1)運籌學教程課件12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0z31-c31=u3+v1-c31=6+10-5=1111-5-5-7-9非基變量xij的檢驗數zij-cij對偶變量法(1)運籌學教程課件12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0z32-c32=u3+v2-c32

59、=6+6-9=+3+3-5-5-7-911非基變量xij的檢驗數zij-cij對偶變量法(1)運籌學教程課件12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0選擇進基變量,確定離基變量x31進基, minx21,x33=min8,6=6, x33離基+3-5-5-7-911運籌學教程課件12346753114148427221312275910636131922131213調整運量,重新計算檢驗數,確定進基、離基變量x14進基, minx11,x34=min14,13=13, x34離基-11-5-5+4+2-8運籌學教程課

60、件12346753111314842722131227591063191922131213調整運量, 重新計算檢驗數所有zij-cij0，由互補松弛關系得到，相應的對偶變量滿足wi-wj=cij加上wm=0，可以依次計算各對偶變量的值。運籌學教程課件w2=3w60w3=6w5=4w1=9c24=5c46=1c13=3c35=2c56=4c34=4c12=6234561w4=1對于非基變量xij，檢驗數為：wi-wj-cij非基變量x24的檢驗數為：w2-w4-c24=3-1-5=-3非基變量x34的檢驗數為：w3-w4-c34=6-1-4=+1計算結果與圈法相同。運籌學教程課件最小費用流問題的