《运筹学》线性规划.ppt

《《运筹学》线性规划.ppt》由会员分享，可在线阅读，更多相关《《运筹学》线性规划.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2章章 线性规划线性规划例例1 穗羊公司的例子III每周可使用量A（千克）125B（吨）214C（百工时）439单位产品利润（万元）32问该公司每周应生产产品I与产品II各多少单位，才能使每周的获利达到最大？l假设产品I、II每周的产量分别是x1和x2，得到如下的数学模型其中s.t.是英文词组subject to的缩写，表示“受限制于”的意思，有时也约去不写出来。该问题常称为生产计划问题生产计划问题或产品组合产品组合（product mix）问题。例例2 设有一批规格为10米长的圆钢筋，将它截成分别为3米，4米长的预制构件的短钢筋各100根，问怎样截取最省料？因为，10米长的钢筋截为3米或

2、4米长，共有三种截法：截法：3 3 3 1 米截法：3 3 4 0 米截法：4 4 0 2 米假设按截法，各截取10米长的钢筋分别为x1,x2,x3根 则可以获得3米长的短钢筋的根数是3x1+2x2 4米长短钢筋的根数是x2+2x3 按问题要求它们应该不小于100根。总共用料是x1+x2+x3要达到最省料的目的，就必须使总用料最小。例2的模型就是例2 中的问题常称为下料问题下料问题。线性规划的三个要素：决策变量决策变量目标函数目标函数约束条件约束条件其次线性规划模型必须满足如下两个要求：目标函数必须是决策变量的线性函数；目标函数必须是决策变量的线性函数；约束条件必须是含决策变量的线性等式或不等

3、式约束条件必须是含决策变量的线性等式或不等式。运筹学建模步骤:识别问题定义决策变量建立约束条件建立目标函数2.2 线性规划模型的一般形式和标准形式线性规划模型的一般形式和标准形式 为了讨论一般的线性规划问题的求解。我们先给出线性规划模型的一般形式如下：2.2.1 线性规划的一般模型线性规划的一般模型l这里一共包含有n个决策变量，m个约束条件；l对目标函数既可以求最大的也可以求最小；l约束条件有,=型；l决策变量通常非负，但也可以有其它情况；lcj:称为价值系数；bi:资源常数（右端常数）laij称为技术系数、工艺系数在今后的讨论中，为方便起见，还将用到线性规划模型一般形式的各种简写的形式。利用

4、和号“”，线性规划模型的一般形式可写为：利用向量，可以将一般形式表示为：其中在今后的讨论，常将矩阵 称为线性规划问题的（约束条件）系数矩阵系数矩阵。明显地系数矩阵 与矩阵 之间存在关系：用矩阵的记号可以将线性规划模型一般形式写成：其中 同上，而矩阵 是由各约束条件的系数（技术系数）构成的 矩阵：2.2.2 线性规划的标准形式线性规划的标准形式它具有如下四个特征：目标函数求max；约束条件两端用“=”连结；bi非负；所有决策变量xj非负。2.2.3 将线性规划的模型化为标准形式1、目标函数求最小值的情形、目标函数求最小值的情形 取原目标函数的相反数为新的目标函数，对原目标函数求最小值的问题就等价

5、于对这一新的目标函数求最大值的问题。例如：等价于 2、约束条件为不等式、约束条件为不等式 (a)转化为xs表示决策中尚未使用的那部分资源，因此称这一变量为松弛变量松弛变量。（b）转化为：它表示决策结果超过了实际需要的部分，因此常称它为剩余变量剩余变量。无论是松弛变量还是剩余变量在决策中都不产生实际价值，因此它们在它们在目标函数中的系数都应该为零目标函数中的系数都应该为零。在后面的讨论中，有时也将松弛变量和剩余变量统称为松弛变量。3、约束条件右端常数为负数、约束条件右端常数为负数 只需将这一约束条件两端同乘“-1”就可化为一个等价的约束条件，其右端常数满足标准形式的要求。4、决策变量不满足非负约

