运筹学运输问题备用

1、运 筹 学 教 程4.0 版蒋 绍 忠 制作浙 江 大 学 管 理 学 院2005年6月运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。前言运筹学简介运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，

2、英文是Operational 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 x4=0max z=x1+2x2s.t. x1+x23 x2 1 x1, x2 0max z=x

4、1+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=0OABCDq标准化的线性规划问题，有n个变量，m个约束。q令其中n-m个变量等于零，如果剩下的m个变量的系数矩阵的行列式不等于0，这个mm的矩阵称为线性规划的一个基。等于0的n-m个变量称为非基变量，m个变量称为基变量。q求解mm的

5、线性方程组，得到基变量的一组解，连同等于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基础可行解x1=0, x4=0 x2=1, x3=2基础可行解x2=0, x3=0 x1=3, x4=1基础可行解x3=0, x4=0

6、 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-x318x1-x2+x33x1,x2,x30min z= -2x1-3x2-x3stx1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x

7、2+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 x1+3x2+x4=152x1+3x2=18x1-x2=3基变量x1、x2、x4，非基变量x3、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0

8、，2/5，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1+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，3，0，0，-3，0）是基础解，但不是可行解，不是一个极点。x1+3x2=152x1+3x2=18x1-x2+x6=3基变量x1、x2、x6，非基变量x3、x4、x5基础解为（x1，x2，

9、x3，x4，x5，x6）=（3，4，0，0，0，4）是基础可行解，表示可行域的一个极点。目标函数值为：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+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，-30，0，0）是基础解，但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3+x5=18-x2+x3=3基变量x1、x2、x3，非基变量x4

10、、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=33x2+x3=153x2-x3=18-x2+x3+x6=3基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，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.

11、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,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

12、,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/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-

13、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第二次叠代：目标函数和基变量分别用非基变量表示： 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成

14、为非基变量当前基础可行解：(x1,x2,x3,x4)=(2,1,0,0)z=-4x2=0 x1=0 x3=0 x4=0OABC第三次叠代：目标函数和基变量分别用非基变量表示： z=-4+x3+x4 x1 =2-x3+x4 x2=1 -x4非基变量在目标函数中的系数全部大于0，已获得最优解。单纯形法原理（4）最优解的判定x1=2成为基变量，x3=0成为非基变量当前基础可行解：(x1,x2,x3,x4)=(2,1,0,0)z=-4x2=0 x1=0 x3=0 x4=0OABC单纯形法原理(5)叠代过程回顾第一次叠代x2进基，x4离基第二次叠代x1进基，x3离基(x1,x2,x3,x4)=(0,0,

15、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的基变

16、量离基。转STEP 1。=目标函数约束条件基矩阵右边常数=基变量=进基变量离基变量目标函数约束条件右边常数=目标函数约束条件新的基矩阵右边常数=进基变量离基变量目标函数约束条件基矩阵=目标函数约束条件新的基矩阵右边常数=线性规划基本概念练习（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、这个线性规划的可行域是（

17、）。3、对于z=2和4,分别画出目标函数等值线。4、这个线性规划的最优解位于（ ）。ACEFBCDHEGHICDGEz=2z=4CD4036x1x2OABCEFGHI46-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 转到第二阶段，从

18、原问题的初始基础可行解出发，求出原问题的最优解。案例一 食油生产计划储罐1储罐2储罐3储罐4储罐5硬质油1硬质油2软质油1软质油2软质油3硬质油精炼软质油精炼混合成品油原料加工成品DUAL对偶问题max y=bTWs.t. ATWCW 0minbACTCATbTmaxmnmn二、对偶问题的性质1、对偶的对偶就是原始问题对偶的定义max y=bTWs.t. ATWCW 0对偶的定义min y=-bTWs.t. -ATW-CW 02、其他形式问题的对偶原始问题约束条件的性质，影响对偶问题变量的性质。原始问题变量的性质，影响对偶问题约束条件的性质。max y=bTWs.t. ATWC W 0max

19、y=bTWs.t. ATWC W :unrmax y=bTWs.t. ATWC W 0min 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)；q 原始问题约束条件的个数(4)等于对偶问题变量的个数(4

20、)。q原始问题变量的性质影响对偶问题约束条件的性质。q 原始问题约束条件的性质影响对偶问题变量的性质。三、原始对偶关系1、可行解的目标函数值之间的关系 设XF、WF分别是原始问题和对偶问题的可行解z=CTXF WTAXF WTb=y2、最优解的目标函数值之间的关系 设Xo、Wo分别是原始问题和对偶问题的最优解 z=CTXo=WoTAXo=WoTb=y3、原始问题和对偶问题最优解之间的互补松弛关系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对偶

