浙江大学mba教材-ppt课件

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是根底解，但不是可行解。基变量x1、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