6、束、决策变量不满足非负约束 （a）（b）如x3无约束，则令 例如，将例1中的线性规划模型化为标准形式就是：其中 就是分别对第一、第二、第三个约束条件中添加的松弛变量。例3 化如下的线性规划问题模型为标准形式。(1)变量是非正的，所以要将模型中的所有都用代替，其中(2)变量无约束，因此取两个变量使得。在模型中，所有的都用代替。在模型中，所有的(5)约束条件2是“”型的，因此需要在左边加上一个松弛变量化为等式，即”型的，并且右端的常数小于零。(3)目标函数是求最小值的，因此令，即(4)约束条件1是“然后在两端乘以-1得也就是因此先将其左边减取一个剩余变量使它化为等式：也就是。从而得到模型的标准形式

7、为课堂练习 某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）ABCD价格价格M0.50.20.30300N0.10.30.40.2200每头每头日需日需10587养分饲料课堂练习 某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）ABCD价格价格M0.50.20.30300N0.10.30.40.2200每头日需每头日需10587养分饲料答案：设购买M

8、饲料x1，N饲料x20.5 x1+0.1x2100.2x1+0.3x2 50.3x1+0.4x2 8 0.2x2 7x1,x20s.t.Min Z=300 x1+200 x22.3 线性规划的图解法线性规划的图解法 对只包含两个决策变量只包含两个决策变量的线性规划问题，可以用图解法图解法来求解。图解法顾名思义就是通过作图来求解的方法，它简单直观、并有助于说明一般线性规划问题求解的基本原理。有关概念可行解：可行解：我们将满足线性规划问题的所有约束条件的变量x1和x2的一组取值称为线性规划问题的一个可行解可行解。通常用X表示。可行域：可行域：我们将可行解的集合称为可行域可行域。最优解：最优解：因此

9、我们求解线性规划问题，就是要求使得目标函数取最优值（对例1，就是取最大值）的可行解，这样的可行解就称为线性规划问题的最优解最优解。通常用X*表示。最优值：最优值：即最优的目标函数值,通常用z*表示图解法步骤:建立平面直角坐标系 图示约束条件,求可行域图示目标函数求最优解建立直角坐标系图示约束条件，求可行域x1x2图示目标函数求最优解x1x2最优解等值线向右上方移动，函数值变大。在其即将离开可行域时达到B（3/2,1）点。所以最优解为：此时最优值为：2.2.2 线性规划求解的可能结局线性规划求解的可能结局 1、有唯一的最优解、有唯一的最优解2、有无穷多个最优解、有无穷多个最优解（将目标函数改为

10、z=4x1+3x2）max z=3x1+5.7x2 s.t.x1+1.9x2 3.8 x1 -1.9x2 3.8 x1+1.9x2 11.4 x1 -1.9x2 -3.8 x1，x2 0 x1x2ox1-1.9 x2=3.8 x1+1.9 x2=3.8x1+1.9 x2=11.4（7.6,2）D0=3 x1+5.7 x2 max Z min Z（3.8,4）34.2=3 x1+5.7 x2 可行域可行域x1-1.9 x2=-3.8(0,2)(3.8,0)绿色线段上的所有点绿色线段上的所有点都是最优解都是最优解,即有无穷多即有无穷多最优解。最优解。Zman=34.23、无界解、无界解 指线性规划

11、问题有可行解，但是在可行域，目标函数值是无界的，因而达不到有限最优值。因此线性规划问题不存在最优解。4、无可行解、无可行解 指找不到一组变量能满足线性规划的所有约束条件的情况，也就是线性规划问题不存在可行解，或者说可行域是空集。例如线性规划问题：LP 解的几种情况（1）唯一解（2）多重最优解（3）无可行解注：出现（3）、（4）情况时，建模有问题（4）无有限最优解另外两个重要的结论：线性规划问题可行域若不是空集，则它是一个凸集；线性规划问题可行域若不是空集，则它是一个凸集；线性规划问题的最优解若存在，则一定可以在其可行域线性规划问题的最优解若存在，则一定可以在其可行域的一个顶点上达到。的一个顶点

