第8章_整数规划(带答案)

1、12第八章第八章 整数规划整数规划 1 整数规划的图解法整数规划的图解法 2 整数规划的计算机求解整数规划的计算机求解 3 整数规划的应用整数规划的应用 4 整数规划的分枝定界法整数规划的分枝定界法3整数规划整数规划是一类要求变量取整数值的数学规划，是一类要求变量取整数值的数学规划，可分成可分成线性线性和和非线性非线性两类。两类。求整数解的线性规划问题，求整数解的线性规划问题，应注意：应注意：不是不是用四舍五入法用四舍五入法和和去尾法对线性规划的非去尾法对线性规划的非整数解加以处理就能解决的。整数解加以处理就能解决的。整数线性规划整数线性规划一些基本算法的设计是一些基本算法的设计是以相应以相应

2、线性规划的最优解为出发点线性规划的最优解为出发点而发展出来的。而发展出来的。根据变量的取值情况，整数线性规划又可以分根据变量的取值情况，整数线性规划又可以分为为纯整数规划纯整数规划（所有变量取（所有变量取非负非负整数），整数），混合混合整数规划整数规划（部分变量取（部分变量取非负非负整数），整数），0-1整数规整数规划划（变量只取（变量只取0或或1）等。）等。第八章第八章 整数规划整数规划4整数规划是数学规划中一个较弱的分支，目前整数规划是数学规划中一个较弱的分支，目前有成熟的方法解有成熟的方法解线性整数规划问题线性整数规划问题，而非线性，而非线性整数规划问题，还没有好的办法。整数规划问题，还

3、没有好的办法。整整数线性规划数线性规划(Integer Linear Programming，简记为简记为ILP)问题研究的是要求变量取整数值时，问题研究的是要求变量取整数值时，在一组线性约束条件下一个线性函数最优问题，在一组线性约束条件下一个线性函数最优问题，是应用非常广泛的运筹学的一个重要分支。是应用非常广泛的运筹学的一个重要分支。 第八章第八章 整数规划整数规划51 1 整数规划的图解法整数规划的图解法例例1. 某公司拟用集装箱托运甲、乙两种货物，某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。托运

4、所受限制如表所示。甲种货物至多托运甲种货物至多托运4件件，问两种货物各托运多，问两种货物各托运多少件，可使获得的利润最大。少件，可使获得的利润最大。货物货物每件体积每件体积(立方米立方米)每件重量每件重量(百千克百千克)每件利润每件利润（百元）（百元）甲甲乙乙19527344023托运限制托运限制1365140 6货物货物每件体积每件体积(立方米立方米)每件重量每件重量(百千克百千克)每件利润每件利润（百元）（百元）甲甲乙乙19527344023托运限制托运限制1365140 解：设解：设x1 、 x2分别为甲、乙两种货物托运的件数，建分别为甲、乙两种货物托运的件数，建立模型。立模型。 目标函

5、数：目标函数： Max z = 2x1 +3x2 约束条件：约束条件：s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 4 x1，x2 0, 为整数为整数。如果去掉最后一个约束，就是一个线性规划问题如果去掉最后一个约束，就是一个线性规划问题.1 1 整数规划的图解法整数规划的图解法7利用图解法，得到线性规划的最优解为利用图解法，得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为目标函数值为14.66。由图表可看出由图表可看出, 整数规划的最优解（黄色叉号）为整数规划的最优解（黄色叉号）为x1=4, x2=2,目标函数值为目标函数值为1

6、4。Max z = 2x1 +3x2195x1+273x2=13654 x1+40 x2 =1404231123x2x11 1 整数规划的图解法整数规划的图解法Max z = 2x1 +3x2 约束条件：约束条件：s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 48由于相应的由于相应的线性规划的可行域包含线性规划的可行域包含了其了其整整数规划的可行点数规划的可行点，则对于整数规划，易知，则对于整数规划，易知有以下性质：有以下性质：性质性质1：任何求最大目标函数值的纯整数规：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值划或混合整数规划