21、引进松弛变量引进松弛变量互补松弛关系X，XsW，WsXTWS=0 WTXS=0max 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=0 wixn+i=0 (i=1,2,m; j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于03、原始问题和对偶问题最优解的充分必要条件 AX-X

22、S=b 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）四、对偶单纯形法maxz=x1+2x2+x3s.t.x1+x2+x312 2x1+3x2+x318 -x1+x2+x324 x1x2x3 0min y=12w1+18w2+24w3s.t.w1+2w2-w3 1w1+3w2+w3 2w1+w2+w3

23、1w1w2w3 0maxz=x1+2x2+x3s.t.x1+x2+x3+x4=12 2x1+3x2+x3+x5=18 -x1+x2+x3+x6=24 x1x2x3x4x5x60zx1x2x3x4x5x6RHSz11210000 x401111001212/1x502310101818/3x60-1110012424/1对偶问题的解（w1, w2, w3, w4, w5,w6）=(0, 0, 0, -1, -2, -1)min y=12w1+18w2+24w3s.t.w1+2w2-w3 1w1+3w2+w3 2w1+w2+w3 1w1w2w3 0不是对偶问题的可行解zx1x2x3x4x5x6RH

24、Sz1-1/301/30-2/30-12x401/302/31-1/3066/2/3x202/311/301/3066/1/3x60-5/302/30-1/311818/2/3对偶问题的解（w1, w2, w3, w4, w5,w6）=(0, 2/3, 0, 1/3, 0, -1/3)min y=12w1+18w2+24w3s.t.w1+2w2-w3 1w1+3w2+w3 2w1+w2+w3 1w1w2w3 0不是对偶问题的可行解zx1x2x3x4x5x6RHSz1-1/200-1/2-1/20-15x301/2013/2-1/209x201/210-1/21/203x60-200-10112

25、对偶问题的解（w1, w2, w3, w4, w5,w6）=(1/2, 1/2, 0, 1/2, 0, 0)min y=12w1+18w2+24w3s.t.w1+2w2-w3 1w1+3w2+w3 2w1+w2+w3 1w1w2w3 0是对偶问题的可行解结论 单纯形法求解的过程，从对偶的观点来看，是在始终保持原始可行解的条件下，不断改进对偶可行性的过程。一个从对偶不可行的解，经过几次叠代，逐步向对偶可行解靠拢，一旦得到的解既是原始可行的，又是对偶可行的，这个解就分别是原始问题和对偶问题的最优解。1、用单纯形表求解原始问题的四种形式min z=CTXs.t. AXb X 0min z=CTXs.

26、t. AX b X 0max z=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

27、 W, WS0zXXSRHS1CBTB-1A-CT-CBTB-1CBTB-1b0B-1A-B-1B-1bWT=CBTB-1WST=CT-WTAmin 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=bTWs.t. ATW

28、+WS=C W 0, WS0zXXSRHS1CBTB-1A-CTCBTB-1CBTB-1b0B-1AB-1B-1bWT=CBTB-1WST=CT-WTAmax 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. AX-XS=b X, XS0min y=bTW

29、s.t. ATW-WS=C W 0, WS0zXXSRHS1CBTB-1A-CT-CBTB-1CBTB-1b0B-1A-B-1B-1bWT=CBTB-1WST=WTA- CTmax 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-CT0T00AIbmax z=CTXs.t. AX+XS=b X, XS0min

30、 y=bTWs.t. ATW-WS=C W, WS0zXXSRHS1CBTB-1A-CTCBTB-1CBTB-1b0B-1AB-1B-1bWT=CBTB-1WST=WTA- CTmin 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, w4, w50(w1, w2)=(6,0)(w1,w2,w3,w4,w5)=(6, 0, 0

31、, 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, x50max y=w1

32、-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、对偶单纯形法（初始解原始不可行的问题）0 xxx2xx2x5xx3x24xxx. t . sxx2x3zmin3213213213213210 xxxxxx2xxx2

33、x5xxx3x24xxxx. t . sxx2x3zmin6543216321532143213210 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 -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

34、 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 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,

35、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、初始解原始、对偶都不可行的问题0 xxx2xx2x5xx3x24xxx. t . sx2x2x3zmin3213213213213210 xxxxxx2xxx2x5xxx3x24xxxx. t . sx2x2x3zmin6543216321532143213210 xxxxxx2xxx2x25xxx3x24xxxx. t . sx2x2x3zmin6543216321532

36、14321321zx1x2x3x4x5x6RHSz1-3-220000 x401-111004x502-31010-5x60-22-1001-2解法1：先解决原始可行性zx1x2x3x4x5x6RHSz1-700024-18x40-100112-5x200100-1-17x302010-2-316zx1x2x3x4x5x6RHSz1-720002-4x40-1101012x500-10011-7x302-2100-12zx1x2x3x4x5x6RHSz1000-7-5-1017x10100-1-1-25x200100-1-17x300012016在得到原始可行解时同时得到对偶可行解，已获得最优

37、解：（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=17zx1x2x3x4x5x6RHSz1-3-220000 x401-111004x502-31010-5x60-22-1001-2zx1x2x3x4x5x6RHSz1-500-200-8x301-111004x501-20-110-9x60-1101012解法2：先解决对偶可行性已得到对偶可行解，再用对偶单纯形法求解zx1x2x3x4x5x6RHSz1000-7-

38、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, 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=170 xxxxxxbxxaxaxabxxaxaxabxxaxaxa. t .

39、sxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111nn2211五、对偶的经济解释1、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）2、对偶问题0wwwwwwcwwawawacwwawawacwwawawa. t . swbwbwbyminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm2211资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解w

40、1、w2、.、wm称为m种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，最大利润 max z=min y3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0种资源的边际利润第种资源的增量第最大利润的增量iibzwiooimmii2211wbwbwbwbyzmmiii2211wbw)bb(wbwbzziiwbzw1w2wm4、产品的机会成本机会成本表示减少一件产品所节省的所有资源可以增加的利润mmjiij2j21j1wawawawa增加单位资源可以增加的利润减少一件

41、产品的产量可以节省的资源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211机会成本利润差额成本5、产品的差额成本（Reduced Cost）wm+j=(ai1w1+ai2w2+.aimwm)-cj差额成本机会成本利润0wwwwwwcwwawawacwwawawacwwawawa. t . swbwbwbyminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm22115、互补松弛关系的经济解释wixn+

42、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+31

43、x2+55x3+32x4+70 x5s.t. x1+2x2+ 3x4+2x54000 2x1+2x2+3x3+ x4+4x52000 x1 +2x3+2x4+2x51800 4x1+3x2+5x3 +3x52400 x1，x2，x3，x4，x50产品1产品2产品3产品4产品5资源限量资源A1.02.03.02.04000资源B2.02.03.01.04.02000资源C1.02.02.02.01800资源D4.03.05.03.02400利润3231553270LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)45850.00 VARI

44、ABLEVALUE 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产品产品编号12345资源利润（元/件）3231553270产量（

45、件）055009000机会成本(元/件)限量（吨）占用（吨）剩余（吨）影子价格（元/吨）差额成本(元/件)设备设备A1.02.03.02.040000设备B2.02.03.01.04.0200015.5设备C1.02.02.02.018008.25设备D4.03.05.03.0240002000075038002000180016507.2508.008.539.253163.03278.5产品的机会成本产品对设备的消耗设备的影子价格资源的占用 产品产量产品对设备的消耗资源的剩余资源限量资源占用产品的差额成本产品的机会成本产品利润产品产量和产品的机会差额成本互补松弛资源剩余和资源的影子价格互补

46、松弛2312341d1=22d2=13d3=12d4=13s2=27s3=19s1=14供应地运价需求地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=zmin3433323124232221141312113424143323133222123121113433323124232221141312113433323124232

47、22114131211供应地约束需求地约束由于前m个供应地约束和后n个需求地约束是线性相关的，因此运输问题系数矩阵的秩m+n。可以证明，运输问题系数矩阵的秩为m+n-1。即运输问题有m+n-1个基变量，mn-(m+n-1)个非基变量。例如以上问题m=3，n=4，基变量为3416个，非基变量为1266个。123467531x11x12x13x141484272x21x22x23x2427591063x31x32x33x341922131213 m个供应地、n个需求地的运输问题，任何一个基要满足以下三个条件：基变量的个数为m+n-1；同行同列的基变量不能形成回路；运输表的每一行和每一列中至少有一个

48、基变量。基在运输表中的表示运输表中同行同列的变量组成回路 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）1234675311314184272131227259106319190221312133000初始基础可行解最小元素法（4）12346

49、753111314084272131227259106319190221312132000初始基础可行解最小元素法（5）123467531113140842722131227059106319190221312130000初始基础可行解最小元素法（6）1234675311414842728136275910636131922131213-5非基变量xij的检验数zij-cij闭回路法(1)z12-c12=(c11-c21+c22)-c12=6-8+4-7=-51234675311414842728136275910636131922131213-5z13-c13=(c11-c21+c23)-c

50、13=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-c33+ c34)-c24=(2-10+6)-7=-9-9-5-7非基变量xij的检验数zij-cij闭回路法(4)123467531