12、上达到。最优解：x1=0，x2 =1 最优目标值 z =3课堂练习图解法求解线性规划012341234x1x2O-1-2(1)(2)(3)例 某工厂经市场调研，决定生产甲、乙两种产品，其单台利润分别为60元和30元，两种产品共用一种钢材、一台设备，其资源及获利情况如下：甲乙现有资源钢材消耗定额（公斤/台）24600公斤台时消耗定额（小时/台）31400小时配件（件/台）20250件利润（元）6030求利润最大的产品结构决策。确定目标函数及约束条件建立数学模型目标函数：将不等式变为等式并在x1x2坐标图中作出直线 最优点在凸边形的顶点，代入（1）式可得maxP解解：设变量：设甲生产设变量：设甲生

13、产x1台，乙生产台，乙生产x2台，可得最大利润台，可得最大利润约束条件：05050100100150150200250300350200250300350400 x1x2A(0,150)B(100,100)C(125,25)D(125,0)(4)2.4 线性规划解的基本概念与性质线性规划解的基本概念与性质 在本节，我们主要考虑模型具有标准形式的线性规划问题（2.6）线性规划问题解的概念及性质对于线性规划问题（2.6）来说，可行解实际上是由约束条件构成的线性方程组（常称为约束方程组约束方程组）的解，并且还满足非负约束条件，即各个决策变量都取非负值：。对于线性规划问题（2.6），可以证明如下的结论

14、：定理定理2.1 线性规划问题的可行域如果不是空集，就一定是凸集。凸集凸集:指一个非空集，并且以其中任意两个点为端点的直线段上的所有点都属于该集合。顶点：顶点：在凸集中，如果一个点不位于其他两点为端点的线段的内部，则称其为该凸集的顶点顶点。例如上图中第一个凸集的A点，或第二个凸集的B点，分别是相应的凸集的顶点。哪个是凸集呢？今后我们将A的任一个具有这样的特征的子矩阵B称为线性规划问题（2.6）的一个基基。也就是说线性规划问题的基就是矩阵A的一个 且行列式不为零的子矩阵。我们将约束方程组的系数矩阵称为线性规划问题的系数矩系数矩阵阵，并且总总假定其秩等于其行数假定其秩等于其行数：。这意味着系数矩阵

15、的各行是线性无关的，这也表明约束方程中的各个方程是相互独立的。由于矩阵A的秩为m,故至少存在一个 的子矩阵B，其行列式不为零。例如，对于线性规划问题 其系数矩阵为 则下面两个矩阵都是该线性规划问题的基。和还能找出其它基吗？例如，对上面的线性规划问题，若我们考虑基则线性规划问题的基变量基变量就是x2和x4，而x1和x3就是非基变量非基变量。但如果我们考虑的基是则基变量是x1和x2，非基变量是x3和x4。可见在线性规划问题中所谓基变量就是由m个变量构成的一组变量，其系数构成的行列式不等于零；反之满足系数行列式不等于零的一组m个变量，就是基变量。基解基解：在约束方程组中，令非基变量等于0的解。基可行

16、解：基可行解：基解+可行解 例如，对于上面的线性规划问题，如果取x1，x2为基变量，则令非基变量x3，x4为零，约束方程组为 解之得 。故我们得到基解注意到这个基解还是一个可行解。是否所有的基解都是基可行解？（选x1,x3作为基变量）定理定理2.2：线性规划问题的基可行解是其可行域的顶点。定理定理2.3：线性规划问题的最优解如果存在，则一定有一个基可行解是最优解。2.6 单纯形法计算单纯形法计算l基本思路：l首先将线性规划问题化成标准形式l求出初始基本可行解l判断其是否为最优解l如果不是最优，则迭代到其相邻的基本可行解，并再次检验 旦茨基教授在一次演说中，形象而风趣地说明了单纯形解法的奇效：设

17、给70个人分配70项任务，每人一项。如果每人完成各项任务所需要付出的代价（时间、工资）都知道，要寻求代价最小的方案。所有的可行方案共有70！种。70！比 还要大。不仅如此，还能预测当方案中某因素发生变化，对决策目标的影响。l 线性规划问题的可行解有无穷多个，与某一凸集上的无穷多个点一一对应。要从无穷多个可行解中寻找最优解，几乎不可能。可以证明，最优解必定能取在凸集的顶点（极点、基本可行解）上，而极点的个数是有限的。当然，这个“有限”，数字往往相当可观，如前面的70！，要逐个比较的话，也不现实。而单纯形解法，用跨跃的方式，高速地优化基本可行解，迅速达到最优。单纯形法跨跃式地寻求最优解优max S

