1、目 錄第一章線性規劃第二章對偶第三章整數規劃第四章運輸問題第五章網絡優化第六章動態規劃第一章 線性規劃線性規劃模型線性規劃的圖解可行域的性質線性規劃的根本概念根底解、根底可行解單純形表線性規劃的矩陣表示線性規劃模型線性規劃模型的構造目的函數 ：max，min約束條件：,=,變量符號：0, unr, 0線性規劃的規范方式目的函數：min約束條件：=變量符號：0線性規劃的圖解max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20可行域目的函數等值線最優解64-860 x1x2可行域的性質線性規劃的可行域是凸集線性規劃的最優解在極點上凸集凸集不是凸集極點線性規劃的根本概念

2、線性規劃的基矩陣、基變量、非基變量=目的函數約束條件行列式0基矩陣右邊常數基變量x1、x2、x3，非基變量x4、x5、x6根底解為x1，x2，x3，x4，x5，x6=5，3，1，0，0，0是根底可行解，表示可行域的一個極點。目的函數值為：z=20基變量x1、x2、x4，非基變量x3、x5、x6根底解為x1，x2，x3，x4，x5，x6=27/5，12/5，0，2/5，0，0是根底可行解，表示可行域的一個極點。目的函數值為：z=18基變量x1、x2、x5，非基變量x3、x4、x6根底解為x1，x2，x3，x4，x5，x6=6，3，0，0，-3，0是根底解，但不是可行解，不是一個極點。基變量x1、

3、x2、x6，非基變量x3、x4、x5根底解為x1，x2，x3，x4，x5，x6=3，4，0，0，0，4是根底可行解，表示可行域的一個極點。目的函數值為：z=18基變量x2、x3、x4，非基變量x1、x5、x6根底解為x1，x2，x3，x4，x5，x6=0，21/2，27/2，-30，0，0是根底解，但不是可行解?；兞縳1、x2、x3，非基變量x4、x5、x6根底解為x1，x2，x3，x4，x5，x6=0，3，6，0，15，0是根底可行解，表示可行域的一個極點。目的函數值為：z=15基變量x1、x2、x3，非基變量x4、x5、x6根底解為x1，x2，x3，x4，x5，x6=0，11/2，-3/

4、2，0，0，10是根底解但不是可行解。=目的函數約束條件基矩陣右邊常數進基變量、離基變量、基變換=基變量=進基變量離基變量目的函數約束條件右邊常數=目的函數約束條件新的基矩陣右邊常數=進基變量離基變量目的函數約束條件基矩陣=目的函數約束條件新的基矩陣右邊常數=根底解、根底可行解max z=x1+3x2Ds.t. x1+ x2+x3=6 B-x1+2x2 +x4=8 x4=0 C x3=0 x1, x2,x3,x40 x1=0 E O x2=0 A單純形表求解線性規劃問題寫成規范化方式寫出單純形表25/136/20-3-20-2-72011/201-1/27/1/21x51/2101/218/1

5、/2071811/21/2x20 x6離基，x2進基，x5離基，x1進基，0-4-2-2-1-8601102-11x101-1101411010 x20得到最優解，最優解為：x1，x2，x3，x4，x5，x6=14，11，0，0，0，0min z=-86，max z=86線性規劃的矩陣表示=CBTB-1aj-cj=zj-cj 稱為非基變量的檢驗數Reduced CostB-1aj=Yj， B-1b= ，CBTB-1b=z0第二章 對偶線性規劃對偶的定義對偶問題的性質原始對偶關系 目的函數值之間的關系 最優解之間的關系互補松弛關系 最優解的Kuhn-Tucher條件對偶可行基對偶單純形法對偶的經

