10411300114---张伟.doc

湖南工业大学课 程 设 计资 料 袋 理 学院(系、部) 2012~2013 学年 第 2 学期 课程名称 图论及其应用 指导教师 陈平鸽 职称 讲师 学生姓名 张伟 专业班级 数学应用1001 学号 10411300114 学生姓名 鲁怀亮 专业班级 数学应用1001 学号 10411300138 学生姓名 姚俊杰 专业班级 数学应用1001 学号 10411300134 题 目 整车物流调度系统 成 绩 起止日期2013 年 6月 16 日～ 2012 年 6 月 21 日目 录 清 单序号材 料 名 称资料数量备 注1课程设计任务书12课程设计说明书13课程设计任务书2012—2013学年 第2学期 理 学院 数学与应用数学 专业 1001 班级课程名称： 图论及其应用 设计题目： 地板砖铺设问题 完成期限：自 2013 年 6 月 16 日至 2013 年 6 月 21 日共 1 周内容及任务内容：1、问题的选择与提出。

2、方法与模型的选择3、数据的调查、收集与统计分析，以及具体模型的建立4、解的问题与评价任务:为使地板铺设成本最小化,同时需要考虑整块地板砖的使用比例，即切割地板砖数尽量少,达到美观效果进度安排起止日期工作内容6月16日至6月18日明确课程设计目的及任务，查找资料和文献6月19日至6月20日就所给问题建立数学模型、编写相关程序并求解6月21日总结设计的心得与不足主要参考资料［1］杨云峰, 数学建模与数学软件，辽宁：哈尔滨工程大学出版社2012.[2]殷志宏著,线性规划，陕西：兰州大学出版社2003.指导教师（签字）: 年 月 日系（教研室）主任(签字）： 年 月 日 / 图论及其应用课程设计说明书理学院2013年6 月 18 日目 录一、问题描述 5二、模型假设 6三、符号说明 6四、模型的建立与求解 7五、模型的评价 14六、参考文献..14七、附件14 地板砖铺设问题一、问题的提出 在工程中经常会遇到将一种固定形状的材料铺设到某种物体表面的问题.房屋地板砖的铺设就是其中的一种典型实例。

在地板砖的铺设问题中，需要考虑地板砖的成本、铺设人工费用以及地板砖破损成本等方面，目标是为了使成本最小化，同时需要考虑整块地板砖的使用比例，即切割地板砖数尽量少,达到美观效果 设工程中能购买到的地板砖的尺寸、价格、安装费用、破损概率等参数如表1所示需要铺设的房屋地面结构如图1所示假设每块地板砖只能沿着平行于边的方向切割，最多只能切割一次,且切割所用人工费跟切割长度成正比 1 综合考虑影响地板砖铺设成本的因素,建立计算地板砖铺设总成本的模型 2.当今使用一种尺寸的地砖进行铺设，设计一种算法进行地板砖的自动铺设,并计算铺设地板砖的块数、利用率和总费用，分析哪种尺寸的地板砖铺设成本最低. 3．使用多种尺寸的地板砖进行混合铺设，又如何实现地板砖的自动铺设，并计算铺设各种尺寸地板砖的块数、利用率和总费用. 4．根据所建模型、算法和计算结果，为地板砖铺设提出一些意见和建议表1 各种地板砖相关参数尺寸单价（元）破损概率(%）切割成本（元/块）800mm*800mm18084600mm*600mm13073600mm＊300mm8063或1.5400mm*400mm7252300mm＊300mm4531。

5图1 户型结构图（单位mm）二、问题的分析1 对问题1的分析 建立计算地板砖铺设总成本的模型即可以把该问题定义为建立整数性规划模型我们可以将题目所给的布局划分为矩形，然后通过考虑每个矩形的成本模型，再进行叠加，就可以求取总成本最后列出总成本最低的目标函数以及约束条件其中我们要以铺设成本为函数，以寻求该函数的最小值为目标，以房间面积为约束条件.由题意可知决策变量必取整数，符合整数线性规划的定义.将所给需铺设的户型分为十三个区域先计算每一区域的最小费用，最后叠加求解总的最小费用2 对问题2的分析 由于我们只采用一种尺寸的地砖进行铺设，所以我们要进行性价比分析，选用性价比最高的砖优先铺设,然后考虑性价比由高到低顺序另和切下的废料的整块铺设，优先使用废料进行铺设，最后剩余狭小部分,一方面考虑切割废料的切割成本，另一方面考虑300＊300mm的切割成本,选择成本低的来进行填充，然后进行总费用,总块数，利用率，以及美观程度的计算得出最优结果3 对问题3的分析 当我们采用多种尺寸的地板砖进行混合铺设时，我们首先可以运用摊还分析思想对该问题进行分析,然后对地板砖进行性价比分析，选出单位面积价格最低的砖进行优先整块铺设。

然后根据性价比由高到低顺序进行整块填充,与此同时还要考虑切下的废料的整块铺设，最后剩余部分，考虑切割废料和300＊300mm的成本,来进行填充,然后进行总费用，总块数,利用率，以及美观程度的计算.得出最优结果.三、问题的假设1.每块地板砖只能切割一次,切割的方向为沿着平行于边的方向每块地板砖切割所用人工费与所切割长度成正比3.地砖切割的成本为地砖的单价，不对其他因素的进行考虑4.铺设地板砖时不需要考虑家具等限制，只考虑墙面限制，进行地面全面铺设5.地板砖的铺设没有缝隙间隔，相邻砖之间严格无缝连接切割之后破损的地板砖只能成为废料，不能在利用四、符号的说明i房间标号j砖的种类标号W总费用第i个区域的费用第i个区域第j种完整砖的块数第i个区域第j种非完整砖的块数第j种砖的单价第j种砖被切割以后的单价第j种砖的长度第j种砖的宽度第j种砖被切割以后的长度第j种砖被切割以后的宽度第i个区域的面积第i个区域的长第i个区域的宽第i个区域使用砖的总数五、模型的建立与求解 问题一的解决建立总成本模型我们由题目所给出的图可以知道我们必须首先考虑到所给平面布局，由于每个房间都不是规则的体形，而为了建立一个有指导意义的总成本模型，我们要将不规则房间划分为N个矩形，划分完成以后，我们只需要对矩形进行分析，建模，然后进行叠加，就可以求出总成本模型。

对整个布局划分情况如下图所示：将整个平面布局划分为以上13个区域，然后运用整数线性规划知识建立数学模型其中在对对单独一个区域进行矩形划分时，划分的界线两边我们应该要尽量保证都是未切割的砖，这样可以保证美观效果问题二的解决对于第二问,考虑只能用一种砖来铺设，我们可以把对该问题建立属性模型看成建立目标函数：总成本：总块数：利用率:美观程度：约束条件：然后我们通过MATLAB对该问题进行求解:我们分砖是由正方形构成和砖是由长方形构成两种情况讨论:第一：砖是由正方形构成，即边长分别为800,600,400，300mm方案如下：先用这样的正方形砖进行铺设剩余边角显然必须用这种砖来切割进行填补最后结果通过MATLAB实现第二：砖是由长方形构成，即边长为600*300mm方案如下：先对每个区域进行整块铺设剩余边角分两种情况处理,若余下边角长度足够，优先切割600的边，来进行填补，若余下边角长度小于600，则切割300的边，来进行填补值得注意的是，上述方案未考虑切割后废料的再利用和再切割利用，下面考虑废料的再利用,在运用MATLAB进行计算处理的时候建立一个备忘,将切割后的废料存入备忘,在第一步整砖铺设完成以后，一方面考虑整砖的切割，另一方面从废料中搜索符合尺寸的废料,原则是优先选择废料进行填补之后考虑废料和整块的切割工作,通过MATLAB进行求解其总费用,通过利用率公式,求得利用率，以及美观公式，求得美观率，并对利用废料前后各数据进行对比结果为：问题三的解决对于第三问，用多种砖进行铺设，首先，像前两问一样,然后，将房间分成13个区，运用摊还分析和二维下料的方法针对每一个区进行铺设。

对其总成本，利用率，总块数以及美观程度进行计算目标函数:具体分析：1：求出每种砖单位面积的价钱，找出性价比最高的砖，即主要要铺设的砖800mm*800mm性价比最高，优先选择.2：根据破损概率，运用数学期望的知识,通过MATLAB编程求得5种砖每种砖切一刀所需的成本切割成本:(3：运用摊还分析对每个区进行分析：首先，应主要铺设800*800这种性价比最高的砖，考虑到若两条边都是800的整数倍，那么可以全部用800*800的砖铺设，就是最优结果，下面从简单到复杂依次进行考虑：若或者为整数（假设是𝑝𝑖 𝑎1）,即i区域有一条边被800＊800的砖铺满，形如砖是由长方形构成对于下边面积为的区域我们根据尽量不切，尽量选用性价比高的的原则，结合800*n和的长度，按照600＊600，600*300，400＊400，300＊300的顺序进行填补,剩余的图形如图：对于剩余的狭小面积，最窄的边也一定小于300mm我们不得不进行切割来填补，根据所剩长条状的狭小面积的尺寸,选择600＊300或者300*300的砖,沿长边600或者300进行切割，铺设铺设后的可能结果如图：最后剩下的小区域,可能是两个边长都小于300的矩形,也可能是一个边长都小于300的矩形,用300*300进行切割填补。

如上图所示.以上讨论了一条边被800＊800填满的情况,、当两边都不会被800*800的砖铺满时,情况如图所示：同理按照2，3,4，5号砖进行铺设，最后剩余的情形如图所示：同理每个剩余都是边长小于300的矩形，用300＊300进行切割填补。