《运筹学教程》PPT课件

运筹学教程4.0版,运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。,前言运筹学简介,运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英文是OperationalResearch，在美国称为OperationsResearch。,战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，OperationsResearch就转义成为“作业研究”。我国把OperationsResearch译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。,运筹学的内容十分广泛，包括线性规划、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划、整数规划、运输问题、网络优化、动态规划和排队论。,目录,第一章线性规划第二章对偶第三章整数规划第四章运输问题第五章网络优化第六章动态规划第七章排队论,第一章线性规划,线性规划模型线性规划的图解可行域的性质线性规划的基本概念基础解、基础可行解单纯形表线性规划的矩阵表示,线性规划模型,线性规划模型的结构目标函数：max，min约束条件：,=,变量符号：0,unr,0线性规划的标准形式目标函数：min约束条件：=变量符号：0,线性规划的图解,maxz=x1+3x2s.t.x1+x26-x1+2x28x10,x20,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,可行域的性质,线性规划的可行域是凸集线性规划的最优解在极点上,凸集,凸集,不是凸集,线性规划可行域和最优解的几种情况,1、可行域封闭唯一最优解,2、可行域封闭多个最优解,3、可行域开放唯一最优解,4、可行域开放多个最优解,5、可行域开放目标函数无界,6、无可行解,x3=0,x4=0,maxz=x1+2x2s.t.x1+x23x21x1,x20,maxz=x1+2x2s.t.x1+x2+x3=3x2+x4=1x1,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,线性规划的基本概念基础解、基础可行解、极点,x2=0,x1=0,O,A,B,C,D,标准化的线性规划问题，有n个变量，m个约束。令其中n-m个变量等于零，如果剩下的m个变量的系数矩阵的行列式不等于0，这个mm的矩阵称为线性规划的一个基。等于0的n-m个变量称为非基变量，m个变量称为基变量。求解mm的线性方程组，得到基变量的一组解，连同等于0的非基变量这n个变量的值称为线性规划的一个基础解。如果一个基础解中的所有变量都是非负的，这个基础解称为基础可行解。线性规划的基础可行解就是可行域的极点。,线性规划的基本概念基础解、基础可行解、极点,maxz=x1+2x2s.t.x1+x23x21x1,x20,maxz=x1+2x2s.t.x1+x2+x3=3x2+x4=1x1,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）松弛变量的表示,maxz=x1+2x2s.t.x1+x23x21x1,x20,maxz=x1+2x2s.t.x1+x2+x3=3x2+x4=1x1,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-x2x4=1-x2,单纯形法原理(2)第一次叠代,确定离基变量的进一步讨论,设非基变量为x1、x2，基变量为x3、x4、x5，进基变量为x2,x3=5-x1-4x2x4=4-2x1-3x2x5=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+4x2x4=4-2x1-3x2x5=2-3x1-x2,x3增加4/3=1.332/1=2,min4/3,2/1=4/3当x2增加到1.33时x40离基,x3=5-x1+4x2x4=4-2x1+3x2x5=2-3x1-x2,x3增加x4增加2/1=2,min2/1=2/1当x2增加到2时x50离基,x3=5-x1+4x2x4=4-2x1+3x2x5=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+x4x2=1-x4,单纯形法原理（3）第二次叠代,x2=0,x1=0,x3=0,x4=0,O,A,B,C,第三次叠代：目标函数和基变量分别用非基变量表示：z=-4+x3+x4x1=2-x3+x4x2=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）单纯形法总结,STEP0找到一个初始的基础可行解，确定基变量和非基变量。转STEP1。STEP1将目标函数和基变量分别用非基变量表示。转STEP2。STEP2如果目标函数中所有非基变量的系数全部为正数，则已经获得最优解。运算终止。否则，选取系数为负数并且绝对值最大的非基变量进基。转STEP3。STEP3如果进基变量增加时，基变量都不减少，则可行域开放，目标函数无界。运算终止。否则，随着进基变量的增加，最先下降到0的基变量离基。转STEP1。,目标函数,约束条件,基矩阵,右边常数,进基变量、离基变量、基变换,=,基变量,进基变量,离基变量,目标函数,约束条件,右边常数,=,目标函数,约束条件,新的基矩阵,右边常数,=,进基变量,离基变量,目标函数,约束条件,基矩阵,=,目标函数,约束条件,新的基矩阵,右边常数,=,线性规划基本概念练习（1）,0,3,6,x1,x2,O,A,B,C,E,F,G,H,I,4,6,-2,minz=-x1+2x2s.t.3x1+2x212(1)x1+2x26(2)-2x1+x24(3)x1,x20,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，则xn+i=0,如果xn+i0，则wi=0,边际利润大于0的资源，在最优生产计划条件下没有剩余,wm+jxj=0,如果wm+j0，则xj=0,如果xj0，则wm+j=0,最优生产计划条件下有剩余的资源，其边际利润等于0,差额成本大于0（机会成本大于利润）的产品，不安排生产,安排生产的产品，差额成本等于0（机会成本等于利润）,和资源有关的量资源限量（吨）资源占用（吨）资源剩余（吨）资源限量资源占用资源的影子价格（资源的边际利润）（元/吨）和产品有关的量产品利润（元/件）产品产量（件）产品的机会成本（元/件）产品的差额成本（元/件）机会成本利润,互补松弛关系,maxz=32x1+31x2+55x3+32x4+70 x5s.t.x1+2x2+3x4+2x540002x1+2x2+3x3+x4+4x52000 x1+2x3+2x4+2x518004x1+3x2+5x3+3x52400 x1，x2，x3，x4，x50,LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)45850.00VARIABLEVALUEREDUCEDCOSTX10.0000007.250000X2550.0000000.000000X30.0000008.000000X4900.0000000.000000X50.0000008.500000ROWSLACKORSURPLUSDUALPRICES2)200.0000000.0000003)0.00000015.5000004)0.0000008.2500005)750.0000000.000000NO.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个需求地约束是线性相关的，因此运输问题系数矩阵的秩0，有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的检验数zij-cij对偶变量法(1),z14-c14=u1+v4-c14=(-4)+0-3=-7,-7,-5,-5,非基变量xij的检验数zij-cij对偶变量法(1),z24-c24=u2+v4-c24=(-2)+0-7=-9,-9,-5,-5,-7,非基变量xij的检验数zij-cij对偶变量法(1),z31-c31=u3+v1-c31=6+10-5=11,11,-5,-5,-7,-9,非基变量xij的检验数zij-cij对偶变量法(1),z32-c32=u3+v2-c32=6+6-9=+3,+3,-5,-5,-7,-9,11,非基变量xij的检验数zij-cij对偶变量法(1),选择进基变量,确定离基变量,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，由互补松弛关系得到，相应的对偶变量满足wi-wj=cij加上wm=0，可以依次计算各对偶变量的值。,w2=3,w60,w3=6,w5=4,w1=9,c24=5,c46=1,c13=3,c35=2,c56=4,c34=4,c12=6,2,3,4,5,6,1,w4=1,对于非基变量xij，检验数为：wi-wj-cij非基变量x24的检验数为：w2-w4-c24=3-1-5=-3非基变量x34的检验数为：w3-w4-c34=6-1-4=+1计算结果与圈法相同。,最小费用流问题的单纯形法总结,确定网络的一个初始基础可行解生成树；求出各非基边（生成树的弦）的检验数圈法对偶变量法确定进基变量：检验数为正数，数值最大的非基边确定离基变量：在圈中与圈方向相反的边中流量最小的边离基。,5,2,1,3,4,b1=8,b2=-3,b3=-4,b4=5,b5=-6,c14=2,c12=3,c13=5,c43=4,c54=7,c23=6,c35=8,c25=1,最小费用流问题非基变量检验数的圈法,5,2,1,3,4,b1=8,b2=-3,b3=-4,b4=5,b5=-6,x14=5,x12=3,x43=10,x35=6,c14=2,c12=3,c13=5,c43=4,c54=7,c23=6,c35=8,c25=1,z=c12x12+c14x14+c43x43+c35x35=33+25+410+86107,检验数4+2-5=+1,检验数4+2-3-6=-3,检验数8+4+2-3-1=+10,检验数-4-8-7=-19,5,2,1,3,4,b1=8,b2=-3,b3=-4,b4=5,b5=-6,x14=5,x12=3,x43=10,x35=6,minx35,x43,x14=5，x14离基，调整流量,c14=2,c12=3,c13=5,c43=4,c54=7,c23=6,c35=8,c25=1,5,2,1,3,4,b1=8,b2=-3,b3=-4,b4=5,b5=-6,x34=5,x12=8,x35=1,x25=5,最优解。x12=8,x25=5,x43=5,x35=1,minz=57,c14=2,c12=3,c13=5,c43=4,c54=7,c23=6,c35=8,c25=1,检验数-8+1+3-5=-9,检验数-8+1-6=-13,检验数-4-8+1+3-2=-10,检验数-4-8-7=-19,5,2,1,3,4,w1=14,w2=11,w3=8,w4=12,w5=0,c14=2,c12=3,c13=5,c43=4,c54=7,c23=6,c35=8,c25=1,w3-w5=8,w4-w3=4,w1-w4=2,w1-w2=3,检验数=w1-w3-c13=+1,检验数=w2-w3-c23=-3,检验数=w2-w5-c25=+10,检验数=w5-w4-c54=-19,最小费用流问题非基变量检验数的对偶变量法,5,2,1,3,4,b1=8,b2=-3,b3=-4,b4=5,b5=-6,x14=5,x12=3,x43=10,x35=6,minx35,x43,x14=5，x14离基，调整流量,c14=2,c12=3,c13=5,c43=4,c54=7,c23=6,c35=8,c25=1,5,2,1,3,4,w1=4,w2=1,w3=8,w4=12,w5=0,c14=2,c12=3,c13=5,c43=4,c54=7,c23=6,c35=8,c25=1,w3-w5=8,w4-w3=4,w2-w5=1,w1-w2=3,检验数=w1-w3-c13=-9,检验数=w2-w3-c23=-13,检验数=w1-w4-c14=-10,检验数=w5-w4-c54=-19,最优解。x12=8,x25=5,x43=5,x35=1,minz=57,x14=5,x12=8,x43=5,x35=1,网络最大流问题,2,3,4,5,6,7,1,f,f,6,2,4,3,7,4,3,1,7,9,8,8,以下网络中，节点称为源点(Source)，是供应流量的节点，节点称为汇点（Sink），是消耗流量的节点。其他节点都是中转节点，既不产生流量，也不消耗流量。每一条边都有相应的流量上限uij，称为边的容量（Capacity）。每一条边流量的下限都是0。网络最大流问题：对于给定的网络，求从源点到汇点的最大流量。,uij,网络最大流问题的基本概念,链的方向，同向边，反向边从源点到汇点的一条链，链的方向为从源点到汇点链上与链的方向相同的边称为同向边，方向相反的称为反向边。,2,3,4,5,6,7,1,6,2,4,3,7,4,3,1,7,9,8,8,同向边,反向边,同向边,同向边,饱和边，不饱和边，不饱和边流量的间隙，不饱和链，不饱和链的间隙从源点到汇点的一条链，链的方向为从源点到汇点如果同向边（i,j）的流量xij0，称为边(i,j)是不饱和的，间隙ij=xij。如果反向边(i,j)的流量xij0，则称边(i,j)是饱和的。如果从源点到汇点的一条链的边（同向边和反向边）都是不饱和的，这条链称为不饱和链。不饱和链的间隙等于所有边的间隙中最小的间隙。,2,3,4,5,6,7,1,f=8,f=8,6,2,4,3,7,4,3,1,7,9,8,8,x12=6,x13=2,x25=4,x23=2,x34=3,x36=1,x46=2,x57=5,x45=1,x67=3,同向边，间隙12=7-2=5,反向边，间隙23=x23=2,同向边，间隙25=6-4=2,同向边，间隙57=9-5=4,链(1,3)(2,3)(2,5)(5,7)是不饱和链，链的间隙为：min7-2，2，6-4，9-5min5,2,2,4=2,可行流1、每一个节点供应、需求、流入、流出的流量平衡2、每一条边上的流量不小于0，不大于容量，0xijuij可行流的例子,2,3,4,5,6,7,1,f=8,f=8,6,2,4,3,7,4,3,1,7,9,8,8,x12=6,x13=2,x25=4,x23=2,x34=3,x36=1,x46=2,x57=5,x45=1,x67=3,X,X,X,X,网络的割集将网络的节点划分成两个集合X和X，源点在X中，汇点在X中。起点在X中，终点在X中的边集合称为网络的割集，割集是边的集合。割集中边的容量之和称为割集的容量。,2,3,4,1,1,2,2,4,3,割集为(1,3)(2,3)(2,4)割集的容量9,2,3,4,1,1,2,2,4,3,割集为(1,2)(1,3)割集的容量5,X,X,X,X,2,3,4,1,1,2,2,4,3,割集为(1,2)(3,4)割集的容量3,2,3,4,1,1,2,2,4,3,割集为(2,4)(3,4)割集的容量5,网络最大流的流量等于网络最小割集的容量,最大流问题的算法,STEP0：给出一个初始的可行流STEP1：判断每一条边两个方向分别是否饱和，如果不饱和，用箭头表示不饱和的方向。STEP2：寻找从源点到汇点的不饱和链。如果不存在不饱和链，则已经找到网络的最大流。算法终止。否则，计算不饱和链上各条不饱和边的最小间隙。STEP3：按最小间隙增加不饱和链上的流量，转STEP1。,2,3,4,5,6,7,1,f=8,f=8,6,2,4,3,7,4,3,1,7,9,8,8,x12=6,x13=2,x25=4,x23=2,x34=3,x36=1,x46=2,x57=5,x45=1,x67=3,求以下网络从源点1到汇点7的最大流首先给出一个初始可行流,2,3,4,5,6,7,1,f=8,f=8,6,2,4,3,7,4,3,1,7,9,8,8,x12=6,x13=2,x25=4,x23=2,x34=3,x36=1,x46=2,x57=5,x45=1,x67=3,判断每一条边两个方向是否饱和，用箭头表示不饱和的方向,找出从源点到汇点的一条不饱和链：(1,2)(2,5)(5,7)，求出不饱和链的间隙：min8-6,6-4,9-5=min2,2,4=2,调整不饱和链的流量,2,3,4,5,6,7,1,f=10,f=10,6,2,4,3,7,4,3,1,7,9,8,8,x12=8,x13=2,x25=6,x23=2,x34=3,x36=1,x46=2,x57=7,x45=1,x67=3,判断每一条边两个方向是否饱和，用箭头表示不饱和的方向,找出从源点到汇点的一条不饱和链(1,3)(3,4)(4,5)(5,7)，求出不饱和链的间隙：min7-2,4-3,4-1,9-7=min3,1,3,2=1,调整不饱和链的流量,2,3,4,5,6,7,1,f=11,f=11,6,2,4,3,7,4,3,1,7,9,8,8,x12=8,x13=3,x25=6,x23=2,x34=4,x36=1,x46=2,x57=8,x45=2,x67=3,判断每一条边两个方向是否饱和，用箭头表示不饱和的方向,已经不存在从源点到汇点的不饱和链，已获得网络的最大流。最大流的流量为f=11。,求从源点1出发，通过不饱和链可以到达的节点。,得到最小割集划分的节点集合X=1,2,3,X=4,5,6,7。,2,3,4,5,6,7,1,f=11,f=11,6,2,4,3,7,4,3,1,7,9,8,8,x12=8,x13=3,x25=6,x23=2,x34=4,x36=1,x46=2,x57=8,x45=2,x67=3,最小割集的边集合为(2,5)(3,4)(3,6)。最小割集的容量为：64111，等于最大流的流量。,2,3,4,5,6,7,8,1,7,9,4,6,4,3,6,8,3,1,10,4,5,uij,求以下网络从源点1到汇点8的最大流,间隙为min7,6,10=6,间隙为min9,6,4=4,间隙为min4,8,5=4,x=6,x=6,x=6,x=4,x=4,x=4,x=4,x=4,x=4,f=14,f=14,找到从1到8的三条不饱和链：1,2,5,8、1,3,6,8、1,4,7,8,2,3,4,5,6,7,8,1,7,9,4,6,4,3,6,8,3,1,10,4,5,uij,间隙为min5,2,3,4=2,x=6,x=6,x=6,x=4,x=4,x=4,x=4,x=4,x=4,f=14,f=14,找到从1到8的一条不饱和链：1,3,6,5,8,x=2,2,3,4,5,6,7,8,1,7,9,4,6,4,3,6,8,3,1,10,4,5,uij,x=6,x=6,x=8,x=6,x=6,x=4,x=4,x=4,x=4,f=16,f=16,x=2,已经不存在从1到8的不饱和链。最大流f=16。从源点1通过不饱和边可以到达的节点为1、2、3。X1,2,3,最小割集为(2,5),(3,6),(1,4)。割集的容量为6+6+4=16,最短路径问题,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求从1到8的最短路径,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,w1=0,minc12,c14,c16=min0+2,0+1,0+3=min2,1,3=1X=1,4,w4=1,w4=1,w1=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,minc12,c16,c42,c47=min0+2,0+3,1+10,1+2=min2,3,11,3=2X=1,2,4,w2=2,w1=0,w4=1,w2=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,minc13,c23,c25,c47=min0+3,2+6,2+5,1+2=min3,8,7,3=3X=1,2,4,6,w6=3,w2=2,w4=1,w1=0,w6=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,minc23,c25,c47,c67=min2+6,2+5,1+2,3+4=min8,7,3,7=3X=1,2,4,6,7,w7=3,w2=2,w4=1,w1=0,w6=3,w7=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,minc23,c25,c75,c78=min2+6,2+5,3+3,3+8=min8,7,6,11=6X=1,2,4,5,6,7,w5=6,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,5,6,7,minc23,c53,c58,c78=min2+6,6+9,6+4,3+8=min8,15,10,11=8X=1,2,3,4,5,6,7,w3=8,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,5,6,7,minc38,c58,c78=min8+6,6+4,3+8=min14,10,11=10X=1,2,3,4,5,6,7,8,w8=10,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,节点1到节点10的最短路径为1，4，7，5，8，长度为10。同时求出节点1到其他任何一个节点的最短路径。,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=1