最优下料问题的数学模型.pdf

1 最优下料问题的数学模型最优下料问题的数学模型 摘要摘要 本文通过对两个问题进行分析，分别建立模型一、模型二。针对模型一，设计程序 贪心算法，通过 Matlab 编程，得出相应结果。针对模型二，文中通过将二维问题转换 成为一维问题，引用规划模型，做出相应分析。 在在问题一中问题一中，为解决一维下料问题，根据一维下料问题的特点，建立起由其约束条 件组合而成的规划模型，在随机决策的基础上利用贪心算法取每个决策中的最优值，较 快地获得问题的最优解为： 前 6 天下料方案整和为一个方案比制定 4 天， 6 天方案更优， 且前 6 天需用原材料根数为 268，利用率为 99.21%，3 天完成；剩余下料方案为需用原 材料根数为 538，利用率为 98.92%，6 天完成。 （详见表表 6 6- -1 1 和附录表表 6 6- -2 2、表表 6 6- -3 3） 在问题二中在问题二中，基于零件长、宽两个方向上的限制的情况后，根据问题 2 中待加工的 零件的宽只集中在 50mm，30mm，35mm，20mm 四种规格上，将二维问题转化为一维问题， 分别用一维下料问题的方法寻求四种宽度条材在一维情况下的最优方案。在这一过程 中，可根据一维下料问题求解的方法，建立模型二，解多目标整数规划，再进行最优组 合，可以得到两个阶段所使用的条材。 关键关键词词： 贪心算法 最优下料 规划 2 一、问题的一、问题的重述重述 “下料问题(cutting stock problem)”是把相同形状的一些原材料分割加工成若干 个不同规格大小的零件的问题，此类问题在工程技术和工业生产中有着重要和广泛的应 用. 这里的“实用下料问题”则是在某企业的实际条件限制下的单一材料的下料问题。 现考虑单一原材料下料问题. 设这种原材料呈长方形，长度为L,宽度为W，现在 需要将一批这种长方形原料分割成m种规格的零件, 所有零件的厚度均与原材料一致， 但长度和宽度分别为),( ,),( 11mm wlwl，其中wimiWwLl ii , 1,. m种零件 的需求量分别为 m nn, 1 .下料时，零件的边必须分别和原材料的边平行。这类问题在 工程上通常简称为二维下料问题。特别当所有零件的宽度均与原材料相等，即 miWwi, 1,，则问题称为一维下料问题。 一个好的下料方案首先应该使原材料的利用率最大，从而减少损失，降低成本，提 高经济效益。其次要求所采用的不同的下料方式尽可能少，即希望用最少的下料方式来 完成任务。因为在生产中转换下料方式需要费用和时间，既提高成本，又降低效率。此 外，每种零件有各自的交货时间，每天下料的数量受到企业生产能力的限制。因此实用 下料问题的目标是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需 求任务, 同时下料方式数也尽量地小.请你们为某企业考虑下面两个问题。 1、建立一维单一原材料实用下料问题的数学模型, 并用此模型求解下列问题，制 定出在生产能力容许的条件下满足需求的下料方案, 同时求出等额完成任务所需的原 材料数，所采用的下料方式数和废料总长度.单一原材料的长度为 3000mm, 需要完成一 项有53种不同长度零件的下料任务. 具体数据见表一， 其中 i l为需求零件的长度， i n为 需求零件的数量. 此外，在每个切割点处由于锯缝所产生的损耗为5mm. 据估计，该企 业每天最大下料能力是100块 ，要求在4天内完成的零件标号(i)为: 5,7,9,12,15,18,20,25, 28,36,48; 要求不迟于6天完成的零件标号(i) 为:4,11,24,29,32,38,40,46,50. (提示：可分层建模。 (1).先考虑用材料既少,下料方式又少的模型, 或先仅考虑所用材料最少的模型及 增加一种下料方式大致相当于使原材料总损耗增加0.08%情况下的最佳方案。 3 (2).在解决具体问题时,先制定4天的下料方案,再制定6天的下料方案,最后制定53 种零件的下料方案. 这一提示对第2题也部分适用.) 2、 建立二维单一原材料实用下料问题的数学模型, 并用此模型求解下列问题.制定 出在企业生产能力容许的条件下满足需求的下料方案, 同时求出等额完成任务所需的 原材料块数和所需下料方式数.这个问题的单一原材料的长度为 3000mm,宽度为100mm, 需要完成一项有43种不同长度和宽度零件的下料任务. 具体数据见表二，其中 iii nwl, 分别为需求零件的长度、宽度和数量. 切割时的锯缝可以是直的也可以是弯的，切割 所引起的锯缝损耗忽略不计.据估计，该企业每天最大下料能力是20块 要求在4天内完 成的零件标号(i)为: 3,7,9,12,15, 18, 20, 25, 28, 36. 二、问题的二、问题的假设假设 （1）问题一中的零件厚度和宽度均与原材料相等； （2）问题二中的零件厚度均与原材料相等。 （3）切割过程中无人工误差 三、符号的说明三、符号的说明 3.1 问题一的符号说明 符号 说明 max k 等额完成任务所需的原材料数 k 原材料个数 i 零件标号 ki x 在第k个原材料上切割的第i个零件标号的零件数量 m 规格种数 i l 需求零件长度 L 单一原材料长度 ), 2 , 1(midi 需求零件数量 s 需下料的全部零件总长度 Q 下料方式数 * L 废料总长度 4 四、问题的分析四、问题的分析 对于问题一，为一维下料问题，考虑首要目标为使原材料利用率最大，然后再使下 料方式数尽可能少。建立起以原材料使用数量最少为目标函数的规划模型，易知该问题 为 NP 问题，故用一般的规划算法很难求解，在现有的算法中也没有一种算法可以求出 确定的最优解， 求解此类问题的算法有单目标或多目标模型, 遗传算法, 模拟退火法, 启 发式算法, 分支定界法等，本文利用贪心算法在随机决策方案的基本上采取择优原则， 经多次选取后可将需要量全部完成。 对于问题二，这是特殊的二维下料问题。很容易观察到：问题二中所有零件的长度 都大于原材料的宽度，零件的宽度只有 4 种，大于 80 的宽度组合大约 10 多种。因此由 上述度量知实际宽度组合会更少。这样解问题二的通常想法是将其转化成问题一的形 式，同时也可以得出与问题一相类似的理论模型。 五、五、模型的建立模型的建立与求解与求解 5.15.1 问题一问题一 5.1.15.1.1 模型一的建立模型一的建立与求解与求解 1 1、 模型一的建立模型一的建立 1） 约束条件 如题，设原材料呈长方形，长度为L，现在需要将一批这种长方形原料分割成m种 规格的零件, 所有零件的厚度和宽度均与原材料一致，第i种规格的零件的长度为 i l ， 需求量为), 2 , 1(mini个。 共耗用 max k个原材料，且在第k个原材料上切割的第i个零件标号的零件数量为 ki x， 则有： （1）原材料规格与锯缝损耗约束条件为： max 11 , 2 , 1,5kkLxxl m i ki m i kii 1 （2）需求量约束条件为： 5 max 1 , 2 , 1, k k iki minx 2 以及对 ki x的非负整数要求。 （3）下料方式约束条件为： max 11 5min k k ki m i xQ 3 （4）下料能力约束条件为： 每天的最大下料能力有：100 j K 4 2） 目标函数的建立 目标函数的建立是为求得 max k的最小值，因此建立如下： Zx midix kkLxl k ki k k ki m i kii max 1 1 max max , 2 , 1, , 2 , 1, min 3 其中，, 2 , 1 , 0 Z为非负整数的集合。 3） 求得所需原材料最小值 设 m i iin ls 1 ，表示需下料的全部零件总长度。进而定义： 其他 为整数 , 1)/int( /,/ * Ls LsLs k 4 则所需原材料的最小值为 * k，若由目标函数3 求得的结果 * max kk，则计算结果有误， 需要修正程序算法，或是重新建立模型。由式4 求得的最小值可避免犯一些明显的错 误，并且可对程序进行验证。 4）结果表示： 6 （1）等额完成任务所需的原材料数： max k （2）下料方式数：Q （3）废料总长度：sknlkL m i ii max 1 max * 30003000 （4）下料方案： 从上述模型可得出，下料方案为满足模型约束条件的最优解。 2 2、算法实现、算法实现随机决策下的贪婪算法随机决策下的贪婪算法 Step1Step1: : 对于给定需要完成的产品， 长度和需求量分别为 L 和 n， 构造一个 n 行 1 列矩阵 NL， 形如： M n M n n M L L L L L L NL 1 2 1 2 1 1 1 1 其中 iL 1 表示第 1 种材料的第 i 个排列， nL 1 中的n表示第一种材料 的总需求量。 Step2:Step2: 产生 100 个随机数组，每个随机数组包含 20 个数，随机数组j i R的取值范围为 )(1NLlength,其中 j i R表示第i个数组里面的第j个随机数的值。将每一组数组的值 i R对应到 Step1 构造的矩阵NL中的第 i R个数中,结果是产生 100 组策略， 每组策略有 20 个值。 Step3Step3： 将产生的 Step2 产生的 100 组策略装进 100 个队列中，对每个队列进行分流操作， 从第 1 组的第一个值开始累加到第一组的第 20 个数，累加过程中如果累加值超出 3000 7 的，该值不被采用，否则该值被分流进盒子，如果循环操作至第 100 组随机值，最后结 果将产生出 100 组随机策略组合，每组的累加值均满足小于 3000，即： 30005(, 30005,5 i jiii i ji j i ii i RSifSS RSifRSS S 100, 2 , 1i 20, 2 , 1j Step4Step4： 对 Step3 产生的 100 种满足条件的随机组合采取择优选择，即选择)max( i S，此为 一次贪心决策结果，将构成)max( i S的各长度值从NL矩阵中去掉，即将其值变为 0. Step5:Step5: 判断NL矩阵中的非零值个数，当0)(NLNoZeros时，即表示NL中的每个值都 已经被选出，否则继续 Step2Step5。 由以上 Step1Step5 结束后易知最终结果为各类型需求量均能被满足，此为最终 的解。 在实际操作中可能 Step2 中的 100 个随机数组中有些数组的 20 个随机值出现雷同数值， 亦即 k i j i RR，此时如果 i R所对应的 i S为)max( i S，那么该随机决策将是一种伪决策， 此行为将导致NL矩阵中的某一值被 i S累加了多次，为此，可以将 Step5 中的判断函数: 0)(NLNoZeros 改为 10 )( )( NLLength NLNoZeros 即NL中剩下 10 1 未被选择时即跳出，然后对剩下的 10 1 进行重组合，即将NL中等于 0 的数剔除，非零数值重新组合成新的NL,再继续运行 Step1Step5 即可尽量避免当 k i j i RR时， i R所对应的 i S为)max( i S的情况。 至此，利用 Matlab 编程可求出满足题目要求的方案，从方案中可以检测出 k i j i RR时， i R所对应的 i S为)max( i S的情况仅为四种，对四种方案人为处理后即可 得到最终结果。 易求出该算法的时间复杂度仅为)(TKnsumO， 其中)(nsum表示总需求量，K 表示随机决策的个数（本文中取 100） ，T表示每个随机决策中的队列长度（本文中取 8 20） 。此算法较之遗传算法等的优点是减少时间复杂度，可以在较短时间内求出满意解， 而空间复杂度基本相同，缺点是下料方案是随机性的，结果中有些下料方案可能只被执 行数次。 5.25.2 问题二问题二 5.2.1 模型二的建立模型二的建立 1 1、问题二模型的初步分析与建立问题二模型的初步分析与建立 问题二中的二维下料问题，由于零件长、宽两个方向上的限制，相比于一维下料问 题复杂得多。这一问题还要求集合 D 中的零件必须在第一阶段(前四天)完成，而企业每 天的下料能力是 20 块。基于这一条件，本文模型的目标是尽可能节省原材料，并采用 尽量少的下料方式。 k j j b 1 min，)(min 1 j k j b ， 0, 0 0, 1 )( j j j b b b 0;1 ;1 ;1 2 1 2 1 2 1 2 1 , 1;, 1;, 2 , 1, 2 1 2 1 , 1;, 1;, 2 , 1, 2 1 2 1 80 ;, 2 , 1, . . 21212121 1 1 21 212211212211 kkiiakakmii wwyyllxx atkjmiwLyw atkjmilLxl ba minba ts jiji iijkijkiiijkijki ijiijti ijiijti j k jDi ij i k j jij 或 ）（ 其中，k：全部可行下料方式数； ij a：表示第i号零件在第j种方式下切得的个数； j b：表示第j种下料方式耗材块数；D零件i|i=3,7，9,12,15,18,20,25,28,36， 即前 4 天须完成的零件集合； iii nwl,：第i号零件的长、宽、加工个数； ijkijk yx ,：第i号 零件在第j中下料方式下切得第k块零件中心的横坐标、纵坐标。 9 2 2、 模型的进一步分析模型的进一步分析 根据问题 2 的特点，待加工的零件的宽只集中在 50mm，30mm，35mm，20mm 四种规 格上，可将二维问题转化为一维问题，对四种宽度且长 3000mm 的条材，分别用一维下 料问题的方法寻求四种宽度条材在一维情况下的最优方案。 根据一维下料问题求解的方法，解多目标整数规划，可以得到两个阶段所使用的条 材。然后，将上述四种宽度的条材进行搭配，按仅有的无损失的方式列出。并进行优化 组合，即以原板材消耗块数最少为目标，建立整数规划模型，模型二： 54321 minmmmmm 354 20532 30432 5021 2 52 2 2 . . Mm Mmmm Mmmm Mmm ts 利用 matlab 编程可得到第一阶段最优解和第二阶段最优解。 六、六、模型的模型的实证与实证与评价评价 6.1 6.1 问题一模型一的实证分析问题一模型一的实证分析 根据模型一，结合贪婪算法，利用 matlab 编程得出结果，如表 6-1。 表 6-1 各方案对比结果表 项目 数量 计划一 计划二 前 4 天任务 5-6 天任务 前 6 天任务 剩余任务 零件总长度 444649 354361 799010 1599898 原材料个数 152 123 267 536 原材料最小值 149 119 267 534 下料方式数 42 45 70 206 废料总长度 11351 14639 10990 17102 完成天数 2 2 3 6 利用率 97.51% 96.03% 99.21% 9892% 10 从表 6-1 中，可知，采用计划二所使用的原材料数量要比采用计划一少 7 个，且利 用率也更优，总废料长度也更少。 另外，也可得出，根据完成天数的不同而选出的最佳方案，产生了两个最佳生产计 划，可供企业站在不同角度选择合适企业的生产计划进行生产。 计划一：计划一： 考虑到原材料的供给不足，尚不够完成前 6 天的任务；且公司资金需要周转，不打 算将大量资金投入到原材料的购进，使仓库囤积货物。 因此考虑在第 1、2 天完成四天的下料方案，第 3，4 天不生产，第 5，6 天完成 6 天剩下的下料方案；完成剩余的 53 种零件的下料方案。 计划二：计划二： 公司已经将 53 种零件需要的原材料全部购进；且公司仍有继续接到定单的打算， 因此需要尽早完成全部下料方案的生产。则先选择完成用 3 天时间完成前 6 天任务，再 完成剩余的 53 种零件的下料方案。 综合以上两方面的考虑，本文给出计划二的下料方案，详见附录表表 6 6- -2 2 和表表 6 6- -3 3 6.26.2 问题二模型二的实证分析问题二模型二的实证分析 略 11 参考文献参考文献 1 王 娟、温阳俊. 二维实用下料问题的数学模型及较优解. 数学的实践与认识.第 36 卷第 7 期 . 2 倪 勤. 实用下料问题的评注. 数学的实践与认识.第 35 卷第 7 期. 3 金咏怡.产品下料问题的一种求解方法. 湖南商学院学报. 第 10 卷第 1 期. 4 谷峰、韩润春、杨亚锋、王帅印. 一维实用下料问题的一种解法.河北理工大学学 报(自然科学版) 第 32 卷第 3 期 12 附录： 表表 6 6- -2 2 6 天下料方案 序号 下料数 1 1477 1477 3 2 1180 1477 290 1 3 882 1477 600 9 4 1105 1313 265 290 1 5 882 1477 290 290 14 6 1477 600 290 600 0 0 0 0 3 7 1313 882 732 0 0 0 0 0 1 8 882 882 1180 0 0 0 0 0 5 9 882 1030 1030 0 0 0 0 0 2 10 882 1477 290 328 0 0 0 0 2 11 882 0 290 882 0 0 0 0 3 12 290 1313 1105 265 0 0 0 0 1 13 882 290 690 1105 0 0 0 0 1 14 600 600 1477 290 0 0 0 0 2 15 882 0 434 732 0 0 0 0 1 16 665 1477 265 290 265 0 0 0 1 17 882 882 882 290 0 0 0 0 21 18 882 882 600 600 0 0 0 0 4 19 882 1232 265 600 0 0 0 0 4 20 882 745 882 434 0 0 0 0 1 21 1055 290 290 732 600 0 0 0 1 22 290 0 434 845 845 265 0 0 1 23 882 434 882 732 0 0 0 0 9 24 665 290 882 845 290 0 0 0 2 25 434 578 882 265 265 0 0 0 1 26 882 882 265 265 665 0 0 0 1 27 600 1030 290 290 745 0 0 0 1 28 1030 845 265 265 290 265 0 0 1 29 600 882 0 882 0 0 0 0 1 30 732 265 265 845 845 0 0 0 1 31 290 665 845 882 265 0 0 0 1 32 290 434 1030 600 600 0 0 0 1 33 882 290 290 882 600 0 0 0 2 34 290 745 745 882 290 0 0 0 1 35 434 434 882 578 0 0 0 0 1 36 600 882 600 600 290 0 0 0 1 37 434 1055 600 882 0 0 0 0 1 38 1313 0 0 0 0 0 0 0 1 39 882 434 265 265 265 0 578 0 1 40 845 882 665 578 0 0 0 0 1 13 41 882 600 600 882 0 0 0 0 5 42 265 882 265 600 665 265 0 0 1 43 882 290 600 290 600 290 0 0 1 44 434 265 265 882 265 290 290 0 1 45 265 265 265 290 882 732 265 0 1 46 290 665 290 845 882 0 0 0 11 47 578 265 1030 665 434 0 0 0 1 48 882 665 882 265 265 0 0 0 1 49 265 265 290 290 845 732 265 0 1 50 265 265 265 578 882 265 434 0 1 51 434 265 290 1105 265 600 0 0 1 52 600 290 600 600 882 0 0 0 28 53 265 265 882 732 290 265 0 0 1 54 434 845 290 290 265 845 0 0 5 55 434 845 265 882 265 265 0 0 1 56 600 265 665 290 290 578 265 0 1 57 290 290 290 1105 434 290 265 0 4 58 265 600 265 265 882 690 0 0 2 59 600 665 265 882 265 290 0 0 63 60 845 665 265 600 265 328 0 0 1 61 600 434 328 290 882 434 0 0 1 62 265 882 732 265 290 265 265 0 16 63 290 665 600 690 434 290 0 0 1 64 290 290 845 290 665 290 290 0 2 65 265 265 290 265 845 434 600 0 3 66 882 265 290 265 265 434 290 265 2 67 290 290 265 290 732 0 265 265 265 1 68 290 290 665 290 578 265 290 290 1 69 290 434 665 434 265 290 290 290 1 70 265 290 290 290 732 290 265 265 265 1 表 6-3 剩余下料方案 序号 下料数 1 1285 1680 0 0 0 0 0 0 0 0 12 2 1680 1046 255 0 0 0 0 0 0 0 2 3 830 1743 405 0 0 0 0 0 0 0 1 4 1680 975 313 0 0 0 0 0 0 0 1 5 1177 1532 275 0 0 0 0 0 0 0 7 6 588 630 1743 0 0 0 0 0 0 0 1 7 630 582 1743 0 0 0 0 0 0 0 1 8 1680 411 893 0 0 0 0 0 0 0 3 9 590 714 1680 0 0 0 0 0 0 0 1 14 10 1680 719 582 0 0 0 0 0 0 0 6 11 588 714 1680 0 0 0 0 0 0 0 2 12 1680 830 313 155 0 0 0 0 0 0 1 13 830 1680 275 184 0 0 0 0 0 0 1 14 588 633 1680 0 0 0 0 0 0 0 1 15 1680 630 590 0 0 0 0 0 0 0 1 16 313 795 1680 184 0 0 0 0 0 0 1 17 590 588 1680 0 0 0 0 0 0 0 3 18 1680 588 588 0 0 0 0 0 0 0 21 19 582 1680 588 0 0 0 0 0 0 0 3 20 766 1680 275 255 0 0 0 0 0 0 2 21 588 0 1680 0 0 0 0 0 0 0 2 22 1680 582 0 0 0 0 0 0 0 0 2 23 588 1743 184 275 184 0 0 0 0 0 1 24 1680 540 0 0 0 0 0 0 0 0 1 25 1680 275 719 275 0 0 0 0 0 0 1 26 275 588 1680 0 0 0 0 0 0 0 3 27 1680 582 275 0 0 0 0 0 0 0 1 28 411 1285 1285 0 0 0 0 0 0 0 2 29 633 1680 411 255 0 0 0 0 0 0 11 30 630 414 1680 255 0 0 0 0 0 0 1 31 255 633 1680 405 0 0 0 0 0 0 6 32 1680 630 255 411 0 0 0 0 0 0 1 33 1680 540 275 0 0 0 0 0 0 0 1 34 1680 540 255 0 0 0 0 0 0 0 1 35 455 588 1680 255 0 0 0 0 0 0 44 36 313 630 1680 275 0 0 0 0 0 0 2 37 420 588 275 1680 0 0 0 0 0 0 3 38 275 1680 590 414 0 0 0 0 0 0 1 39 411 590 1680 275 0 0 0 0 0 0 2 40 590 405 1680 255 0 0 0 0 0 0 1 41 415 588 1680 275 0 0 0 0 0 0 1 42 1680 0 0 0 0 0 0 0 0 0 3 43 411 588 1680 275 0 0 0 0 0 0 4 44 590 1680 405 275 0 0 0 0 0 0 3 45 275 405 1680 588 0 0 0 0 0 0 12 46 405 1680 255 582 0 0 0 0 0 0 1 47 1680 313 588 313 0 0 0 0 0 0 1 48 275 1680 588 313 0 0 0 0 0 0 7 49 588 275 1680 255 0 0 0 0 0 0 1 50 275 588 1680 275 0 0 0 0 0 0 1 51 255 275 1680 582 0 0 0 0 0 0 2 52 275 275 1680 0 0 0 0 0 0 0 1 15 53 588 275 1680 275 155 0 0 0 0 0 17 54 540 313 1680 255 184 0 0 0 0 0 1 55 1680 275 0 0 275 184 0 0 0 0 1 56 275 1680 275 0 275 0 0 0 0 0 2 57 1680 255 0 255 255 0 0 0 0 0 1 58 893 1532 275 275 0 0 0 0 0 0 1 59 1680 275 184 420 405 0 0 0 0 0 1 60 255 1680 488 275 275 0 0 0 0 0 4 61 313 1680 275 275 405 0 0 0 0 0 3 62 1680 255 255 255 255 0 0 0 0 0 1 63 1680 275 275 275 275 0 0 0 0 0 2 64 1532 405 766 275 0 0 0 0 0 0 2 65 1680 275 275 275 275 184 0 0 0 0 1 66 313 1532 405 719 0 0 0 0 0 0 1 67 255 588 588 1532 0 0 0 0 0 0 1 68 1532 582 590 275 0 0 0 0 0 0 33 69 588 1532 582 275 0 0 0 0 0 0 48 70 313 1532 540 590 0 0 0 0 0 0 1 71 313 588 540 1532 0 0 0 0 0 0 1 72 405 630 1532 405 0 0 0 0 0 0 1 73 630 313 184 313 1532 0 0 0 0 0 1 74 1532 275 255 633 275 0 0 0 0 0 2 75 1532 633 255 275 275 0 0 0 0 0 76 1532 588 184 415 255 0 0 0 0 0 2 77 313 313 1532 540 275 0 0 0 0 0 1 78 1532 405 313 405 313 0 0 0 0 0 1 79 405 184 313 275 1532 255 0 0 0 0 1 80 590 847 255 1285 0 0 0 0 0 0 1 81 1285 830 588 275 0 0 0 0 0 0 9 82 582 275 830 1285 0 0 0 0 0 0 1 83 830 1217 588 184 155 0 0 0 0 0 1 84 719 1217 588 455 0 0 0 0 0 0 1 85 588 582 1217 588 0 0 0 0 0 0 3 86 582 582 588 1217 0 0 0 0 0 0 1 87 313 1285 588 588 184 0 0 0 0 0 1 88 255 1285 590 255 588 0 0 0 0 0 9 89 1285 255 255 588 588 0 0 0 0 0 12 90 275 582 1285 275 540 0 0 0 0 0 1 91 1285 588 275 415 405 0 0 0 0 0 1 92 411 1285 588 275 405 0 0 0 0 0 2 93 590 1285 275 405 405 0 0 0 0 0 1 94 1285 405 588 405 275 0 0 0 0 0 1 95 1285 588 411 275 255 155 0 0 0 0 1 16 96 1285 405 255 255 582 184 0 0 0 0 1 97 255 255 582 1285 313 275 0 0 0 0 1 98 1285 275 405 275 540 184 0 0 0 0 1 99 255 255 830 588 1046 0 0 0 0 0 1 100 540 405 1217 255 275 275 0 0 0 0 1 101 588 582 588 184 1032 0 0 0 0 0 5 102 405 255 1217 405 275 405 0 0 0 0 1 103 1177 582 405 255 275 275 0 0 0 0 3 104 275 255 275 275 1285 255 184 155 0 0 1 105 275 1032 255 719 411 275 0 0 0 0 1 106 630 588 588 893 275 0 0 0 0 0 3 107 719 582 588 830 255 0 0 0 0 0 1 108 719 588 275 540 847 0 0 0 0 0 1 109 275 588 795 719 590 0 0 0 0 0 1 110 411 893 455 633 582 0 0 0 0 0 1 111 1046 405 582 255 275 405 0 0 0 0 1 112 588 313 630 830 588 0 0 0 0 0 1 113 405 255 414 1032 588 275 0 0 0 0 1 114 275 1032 411 405 588 255 0 0 0 0 1 115 590 588 405 540 847 0 0 0 0 0 1 116 588 313 975 255 255 582 0 0 0 0 1 117 588 830 540 588 405 0 0 0 0 0 1 118 830 540 411 588 582 0 0 0 0 0 1 119 795 588 411 588 590 0 0 0 0 0 1 120 588 415 588 795 588 0 0 0 0 0 1 121 588 588 795 411 588 0 0 0 0 0 1 122 795 582 588 405 590 0 0 0 0 0 1 123 719 630 582 588 455 0 0 0 0 0 1 124 582 590 590 630 582 0 0 0 0 0 1 125 588 588 633 582 582 0 0 0 0 0 2 126 540 630 582 582 630 0 0 0 0 0 1 127 588 588 588 588 588 0 0 0 0 0 2 128 275 830 275 411 588 590 0 0 0 0 2 129 830 275 588 275 588 411 0 0 0 0 2 130 405 588 830 275 588 275 0 0 0 0 2 131 830 582 275 275 588 405 0 0 0 0 1 132 588 405 588 313 795 275 0 0 0 0 1 133 633 630 588 588 255 275 0 0 0 0 2 134 590 275 630 588 255 630 0 0 0 0 1 135 847 540 184 588 275 275 255 0 0 0 2 136 313 633 590 255 590 588 0 0 0 0 1 137 588 405 405 719 582 255 0 0 0 0 1 138 313 588 588 590 255 630 0 0 0 0 1 17 139 588 588 275 633 275 588 0 0 0 0 2 140 588 184 405 588 588 590 0 0 0 0 2 141 588 255 588 275 275 795 184 0 0 0 1 142 588 313 590 588 275 588 0 0 0 0 1 143 540 582 588 411 255 588 0 0 0 0 3 144 847 582 455 275 255 275 275 0 0 0 1 145 588 275 275 184 405 405 830 0 0 0 1 146 313 405 275 275 275 590 830 0 0 0 1 147 405 582 405 405 588 582 0 0 0 0 1 148 582 588 588 590 275 155 184 0 0 0 1 149 184 582 588 184 588 582 255 0 0 0 2 150 255 590 588 588 411 275 0 0 0 0 1 151 275 588 255 588 405 0 588 0 0 0 1 152 255 582 313 719 582 255 255 0 0 0 1 153 275 275 719 582 582 255 275 0 0 0 1 154 714 588 275 275 275 255 582 0 0 0 1 155 184 588 633 588 411 405 155 0 0 0 1 156 275 830 275 275 275 255 588 184 0 0 2 157 582 255 630 405 582 255 255 0 0 0 1 158 275 255 590 588 590 255 411 0 0 0 1 159 275 588 411 588 590 255 255 0 0 0 1 160 588 255 415 275 588 588 255 0 0 0 2 161 255 275 588 414 588 588 255 0 0 0 2 162 588 588 275 411 255 588 255 0 0 0 1 163 405 255 590 588 588 255 275 0 0 0 2 164 255 588 588 582 275 420 255 0 0 0 2 165 275 582 420 255 588 582 255 0 0 0 1 166 275 275 582 582 405 590 255 0 0 0 9 167 582 405 582 588 255 275 275 0 0 0 5 168 588 588 313 275 275 582 313 0 0 0 1 169 588 588 313 540 405 255 275 0 0 0 6 170 540 313 582 411 588 275 255 0 0 0 2 171 588 405 405 405 630 255 275 0 0 0 2 172 405 405 275 411 582 255 630 0 0 0 1 173 588 411 455 255 411 588 255 0 0 0 1 174 275 588 630 255 184 255 588 184 0 0 1 175 411 414 411 588 275 590 275 0 0 0 1 176 275 411 582 405 275 588 420 0 0 0 1 177 405 405 275 275 405 588 588 0 0 0 1 178 275 590 184 255 590 588 184 275 0 0 1 179 275 184 184 275 590 588 275 588 0 0 1 180 184 184 588 275 588 275 588 275 0 0 3 181 184 275 411 540 184 588 588 184 0 0 1 18 182 275 155 588 255 588 588 255 255 0 0 1 183 275 275 275 719 275 582 275 275 0 0 1 184 588 255 630 405 255 255 255 313 0 0 1 185 588 275 405 630 255 255 275 275 0 0 2 186 405 275 275 633 582 255 275 255 0 0 1 187 588 588 275 405 255 405 255 184 0 0 1 188 255 255 588 275 275 590 313 405 0 0 5 189 405 275 275 588 313 255 588 255 0 0 1 190 275 590 414 582 313 255 255 275 0 0 1 191 588 275 275 275 405 590 275 275 0 0 6 192 582 415 313 255 275 588 275 255 0 0 1 193 275 275 414 588 582 313 255 255 0 0 1 194 275 588 588 275 275 275 275 405 0 0 1 195 588 275 411 275 275 582 275 275 0 0 1 196 275 582 540 405 313 405 255 184 0 0 1 197 455 275 255 313 590 255 405 411 0 0 1 198 411 275 588 405 455 275 275 275 0 0 1 199 275 275 411 275 275 582 411 455 0 0 1 200 275 275 590 184 275 255 590 255 255 0 1 201 588 275 588 275 184 275 255 255 255 0 1 202 540 582 275 184 255 275 313 275 255 0 1 203 255 588 255 255 540 275 255 275 255 0 1 204 255 588 2