浙江大学运筹学教程经典全套课件【精品】

运 筹 学 教 程,运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。,前言运筹学简介,运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英文是Operational Research，在美国称为Operations Research。,战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，Operations Research就转义成为“作业研究”。我国把Operations Research译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。,运筹学的内容十分广泛，包括线性规划、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划、整数规划、运输问题、网络优化、动态规划和排队论。,目 录,第一章线性规划第二章对偶第三章整数规划第四章运输问题第五章网络优化第六章动态规划第七章排 队 论,第一章 线性规划,线性规划模型线性规划的图解可行域的性质线性规划的基本概念基础解、基础可行解单纯形表线性规划的矩阵表示,线性规划模型,线性规划模型的结构目标函数 ：max，min约束条件：,=,变量符号：0, unr, 0线性规划的标准形式目标函数：min约束条件：=变量符号：0,线性规划的图解,max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,可行域的性质,线性规划的可行域是凸集线性规划的最优解在极点上,凸集,凸集,不是凸集,线性规划可行域和最优解的几种情况,1、可行域封闭 唯一最优解,2、可行域封闭 多个最优解,3、可行域开放 唯一最优解,4、可行域开放 多个最优解,5、可行域开放 目标函数无界,6、无可行解,x3=0,x4=0,max z=x1+2x2s.t. x1+x23 x2 1 x1, x2 0,max z=x1+2x2s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40,x1=0, x2=0x3=3, x4=1,x1=0, x4=0 x2=1, x3=2,x2=0, x3=0x1=3, x4=1,x3=0, x4=0 x1=2, x2=1,x1=0, x3=0 x2=3, x4=-2,线性规划的基本概念基础解、基础可行解、极点,x2=0,x1=0,O,A,B,C,D,标准化的线性规划问题，有n个变量，m个约束。令其中n-m个变量等于零，如果剩下的m个变量的系数矩阵的行列式不等于0，这个mm的矩阵称为线性规划的一个基。等于0的n-m个变量称为非基变量，m个变量称为基变量。求解mm的线性方程组，得到基变量的一组解，连同等于0的非基变量这n个变量的值称为线性规划的一个基础解。如果一个基础解中的所有变量都是非负的，这个基础解称为基础可行解。线性规划的基础可行解就是可行域的极点。,线性规划的基本概念基础解、基础可行解、极点,max z=x1+2x2s.t. x1+x23 x2 1 x1, x2 0,max z=x1+2x2s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40,x1=0, x2=0 x3=3, x4=1基础可行解,x1=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是基础解，但不是可行解,O,A,B,x3=0,x4=0,x2=0,x1=0,C,D,可行域,几何概念,代数概念,约束直线,满足一个等式约束的解,约束半平面,满足一个不等式约束的解,约束半平面的交集：凸多边形,满足一组不等式约束的解,约束直线的交点,基础解,可行域的极点,基础可行解,目标函数等值：一组平行线,目标函数值等于一个常数的解,搜索所有基础可行解求出最优解,基变量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、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/2，0，0，10）是基础解但不是可行解。, ,单纯形法原理（1）松弛变量的表示,max z=x1+2x2s.t. x1+x23 x2 1 x1, x20,max z=x1+2x2s.t. x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40,x2=0,x1=0,x3=0,x4=0,O,A,B,C,D, ,x2=0,x1=0,x3=0,x4=0,O,A,B,C,第一次叠代：目标函数和基变量分别用非基变量表示： z=-x1-2x2选择x2进基 x3 =3-x1-x2 x4=1 -x2,单纯形法原理(2)第一次叠代,确定离基变量的进一步讨论,设非基变量为x1、x2，基变量为x3、x4、x5，进基变量为x2,x3 =5- x1-4x2 x4 =4-2x1-3x2 x5 =2-3x1- x2,5/4=1.254/3=1.332/1=2,min5/4,4/3,2/1=5/4当x2增加到1.25时x30离基,x3 =5- x1+4x2 x4 =4-2x1-3x2 x5 =2-3x1- x2,x3增加4/3=1.332/1=2,min4/3,2/1=4/3当x2增加到1.33时x40离基,x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1- x2,x3增加x4增加2/1=2,min2/1=2/1当x2增加到2时x50离基,x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1+ x2,x3增加x4增加x5增加,x2可以无限增加，可行域是开放区域，目标函数无界,x2=0,x1=0,x3=0,x4=0,O,A,B,C,第二次叠代：目标函数和基变量分别用非基变量表示： z=-2-x1+2x4选择x1进基 x3 =2-x1+x4 x2=1 -x4,单纯形法原理（3）第二次叠代,x2=0,x1=0,x3=0,x4=0,O,A,B,C,第三次叠代：目标函数和基变量分别用非基变量表示： z=-4+x3+x4 x1 =2-x3+x4 x2=1 -x4非基变量在目标函数中的系数全部大于0，已获得最优解。,单纯形法原理（4）最优解的判定,x2=0,x1=0,x3=0,x4=0,O,A,B,C,单纯形法原理(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 1 将目标函数和基变量分别用非基变量表示。转STEP 2。STEP 2 如果目标函数中所有非基变量的系数全部为正数，则已经获得最优解。运算终止。否则，选取系数为负数并且绝对值最大的非基变量进基。转STEP 3。STEP 3 如果进基变量增加时，基变量都不减少，则可行域开放，目标函数无界。运算终止。否则，随着进基变量的增加，最先下降到0的基变量离基。转STEP 1。,目标函数,约束条件,基矩阵,右边常数,进基变量、离基变量、基变换,=,基变量,进基变量,离基变量,目标函数,约束条件,右边常数,=,目标函数,约束条件,新的基矩阵,右边常数,=,进基变量,离基变量,目标函数,约束条件,基矩阵,=,目标函数,约束条件,新的基矩阵,右边常数,=,线性规划基本概念练习（1）,0,3,6,x1,x2,O,A,B,C,E,F,G,H,I,4,6,-2,min z=-x1+2x2s.t. 3x1+2x212(1) x1+2x2 6(2) -2x1+ x2 4(3) x1, x2 0,1、约束条件（1）对应的直线是（ ），对应的半平面是 约束条件（2）对应的直线是（ ），对应的半平面是 约束条件（3）对应的直线是（ ），对应的半平面是,2、这个线性规划的可行域是（ ）。3、对于z=2和4,分别画出目标函数等值线。4、这个线性规划的最优解位于（ ）。,ACEF,BCDH,EGHI,CDGE,z=2,z=4,C,D,4,0,3,6,x1,x2,O,A,B,C,E,F,G,H,I,4,6,-2,D,线性规划基本概念练习（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,硬质油精炼,软质油精炼,混合,成品油,原料,加工,成品,第二章 对偶线性规划,对偶的定义对偶问题的性质原始对偶关系 目标函数值之间的关系 最优解之间的互补松弛关系 最优解的Kuhn-Tucher条件对偶可行基对偶单纯形法对偶的经济解释,DUAL,一、对偶的定义,原始问题min z=CTXs.t.AXbX 0,对偶问题max y=bTWs.t. ATWCW 0,min,b,A,CT,C,AT,bT,max,m,n,m,n,二、对偶问题的性质,1、对偶的对偶就是原始问题,min z=CTXs.t. AXb X 0,max y=bTWs.t. ATWCW 0,min y=-bTWs.t. -ATW-CW 0,max z=-CTXs.t. -AX-b X 0,2、其他形式问题的对偶,原始问题约束条件的性质，影响对偶问题变量的性质。原始问题变量的性质，影响对偶问题约束条件的性质。,min z=CTXs.t. AXb X 0,max y=bTWs.t. ATWC W 0,min z=CTXs.t. AX=b X 0,max y=bTWs.t. ATWC W :unr,min z=CTXs.t. AXb X 0,max y=bTWs.t. ATWC W 0,min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max 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: unr,原始问题变量的个数(3)等于对偶问题约束条件的个数(3)； 原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质。 原始问题约束条件的性质影响对偶问题变量的性质。,三、原始对偶关系,1、可行解的目标函数值之间的关系 设XF、WF分别是原始问题和对偶问题的可行解z=CTXF WTAXF WTb=y2、最优解的目标函数值之间的关系 设Xo、Wo分别是原始问题和对偶问题的最优解 z=CTXo=WoTAXo=WoTb=y,3、原始问题和对偶问题最优解之间的互补松弛关系,min z=CTXs.t. AX-XS=b X, XS0,max y=bTWs.t. ATW+WS=C W, WS0,min z=CTXs.t. AXb X 0,max y=bTWs.t. ATWC W0,互补松弛关系,XTWS=0 WTXS=0,min z=CTXs.t.AX-XS=bX, XS 0,max y=bTWs.t. ATW+WS=CW, WS 0,XTWS=0WTXS=0,AT,W,I,Ws,C,m,n,=,n,X,A,-I,Xs,b,=,n,m,m,原始问题和对偶问题变量、松弛变量的维数,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、原始问题和对偶问题最优解的充分必要条件,Kuhn-Tucher 条件,四、对偶单纯形法,对偶问题的解（w1, w2, w3, w4, w5,w6）=(0, 0, 0, -1, -2, -1),不是对偶问题的可行解,对偶问题的解（w1, w2, w3, w4, w5,w6）=(0, 2/3, 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 0,min z=CTXs.t. AX b X 0,max z=CTXs.t. AX b X 0,max z=CTXs.t. AX b X 0,（2）,（3）,（4）,（1）,单纯形表和对偶(1),min z=CTXs.t. AX-XS=b X, XS0,max y=bTWs.t. ATW+WS=C W, WS0,min z=CTXs.t. AX-XS=b X, XS0,max y=bTWs.t. ATW+WS=C W, WS0,WT=CBTB-1WST=CT-WTA,min z=CTXs.t. AX+XS=b X, XS0,max y=bTWs.t. ATW+WS=C W 0, WS0,单纯形表和对偶(2),min z=CTXs.t. AX+XS=b X, XS0,max y=bTWs.t. ATW+WS=C W 0, WS0,WT=CBTB-1WST=CT-WTA,max z=CTXs.t. AX-XS=b X, XS0,max y=bTWs.t. ATW-WS=C W 0, WS0,单纯形表和对偶(3),max z=CTXs.t. AX-XS=b X, XS0,min y=bTWs.t. ATW-WS=C W 0, WS0,WT=CBTB-1WST=WTA- CT,max z=CTXs.t. AX+XS=b X, XS0,max y=bTWs.t. ATW-WS=C W, WS0,单纯形表和对偶(4),max z=CTXs.t. AX+XS=b X, XS0,min y=bTWs.t. ATW-WS=C W, WS0,WT=CBTB-1WST=WTA- CT,min z=6x1+8x2+3x3s.t. x1+ x2 1 x1+2x2+x3 -1 x1, x2, x3 0,max y=w1-w2s.t. w1+ w2 6 w1+2w2 8 w2 3 w1, w20,max 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,(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, x50,max 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、对偶单纯形法（初始解原始不可行的问题）,已获得最优解：（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、初始解原始、对偶都不可行的问题,解法1：先解决原始可行性,在得到原始可行解时同时得到对偶可行解，已获得最优解：（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、原始问题是利润最大化的生产计划问题,单位产品的利润（元/件）,产品产量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资源（吨/件）,剩余的资源（吨）,消耗的资源（吨）,2、对偶问题,资源限量（吨）,资源价格（元/吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格（Shadow Price）,原始和对偶问题都取得最优解时，最大利润 max z=min y,3、资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,w1w2wm,4、产品的机会成本,机会成本表示减少一件产品所节省的所有资源可以增加的利润,增加单位资源可以增加的利润,减少一件产品的产量可以节省的资源,机会成本,利润,差额成本,5、产品的差额成本（Reduced Cost）,wm+j=(ai1w1+ai2w2+.aimwm)-cj差额成本机会成本利润,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,差额成本大于0（机会成本大于利润）的产品，不安排生产,安排生产的产品，差额成本等于0（机会成本等于利润）,和资源有关的量资源限量（吨）资源占用（吨）资源剩余（吨） 资源限量资源占用资源的影子价格（资源的边际利润）（元/吨）和产品有关的量产品利润（元/件）产品产量（件）产品的机会成本（元/件）产品的差额成本（元/件） 机会成本利润,互补松弛关系,max z=32x1+31x2+55x3+32x4+70x5s.t. x1+2x2+ 3x4+2x54000 2x1+2x2+3x3+ x4+4x52000 x1 +2x3+2x4+2x51800 4x1+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.00000015.500000 4) 0.000000 8.250000 5) 750.000000 0.000000 NO. ITERATIONS= 2,200,0,0,750,3800,2000,1800,1650,7.25,0,8.0,0,8.5,39.25,31,63.0,32,78.5,产品的机会成本产品对设备的消耗设备的影子价格,资源的占用 产品产量产品对设备的消耗,资源的剩余资源限量资源占用,产品的差额成本产品的机会成本产品利润,产品产量和产品的机会差额成本互补松弛,资源剩余和资源的影子价格互补松弛,第四章 运输问题,运输问题的表示网络图、线性规划模型、运输表初始基础可行解西北角法、最小元素法非基变量的检验数闭回路法、对偶变量法确定进基变量，调整运量，确定离基变量,运输问题网络图,供应地,运价,需求地,供应量,需求量,总供应量60吨,总需求量60吨,供求平衡的运输问题,运输问题线性规划模型,供应地约束,需求地约束,由于前m个供应地约束和后n个需求地约束是线性相关的，因此运输问题系数矩阵的秩m+n。可以证明，运输问题系数矩阵的秩为m+n-1。即运输问题有m+n-1个基变量，mn-(m+n-1)个非基变量。例如以上问题m=3，n=4，基变量为3416个，非基变量为1266个。,运输问题的表格表示,运输问题基的表示,m个供应地、n个需求地的运输问题，任何一个基要满足以下三个条件：基变量的个数为m+n-1；同行同列的基变量不能形成回路；运输表的每一行和每一列中至少有一个基变量。,基在运输表中的表示,运输表中同行同列的变量组成回路,初始基础可行解西北角法,8,13,13,14,6,6,初始基础可行解最小元素法（1）,初始基础可行解最小元素法（2）,初始基础可行解最小元素法（3）,初始基础可行解最小元素法（4）,初始基础可行解最小元素法（5）,初始基础可行解最小元素法（6）,-5,非基变量xij的检验数zij-cij闭回路法(1),z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5,-5,z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5,-5,非基变量xij的检验数zij-cij闭回路法(2),-5,z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7,-7,-5,非基变量xij的检验数zij-cij闭回路法(3),-5,z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9,-9,-5,-7,非基变量xij的检验数zij-cij闭回路法(4),-5,z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11,+11,-5,-7,-9,非基变量xij的检验数zij-cij闭回路法(5),-5,z32-c32=(c22-c23+ c33)-c32=(4-2+10)-9=+3,+3,-5,-7,-9,+11,非基变量xij的检验数zij-cij闭回路法(6),选择进基变量,确定离基变量,x31进基, minx21,x33=min8,6=6, x33离基,+3,-5,-5,-7,-9,11,调整运量,重新计算检验数,确定进基、离基变量,x14进基, minx11,x34=min14,13=13, x34离基,-11,-5,-5,+4,+2,-8,调整运量, 重新计算检验数,所有zij-cij0时，相应的wij=0，同时由单纯形表的结构可以知道，对偶问题的松弛变量的相反数就是非基变量的检验数，因此，运输问题非基变量的检验数可以通过下列步骤得到：对于m+n-1个基变量，可以得到对偶问题的m+n-1个等式约束令一个对偶变量vm0，就可以由m+n-1个等式，求出m个对偶变量ui和vj的值已知ui，vj和cij的值，可以求出对偶问题松弛变量，即非基变量检验数的值,令v3=0，得到以下等式方程组,v3=0u2=7v2=-5u1=10v1=-7,-w13=u1+v3-c13=+4-w21=u2+v1-c21=-4,+4,-4,对于基变量x23=11，有u2+v3=c23=7，令v3=0，得到u2=7,v3=0,u2=7,u1=10,v2=-5,v1=-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,总结：求运输问题单纯形法非基变量检验数的对偶变量法：对于基变量xij0，有ui+vj=cij对于m+n-1个基变量以及vn=0，可以列出m+n个等式方程，求解m+n个对偶变量ui和vj非基变量xij的检验数，等于ui+vj-cij,+4,-4,非基变量xij的检验数zij-cij对偶变量法(1),v4=0,u3+v4=c34u3=6,非基变量xij的检验数zij-cij对偶变量法(1),u3+v3=c33v3=4,非基变量xij的检验数zij-cij对偶变量法(1),u2+v3=c23u2=-2,非基变量xij的检验数zij-cij对偶变量法(1),u2+v2=c22v2=6,非基变量xij的检验数zij-cij对偶变量法(1),u2+v1=c21v1=10,非基变量xij的检验数zij-cij对偶变量法(1),u1+v1=c11u1=-4,非基变量xij的检验数zij-cij对偶变量法(1),z12-c12=u1+v2-c12=(-4)+6-7=-5,-5,非基变量xij的检验数zij-cij对偶变量法(1),z13-c13=u1+v3-c13=(-4)+4-5=-5,-5,-5,非基变量xij