6、濟解釋DUAL一、對偶的定義原始問題min z=CTXs.t.AXbX 0對偶問題max y=bTWs.t. ATWCW 0minbACTCATbTmaxmnmn二、對偶問題的性質1、對偶的對偶就是原始問題max z=-CTXs.t. -AX-bX 0min y=-bTWs.t. -ATW-CW 0max y=bTWs.t. ATWCW 0min z=CTXs.t. AXb X 0對偶的定義對偶的定義min z=CTXs.t.AXbX 0max y=bTWs.t. ATWC W 02、其他方式問題的對偶min z=CTXs.t.AXbX 0max y=bTWs.t. ATWC W 0min z

7、=CTXs.t.AX=bX 0max y=bTWs.t. ATWC W ：unr三、原始對偶關系1、可行解的目的函數值之間的關系 設XF、WF分別是原始問題和對偶問題的可行解z=CTXF WTAXF WTb=y2、最優解的目的函數值之間的關系 設Xo、Wo分別是原始問題和對偶問題的最優解 z=CTXo=WoTAXo=WoTb=y3、原始問題和對偶問題最優解之間的互補松弛關系XTWS=0WTXS=0min 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對

8、偶引進松弛變量引進松弛變量互補松弛關系min z=CTXs.t.AX-XS=bX, XS 0max y=bTWs.t. ATW+WS=CW, WS 0XTWS=0WTXS=0mn=WWSATICn=AXS-IbnmmX原始問題和對偶問題變量、松弛變量的維數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，另一個一定等于0Kuhn-Tucher 條件3、原始問題和對偶問題最優解的充分必

9、要條件 (1)原始可行條件PFCAX-XS=bX, XS 0(2)對偶可行條件DFCATW+WS=CW, WS 0(3)互補松弛條件CSCXTWS=0WTXS=0四、對偶單純形法1、用單純形表求解原始問題的四種方式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 02341單純形表和對偶(1)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.

10、ATWC W0對偶問題原始問題引進松弛變量引進松弛變量min z=CTXs.t. AX-XS=b X, XS0max y=bTWs.t. ATW+WS=C W, WS0WT=CBTB-1WST=CT-WTAmin z=CTXs.t. AX+XS=b X, XS0max y=bTWs.t. ATW+WS=C W 0, WS0min z=CTXs.t. AX b X 0max y=bTWs.t. ATWC W 0單純形表和對偶(2)對偶問題原始問題引進松弛變量引進松弛變量min z=CTXs.t. AX+XS=b X, XS0max y=bTWs.t. ATW+WS=C W 0, WS0WT=CB

11、TB-1WST=CT-WTAmax z=CTXs.t. AX-XS=b X, XS0max y=bTWs.t. ATW-WS=C W 0, WS0max z=CTXs.t. AX b X 0min y=bTWs.t. ATW C W 0單純形表和對偶(3)對偶問題原始問題引進松弛變量引進松弛變量max z=CTXs.t. AX-XS=b X, XS0min y=bTWs.t. ATW-WS=C W 0, WS0WT=CBTB-1WST=WTA- CTmax z=CTXs.t. AX+XS=b X, XS0max y=bTWs.t. ATW-WS=C W, WS0max z=CTXs.t. AX

12、 b X 0min y=bTWs.t. ATW C W 0單純形表和對偶(4)對偶問題原始問題引進松弛變量引進松弛變量max z=CTXs.t. AX+XS=b X, XS0min y=bTWs.t. ATW-WS=C W, WS0WT=CBTB-1WST=WTA- CT2、對偶單純形法初始解原始不可行的問題已獲得最優解：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=353、初始解原始、對偶都不可行的問題解法1：先處理原始可行性在得

13、到原始可行解時同時得到對偶可行解，已獲得最優解：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解法2：先處理對偶可行性已得到對偶可行解，再用對偶單純形法求解得到原始可行解，已獲得最優解：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五、對偶的經濟解釋1、原始問