18、S=ooABCDE初始可行解初始可行解为了便于求解，并使得整个求解过程程序化，我们通常是从求一个特殊的基可行解出发进行求解。这个特殊的基可行解称为初始基可行解。要求初始基可行解需先确定初始基变量。我们称基矩阵为单位矩阵（或单位矩阵交换了列以后得到的矩阵）的基变量为初始基变量。因此初始基变量具有特征：它们是一组变量，个数等于约束方程的个数，每个变量仅出现在一个约束方程中且系数为1。初始基变量对应的基解一定是可行解称为初始基可行解。解：解：数学模型数学模型 max S=6x1+4x2 s.t.2x1+3x2 100 4x1+2x2 120 x1,x2 0引进松弛变量引进松弛变量x x3 3,x,x

19、4 4 0 0数学模型标准形式：数学模型标准形式：max S=6xmax S=6x1 1+4x+4x2 2 s.t.2x s.t.2x1 1+3x+3x2 2+x+x3 3 =100=100 4x 4x1 1+2x+2x2 2 +x+x4 4=120=120 x x1 1,x,x2 2,x x3 3,x,x4 4 0 0 A=（P1，P2，P3，P4）=2 3 1 0 4 2 0 1 X=（x1,x2,x3,x4)B=(P3，P4）=1 0 0 1P P3 3，P P4 4线性无关，线性无关，x3,x4x3,x4是基是基变量，变量，x x1 1,x,x2 2,是非基变量。是非基变量。令令A=A

20、=（P P1 1，P P2 2，P P3 3，P P4 4）=2 3 1 0=2 3 1 0 4 2 0 1 4 2 0 1 X=X=（x x1 1,x,x2 2,x,x3 3,x,x4 4)用非基变量表示的方程：用非基变量表示的方程：x x3 3=100-2x=100-2x1 1-3x-3x2 2 x x4 4=120-4x=120-4x1 1-2x-2x2 2 (I)(I)S =6x S =6x1 1+4x+4x2 2 令非基变量令非基变量 （x x1 1,x x2 2）t t=（0 0，0 0）t t 得基础可行解：得基础可行解：x x(1)(1)=(0,0,100,120)=(0,0,

21、100,120)t t S S1 1=0=0 经济含义：不生产产品甲乙，利润为零。经济含义：不生产产品甲乙，利润为零。分析：分析：S =S =6 6x x1 1+4 4x x2 2（分别增加单位产品甲、乙，目标函数分别增加（分别增加单位产品甲、乙，目标函数分别增加6 6、4 4，即利润分别增加，即利润分别增加6 6百元、百元、4 4百元。）百元。）增加单位产品对目标函数的贡献，这就是增加单位产品对目标函数的贡献，这就是检验检验数数的概念。的概念。增加单位产品甲（增加单位产品甲（x1）比乙对目标函数的贡献大）比乙对目标函数的贡献大（检验数最大），（检验数最大），把非基变量把非基变量x1换成基变量

22、，称换成基变量，称x1为为进基变量进基变量，而把基变量而把基变量x4换成非基变量，称换成非基变量，称x4为为出基变量出基变量。确定了确定了进基变量进基变量x x1 1 ，出基变量出基变量x x4 4 以后，得到新的系以后，得到新的系统：统：x x3 3=40-2x=40-2x2 2+（1/21/2）x x4 4 x x1 1=30-=30-（1/21/2）x x2 2-（1/41/4）x x4 4 (II)(II)S=180+x S=180+x2 2-（3/23/2）x x4 4 令新的非基变量（令新的非基变量（x x2 2，x x4 4）=（0 0，0 0）t t得到新的基础可行解：得到新的

23、基础可行解：x x(2)(2)=(30,0,40,0)=(30,0,40,0)t t S S2 2=180=180经济含义：生产甲产品经济含义：生产甲产品3030个，获得利润个，获得利润1800018000元。元。这个方案比前方案，但是否是最优？这个方案比前方案，但是否是最优？分析：分析：S=180+x2-（3/2）x4 非基变量非基变量x2系数仍为系数仍为正正数，确定数，确定x2为为进进基变量基变量。在保证常数项非负的情况下，在保证常数项非负的情况下，确定确定x3为为出基变量。出基变量。得到新的系统：得到新的系统：x1=20+（1/4）x3-（3/8）x4 x2=20-（1/2）x3+（1/

