运筹学-基-最短路-松弛互补.ppt

运筹学 目录 第一章线性规划第二章对偶第三章整数规划第四章运输问题第五章网络优化第六章动态规划第七章排队论 第一章线性规划 线性规划模型线性规划的图解可行域的性质线性规划的基本概念基础解 基础可行解单纯形表线性规划的矩阵表示 线性规划模型 线性规划模型的结构目标函数 max min约束条件 变量符号 0 unr 0线性规划的标准形式目标函数 min约束条件 变量符号 0 线性规划的图解 maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优解 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 是基础解但不是可行解 目标函数 约束条件 基矩阵 右边常数 进基变量 离基变量 基变换 基变量 进基变量 离基变量 目标函数 约束条件 右边常数 目标函数 约束条件 新的基矩阵 右边常数 进基变量 离基变量 目标函数 约束条件 基矩阵 目标函数 约束条件 新的基矩阵 右边常数 基础解 基础可行解 maxz x1 3x2Ds t x1 x2 x3 6B x1 2x2 x4 8x4 0Cx3 0 x1 x2 x3 x4 0 x1 0EOx2 0A 几何概念 代数概念 约束直线 满足一个等式约束的解 约束半平面 满足一个不等式约束的解 约束半平面的交集 凸多边形 满足一组不等式约束的解 约束直线的交点 基础解 可行域的极点 基础可行解 目标函数等值线 一组平行线 目标函数值等于一个常数的解 单纯形表 求解线性规划问题 写成标准化形式 写出单纯形表 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 minz 86 maxz 86 线性规划的矩阵表示 CBTB 1aj cj zj cj称为非基变量的检验数 ReducedCost B 1aj Yj B 1b CBTB 1b z0 第二章对偶线性规划 对偶的定义对偶问题的性质原始对偶关系目标函数值之间的关系最优解之间的关系 互补松弛关系最优解的Kuhn Tucher条件对偶可行基对偶单纯形法对偶的经济解释 DUAL 一 对偶的定义 原始问题minz CTXs t AX bX 0 对偶问题maxy bTWs t ATW CW 0 min b A CT C AT bT max m n m n 二 对偶问题的性质 1 对偶的对偶就是原始问题 2 其他形式问题的对偶 三 原始对偶关系 1 可行解的目标函数值之间的关系设XF WF分别是原始问题和对偶问题的可行解z CTXF WTAXF WTb y2 最优解的目标函数值之间的关系设Xo Wo分别是原始问题和对偶问题的最优解z CTXo WoTAXo WoTb y 3 原始问题和对偶问题最优解之间的互补松弛关系 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 minz CTXs t AX bX 0 maxy bTWs t ATW CW 0 互补松弛关系 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 XTWS 0WTXS 0 m n W WS AT I C n A XS I b n m m X 原始问题和对偶问题变量 松弛变量的维数 w1wiwmwm 1wm jwn m x1xjxnxn 1xn ixn m 对偶问题的变量对偶问题的松弛变量 原始问题的变量原始问题的松弛变量 xjwm j 0wixn i 0 i 1 2 m j 1 2 n 在一对变量中 其中一个大于0 另一个一定等于0 Kuhn Tucher条件 3 原始问题和对偶问题最优解的充分必要条件 1 原始可行条件 PFC AX XS bX XS 0 2 对偶可行条件 DFC ATW WS CW WS 0 3 互补松弛条件 CSC XTWS 0WTXS 0 四 对偶单纯形法 1 用单纯形表求解原始问题的四种形式 minz CTXs t AX bX 0 minz CTXs t AX bX 0 maxz CTXs t AX bX 0 maxz CTXs t AX bX 0 2 3 4 1 单纯形表和对偶 1 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 minz CTXs t AX bX 0 maxy bTWs t ATW CW 0 对偶问题 原始问题 引进松弛变量 引进松弛变量 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 WT CBTB 1WST CT WTA minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW 0 WS 0 minz CTXs t AX bX 0 maxy bTWs t ATW CW 0 单纯形表和对偶 2 对偶问题 原始问题 引进松弛变量 引进松弛变量 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW 0 WS 0 WT CBTB 1WST CT WTA maxz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW 0 WS 0 maxz CTXs t AX bX 0 miny bTWs t ATW CW 0 单纯形表和对偶 3 对偶问题 原始问题 引进松弛变量 引进松弛变量 maxz CTXs t AX XS bX XS 0 miny bTWs t ATW WS CW 0 WS 0 WT CBTB 1WST WTA CT maxz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 maxz CTXs t AX bX 0 miny bTWs t ATW CW 0 单纯形表和对偶 4 对偶问题 原始问题 引进松弛变量 引进松弛变量 maxz CTXs t AX XS bX XS 0 miny bTWs t ATW WS CW WS 0 WT CBTB 1WST WTA CT 2 对偶单纯形法 初始解原始不可行的问题 已获得最优解 x1 x2 x3 x4 x5 x6 5 7 6 0 0 0 minz 35对偶问题的最优解为 w1 w2 w3 w4 w5 w6 1 5 7 0 0 0 maxy 35 3 初始解原始 对偶都不可行的问题 解法1 先解决原始可行性 在得到原始可行解时同时得到对偶可行解 已获得最优解 x1 x2 x3 x4 x5 x6 5 7 6 0 0 0 minz 17对偶问题的最优解为 w1 w2 w3 w4 w5 w6 7 5 10 0 0 0 maxy 17 解法2 先解决对偶可行性 已得到对偶可行解 再用对偶单纯形法求解 得到原始可行解 已获得最优解 x1 x2 x3 x4 x5 x6 5 7 6 0 0 0 minz 17对偶问题的最优解为 w1 w2 w3 w4 w5 w6 7 5 10 0 0 0 maxy 17 五 对偶的经济解释 1 原始问题是利润最大化的生产计划问题 单位产品的利润 元 件 产品产量 件 总利润 元 资源限量 吨 单位产品消耗的资源 吨 件 剩余的资源 吨 消耗的资源 吨 2 对偶问题 资源限量 吨 资源价格 元 吨 总利润 元 对偶问题是资源定价问题 对偶问题的最优解w1 w2 wm称为m种资源的影子价格 ShadowPrice 原始和对偶问题都取得最优解时 最大利润maxz miny 3 资源影子价格的性质 影子价格越大 说明这种资源越是相对紧缺影子价格越小 说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余 这种资源的影子价格一定等于0 w1w2wm 4 产品的机会成本 机会成本表示减少一件产品所节省的资源可以增加的利润 机会成本 利润 差额成本 5 产品的差额成本 ReducedCost 差额成本 机会成本 利润 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 c34u3 6 对偶变量法 3 u3 v3 c33v3 4 对偶变量法 4 u2 v3 c23u2 2 对偶变量法 5 u2 v2 c22v2 6 对偶变量法 6 u2 v1 c21v1 10 对偶变量法 7 u1 v1 c11u1 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进基 min x21 x33 min 8 6 6 x33离基 3 5 5 7 9 11 调整运量 重新计算检验数 确定进基 离基变量 x14进基 min x11 x34 min 14 13 13 x34离基 11 5 5 4 2 8 调整运量 重新计算检验数 所有zij cij 0 得到最优解 Minz 6 1 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 网络的生成树和线性规划的关系 网络的一个生成树对应于线性规划的一个基生成树上的边对应于线性规划的基变量生成树的弦对应于线性规划的非基变量生成树的变换对应于线性规划单纯形法的进基和离基变换 网络最小费用流问题 b2 2 b4 3 b3 5 b5 6 b6 5 b1 5 c24 5 c46 1 c13 3 c35 2 c56 4 c34 4 c12 6 cij单位流量的费用 初始基础可行解 生成树 b6 5 b2 2 b4 3 b3 5 b5 6 b1 5 x13 3 x46 3 x35 8 x56 2 x12 2 2 3 4 5 6 1 确定非基变量x24和x34 b2 2 b6 5 b3 5 b5 6 b1 5 c24 5 c46 1 c13 3 c35 2 c56 4 c34 4 c12 6 2 3 4 5 6 1 b4 3 求x24的检验数z24 c24闭回路法 z24 c24 c46 c56 c35 c13 c12 c24 1 4 2 3 6 5 3 b2 2 b4 3 b3 5 b5 6 b6 5 b1 5 c24 5 c46 1 c13 3 c35 2 c56 4 c12 6 2 3 4 5 6 1 求x34的检验数z34 c34闭回路法 z34 c34 c46 c56 c35 c34 1 4 2 4 1 x34进基 b2 2 b4 3 b3 5 b5 6 b6 5 b1 5 c46 1 c13 3 c35 2 c56 4 c34 4 c12 6 2 3 4 5 6 1 变量x34进基 确定离基变量 min x56 x35 min 2 8 2 x56离基 调整流量 进行基变换 b2 2 b4 3 b3 5 b5 6 b6 5 b1 5 x46 3 x13 3 x35 8 x56 2 x34 0 x12 2 2 3 4 5 6 1 确定非基变量x24和x56 b2 2 b4 3 b3 5 b5 6 b6 5 b1 5 x46 5 x13 3 x35 6 x34 2 x12 2 2 3 4 5 6 1 计算x24和x56的检验数z24 c24 z56 c56 z24 c24 c34 c13 c12 c24 4 3 6 5 4z56 c56 c46 c34 c35 c56 1 4 2 4 1 获得最优解 b2 2 b4 3 b3 5 b5 6 b6 5 b1 5 c24 5 c46 1 c13 3 c35 2 c56 4 c34 4 c12 6 2 3 4 5 6 1 最优解 最优解的目标函数值为 minz 6 2 3 3 4 2 2 6 1 5 46 b2 2 b4 3 b3 5 b5 6 b6 5 b1 5 x46 5 x13 3 x35 6 x34 2 x12 2 2 3 4 5 6 1 网络最大流问题 边的容量和流量容量uij 流量xij可行流满足以下条件的流称为可行流 1 每一个节点流量平衡2 0 xij uij 边的容量和流量 可行流 饱和边 不饱和边 流量的间隙 1 2 是饱和的 2 如果xij uij 边从i到j的方向是不饱和的 1 2 是不饱和的间隙为 12 u12 x12 5 3 2 1 如果xij uij 边从i到j的方向是饱和的 3 如果xij 0 边从j到i的方向是饱和的 2 1 是饱和的 如果xij 0 边从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的不饱和链 链的间隙为 min 8 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 最短路径问题 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 1X 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 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 min c13 c23 c25 c47 min 0 3 2 6 2 5 1 2 min 3 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 min c23 c25 c47 c67 min 2 6 2 5 1 2 3 4 min 8 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 min c23 c25 c75 c78 min 2 6 2 5 3 3 3 8 min 8 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 6 7 min c23 c53 c58 c78 min 2 6 6 9 6 4 3 8 min 8 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 6 7 min c38 c58 c78 min 8 6 6 4 3 7 min 14 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 w2 2 w4 1 w1 0 w6 3 w7 3 w5 6 w3 8 w8 10 第六章动态规划 最短路径问题资源分配问题背包问题机器负荷分配问题 一 最短路径问题 求从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