14、題是利潤最大化的消費方案問題單位產品的利潤元/件產品產量件總利潤元資源限量噸單位產品耗費的資源噸/件剩余的資源噸耗費的資源噸2、對偶問題資源限量噸資源價錢元/噸總利潤元對偶問題是資源定價問題，對偶問題的最優解w1、w2、.、wm稱為m種資源的影子價錢Shadow Price原始和對偶問題都獲得最優解時，最大利潤 max z=min y3、資源影子價錢的性質影子價錢越大，闡明這種資源越是相對緊缺影子價錢越小，闡明這種資源相對不緊缺假設最優消費方案下某種資源有剩余，這種資源的影子價錢一定等于0w1w2wm4、產品的時機本錢時機本錢表示減少一件產品所節省的資源可以添加的利潤添加單位資源可以添加的利潤

15、減少一件產品可以節省的資源時機本錢利潤差額本錢5、產品的差額本錢Reduced Cost差額本錢=時機本錢 - 利潤5、互補松弛關系的經濟解釋在利潤最大化的消費方案中1邊沿利潤大于0的資源沒有剩余2有剩余的資源邊沿利潤等于03安排消費的產品時機本錢等于利潤4時機本錢大于利潤的產品不安排消費第四章 運輸問題運輸問題的表示網絡圖、線性規劃模型、運輸表初始根底可行解西北角法、最小元素法非基變量的檢驗數閉回路法、對偶變量法確定進基變量，調整運量，確定離基變量2321341運輸問題網絡圖s2=10s3=15d1=13d2=21d3=9d4=7s1=25供應量供應地運價需求量需求地675384275910

16、6運輸問題線性規劃模型供應地約束需求地約束運輸問題的表格表示初始根底可行解西北角法813131466初始根底可行解最小元素法1最小元素法2最小元素法3最小元素法4最小元素法5最小元素法6-5非基變量xij的檢驗數zij-cij閉回路法(1)z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5-5閉回路法(2)z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5-5-5閉回路法(3)z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7-7-5-5閉回路法(4)z24-c24=(c23-c

17、33+ c34)-c24=(2-10+6)-7=-9-9-5-7-5閉回路法(5)z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11+11-5-7-9-5閉回路法(6)z32-c32=(c22-c23+ c33)-c32=(4-2+10)-9=+3+3-5-7-9+11非基變量xij的檢驗數zij-cij對偶變量法(1)v4=0對偶變量法(2)u3+v4=c34u3=6對偶變量法(3)u3+v3=c33v3=4對偶變量法(4)u2+v3=c23u2=-2對偶變量法(5)u2+v2=c22v2=6對偶變量法(6)u2+v1=c21v1=10對偶變量法(7)u1+v

18、1=c11u1=-4對偶變量法(8)z12-c12=u1+v2-c12=(-4)+6-7=-5-5對偶變量法(9)z13-c13=u1+v3-c13=(-4)+4-5=-5-5-5對偶變量法(10)z14-c14=u1+v4-c14=(-4)+0-3=-7-7-5-5對偶變量法(11)z24-c24=u2+v4-c24=(-2)+0-7=-9-9-5-5-7對偶變量法(12)z31-c31=u3+v1-c31=6+10-5=1111-5-5-7-9對偶變量法(13)z32-c32=u3+v2-c32=6+6-9=+3+3-5-5-7-911選擇進基變量,確定離基變量x31進基, minx21,

19、x33=min8,6=6, x33離基+3-5-5-7-911調整運量,重新計算檢驗數,確定進基、離基變量x13進基, minx11,x34=min14,13=13, x34離基-11-5-5+4+2-8調整運量, 重新計算檢驗數一切zij-cij0,得到最優解。Min z=61+3 13+8 2+4 13+2 12+5 19=142-11-5-5-4-8-2第五章 網絡優化網絡的根本概念網絡最小費用流問題網絡最大流問題最短途徑問題網絡的根本概念節點與有向邊 每一條邊和兩個節點關聯，一條邊可以用兩個節點的標號表示i，jji途徑Path 前后相繼并且方向一樣的邊序列 P=(1,2),(2,3),