24、4）x4 (III)S =200-（1/2）x3-（5/4）x4 令新的非基变量（令新的非基变量（x x3 3,x,x4 4）t t=（0,00,0）t t得到新的基础可行解：得到新的基础可行解：x x(3)(3)=(20,20,0,0)=(20,20,0,0)t t S S3 3=200=200经济含义：分别生产甲乙产品经济含义：分别生产甲乙产品2020个，可个，可获得利润获得利润2000020000元。元。分析：分析：S =200-S =200-（1/21/2）x x3 3-（5/45/4）x x4 4 目标函数中的非基变量的系数无正数，目标函数中的非基变量的系数无正数，S S3 3=20

25、0=200 是最优值，是最优值，x x(3)(3)=(20,20,0,0)=(20,20,0,0)t t 是最优解。是最优解。该企业分别生产甲乙产品该企业分别生产甲乙产品2020个，可获得个，可获得最大利润最大利润2000020000元。元。利用单纯形表进行计算利用单纯形表进行计算从前面的单纯形法的计算过程可见，所有计算其实都归结为对标准形式的模型的系数的计算。因此可以通过将线性规划的系数矩阵及目标函数系数列成表格的方式进行计算。max z=3x1+2x2x1+2x2+x3 =52x1+x2 +x4 =44x1+3x2 +x5 =9x1,x2,x5 03 21 2 1 0 0 52 1 0 1

26、 0 44 3 0 0 1 93 2 0 0 0 单纯形表检验数l以x3,x4,x5作为初始基变量得到初始单纯形表初始单纯形表如下所示：32000CBXBx1x2x3x4x5b000 x3x4x5124213100010001549320000l该初始单纯形表对应的初始解为X=(0，0，5，4，9)T。对应目标函数值为0.l因为x1的检验数l我们选择x1作为换入变量换入变量。这样可以使目标函数增加得更快。l然后用b列的数除以换入变量列的正的系数，所得最小商对应的变量x4为换出变量。l以x3,x1,x5作为基变量得到第二张单纯形表按第二张单纯形表按如下方式计算：32000CBXBx1x2x3x4

27、x5b000 x3x4x5124213100010001549320000该元素称为主元。下面开始迭代，迭代的目标迭代的目标就是把主元化为1，然后把主元所在列其他系数化为0。x13321/201/210003/21-1/200010-21101/20-3/260该单纯形表对应的基可行解为X=（2，0，3，0，1）T，对应目标函数值为6。现在x2的检验数为1/20，且最大，所以我们选择x2为换入变量。因为min3/(3/2),2/(1/2),1/1=1,所以选择x5作为换出变量。l以x3,x1,x2作为基变量得到第三张单纯形表第三张单纯形表如下所示：32000CBXBx1x2x3x4x5b030

28、 x3x1x50103/21/21100-1/21/2-200132101/20-3/2062x2010-21100015/2-3/23/231003/2-1/23/2000-1/2-1/213/2 现在所有的检验数都小于或者等于0，所以得到最优解为：最优目标函数值为13/2。该表称为最终单纯形表，其具有什么特征？合并的单纯形表合并的单纯形表32000CBXBx1x2x3x4x5b000 x3x4x51242131000100015495/14/29/4320000030 x3x1x50103/21/21100-1/21/2-200132124101/20-3/206032x3x1x20100

29、011005/23/2-2-3/2-1/213/23/21000-1/2-1/213/2单纯形法计算过程单纯形法计算过程l构造初始单纯形表构造初始单纯形表 对标准化后的线性规划问题，首先找出初始基变量，构造初始单纯形表。相应地可以得到初始基可行解，基可行解的目标函数值。l最优性检验最优性检验 若得到单纯形表中所有的检验数都小于或等于零，则该单纯形表给出的基可行解就是最优解，终止计算。否则进行下一步。l确定换入变量确定换入变量 选择最大的正检验数对应的非基变量为换入变量。l确定换出变量确定换出变量 若换入变量（更一般地，若某个正检验数对应的变量）所作列的系数均小于或等于零，则线性规划问题为无界解

