运筹学教程课件

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计算结果与圈法相同。运筹学教程课件最小费用流问题的