7、的最大目标函数值小于小于或等于或等于相应的线性规划的最大目标函数值；相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值合整数规划的最小目标函数值大于或等于大于或等于相应的线性规划的最小目标函数值。相应的线性规划的最小目标函数值。1 1 整数规划的图解法整数规划的图解法9例例2： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x1, x2, x3 0 , 均为整数均为整数用管理运筹学软件用管理运筹学软件求解得：求解得：

8、x1 = 5 x2 = 2 x3 = 2 2 2 整数规划的计算机求解整数规划的计算机求解纯整数规划问题纯整数规划问题1011例例3： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 - 3x2 + 2x3 3 x3 1 x1, x2, x3 0 x1，x3 为整数，为整数，x3 为为0-1变量变量用用管理运筹学管理运筹学软件求软件求解得解得: z = 16.25x1 = 4 x2 = 1.25 x3 = 1 123 3 整数规划的应用整数规划的应用应用实例：应用实例： 投资投资场所的选择问题场所的选择问题 背包问题背包问题

9、 固定成本固定成本问题问题 指派指派问题问题 分布系统设计分布系统设计 投资投资问题问题13143 3 整数规划的应用整数规划的应用 一、投资场所的选择一、投资场所的选择 例例4、京成畜产品公司计划在市区的东、西、南、北四区、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有建立销售门市部，拟议中有10个位置个位置 Aj (j=1,2,3,10)可供选可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定择，考虑到各地区居民的消费水平及居民居住密集度，规定: 在东区由在东区由A1 ， A2 ，A3 三个点三个点至多至多选择选择两个两个； 在西区由在西区由A4 ， A5 两

10、个点中两个点中至少至少选选一个一个； 在南区由在南区由A6 ， A7 两个点中两个点中至少至少选选一个一个； 在北区由在北区由A8 ， A9 ， A10 三个点中三个点中至少至少选选两个两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示预测情况见表所示 (单位：万元单位：万元)。但投资总额。但投资总额不能超过不能超过720万万元，问应选择哪几个销售点，可使年利润为最大元，问应选择哪几个销售点，可使年利润为最大?解：设：解：设：0-1变量变量 xi = 1 (Ai 点被点被选用选用)或或 0 (Ai 点点没被

11、选用没被选用)。 这样我们可建立如下的数学模型：这样我们可建立如下的数学模型：Max z=36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10s.t. 100 x1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xi 0 且且xi 为为0-1变量变量，i = 1, 2, 3, ,10在东区由在东区由A1 ， A2 ，A3 三个点三个点至多至多选择选择两个两个

12、；在西区由在西区由A4 ， A5 两个点中两个点中至少至少选选一个一个；在南区由在南区由A6 ， A7 两个点中两个点中至少至少选选一个一个；在北区由在北区由A8 ， A9 ， A10 三个点中三个点中至少至少选选两个两个补充例、解决某市消防站的布点问题，该城市有补充例、解决某市消防站的布点问题，该城市有6个个区，每个区都可以建消防站。市政府希望设置的消区，每个区都可以建消防站。市政府希望设置的消防站最少，但必须满足在城市的任何地区发生火警防站最少，但必须满足在城市的任何地区发生火警时，消防车时，消防车要在要在15分钟内分钟内赶到现场。据实地测定，赶到现场。据实地测定，各区之间消防车行驶的时间

13、如下表所示，请帮助该各区之间消防车行驶的时间如下表所示，请帮助该市制定一个最省的计划。市制定一个最省的计划。 1 2 3 4 5 61 0 10 16 28 27 202 10 0 24 32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 0 设设 xi =1,0; 1i 区建消防站，区建消防站，0i 区不建消区不建消防站，防站，i=1,6min z = x1 + x2 + x3 + x4 + x5 + x6约束方程保证每个地区都有一个消防站在约束方程保证每个地区都有一个消防站在15分钟行

14、程内。分钟行程内。将将6个地区的条件分别列出：个地区的条件分别列出：s.t. x1 + x2 1, x1 + x2 + x6 1 x3 + x4 1, x3 + x4 + x5 1 x4 + x5 + x6 1, x2 + x5 + x6 1 xi = 0, 1; i=1,6 1 2 3 4 5 61 0 10 16 28 27 202 10 0 24 32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 018 1 2 3 4 5 61 0 10 16 28 27 202 10 0 24