30、，终止计算。否则用换入变量所作列的系数去除b列的对应数，在除得的商中选择最小者对应的基变量为换出变量。l旋转运算旋转运算 确定换入和换出变量后得到新的基变量，然后以换入变量所在列、换出变量所在行交叉处的元素为主元，通过矩阵的初等行变换（一般不使用交换两行的运算）将约束方程组增广矩阵中主元变换为1，主元列的其它元素变换为零。从而得到一个新的单纯形表。然后回到第2步。唯一最优解与无穷多个最优解唯一最优解与无穷多个最优解l若最终单纯形表的非基变量的检验数都小于零,则线性规划问题有唯一的最优解l若最终单纯形表中存在某个非基变量,其检验数等于零,则该线性规划问题有无穷多个最优解.例2.4 利用单纯形法求

31、解下列线性规划问题首先将线性规划标准化很明显可以以x4、x5作为初始基变量，得到初始单纯形如下：-21200CBXBx1x2x3x4x5b00 x4x532-2-1-21100114-21200此时，x2的检验数大于0，还没有得到最优解。但是我们以x2作为换入变量，但是x2所在列所有系数都小于0，此时该线性规划存在无界解无界解。l课堂作业课堂作业:用单纯形法求解用单纯形法求解解：将数学模型化为标准形式：不难看出x4、x5可作为初始基变量，列单纯形表计算。单纯形法的计算步骤单纯形法的计算步骤cj12100icB基变量基变量bx1x2x3x4x50 x4152-32100 x5201/315011

32、21000 x42x220 x x2 22 21/3150120753017131/309022560 x x1 111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3单纯形法小结cj iCBXBbx1x2x3x4x5xm6bcd10 xn1-13e01 ja1-200 xsfg2-11/20 xt4hi11/21 j0-7jkl2、某求极大值、某求极大值LP问题的初始及经过一次迭代后的单纯形表，问题的初始及经过一次迭代后的单纯形表，表如下，表如下，x4、x5为松驰变量，试求表中为松驰变量，试求表中a-l及及m-t的值。的值。解（解（1）因为初始表中）因为

33、初始表中x x4 4、x x5 5为基变量，所以，为基变量，所以，m4；n5；（2）迭代后的表中，基变量为：）迭代后的表中，基变量为：x x1 1、x x5 5，因此：，因此：g1；h0；s1；t5；c cj ja a1 12 20 00 0 i iC CB BX XB Bb bx x1 1x x2 2x x3 3x x4 4x x5 50 0 x x4 46 6b bc cd d1 10 00 0 x x5 51 1-1-13 3e e0 01 1 j ja a1 1-2-20 00 0 x xs sf fg g2 2-1-11/21/20 0 x xt t4 4h hi i1 11/21/

34、21 1 j j0 0-7-7j jk kl l（3）x5为基变量，为基变量，l0；（4）p4由第一个表的由第一个表的1,0T变为第二个表中的变为第二个表中的1/2,1/2T，即即/2 ，因此，因此，f3；b2；c4；d2；c cj ja a1 12 20 00 0 i iC CB BX XB Bb bx x1 1x x2 2x x3 3x x4 4x x5 50 0 x x4 46 6b bc cd d1 10 00 0 x x5 51 1-1-13 3e e0 01 1 j ja a1 1-2-20 00 0a ax x1 1f f1 12 2-1-11/21/20 00 0 x x5 5

35、4 40 0i i1 11/21/21 1 j j0 0-7-7j jk kl l（5 5）同理，行）同理，行）同理，行）同理，行行行行行 行行行行 i i5 5；e e2 2；（6 6）2 2 1 12a2a-7-7，所以，所以，所以，所以，a a4 4；（7 7）j j2 2；k k-2-2；c cj ja a1 12 20 00 0 i iC CB BX XB Bb bx x1 1x x2 2x x3 3x x4 4x x5 50 0 x x4 46 62 24 42 21 10 00 0 x x5 51 1-1-13 3e e0 01 1 j ja a1 1-2-20 00 0a ax x1 13 31 12 2-1-11/21/20 00 0 x x5 54 40 0i i1 11/21/21 1 j j0 0-7-7j jk k0 0