运筹学教程课程.ppt

运筹学课件,天津工业大学,目 录,第一章 线性规划 第二章 对偶 第三章 整数规划 第四章 运输问题 第五章 网络优化 第六章 动态规划,第一章 线性规划,线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 基础解、基础可行解 单纯形表 线性规划的矩阵表示,线性规划模型,线性规划模型的结构 目标函数 ：max，min 约束条件：,=, 变量符号：0, unr, 0 线性规划的标准形式 目标函数：min 约束条件 ：= 变量符号 ：0,线性规划的图解,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,可行域的性质,线性规划的可行域是凸集 线性规划的最优解在极点上,凸集,凸集,不是凸集,极点,线性规划的基本概念,线性规划的基矩阵、基变量、非基变量,=,=,目标函数,约束条件,行列式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、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） 是基础解但不是可行解。,目标函数,约束条件,基矩阵,右边常数,进基变量、离基变量、基变换,基变量,进基变量,离基变量,目标函数,约束条件,右边常数,目标函数,约束条件,新的基矩阵,右边常数,进基变量,离基变量,目标函数,约束条件,基矩阵,目标函数,约束条件,新的基矩阵,右边常数,基础解、基础可行解,max z=x1+3x2 d s.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/1,36/2,0,-3,-2,0,-2,-72,0,1,1/2,0,1,-1/2,7/1/2,1,x5,1/2,1,0,1/2,18/1/2,0,7,18,1,1/2,1/2,x2,0,x6离基，,x2进基，,x5离基，,x1进基，,0,-4,-2,-2,-1,-86,0,1,1,0,2,-1,1,x1,0,1,-1,1,0,14,11,0,1,0,x2,0,得到最优解，最优解为：,（x1，x2，x3，x4，x5，x6）=（14，11，0，0，0，0） min z=-86，max z=86,线性规划的矩阵表示,=,=,right hand side 右边常数,cbtb-1aj-cj=zj-cj 称为非基变量的检验数（reduced cost） b-1aj=yj， b-1b= ，cbtb-1b=z0,第二章 对偶线性规划,对偶的定义 对偶问题的性质 原始对偶关系 目标函数值之间的关系 最优解之间的关系互补松弛关系 最优解的kuhn-tucher条件 对偶可行基对偶单纯形法 对偶的经济解释,dual,一、对偶的定义,原始问题 min z=ctx s.t. axb x 0,对偶问题 max y=btw s.t. atwc w 0,min,b,a,ct,c,at,bt,max,m,n,m,n,二、对偶问题的性质,1、对偶的对偶就是原始问题,2、其他形式问题的对偶,三、原始对偶关系,1、可行解的目标函数值之间的关系 设xf、wf分别是原始问题和对偶问题的可行解 z=ctxf wtaxf wtb=y 2、最优解的目标函数值之间的关系 设xo、wo分别是原始问题和对偶问题的最优解 z=ctxo=wotaxo=wotb=y,3、原始问题和对偶问题最优解之间的互补松弛关系,min z=ctx s.t. ax-xs=b x, xs0,max y=btw s.t. atw+ws=c w, ws0,min z=ctx s.t. axb x 0,max y=btw s.t. atwc w0,互补松弛关系,min z=ctx s.t. ax-xs=b x, xs 0,max y=btw s.t. atw+ws=c w, ws 0,xtws=0 wtxs=0,m,n,=,w,ws,at,i,c,n,=,a,xs,-i,b,n,m,m,x,原始问题和对偶问题变量、松弛变量的维数,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，另一个一定等于0,kuhn-tucher 条件,3、原始问题和对偶问题最优解的充分必要条件 (1)原始可行条件（pfc） ax-xs=b x, xs 0 (2)对偶可行条件（dfc） atw+ws=c w, ws 0 (3)互补松弛条件（csc） xtws=0 wtxs=0,四、对偶单纯形法,1、用单纯形表求解原始问题的四种形式,min z=ctx s.t. axb x 0,min z=ctx s.t. ax b x 0,max z=ctx s.t. ax b x 0,max z=ctx s.t. ax b x 0,（2）,（3）,（4）,（1）,单纯形表和对偶(1),min z=ctx s.t. ax-xs=b x, xs0,max y=btw s.t. atw+ws=c w, ws0,min z=ctx s.t. axb x 0,max y=btw s.t. atwc w0,对偶问题,原始问题,引进松弛变量,引进松弛变量,min z=ctx s.t. ax-xs=b x, xs0,max y=btw s.t. atw+ws=c w, ws0,wt=cbtb-1 wst=ct-wta,min z=ctx s.t. ax+xs=b x, xs0,max y=btw s.t. atw+ws=c w 0, ws0,min z=ctx s.t. ax b x 0,max y=btw s.t. atwc w 0,单纯形表和对偶(2),对偶问题,原始问题,引进松弛变量,引进松弛变量,min z=ctx s.t. ax+xs=b x, xs0,max y=btw s.t. atw+ws=c w 0, ws0,wt=cbtb-1 wst=ct-wta,max z=ctx s.t. ax-xs=b x, xs0,max y=btw s.t. atw-ws=c w 0, ws0,max z=ctx s.t. ax b x 0,min y=btw s.t. atw c w 0,单纯形表和对偶(3),对偶问题,原始问题,引进松弛变量,引进松弛变量,max z=ctx s.t. ax-xs=b x, xs0,min y=btw s.t. atw-ws=c w 0, ws0,wt=cbtb-1 wst=wta- ct,max z=ctx s.t. ax+xs=b x, xs0,max y=btw s.t. atw-ws=c w, ws0,max z=ctx s.t. ax b x 0,min y=btw s.t. atw c w 0,单纯形表和对偶(4),对偶问题,原始问题,引进松弛变量,引进松弛变量,max z=ctx s.t. ax+xs=b x, xs0,min y=btw s.t. atw-ws=c w, ws0,wt=cbtb-1 wst=wta- ct,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,w1 w2 wm,4、产品的机会成本,机会成本 表示减少一件产品所节省的资源可以增加的利润,增加单位资源可以增加的利润,减少一件产品可以节省的资源,机会成本,利润,差额成本,5、产品的差额成本（reduced cost）,差额成本=机会成本 - 利润,5、互补松弛关系的经济解释,在利润最大化的生产计划中 （1）边际利润大于0的资源没有剩余 （2）有剩余的资源边际利润等于0 （3）安排生产的产品机会成本等于利润 （4）机会成本大于利润的产品不安排生产,第四章 运输问题,运输问题的表示 网络图、线性规划模型、运输表 初始基础可行解 西北角法、最小元素法 非基变量的检验数 闭回路法、对偶变量法 确定进基变量，调整运量，确定离基 变量,2,3,2,1,3,4,1,运输问题网络图,s2=27,s3=19,d1=22,d2=13,d3=12,d4=13,s1=14,供应量,供应地,运价,需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,运输问题线性规划模型,供应地约束,需求地约束,运输问题的表格表示,初始基础可行解西北角法,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,闭回路法(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-c33+ 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=c34 u3=6,对偶变量法(3),u3+v3=c33 v3=4,对偶变量法(4),u2+v3=c23 u2=-2,对偶变量法(5),u2+v2=c22 v2=6,对偶变量法(6),u2+v1=c21 v1=10,对偶变量法(7),u1+v1=c11 u1=-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=11,11,-5,-5,-7,-9,对偶变量法(13),z32-c32=u3+v2-c32=6+6-9=+3,+3,-5,-5,-7,-9,11,选择进基变量,确定离基变量,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,得到最优解。 min z=61+3 13+8 2+4 13+2 12+5 19=142,-11,-5,-5,-4,-8,-2,第五章 网络优化,网络的基本概念 最短路径问题 网络最大流问题,网络的基本概念,节点与（有向）边 每一条边和两个节点关联，一条边可以用两个节点的标号表示（i，j）,路径（path） 前后相继并且方向相同的边序列 p=(1,2),(2,3),(3,4),4,2,3,1,4,2,3,1,网络由节点和边组成,回路（circuit） 起点和终点重合的路径称为回路 =(1,2),(2,4),(4,1) 回路中各条边方向相同,4,2,3,1,链（chain） 前后相继并且方向不一定相同的边序列称为链 c=(1,2),(3,2),(3,4),4,2,3,1,连通图 任意两个节点之间至少有一条链的图称为连通图,2,4,3,5,1,圈(cycle) 起点和终点重合的链称为圈 =(1,2),(2,4),(3,4),(1,3) 圈中各条边方向不一定相同,4,2,3,1,树(tree) 无圈的连通图称为树 树中只与一条边关联的节点称为悬挂节点,树的性质,任何树至少有一个悬挂节点,2,4,3,5,1,2,4,3,5,1,2,4,3,5,1,如果树的节点个数为m，则边的个数为m-1,树中任意两个节点之间只有唯一的一条链,在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈,网络的生成树,由网络的所有节点（m个）和网络的m-1条边组成的树称为网络的生成树，网络中不属于生成树的边称为生成树的弦,网络的生成树的变换,网络的一个生成树，增加一条弦，形成唯一的圈，去掉生成树的一条边，得到一个新的网络的生成树,生成树2,生成树3,生成树1,/,/,最短路径问题,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,min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1 x=1,4, w4=1,w1=0,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,min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2 x=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,min c16,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3 x=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,min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 x=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,min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 x=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,6,7,min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8 x=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,6,7,min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10 x=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。,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,网络最大流问题,边的容量和流量 容量uij，流量xij 可行流 满足以下条件的流称为可行流： 1、每一个节点流量平衡 2、0xij uij,边的容量和流量、可行流,饱和边、不饱和边、流量的间隙,（1，2）是饱和的,2、如果xijuij，边从i到j的方向是不饱和的；,（1，2）是不饱和的 间隙为12=u12-x12=5-3=2,1、如果xij=uij，边从i到j的方向是饱和的；,3、如果xij=0，边从j到i的方向是饱和的；,（2，1）是饱和的,如果xij0，边从j到i的方向是不饱和的；,（2，1）是不饱和的 间隙为12=x12=5,给出一个初始的可行流xij=0,找到所有的不饱和边，以及各边可以调整流量的方向,2,3,5,4,6,7,1,f=0,f=0,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=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 调整链的流量：xij=xij+ ,2,3,5,4,6,7,1,f=0,f=0,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,=3,=1,=8,=8,x=0,调整流量，f=1。继续求出网络的不饱和边,2,3,5,4,6,7,1,f=1,f=1,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=1,x=1,x=1,x=1,求出一条从1到7的不饱和链,2,3,5,4,6,7,1,f=1,f=1,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=1,x=1,x=1,x=1,=1,=6,=9,=7,=min 7,1,6,9=1, 调整流量 xij=xij+1, f=f+1=2,调整流量，继续求出网络的不饱和边,2,3,5,4,6,7,1,f=2,f=2,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=1,x=0,x=0,x=1,x=0,x=0,x=0,x=1,x=1,x=1,x=1,x=0,求出一条从1到7的不饱和链,=5,=8,=7,=min 7,5,8=5, 调整流量 xij=xij+5, f=f+5=2+5=7,调整流量，继续求出网络的不饱和边,2,3,5,4,6,7,1,f=7,f=7,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=0,x=1,x=0,x=0,x=0,x=6,x=1,x=1,x=6,x=0,求出一条从1到7的不饱和链,=min 6,7,4,3=3, 调整流量 xij=xij+3, f=f+3=7+3=10,=4,=4,=3,=6,调整流量，继续求出网络的不饱和边,2,3,5,4,6,7,1,f=10,f=10,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=3,x=4,x=3,x=0,x=0,x=9,x=1,x=1,x=6,x=0,求出一条从1到7的不饱和链,2,3,5,4,6,7,1,f=10,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=3,x=4,x=3,x=0,x=0,x=9,x=1,x=1,x=6,x=0,f=10,=1,=3,=7,=3,=min 3,1,3,7=1, 调整流量 xij=xij+1, f=f+1=10+1=11,调整流量，继续求出网络的不饱和边,2,3,5,4,6,7,1,f=11,f=11,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=4,x=5,x=3,x=1,x=0,x=9,x=2,x=1,x=6,x=0,已找不到一条从1到7的不饱和链，从1开始可以到达的节点为1，2，3,已求得最大流,2,3,5,4,6,7,1,f=11,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=4,x=5,x=3,x=1,x=0,x=9,x=2,x=1,x=6,x=0,f=11,最大流f=11，最小割集为（2,5）（3,4）（3,5） u25+u34+u35=6+4+1=11,第六章 动态规划,最短路径问题 资源分配问题 背包问题 机器负荷分配问题,一、最短路径问题,求从a到e的最短路径,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,c1,c3,d1,a,b1,b3,b2,d2,e,c2,f5(e)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,c1,c3,d1,a,b1,b3,b2,d2,e,c2,f4(d1)=5,f5(e)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,c1,c3,d1,a,b1,b3,b2,d2,e,c2,f4(d2)=2,f5(e)=0,f4(d1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,c1,c3,d1,a,b1,b3,b2,d2,e,c2,f4(d2)=2,f5(e)=0,f3(c1)=8,f4(d1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,c1,c3,d1,a,b1,b3,b2,d2,e,c2,f4(d2)=2,f5(e)=0,f3(c2)=7,f4(d1)=5,f3(c1)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,c1,c3,d1,a,b1,b3,b2,d2,e,c2,f4(d2)=2,f5(e)=0,f3(c3)=12,f4(d1)=5,f3(c1)=8,f3(c2)=7,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,c1,c3,d1,a,b1,b3,b2,d2,e,c2,f4(d2)=2,f5(e)=0,f3(c3)=12,f4(d1)=5,f2(b1)=20,f3(c2)=7,f3(c1)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,c1,c3,d1,a,b1,b3,b2,d2,e,c2,f4(d2)=2,f5(e)=0,f3(c3)=12,f4(d1)=5,f2(b2)=14,f3(c2)=7,f3(c1)=8,f2(b1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,c1,c3,d1,a,b1,b3,b2,d2,e,c2,f4(d2)=2,f5(e)=0,f3(c3)=12,f4(d1)=5,f2(b3)=19,f3(c2)=7,f3(c1)=8,f2(b1)=21,f2(b2)=14,2,5