“新秀杯”数学建模竞赛论文封面及格式要求1.doc

地板铺设的最佳方案研究与设计摘要 人们为了尽量美化自己的房间，绞尽脑汁的想出许多铺地砖的方案。而铺地砖也是数学建模中的经典案例，但数学建模更关心的是如何铺设更合理更盈利，如何能浪费最少的原材料。本文通过matlab图像读取处理，把可视的图形转换成矩阵对其进行操作和研究。继而应用了带有预放置矩形块的布局问题模型和贪心循环算法通过计算机对问题进行处理。在模型中套用循环枚举的方法，能够较全面地捕捉到每铺设一块砖时的最优位置，当循环结束时，便得到了目标方案。 首先，把题目中给出的无具体数据的房间布局图片数据化，从而给出房间的长、宽与中间花形图案的各个尺寸规格。对中间花形进行填充处理，并把构成实心花形图案的每一个像素点等效看作一个预放置矩形，那么将要铺设的地板就可以看做若干个自由矩形。然后运用带有预放置矩形块的布局问题模型、贪心算法和回溯算法对本问题进行分析:对其中一定格局下的矩形作占角、穴度的计算分析；挑出穴度最大的合法占角动作。在新的格局下对模型重复以上分析计算，继而通过设定优化条件和目标函数把问题转化为优化问题，运用Matlab数学软件对带有预放置矩形块的布局问题和优化问题进行求解。显然，求解出的结果一定比所假定的基准块数要多。比较两种规格地砖的利用率和总价格，据此选择最优方案。 关键字：预放置矩形 贪心算法 回溯算法 穴度 合法占角动作1、 问题重述随着生活水平的提高，房屋装潢已是入住新居前必要环节。而对装潢材料正确地选材与购买是为房主节约花费与减少浪费的重要手段。现一装修公司正准备对一房间（具体数据图见附录一）铺设地板，可供使用的两种地板的规格分别为地板一：808mm，130mm价格为每平米120元、地板二：长宽均为600mm，价格为每平米75元；在地面上的花朵形状区域已铺设好的前提下，利用这两种规格的地板材料之一铺设花朵以外、矩形以内区域，综合美观等因素，建立数学模型，设计出购材和铺设方案，使达到对地板原料的浪费最少。 二、问题的分析本文分别对铺设这两种地板之一的不同情况下，研究同种规格矩形形状的地板在给定区域内放置位置的选择问题。联系实际，地板的铺设主要考虑的因素包括整齐美观、材料的优质、缩减费用、减少浪费等因素。为满足本题的方案要求，主要以对原材料浪费最少为目标，确定出每种地板的最佳铺设方案，进而通过综合比较选出更加符合条件的地板。在对每种地板的铺设方案进行考虑时，主要考虑对原材料浪费最少的因素。在浪费最少的的基础之上按先后顺序考虑总费用、整齐美观的因素，给出供选用的多种参考方案。并考虑以浪费最少为主要目标的情况下建立最优化模型。首先，把题目中给出的地面图片数据化，对像素点和矩形形状的地板进行抽象处理。对中间花形进行填充处理，并把构成实心花形图案的每一个像素点等效看作一个预放置矩形。将要铺设的地板就可以看做若干个自由矩形。然后运用带有预放置矩形块的布局问题模型、贪心算法和回溯算法对本问题进行分析，继而通过设定优化条件和目标函数把问题转化为优化问题，运用Matlab数学软件对带有预放置矩形块的布局问题和优化问题进行求解。在比较分别有两种地板铺设的最优化方案时，主要考虑浪费最少的因素，其次还要综合它们的费用、美观等因素，而后根据每种方案的优缺点提出最优化的参考方案。应用带有预放置矩形块的布局问题模型能够全面地找到在地板随机组合时出现的最优解，对于像题目中这样的矩形随即分配的实际问题具有重要意义。3、 模型的假设1 假设每块地板都是严格相同的；2 假设地板之间是不可重叠，并且不留缝隙的；3 假设地板是以块为单位出售的；4 假设截下来的费料没有任何利用价值；5 假设浪费最少指的是被截下的废料总面积最小，并且被截的面积尽可能集中 在少数的矩形上；6 所有数据均取自图形处理，真实可靠。四、 名词解释与符号说明1、布局区域：对于一个事先给定的矩形ABCD，以其左下角定点A为坐标原点，水平向右为x轴正向，竖直向上为y轴正向建立直角坐标系。矩形框ABCD所围成的区域称为布局区域。2、 预放置矩形：事先在布局区域内部放置的互不重叠而且位置固定的矩形。3、自由矩形：在布局区域内部放置好预放置矩形后欲放入的矩形。更形式的描述如下：假设S=是n+p个矩形块的集合。其中是自由矩形块，是预放置矩形块。4、S的一个合法布局：指在所有预放置矩形块按指定的方位放置好以后, 确定每一个自由矩形块在布局区域内的位置( 左下角) 和方向( 水平或垂直), 使得任何两个不同矩形块之间都互不重叠。5、 占角：在这里引用围棋中术语，在围棋中，一方把棋子下在棋盘任意一角的星位或星位附近如小目位置，叫做占角，而另一方把棋子下于第一方占角棋子的附近的一着，叫做挂角。实际上占角和挂角就是对角的争夺。6、 格局：一个第k 个格局是指对于n + p 个矩形块, 若在某个时刻其中有k ( pk n + p )个矩形块已被放进矩形框内所得到的平面上的一个有序对。其中: R 是四个边框矩形块(即构成矩形框边界的四个特殊矩形块) 和k 个已被放入矩形框内的矩形块( 包括p 个预放置矩形块)组成的集合； N 是尚未被放入矩形框内的n+ p- k 个自由矩形块组成的集合。当k=p时，称为初始格局；k=n+p-k时，称为终止格局。正在处理的第k个格局称为当前格局。7、 固定矩形块：称四个边框矩形块和k 个已被放入矩形框内的不再移动的矩形块为固定矩形块。8、 占角动作：在当前格局下, 如果某个自由矩形块M 占据了当前格局中的某一个角, 并且该矩形块的两边与形成此角的两个固定矩形块的两边重叠长度均大于0, 则称自由矩形块M 做了一个占角动作。如图一中，如果矩形块M放在位置2和3则相应的放置动作占角动作。9、合法与非法占角动作：若自由矩形块M 做了一个占角动作, 并且该矩形块与格局中的其他任一固定矩形块都互不重叠, 则称自由矩形块M做了一个合法的占角动作; 否则称M 做了一个非法的占角动作。如图一中，在图1中, 自由矩形块M 若被放置在位置1-4, 则M做了一个合法占角动作; 若被垂直地放置在位置5, 则M 做了一个非法占角动作。10、 穴度：在当前格局下, 称为自由矩形块 做了一个合法占角动作后的穴度。其中: 、 分别为 的宽和高, 为与所有已放定的固定矩形块( 除构成角两边的矩形块外)之间的最小欧氏距离。一个合法占角动作的穴度不会大于1, 若某个矩形块占了一个穴( 即该矩形块不仅做了一个合法占角动作, 而且接触到除构成角两边的固定矩形块之外的其他固定矩形块) , 则相应的占角动作的穴度正好等于1。如图1 中, 若矩形块M 被放置在位置4, 则M 占了一个穴。11、最大穴度优先的放置策略是: 在第k 个格局下, 对于每一个自由矩形块, 首先枚举所有的合法占角动作, 并计算每个合法占角动作的穴度, 然后选择穴度最大的那个合法占角动作,将相应的矩形块置入矩形框内, 直到所有自由矩形块全部置入矩形框内, 或自由矩形块的个数不为零但没有做合法占角动作为止。如多个合法占角动作具有相同的最大穴度, 那么就按照下面的优先次序确定一个合法占角动作: 选择所占角坐标最小的合法占角动作, 即先比较所占角的x 坐标, 再比较y 坐标, 谁小谁优先被占用。这样做的目的是在穴度一样大的情况下, 使得待放置的矩形块尽量向左下方靠拢, 使之放得更紧凑些。12、 价值度：在当前格局下, 自由矩形块M 做了一个合法占角动作P, 得到一个新的格局,然后按最大穴度优先的放置策略依次置入剩余的自由矩形块, 直到所有自由矩形块全部置入矩形框内, 或自由矩形块的个数不为零但没有做合法占角动作为止, 此时矩形框内固定矩形块的面积之和称为P 的价值度。5、 模型的建立与求解1、 数据的提取：题目中给出了地面的图片，可以用matlab读取出它的像素点（有关程序见附录二），得到了图片的像素为1440729。欲要计算出房间的大小，通过使用phtoshop图形软件把原图像中房间内部全部填充为黑色（见附录三），在输入到matlab中，计算出图片中黑色的像素点的数量，即为房屋的的总面积。通过计算房屋总面积为31.3955平方米。同理，通过填充花型图案味为全黑色，并且把图片中除花形以外的所有黑色像素点覆盖为白色（见附录三），再输入到matlab中，计算出黑色像素点的数量，继而计算出滑花形的面积。通过计算得出花形的面积为4.1379平方米。这样通过二者的差值便可计算出房屋中需要铺设矩形地板的面积即为27.2576平方米，成为欲填充面积。地板一的面积为0.1050平方米，地板二的面积为0.36平方米。假设地板可以破碎成小到1平方厘米的小块的话，则所需要的地板块数为：259.5962块（地板一）、75.7156块（地板二），称为基准块数；由于产生一部分废料，那么实际需要的地板块数一定大于基准块数。那么后面通过带有预放置矩形块的布局问题模型在基准块数附近取值，以求得最优解。2、 算法描述a)贪心放置过程A(j)：Begin ：Step1:初始化n+p-j个自由矩形块以及矩形块的宽和高，建立四个边框矩形块以及j个固定矩形块所得到的初始格局：Step2:计算当前格局下的所有合法占角动作；Step3:While jn+p且在当前格局下有合法占角动作；Step4:在当前格局下计算每个合法占角动作的穴度；Step5:挑选出穴度最大的那些合法占角动作；Step6:若有多个具有相同最大穴度的合法占角动作，则根据下面的原则挑选出一个合法的占角动作：同最大穴度合法占角动作选取原则：选择