20、(3,4)42314231網絡由節點和邊組成回路Circuit 起點和終點重合的途徑稱為回路 =(1,2),(2,4),(4,1) 回路中各條邊方向一樣4231鏈Chain 前后相繼并且方向不一定一樣的邊序列稱為鏈 C=(1,2),(3,2),(3,4)4231連通圖 恣意兩個節點之間至少有一條鏈的圖稱為連通圖24351圈(Cycle) 起點和終點重合的鏈稱為圈 =(1,2),(2,4),(3,4),(1,3) 圈中各條邊方向不一定一樣4231樹(Tree) 無圈的連通圖稱為樹 樹中只與一條邊關聯的節點稱為懸掛節點樹的性質任何樹至少有一個懸掛節點243512435124351假設樹的節點個數為

21、m，那么邊的個數為m-1樹中恣意兩個節點之間只需獨一的一條鏈在樹的恣意兩個不相鄰的節點之間添加一條邊，那么構成獨一的圈網絡的生成樹由網絡的一切節點m個和網絡的m-1條邊組成的樹稱為網絡的生成樹，網絡中不屬于生成樹的邊稱為生成樹的弦4231423142314231423142314231網絡的生成樹的變換4231網絡的一個生成樹，添加一條弦，構成獨一的圈，去掉生成樹的一條邊，得到一個新的網絡的生成樹423142314231生成樹2生成樹3生成樹1/網絡的生成樹和線性規劃的關系網絡的一個生成樹對應于線性規劃的一個基生成樹上的邊對應于線性規劃的基變量生成樹的弦對應于線性規劃的非基變量生成樹的變換對應

22、于線性規劃單純形法的進基和離基變換網絡最小費用流問題b2=-2b4=3b3=5b5=-6b6=-5b1=5c24=5c46=1c13=3c35=2c56=4c34=4c12=6234561需求節點供應節點cij 單位流量的費用初始根底可行解生成樹b6=-5b2=-2b4=3b3=5b5=-6b1=5x13=3x46=3x35=8x56=2x12=2234561確定非基變量x24和x34b2=-2b6=-5b3=5b5=-6b1=5c24=5c46=1c13=3c35=2c56=4c34=4c12=6234561b4=3求x24的檢驗數z24-c24 閉回路法z24 -c24 =(-c46+c5

23、6+c35+c13-c12)-c24=(-1+4+2+3-6)-5=-3b2=-2b4=3b3=5b5=-6b6=-5b1=5c24=5c46=1c13=3c35=2c56=4c12=6234561求x34的檢驗數z34 -c34 閉回路法z34 -c34 =(-c46+c56+c35)-c34=(-1+4+2)-4=+1，x34進基b2=-2b4=3b3=5b5=-6b6=-5b1=5c46=1c13=3c35=2c56=4c34=4c12=6234561變量x34進基，確定離基變量minx56,x35=min2,8=2, x56離基，調整流量，進展基變換b2=-2b4=3b3=5b5=-6

24、b6=-5b1=5x46=3x13=3x35=8x56=2x34=0 x12=2234561確定非基變量x24和x56b2=-2b4=3b3=5b5=-6b6=-5b1=5x46=5x13=3x35=6x34=2x12=2234561計算x24和x56的檢驗數z24 -c24 、z56-c56z24 -c24 =(c34+c13-c12)-c24=(4+3-6)-5= -4z56 -c56 =(c46+c34-c35)-c56=(1+4-2)-4= -1，獲得最優解b2=-2b4=3b3=5b5=-6b6=-5b1=5c24=5c46=1c13=3c35=2c56=4c34=4c12=6234

25、561最優解最優解的目的函數值為：min z=62+33+42+26+15=46b2=-2b4=3b3=5b5=-6b6=-5b1=5x46=5x13=3x35=6x34=2x12=2234561網絡最大流問題2354671ffu25=6u42=2u45=4u23=3u13=7u34=4u46=3u36=1u65=7u57=9u67=8u12=8邊的容量和流量容量uij，流量xij可行流滿足以下條件的流稱為可行流：1、每一個節點流量平衡2、0 xij uij邊的容量和流量、可行流21xij=5uij=521xij=3uij=5飽和邊、不飽和邊、流量的間隙1，2是飽和的2、假設xij0，邊從j到