15、32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 0第第2个地区建一个（地区个地区建一个（地区1、2、6都解决了）都解决了）第第4个地区建一个（地区个地区建一个（地区3、4、5都解决了）都解决了）二、二、背包问题背包问题（补充）（补充）背包可装入背包可装入8单位重量，单位重量，10单位体积物品。若单位体积物品。若背包中背包中每件物品至多只能装一个每件物品至多只能装一个，怎样才能使背包，怎样才能使背包装的物品价值最高。装的物品价值最高。物品物品 名称名称 重量重量 体积体积 价值价值 1

16、书书 5 2 20 2 摄像机摄像机 3 1 30 3 枕头枕头 1 4 10 4 休闲食品休闲食品 2 3 18 5 衣服衣服 4 5 15 解：解：xi为是否带第为是否带第 i 种物品种物品Max Z=20 x1 + 30 x2 +10 x3+18x4 +15x55x1+3x2 +x3 +2x4 +4x5 82x1+x2 +4x3 +3x4 +5x5 10 xi为为0, 1物品物品 名称名称 重量重量 体积体积 价值价值 1 书书 5 2 20 2 摄像机摄像机 3 1 30 3 枕头枕头 1 4 10 4 休闲食品休闲食品 2 3 18 5 衣服衣服 4 5 15 一般形式：一般形式：0

17、max11iniiiniiixbxaxCZ, 整数整数 xi为是否携带第为是否携带第i 种物品种物品ai为为i 物品单位重量，物品单位重量，b为最大负重为最大负重ci为为i 物品重要性估价物品重要性估价223 3 整数规划的应用整数规划的应用三、固定成本问题三、固定成本问题 例例5高压容器公司制造小、中、大三种尺寸的金属高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的用，每种容器售出一只

18、所得的利润分别为利润分别为 4万元、万元、5万元、万元、6万元万元，可使用的金属板有，可使用的金属板有500吨，劳动力有吨，劳动力有300人人/月，机月，机器有器有100台台/月，此外不管每种容器制造的数量是多少，都月，此外不管每种容器制造的数量是多少，都要支付一笔要支付一笔固定的费用：小号是固定的费用：小号是l00万元，中号为万元，中号为 150 万万元，大号为元，大号为200万元。万元。现在要制定一个生产计划，使获得现在要制定一个生产计划，使获得的利润为最大。的利润为最大。23解：这是一个整数规划的问题。解：这是一个整数规划的问题。 设设x1，x2， x3 分别为小号容器、中号容器和大分别

19、为小号容器、中号容器和大号容器的生产数量。号容器的生产数量。各种容器的固定费用只有在各种容器的固定费用只有在生产该种容器时才投入，若不生产则没有这部分生产该种容器时才投入，若不生产则没有这部分费用，费用，为了说明固定费用的这种性质，为了说明固定费用的这种性质，设设 yi = 1(当当生产第生产第 i种容器种容器, 即即 xi 0 时时) 或或0（当不生产第（当不生产第 i种种容器即容器即 xi = 0 时）。时）。 引入约束引入约束 xi M yi ，i =1，2，3，M充分大，充分大，以保证当以保证当 yi = 0 时，时，xi = 0 。 3 3 整数规划的应用整数规划的应用即：不投入固即

20、：不投入固定费用，是不定费用，是不能投入生产的能投入生产的24这样我们可建立如下的数学模型：这样我们可建立如下的数学模型：Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大充分大 xj 0 yj 为为0-1变量变量，i = 1,2,33 3 整数规划的应用整数规划的应用没有固定投入，就不生产没有固定投入，就不生产.yi =0，则，则xi=0. xi是数量，是数量，M为一个充分大的数

21、。为一个充分大的数。一个容器至少需要一个容器至少需要2个劳动个劳动力，共有力，共有300个劳动力，因个劳动力，因此容器数量不会超过此容器数量不会超过150.因因此当此当yi =1时，时，M可取可取150投入固定费用，投入固定费用，生产小号容器生产小号容器y1y2y325三、指派问题三、指派问题 有有 n n 项不同的任务，恰好项不同的任务，恰好 n n 个人可分个人可分别承担这些任务，但由于每人特长不同，完别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必成各项任务的效率等情况也不同。现假设必须指派须指派每个人去完成一项任务每个人去完成一项任务，怎样把，怎样把 n n