51、1414842728136275910636131922131213-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的检验数zij-cij闭回路法(6)12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0选择进基变量,确

52、定离基变量x31进基, minx21,x33=min8,6=6, x33离基+3-5-5-7-91112346753114148427221312275910636131922131213调整运量,重新计算检验数,确定进基、离基变量x14进基, minx11,x34=min14,13=13, x34离基-11-5-5+4+2-812346753111314842722131227591063191922131213调整运量, 重新计算检验数所有zij-cij0时，相应的wij=0，同时由单纯形表的结构可以知道，对偶问题的松弛变量的相反数就是非基变量的检验数，因此，运输问题非基变量的检验数可以通

53、过下列步骤得到：对于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=7v3=0u2=7u1=10v2=-5v1=-7对于基变量x22=7，有u2+v2=c22=2，由u2=7，得到v2=-5对于基变量x12=10，

54、有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-412346753114u1842728136u2591063613u3v1

55、v2v3v4=0非基变量xij的检验数zij-cij对偶变量法(1)v4=012346753114u1842728136u2591063613u3=6v1v2v3v4=0u3+v4=c34u3=6非基变量xij的检验数zij-cij对偶变量法(1)12346753114u1842728136u2591063613u3=6v1v2v3=4v4=0u3+v3=c33v3=4非基变量xij的检验数zij-cij对偶变量法(1)12346753114u1842728136u2=-2591063613u3=6v1v2v3=4v4=0u2+v3=c23u2=-2非基变量xij的检验数zij-cij对偶变量

56、法(1)12346753114u1842728136u2=-2591063613u3=6v1v2=6v3=4v4=0u2+v2=c22v2=6非基变量xij的检验数zij-cij对偶变量法(1)12346753114u1842728136u2=-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)123467

57、53114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0z12-c12=u1+v2-c12=(-4)+6-7=-5-5非基变量xij的检验数zij-cij对偶变量法(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

58、+v4-c14=(-4)+0-3=-7-7-5-5非基变量xij的检验数zij-cij对偶变量法(1)12346753114u1=-4842728136u2=-2591063613u3=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)123

59、46753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0z32-c32=u3+v2-c32=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-91112346753114148427221312275910636131922131213调整运量,重新计算检验数,确定进基

60、、离基变量x14进基, minx11,x34=min14,13=13, x34离基-11-5-5+4+2-812346753111314842722131227591063191922131213调整运量, 重新计算检验数所有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的检验