26、i的方向是不飽和的；2，1是不飽和的間隙為12=x12=5給出一個初始的可行流xij=02354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0找到一切的不飽和邊，以及各邊可以調整流量的方向2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0找到一條從1到7的不飽和鏈鏈的間隙為： = min8,3,1,8=1調整鏈的流量：

27、xij=xij+ 2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0=3=1=8=8x=0調整流量，f=1。繼續求出網絡的不飽和邊2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=1x=1x=1x=1求出一條從1到7的不飽和鏈2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x

28、=0 x=0 x=0 x=0 x=0 x=1x=1x=1x=1=1=6=9=7=min 7,1,6,9=1, 調整流量 xij=xij+1, f=f+1=2調整流量，繼續求出網絡的不飽和邊2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0 x=0 x=1x=0 x=0 x=0 x=1x=1x=1x=1x=0求出一條從1到7的不飽和鏈2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0 x=0 x=1x=0 x=0 x=0 x=1x=1x=1x=1x=0=5=8=7=min 7,

29、5,8=5, 調整流量 xij=xij+5, f=f+5=2+5=7調整流量，繼續求出網絡的不飽和邊2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=0 x=1x=0 x=0 x=0 x=6x=1x=1x=6x=02354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=0 x=1x=0 x=0 x=0 x=6x=1x=1x=6x=0求出一條從1到7的不飽和鏈=min 6,7,4,3=3, 調整流量 xij=xij+3, f=f+3=7+3=10=4=4=3=6調整流量，

30、繼續求出網絡的不飽和邊2354671f=10f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=3x=4x=3x=0 x=0 x=9x=1x=1x=6x=0求出一條從1到7的不飽和鏈2354671f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=3x=4x=3x=0 x=0 x=9x=1x=1x=6x=0f=10=1=3=7=3=min 3,1,3,7=1, 調整流量 xij=xij+1, f=f+1=10+1=11調整流量，繼續求出網絡的不飽和邊2354671f=11f=11u=6u=2u=4u=3

31、u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=4x=5x=3x=1x=0 x=9x=2x=1x=6x=0已找不到一條從1到7的不飽和鏈，從1開場可以到達的節點為1，2，3已求得最大流2354671f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=4x=5x=3x=1x=0 x=9x=2x=1x=6x=0f=11最大流f=11，最小割集為2,53,43,5u25+u34+u35=6+4+1=11最短途徑問題237184566134105275934682求從1到8的最短途徑237184566134105275934682X=1,

32、 w1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4, w4=1w1=0w1=0237184566134105275934682X=1,4min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4, w2=2w1=0w4=1w2=2237184566134105275934682X=1,2,4min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6, w6=3w2=2w4=1w1=0w6=3237184566

33、134105275934682X=1,2,4,6min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7, w7=3w2=2w4=1w1=0w6=3w7=3237184566134105275934682X=1,2,4,6,7min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7, w5=6w2=2w4=1w1=0w6=3w7=3w5=6237184566134105275934682X=1,2,4,6,7min c23,c53,c58,c78

34、=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7, w3=8w2=2w4=1w1=0w6=3w7=3w5=6w3=8237184566134105275934682X=1,2,3,4,6,7min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2,3,4,5,6,7,8, w8=10w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10237184566134105275934682X=1,2,3,4,6,7,81到10的最短途徑為1，4，7，5，8，長度為10。w2=2w4=1

35、w1=0w6=3w7=3w5=6w3=8w8=10第六章 動態規劃最短途徑問題資源分配問題背包問題機器負荷分配問題2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短途徑問題求從A到E的最短途徑2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72511214106104131112396581052C1C3D