22、 项任务指派给项任务指派给n n个人，使得完成个人，使得完成 n n 项任务的项任务的总的效率最高总的效率最高，这就是，这就是指派问题。指派问题。 3 3 整数规划的应用整数规划的应用26例例6 6有四个工人，要分别指派他们完成四项有四个工人，要分别指派他们完成四项不同的工作，不同的工作，每人做各项工作所消耗的时间每人做各项工作所消耗的时间如下表所示如下表所示，问应如何指派工作，才能使，问应如何指派工作，才能使总总的消耗时间为最少的消耗时间为最少。3 3 整数规划的应用整数规划的应用27解：引入解：引入01变量变量 xij，并令并令 xij =1(当指派第当指派第 i人去完成第人去完成第j项工

23、作时项工作时)或或0(当不指当不指派第派第i人去完成第人去完成第j项工作时项工作时)这可以表示为一个这可以表示为一个0-1整数规划问题：整数规划问题：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x443 3 整数规划的应用整数规划的应用28整数规划模型为：整数规划模型为：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21

24、x42+23x43+17x44s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干工作

25、只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干工作只能一人干) xij 为为0-1变量变量，i,j = 1,2,3,43 3 整数规划的应用整数规划的应用每人只每人只能干一能干一项工作项工作一项工一项工作只能作只能由一个由一个人干人干 对于有对于有m个人完成个人完成n项任务的一般指派问题，项任务的一般指派问题，设：设：29变量为1-0,.,2, 1, 1,.,2, 1, 1min1111ijmiijnjijminjijijxnjxmixxCZm不一定等于不一定等于n，当当mn时，有的时，有的人没有任务。人没有任务。第第i个人完成的任务个人完成的任务且最多承担一项

26、且最多承担一项第第j项工作正好有一项工作正好有一人承担人承担注意：当注意：当m0 yi=0时，当不利用第时，当不利用第i种设备生产时，此时相应种设备生产时，此时相应的的Xi=0 目标函数为：目标函数为： Min Z=7x1+2x2+5x3+100y1+300y2+200y358 (1) 约束条件约束条件 X1 800，X2 1200，X3 1400， X1+X2+X3=2000(改大于等于结果相同改大于等于结果相同) 0.5X1+1.8X2+1.0X3 2000 还得保证还得保证Yi=0时，时，Xi=0.(没有准备费就不启没有准备费就不启用该设备用该设备)，引入一个很大的，引入一个很大的M X

27、i M Yi（i=1,2,3） Xi 0,（i=1,2,3） Yi（i=1,2,3）是）是0-1变量变量59 （2）约束条件改为 0.5X1+1.8X2+1.0X3 250060 （3）约束条件改为 0.5X1+1.8X2+1.0X3 280061 （4）去掉电量的约束条件62第第5题题635：二二50080070064yi是是0-1变量，变量， yi=0，相当于该，相当于该库房不存在库房不存在需求量需求量上海上海y2，武汉，武汉y40,10,01,1最多最多2个库房个库房武汉和广州不能同时建武汉和广州不能同时建i=1,2,3,4北京北京上海上海广州广州武汉武汉华北华北华中华中华南华南2第第6

28、题：指派问题题：指派问题（1）引入引入01变量变量 xij，并令并令 xij =1(当指派第当指派第i人去完成第人去完成第j项工作时项工作时) 0(当不指派第当不指派第i人去完成第人去完成第j项工作时项工作时)目标函数 Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+18x21+ 24x22+ 27x23+ 20 x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20 x42+ 24x43+ 19x4465 x11+ x12+ x13+ x14= 1 (甲只能干一项工作甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能

29、干一项工作乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干工作只能一人干)66 （2）把目标函数改为求最大值即可，即：）把目标函数改为求最大值即可，即：M

30、ax Z= 20 x11+ 19x12+ 20 x13+ 28x14+18x21+ 24x22+ 27x23+ 20 x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20 x42+ 24x43+ 19x44约束条件不变约束条件不变67 （3）增加了一项工作增加了一项工作E，问应指派，问应指派四个人干四个人干哪四项工作哪四项工作，共有五项工作，则结果中肯定，共有五项工作，则结果中肯定有一项工作无人做。有一项工作无人做。 mn，人数少于任务数。此时，添加虚拟，人数少于任务数。此时，添加虚拟人数人数n-m=1个，该人是虚拟的，因此完成各个，该人是虚拟的，因此完成各项工

31、作所需的时间都设为项工作所需的时间都设为0.此时变为此时变为5个人个人完成完成5项工作的问题了。项工作的问题了。Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+17x15 + 18x21+24x22+27x23+ 20 x24+ 20 x25+ 26x31+16x32+15x33+ 18x34+ 15x35+ 17x41+ 20 x42+ 24x43+ 19x44 +16x45 + 0 x51+ 0 x52+ 0 x53+ 0 x54 +0 x5568甲乙丙甲乙丙丁每个丁每个人做第人做第5项工作项工作的时间的时间 约束条件 x11+ x12+ x13+ x14 + x1

32、5 = 1 x21+ x22+ x23+ x24 + x25 = 1 x31+ x32+ x33+ x34 + x35 = 1 x41+ x42+ x43+ x44 + x45 = 1 x51+ x52+ x53+ x54 + x55 = 1 x11+ x21+ x31+ x41 + x51 =1 x12+ x22+ x32+ x42 + x52 =1 x13+ x23+ x33+ x43 + x53 = 1 x14+ x24+ x34+ x44 + x54 = 1 x15+ x25+ x35+ x45 + x55 = 169结果中安排第结果中安排第5个虚拟人去个虚拟人去做哪项工作，做哪项工作

33、，表明实际中该表明实际中该项工作无人做项工作无人做70方法二：方法二：x11+ x12+ x13+ x14 + x15 = 1 (甲只能干一项工作甲只能干一项工作) x21+ x22+ x23+ x24 + x25 = 1 (乙只能干一项工作乙只能干一项工作)x31+ x32+ x33+ x34 + x35 = 1 (丙只能干一项工作丙只能干一项工作)x41+ x42+ x43+ x44 + x45 = 1 (丁只能干一项工作丁只能干一项工作)x11+ x21+ x31+ x41 1 ( A工作工作)x12+ x22+ x32+ x42 1 ( B工作工作)x13+ x23+ x33+ x43

34、 1 ( C工作工作)x14+ x24+ x34+ x44 1 ( D工作工作)x15+ x25+ x35+ x45 1 ( E工作工作)Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+17x15 + 18x21+24x22+27x23+ 20 x24+ 20 x25+ 26x31+16x32+15x33+ 18x34+ 15x35+ 17x41+ 20 x42+ 24x43+ 19x44 +16x45 用用普通线性规普通线性规划模块划模块求解求解 （4）增加了一个人，问应指派哪四个人去）增加了一个人，问应指派哪四个人去干这四项工作，肯定有一个人没有工作做。干这四项工作

35、，肯定有一个人没有工作做。目标函数目标函数 Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+ 18x21+ 24x22+ 27x23+ 20 x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20 x42+ 24x43+ 19x44 + 16x51+ 17x52+ 20 x53+ 21x5471 方法一：虚设一个工作，每个人完成此项工方法一：虚设一个工作，每个人完成此项工作的时间设为作的时间设为0.72x11+ x12+ x13+ x14 + x15 = 1 x21+ x22+ x23+ x24 + x25 = 1x31+ x32+ x33

36、+ x34 + x35 = 1x41+ x42+ x43+ x44 + x45 = 1x51+ x52+ x53+ x54 + x55 = 1x11+ x21+ x31+ x41 + x51 =1x12+ x22+ x32+ x42 + x52 =1x13+ x23+ x33+ x43 + x53 = 1x14+ x24+ x34+ x44 + x54 = 1x15+ x25+ x35+ x45 + x55 = 1Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+0 x15 + 18x21+24x22+27x23+ 20 x24+ 0 x25+ 26x31+16x32+15x33+ 18x34+ 0 x35+ 17x41+ 20 x42+ 24x43+ 19x44 +0 x45 + 16x51+ 17x52+20 x53+ 21x54 +0 x5