日志
数模论文1
热度 6 ||
目录
一、问题重述......................................................................................................................................................................................................................................................二、模型假设............................................................................................................................三、问题分析............................................................................................................................3.1 问题一..........................................................................................................................3.2 问题二..........................................................................................................................3.3 问题三..........................................................................................................................四、符号说明............................................................................................................................五、模型建立及求解................................................................................................................. 5.1、建模准备....................................................................................................................5.1.1.计算餐椅模板的面积........................................................................................... 5.1.2.图形的像素化处理...............................................................................................5.2 问题一..........................................................................................................................5.2.1 模型建立及算法选择........................................................................................... 5.2.2 模型的改进：.................................................................................................... 5.3 问题二........................................................................................................................ 5.4 问题三....................................................................................................................... 六、模型的评价及推广应用.....................................................................................................6.1 问题一模型................................................................................................................. 6.1.1 模型分析及评价.................................................................................................6.1.2 推广应用........................................................................................................... 6.2 问题三模型.......................................................................................................... 6.2.1 模型分析........................................................................................................... 七、参考文献..........................................................................................................................八、附录文件........................................................................................................................
一、问题重述
在实际生产生活中裁剪是必不可少的，裁剪的好坏、利用率的高低，直接影生产厂家的经济利益，首先定义以下三个概念：
1、牛皮：整张，未裁剪的牛皮原料，经过数码取像技术转化成CAD 文件格二维区域；
2、皮板：最终产品的模板，一般由硬纸板制成的，用于裁剪。产品设计完经过数码取像技术转化成CAD 文件格式的二维区域；
3、皮件:由皮革缝制成皮套，再通过其他工艺加工成的最终产品（例如皮包鞋、皮沙发等）。
根据以上定义，本问题研究的对象是数码二维区域。附件提供了2 张牛皮沙发模板和椅子模板，根据知道沙发和椅子的各个部位的皮模板可以制造一把皮和一把餐椅。在实际生产中经常要求牛皮的利用率要尽可能大，为此我们需要解下三个问题:
1、假设N 张牛皮的模板都和提供的两张一样，试建立数学模型，在厂家皮单确定的情况下，针对N 张牛皮的排料算法，要求牛皮的利用率最大化；
2、在某批沙发订单确认的情况下，在采购了40 张牛皮裁剪结束之后（发下定余量），插入一个餐椅皮件订单。利用裁剪的余量，再增加8 张牛皮，计算出增加的餐椅数量；
3、附件还给出了近1 年左右某些连续订单，在积累一定历史数据的情况下，对增加的产品计算出一个合理的价格范围，在考虑市场因素的前提下，建立数学确定一个促销价格。
二、模型假设
1．裁剪过程中不出现错误，即不考虑裁坏牛皮等情况；
2．假设裁剪过程为无缝切割；
3．假定生产皮件的原料成本及劳动力成本稳定不会产生大的变动；
4．认为厂家的生产能力足够大；
5．不考虑市场中的竞争因素
三、问题分析
3.1问题一
法、凸包算法及其平移技术、临界多边形法、智能优化算法（括人工神经网络、算法、模拟退火、禁忌搜索算法）等，但对于一个实际的问题到底使用哪种算法得到最化结果，该没有完备的理论。
我们进行初步分析，认为虽然包络矩形法比较简单，而且能将二维问题转化维问题，有较多的比较成熟的算法。但针对于此题牛皮和皮板都是不规则二维若采用包络矩形方法对皮板和牛皮进行处理则会产生较多的浪费。
而智能优化算法较难掌握，而二维不规则排料属于最复杂的组合优化问题其复杂性主要由多边形的不规则几何形状和不同的次序组合引起，由于零件形状则，所以不同零件之间的靠接，判交等处理比较复杂，计算复杂度高，不同的次合、旋转角度都可能导致不同的排料结果，【2】在有限的时间内我们没有较高的把顺利求解，所以我们的想法是针对目前的算法进行相应改进，形成我们自己的解问题的算法。
综合考虑利用率和自身的能力，我们决定对图形进行离散化处理，并用矩阵表示，这样既避免了包络矩形方法利用率低的缺点，同时使处理后的图形的边正减少了旋转角度造成的较大的时间复杂度和空间复杂度。
3.2问题二
这一问可以说成是第一问的实践检验，给40 张牛皮，按照沙发的模板进行即开始的时候只是在40 张牛皮上生产沙发，我们的想法是尽可能多的生产沙发为公司在采购的时候一般都是依据订单量采购的，首先必须保证能够足够生产订裁量，然后才会有余量。这进行之后在其余量的基础上再增加8 张牛皮，然后对模板进行排料，要生产更多的餐椅就是要求利用率最大化，就转化为问题一了3.3问题三
这一问是要在考虑市场因素的前提下确定皮件产品的合理价格范围，市场因括供需关系、原料价格、生产成本、生产周期、利润等各种因素之间的复杂作用但这道题没有提供更多的信息，无法综合考虑各种因素来确定皮件的合理价格。于是基于订单数，再考虑一些市场因素如供求关系等来给出皮件一个价格范围，是既保证皮件厂有较大的利润，又可以吸引用户有更多的持续订单，因此我们建基于供需差额的调价模型。
四、符号说明
符号符号意义单位
0 p 沙发的基准价格元
i p 沙发第i 个月的销售价格元
0 q 餐椅的基准价格元
i q 餐椅第i 个月的销售价格元
i D 第i 个月的订单数把
i S 第i 个月的生产量把
s k 沙发调整价格时的系数
c k 餐椅调整价格时的系数
五、模型建立及求解
5.1、建模准备
5.1.1.计算餐椅模板的面积
由于题目中提供了沙发模板和餐椅模板，但只给出了沙发模板的面积和比我们需要根据沙发的比例计算出餐椅的面积，才能进行实际建模处理问题。但我处理的过程发现提供的沙发模板的数据存在很多问题，因为有不少图形比例尺一，我们无法找到一个参照的比例尺，这给我们的工作造成不小的麻烦。而且有同面积的图形用PHOTOSHOP CS3 的分析中的记录测量工具计算像素点数差别还有一点就是提供沙发模板前38 张图像素全为1224*500，后几个为1224*564，椅为640*480；也就是说在用数码取像时使用的标准不一样。因此为了方便的设合理的优化排料算法，我们首先需要将所有的模板化成一个统一的标准，这样才行排料运算。
我们的想法就是既然沙发有这么多组数据，而且给出了面积和比例尺，我们用PHOTOSHOP CS3 的分析中的记录测量工具计算像素点数，进而可以求得对一个沙发模板面积下单位面积对应的像素点数，下面是沙发模板面积及其对应的面积像素点散点图：
0
50000
100000
150000
200000
250000
300000
350000
400000
450000
500000
0 10 20 30 40 50
沙发模板面积
单位面积像素点数
单位面积像素点0.05
从图像及实际处理后的数据分析上可以得出，单位面积的像素点数为215000，
然后就可以根据这个标准计算出沙发的每个模板的理论像素点数，并且可以计算椅的面积。
在计算餐椅面积时我们还考虑到题目提供的餐椅模板是640*480，约为沙发所以椅子单位面积的像素点数为107500，然后用经PHOTOSHOP CS3 的分析中录测量工具计算像素点数除以107500，即可得到餐椅面积，将面积保留三位小后根据求得的面积即可计算出其理论像素点数。
具体处理结果见附件[3]
5.1.2.图形的像素化处理
由于我们建立的模型和设计的算法都是基于网格矩阵实现的，因此我们需要对提供的图形用PHOTOSHOP CS3 进行像素化处理，然后对处理过的图形进行编码，之后就可以进行我们的算法实现了。
我们处理这道题的思路就是对一个图形进行0—1 编码，牛皮模板上有牛皮方编码为0，其余地方编码为1，对于沙发和餐椅模板有模板的地方编码为1，没地方编码为0，然后就是将沙发模板和餐椅模板的矩阵放到牛皮的矩阵中。因此化处理即是在1 的计算基础上，将所有模板都处理成MATLAB 可以读入的矩阵也即像素化。我们在设计算法时将一个像素点认为是数值。
像素化的具体过程如下：
1、打开PHOTOSHOP CS3，调入一个图像，设置容差为32；
2、使用快速选择工具选中皮件范围，然后反向选择，删除；
3、重新选择皮件范围，点shift+F5，设置颜色，然后复制；
4、新建图形，选择8 位灰度值，点回车，粘贴即可。
运算能力就比较理想，这样得到了最终处理结果，下面是一张牛皮经以上处理步得到的结果：
沙发模板和餐椅模板像素化处理后按照一定比例缩小后的结果见附录文件5.2问题一
5.2.1模型建立及算法选择
在建模准备的基础上就可以解决问题了，我们设计算法的基本思想就是对张牛皮，用足够多的线条将牛皮网格化，将模板也这样处理，然后就可以将模板牛皮模板上了。为了将模板进行网格化，我们使用的是PHOTOSHOP CS3 处理照像素点进行0-1 编码。为此我们引入两个编码矩阵：
其中ij a 表示的是牛皮网格化后的矩阵， mn b 表示的是皮件模板网格化后的矩我们的主体算法思想就是不断地取矩阵b ，然后放到矩阵ij a 上。然后就是1 1
1 1
ij a
⎛ ⎞
=⎜ ⎟ ⎜ ⎟
⎜ ⎟
⎝ ⎠
…
⋮ ⋱ ⋮
⋯
0 0 0
0 0
0 0 0
mn b
⎛ ⎞
= ⎜ ⎟ ⎜ ⎟
⎜⎝ ⎟⎠
⋱
变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动据个体编码表示方法的不同，可以有以下的算法：
1)实值变异；
2)二进制变异。
一般来说，变异算子操作的基本步骤如下:
1)对群中所有个体以事先设定的编译概率判断是否进行变异；
2)对进行变异的个体随机选择变异位进行变异。
选择
从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又再生算子(reproduction operator)。选择的目的是把优化的个体(或解)直接遗传到下或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的度评估基础上的，目前常用的选择算子有以下几种:适应度比例方法、随机遍历法、局部选择法、局部选择法。其中轮盘赌选择法（roulette wheel selection）是单也是最常用的选择方法。
对于一个系统，如果要对它进行优化，首先要进行以下步骤：
1、首先根据实际情况产生一代个体。
2、我们记这代为P1 (带下标的)。
3、我们选择其中达到把其中达到要求保留。
4、将生下来的子代组成一个新的系统，将他们置于这个系统中进行杂交，新的一代，记为P2，
5、选择其中达到要求的进行保留。
6、以此循环，直到全部达到要求为止。
我们以一张排满皮件的牛皮作为一个个体，每次零件排好，选择符合最开始的牛皮，保留，再用生下来的皮件在牛皮上进行排样。再选择合格的牛皮进行直到剩下来的所有皮件不足以排满一张牛皮为止。
具体的算法流程图如下。
根据达尔文进化论的原理，性能优良的有利变异出现的频率是非常低的，在代进行随机生成的时候，朝着我们所需要的方向进行变异的子代个体出现的频少。理论上通过大量的子代，在长时间的演化过程中，可以出现非常优异的后实际上这个过程是漫长的，不定向的。
把个原理应用于本题，考虑到矩阵计算的复杂性，随机调整的多样性，产生的情况非常多，而只有很少的比例可以产生所需要的个体子代。为了提高出现所的子代的概率，我们采取了两种措施，正如上面的流程图所示：首先是采取措施子代多样化，我们通过随机旋转皮件0 度，180 度和270 度）。增加了皮件的自使得理论上可以出现更加优良的变异；再有就是没排放一个零件，我们人为得将向左上角，通过人工定向调整，可以使得优良的子代更快出现。
根据这种思想我们的编程人员使用MATLAB 编写了程序，这个程序在运行
上排料后利用率已经达到设定的值。就我们的算法思想而言，最后牛皮的利用率达到足够高。对于本题，我们的结果受到计算机性能的限制，虽然理论上可以出常优良的排样情况，但鉴于个人电脑的计算性能和本题中过多的计算以及算法本不够优化，使得本题的结果无法达到理论上理想状态。
经过多次对程序进行运行尝试，最终我们选择了45%的利用率作为排料结我们首先设定期望的牛皮利用率为0.45，然后生产10 把沙发，30 张餐椅，一共了68 张牛皮，程序运行的速度比较快，得到的利用率都在0.45 以上。用MATLAB
的绘图工具可以绘制对牛皮进行排料后的结果图像，其中随机选取几张牛皮的排果表示如下：
由于对沙发和椅子模板进行了统一的像素化处理。使得沙发皮件所占的像素大，有的单一零件所占像素点就站到牛皮模板的将近40%，所以最终算法的利用提高需要增加非常多的时间。所以选择45%作为一个选择牛皮模板的划线标准是现有的计算机设备和算法的实际情况定下的折中标准。
我们为了提高牛皮的利用率，在尝试中设定牛皮的利用率为0.70，生产沙把，餐椅30 把，但是程序在内存为2G，操作系统为WINDOWS 的32 位机上运10 个小时，依然没有给出最终结果，最后不得不终止程序的运行，下面是程序执的截图:
5.2.2模型的改进：
1. 计算机模拟的时候采用了MATLAB 的编译环境，而由于MATLAB 的类似于调试的编译原理，使得运算的效率本来不高。如果用效率更加高的C++变成集数据录入，数据保存且可视化的程序，将会使的计算速度大大提高，每个出现的速度更加快，这样在同样的时间中可以出现更多的子代，对我们的选常有利；
2. 本题的算法基于MATLAB 的矩阵运算，由于在大量的调整和选择的时候过赖计算能力，使得我们编号的程序有待改进；
3. 可以加入基于对全局判断的逻辑判断条件，类似于人工排样的时候所用方法入带有人工智能性质的排样思路可以使得出现优良子代的概论大大提高。这们的模型可以进一步改进的地方。
4. 如果不对我们的模型进行大的变动，又希望可以得到更加优化的结果，可以条件的情况下，借助于商用超级计算机。
5.3问题二
由于按照我们在第一问达到的0.45 的利用率，40 张牛皮生产的沙发数为大把，这道题我们首先是设定程序中生产沙发的数量为7 个，餐椅数量为0 个，运
13 把、14 把、15 把，分别运行程序，对11 张餐椅进行排料，最后发现当生产餐数量为14 把时，使用的牛皮数正好是11 张，已经将所有牛皮用完，而且利用率了50%，在51%-52%之间。利用率有了部分提高。所以我们解决此道问题的最果即为可以增加的餐椅数量为14 把。
5.4 问题三
市场是“一双看不见的手”，它自动发挥着调节作用使市场趋于稳定，站在者一方来考虑，为了获得持续较高的利润，需要不断地根据供求关系，适时的调己的价格。在实际生活中，生产者可通过两种策略来制定、调整产品的价格。一略是根据所获利润来调价，即生产者或以利润目标为中心来制定产品的价格。比生产者出售一种产品的价格为p，由于生意不错，他打算适当提价；提价之后发得利润更大，于是继续提价；但再提价后因价格偏高，顾客减少使其利润下降，又决定适当降价；总之他不断地依利润增减调整产品的价格。另一种基于供需差调价策略，即根据产品供需情况来调价，使产品价格的升降与供需差额成正比。一种产品的需求量D大于供给量S，这将引起该产品的价格上升；反之，如果供求则将引起产品价格下降。在以供需差额为基础的调价策略中，价格的升降与供额成正比。【3】
对于此问题，我们定义价格和市场供需满足如下的关系：
1．本阶段的市场订单由上一阶段的产品定价决定，二者成反比关系；即若月的产品售价较低，则该月的订单数会较上个月有所增加，反之减少。
2．本阶段产品的价格有本阶段产品的供需差额决定，二者成反比关系：当于求时，价格下调；供小于求时，价格上升。
本题中，由于市场上沙发和餐椅的价格没有一个较为统一的标准，我们为和餐椅设定一个基准价格0 p ， 0 q ，每个月份产品的价格调整都是在基准价格上的，例如第i 个月沙发的调整价格i i 0 Δp = p − p 。
沙发第i 阶段的价格与当前阶段供求差额成一反比关系:
0 ( ) i s i i p = p −k S −D --------------------------------------------- 第i 阶段的产品需求量i D 与第i −1阶段的产品定价i 1 p − 有如下关系:
3 2 1
1 1 1 ( ) * * * i i i i i D f p a p b p c p d − − − = = − + − + ----------------------------- 由于我们无法确定每一次厂家生产皮件的增加量，为了简化问题，我们认为每一月的产量都在订单量的基础上增加10%，即
1.1 i i S = D --------------------------------------------------- 则(1)式即可简化为:
3 2
0 1 0 1 0 1 * ( 0.1* ) * ( 0.1* ) * ( 0.1* ) i i i i D a p D b p D c p D d − − − = − − + − − − + ---------- 简化为:
' 3 ' 2 ' '
1 1 1 * * * i i i i D a D b D c D d − − − = + + + ---------------------------- 该式即为要求解的式子，我们选用了2009年的12组数据，代入(6)式得到11元一次方程组，这是一个矛盾方程组，我们利用偏最小二成原理，编写C程序求对于餐椅求解思路一样，其模型如下:
q i= q0 −kc (Si −Di ) ---------------------------------------- 3 2 1
1 1 1 ( ) * * * i i c i c i c i c D f p a q b q c q d − − − = = − + − + -------------------- 程序运行结果如下
b = 0.181208, c = −11.862747 , d = 303.767693 ,并且可以看出这个系数可以很反映出这个月和上个月沙发订单的关系，曲线拟合的很好。然后对比（5）（6）可以得到沙发调整价格时的系数s k ，然后就可以得到第i 个月的沙发价格和基准价系， 进而可以得到沙发合理的价格范围； 同理， 对于餐椅其系a' = 0.000015,b' = 0.012189, c' = 3.895381, d' = −185.101609，比较（7）（8）两式可餐椅调整价格时的系数为c k ，则可得到第i 个月的餐椅价格和基准价格的关系如下，可知合理价格范围为。我们在计算时只选用2009 年的12 组数据，准备用2010 年的三组数据对得的结果进行验证。
六、模型的评价及推广应用
6.1问题一模型
6.1.1模型分析及评价
我们首先分析了现有的一些算法，比如矩形包络法，其基本思想就是用矩形边形将不规则零件包络起来，然后转化为矩形优化排料，由于矩形零件排料算法的比较成熟，接下来就可以选用相应的一些算法进行解决了。这种处理问题的思较好，一般在家具生产等领域都使用这种方法处理。但是这种处理方法有明显的因为牛皮属于比较稀有的原料，价格相对来说比较高，而用矩形包络法得到的结是很优化，也会有很多的原料浪费，因此我们没有选用这种方法；临界多边形法法思想即用用多边形的点和边来表示位置，优点是求解精度高，但存在明显的即算法设计太复杂，执行起来麻烦，而且不能保证得到比较理想的结果；凸包算其平移技术，这种方法是将二维不规则零件的排料问题转化为计算几何问题，要包首先要说凸性的定义，简单点说就是平面邻域中任意两点所在的线段上的点都邻域中，则该邻域具有凸性。简单推敲一下，就可以发现如果邻域中存在一阶导连续的点一定无法被某点集线性表示出来。一般的计算几何问题都是处理的离散形成的平面域，所以我们感兴趣的是怎样找一个包含这个点集的面积最小的凸形，这就是凸包。这种处理方式尚不太成熟，正处于研究阶段，而且要找到一个凸包就是相当麻烦了，而我们需要排的零件较多，而且有两张不一样的牛皮模生产中需要的牛皮数量比较多；针对此题智能优化算法是一种比较好的方法，而些年针对二维不规则零件的优化排料问题，使用智能优化算法研究的比较火热。文献[6]中介绍的在遗传算法的基础上可以用BL 算法、下台阶法、最低水平线法件进行编码并转化为样图，但是我们没有完全照搬这种方法进行解决，我们是基
排料优化过程中我们引入了遗传算法的变异和自然选择的思想进行编程种处理问题的思路比较新颖。
b) 我们在建模的过程中使用PHOTOSHOP CS3 的记录测量工具对所有模板处理，这种方式很好的解决了提供的模板出现的诸多问题，将所有模板统一化处理，并根据计算出的比例得到了餐椅的面积。
c) 我们想到用像素点来对模板进行0-1 编码处理，这种处理方式很方便将矩阵化，然后导入MATLAB 中。
d) 用离散的矩阵表示图形，能够实现正交化，使得每个皮板的摆放只有四位角度，降低了程序的负杂度；并且离散化会比包络矩形的利用率更高缺点：
1. 我们的模型理论上可以使牛皮达到很高的利用率，但由于受到计算机运度的限制，我们最后得到的结果很不理想。
2. 为了提高牛皮的利用率我们可以有两种方式：一、增加零件选择次数；提高像素点数，但由于每一种方式都会大量的增加程序的运行时间，所们不得不缩小这些方面，以降低牛皮利用率为代价来缩短程序运行时间我们首先分析了现有的一些算法，比如矩形包络法的优缺点，然后结合该问具体情况，选择了现有模型。
A．包络矩形法
优点：算法成熟，能够将二维问题转化为一维问题；矩形空间角度仅存在两况，降低了算法的复杂度。缺点：对原料的利用率低，尤其是在本题中牛皮模板规则程度较高的情况下，不容易得到较高的利用率。
B．临界多边形法
优点：用多边形的点和边来表示位置，求解精度高。缺点：算法设计复杂。
C．离散矩阵化
优点：用离散的矩阵表示图形，能够实现边的正交化，使得每个皮板的摆放四种方位角度，降低了程序的负杂度；并且离散化会比包络矩形的利用率更高。矩阵的阶数比较大，会使算法的时间复杂度比较大。
综合上述分析，我们最终选取离散矩阵化方法来求解。
6.1.2推广应用
1. 问题一模型适用于建议一个使用计算机对带有复杂逻辑判断的实际问题进行简单而有效的算法。这个算法理论上可以出现最优解，但根据实际情况需要的时间。本题中由于计算量过于巨大，排样的变异种类过多使得这个计算耗多，要是换做别的计算量较小的实际问题，我们给出的算法还是有很大的实用价值。
2. 基于遗传算法的计算机模拟算法可以在条件允许的情况下避免对个体间实际间不清楚的实际问题进行处理。避免对个体间关系的复杂的考虑分析是以大计算为代价的。
6.2问题三模型
6.2.1模型分析
针对本问建立的基于市场供需差额的调价模型是基于市场经济的自动调价建立的，具有很强的现实意义。模型对市场环境进行了粗略的模拟，分别构造了格变化的需求函数和随供需差额变化的价格函数；通过历史数据进行拟合估计，出两个函数的具体参数。缺点本题中忽略了市场中存在竞争情况和复杂的消费理，仅建立了一个简单的价格随供求差额改变的模型。因此我们的模型比较粗后也没有得到结果。
七、参考文献
[1] 计华,刘弘．优化排料算法的研究与实现．小型徽莹计算机系统．2001 年3 [2] 张英杰．二维不规则零件自动排料的优化算法．机械设计与研究．2009 年[3] 胡振华，聂艳晖．基于供需差额的调价策略的鲁棒性研究．管理工程学报．年第三期
[4] 唐玉霞．论导数在经济分析中的应用．财经管理．2009.7 上月刊
[5] 彭文丽等．优化排料算法的研究现状与趋势．模具工业．2006 年第32 卷第[6] 曹新明，蒋瑞斌．不规则零件最小包络矩形的求解研究．科技通报．2007 年第23 卷第一期
八、附录文件
[1].模板像素化处理结果；
[2].matlab 程序源代码；
[3].模板理论像素点数；
[4].曲线拟合程序代码；
[5].程序的运行结果；保存在MATLAB 的工作空间中，见附录文件中：
第一问.mat 第二问(1).mat 第二问(2).mat 的以date 命名的结构体当中其中是以0-1 矩阵形式表示的排列好的模版，date.precise 排好的模版的利用率
一、问题重述......................................................................................................................................................................................................................................................二、模型假设............................................................................................................................三、问题分析............................................................................................................................3.1 问题一..........................................................................................................................3.2 问题二..........................................................................................................................3.3 问题三..........................................................................................................................四、符号说明............................................................................................................................五、模型建立及求解................................................................................................................. 5.1、建模准备....................................................................................................................5.1.1.计算餐椅模板的面积........................................................................................... 5.1.2.图形的像素化处理...............................................................................................5.2 问题一..........................................................................................................................5.2.1 模型建立及算法选择........................................................................................... 5.2.2 模型的改进：.................................................................................................... 5.3 问题二........................................................................................................................ 5.4 问题三....................................................................................................................... 六、模型的评价及推广应用.....................................................................................................6.1 问题一模型................................................................................................................. 6.1.1 模型分析及评价.................................................................................................6.1.2 推广应用........................................................................................................... 6.2 问题三模型.......................................................................................................... 6.2.1 模型分析........................................................................................................... 七、参考文献..........................................................................................................................八、附录文件........................................................................................................................
一、问题重述
在实际生产生活中裁剪是必不可少的，裁剪的好坏、利用率的高低，直接影生产厂家的经济利益，首先定义以下三个概念：
1、牛皮：整张，未裁剪的牛皮原料，经过数码取像技术转化成CAD 文件格二维区域；
2、皮板：最终产品的模板，一般由硬纸板制成的，用于裁剪。产品设计完经过数码取像技术转化成CAD 文件格式的二维区域；
3、皮件:由皮革缝制成皮套，再通过其他工艺加工成的最终产品（例如皮包鞋、皮沙发等）。
根据以上定义，本问题研究的对象是数码二维区域。附件提供了2 张牛皮沙发模板和椅子模板，根据知道沙发和椅子的各个部位的皮模板可以制造一把皮和一把餐椅。在实际生产中经常要求牛皮的利用率要尽可能大，为此我们需要解下三个问题:
1、假设N 张牛皮的模板都和提供的两张一样，试建立数学模型，在厂家皮单确定的情况下，针对N 张牛皮的排料算法，要求牛皮的利用率最大化；
2、在某批沙发订单确认的情况下，在采购了40 张牛皮裁剪结束之后（发下定余量），插入一个餐椅皮件订单。利用裁剪的余量，再增加8 张牛皮，计算出增加的餐椅数量；
3、附件还给出了近1 年左右某些连续订单，在积累一定历史数据的情况下，对增加的产品计算出一个合理的价格范围，在考虑市场因素的前提下，建立数学确定一个促销价格。
二、模型假设
1．裁剪过程中不出现错误，即不考虑裁坏牛皮等情况；
2．假设裁剪过程为无缝切割；
3．假定生产皮件的原料成本及劳动力成本稳定不会产生大的变动；
4．认为厂家的生产能力足够大；
5．不考虑市场中的竞争因素
三、问题分析
3.1问题一
法、凸包算法及其平移技术、临界多边形法、智能优化算法（括人工神经网络、算法、模拟退火、禁忌搜索算法）等，但对于一个实际的问题到底使用哪种算法得到最化结果，该没有完备的理论。
我们进行初步分析，认为虽然包络矩形法比较简单，而且能将二维问题转化维问题，有较多的比较成熟的算法。但针对于此题牛皮和皮板都是不规则二维若采用包络矩形方法对皮板和牛皮进行处理则会产生较多的浪费。
而智能优化算法较难掌握，而二维不规则排料属于最复杂的组合优化问题其复杂性主要由多边形的不规则几何形状和不同的次序组合引起，由于零件形状则，所以不同零件之间的靠接，判交等处理比较复杂，计算复杂度高，不同的次合、旋转角度都可能导致不同的排料结果，【2】在有限的时间内我们没有较高的把顺利求解，所以我们的想法是针对目前的算法进行相应改进，形成我们自己的解问题的算法。
综合考虑利用率和自身的能力，我们决定对图形进行离散化处理，并用矩阵表示，这样既避免了包络矩形方法利用率低的缺点，同时使处理后的图形的边正减少了旋转角度造成的较大的时间复杂度和空间复杂度。
3.2问题二
这一问可以说成是第一问的实践检验，给40 张牛皮，按照沙发的模板进行即开始的时候只是在40 张牛皮上生产沙发，我们的想法是尽可能多的生产沙发为公司在采购的时候一般都是依据订单量采购的，首先必须保证能够足够生产订裁量，然后才会有余量。这进行之后在其余量的基础上再增加8 张牛皮，然后对模板进行排料，要生产更多的餐椅就是要求利用率最大化，就转化为问题一了3.3问题三
这一问是要在考虑市场因素的前提下确定皮件产品的合理价格范围，市场因括供需关系、原料价格、生产成本、生产周期、利润等各种因素之间的复杂作用但这道题没有提供更多的信息，无法综合考虑各种因素来确定皮件的合理价格。于是基于订单数，再考虑一些市场因素如供求关系等来给出皮件一个价格范围，是既保证皮件厂有较大的利润，又可以吸引用户有更多的持续订单，因此我们建基于供需差额的调价模型。
四、符号说明
符号符号意义单位
0 p 沙发的基准价格元
i p 沙发第i 个月的销售价格元
0 q 餐椅的基准价格元
i q 餐椅第i 个月的销售价格元
i D 第i 个月的订单数把
i S 第i 个月的生产量把
s k 沙发调整价格时的系数
c k 餐椅调整价格时的系数
五、模型建立及求解
5.1、建模准备
5.1.1.计算餐椅模板的面积
由于题目中提供了沙发模板和餐椅模板，但只给出了沙发模板的面积和比我们需要根据沙发的比例计算出餐椅的面积，才能进行实际建模处理问题。但我处理的过程发现提供的沙发模板的数据存在很多问题，因为有不少图形比例尺一，我们无法找到一个参照的比例尺，这给我们的工作造成不小的麻烦。而且有同面积的图形用PHOTOSHOP CS3 的分析中的记录测量工具计算像素点数差别还有一点就是提供沙发模板前38 张图像素全为1224*500，后几个为1224*564，椅为640*480；也就是说在用数码取像时使用的标准不一样。因此为了方便的设合理的优化排料算法，我们首先需要将所有的模板化成一个统一的标准，这样才行排料运算。
我们的想法就是既然沙发有这么多组数据，而且给出了面积和比例尺，我们用PHOTOSHOP CS3 的分析中的记录测量工具计算像素点数，进而可以求得对一个沙发模板面积下单位面积对应的像素点数，下面是沙发模板面积及其对应的面积像素点散点图：
0
50000
100000
150000
200000
250000
300000
350000
400000
450000
500000
0 10 20 30 40 50
沙发模板面积
单位面积像素点数
单位面积像素点0.05
从图像及实际处理后的数据分析上可以得出，单位面积的像素点数为215000，
然后就可以根据这个标准计算出沙发的每个模板的理论像素点数，并且可以计算椅的面积。
在计算餐椅面积时我们还考虑到题目提供的餐椅模板是640*480，约为沙发所以椅子单位面积的像素点数为107500，然后用经PHOTOSHOP CS3 的分析中录测量工具计算像素点数除以107500，即可得到餐椅面积，将面积保留三位小后根据求得的面积即可计算出其理论像素点数。
具体处理结果见附件[3]
5.1.2.图形的像素化处理
由于我们建立的模型和设计的算法都是基于网格矩阵实现的，因此我们需要对提供的图形用PHOTOSHOP CS3 进行像素化处理，然后对处理过的图形进行编码，之后就可以进行我们的算法实现了。
我们处理这道题的思路就是对一个图形进行0—1 编码，牛皮模板上有牛皮方编码为0，其余地方编码为1，对于沙发和餐椅模板有模板的地方编码为1，没地方编码为0，然后就是将沙发模板和餐椅模板的矩阵放到牛皮的矩阵中。因此化处理即是在1 的计算基础上，将所有模板都处理成MATLAB 可以读入的矩阵也即像素化。我们在设计算法时将一个像素点认为是数值。
像素化的具体过程如下：
1、打开PHOTOSHOP CS3，调入一个图像，设置容差为32；
2、使用快速选择工具选中皮件范围，然后反向选择，删除；
3、重新选择皮件范围，点shift+F5，设置颜色，然后复制；
4、新建图形，选择8 位灰度值，点回车，粘贴即可。
运算能力就比较理想，这样得到了最终处理结果，下面是一张牛皮经以上处理步得到的结果：
沙发模板和餐椅模板像素化处理后按照一定比例缩小后的结果见附录文件5.2问题一
5.2.1模型建立及算法选择
在建模准备的基础上就可以解决问题了，我们设计算法的基本思想就是对张牛皮，用足够多的线条将牛皮网格化，将模板也这样处理，然后就可以将模板牛皮模板上了。为了将模板进行网格化，我们使用的是PHOTOSHOP CS3 处理照像素点进行0-1 编码。为此我们引入两个编码矩阵：
其中ij a 表示的是牛皮网格化后的矩阵， mn b 表示的是皮件模板网格化后的矩我们的主体算法思想就是不断地取矩阵b ，然后放到矩阵ij a 上。然后就是1 1
1 1
ij a
⎛ ⎞
=⎜ ⎟ ⎜ ⎟
⎜ ⎟
⎝ ⎠
…
⋮ ⋱ ⋮
⋯
0 0 0
0 0
0 0 0
mn b
⎛ ⎞
= ⎜ ⎟ ⎜ ⎟
⎜⎝ ⎟⎠
⋱
变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动据个体编码表示方法的不同，可以有以下的算法：
1)实值变异；
2)二进制变异。
一般来说，变异算子操作的基本步骤如下:
1)对群中所有个体以事先设定的编译概率判断是否进行变异；
2)对进行变异的个体随机选择变异位进行变异。
选择
从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又再生算子(reproduction operator)。选择的目的是把优化的个体(或解)直接遗传到下或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的度评估基础上的，目前常用的选择算子有以下几种:适应度比例方法、随机遍历法、局部选择法、局部选择法。其中轮盘赌选择法（roulette wheel selection）是单也是最常用的选择方法。
对于一个系统，如果要对它进行优化，首先要进行以下步骤：
1、首先根据实际情况产生一代个体。
2、我们记这代为P1 (带下标的)。
3、我们选择其中达到把其中达到要求保留。
4、将生下来的子代组成一个新的系统，将他们置于这个系统中进行杂交，新的一代，记为P2，
5、选择其中达到要求的进行保留。
6、以此循环，直到全部达到要求为止。
我们以一张排满皮件的牛皮作为一个个体，每次零件排好，选择符合最开始的牛皮，保留，再用生下来的皮件在牛皮上进行排样。再选择合格的牛皮进行直到剩下来的所有皮件不足以排满一张牛皮为止。
具体的算法流程图如下。
根据达尔文进化论的原理，性能优良的有利变异出现的频率是非常低的，在代进行随机生成的时候，朝着我们所需要的方向进行变异的子代个体出现的频少。理论上通过大量的子代，在长时间的演化过程中，可以出现非常优异的后实际上这个过程是漫长的，不定向的。
把个原理应用于本题，考虑到矩阵计算的复杂性，随机调整的多样性，产生的情况非常多，而只有很少的比例可以产生所需要的个体子代。为了提高出现所的子代的概率，我们采取了两种措施，正如上面的流程图所示：首先是采取措施子代多样化，我们通过随机旋转皮件0 度，180 度和270 度）。增加了皮件的自使得理论上可以出现更加优良的变异；再有就是没排放一个零件，我们人为得将向左上角，通过人工定向调整，可以使得优良的子代更快出现。
根据这种思想我们的编程人员使用MATLAB 编写了程序，这个程序在运行
上排料后利用率已经达到设定的值。就我们的算法思想而言，最后牛皮的利用率达到足够高。对于本题，我们的结果受到计算机性能的限制，虽然理论上可以出常优良的排样情况，但鉴于个人电脑的计算性能和本题中过多的计算以及算法本不够优化，使得本题的结果无法达到理论上理想状态。
经过多次对程序进行运行尝试，最终我们选择了45%的利用率作为排料结我们首先设定期望的牛皮利用率为0.45，然后生产10 把沙发，30 张餐椅，一共了68 张牛皮，程序运行的速度比较快，得到的利用率都在0.45 以上。用MATLAB
的绘图工具可以绘制对牛皮进行排料后的结果图像，其中随机选取几张牛皮的排果表示如下：
由于对沙发和椅子模板进行了统一的像素化处理。使得沙发皮件所占的像素大，有的单一零件所占像素点就站到牛皮模板的将近40%，所以最终算法的利用提高需要增加非常多的时间。所以选择45%作为一个选择牛皮模板的划线标准是现有的计算机设备和算法的实际情况定下的折中标准。
我们为了提高牛皮的利用率，在尝试中设定牛皮的利用率为0.70，生产沙把，餐椅30 把，但是程序在内存为2G，操作系统为WINDOWS 的32 位机上运10 个小时，依然没有给出最终结果，最后不得不终止程序的运行，下面是程序执的截图:
5.2.2模型的改进：
1. 计算机模拟的时候采用了MATLAB 的编译环境，而由于MATLAB 的类似于调试的编译原理，使得运算的效率本来不高。如果用效率更加高的C++变成集数据录入，数据保存且可视化的程序，将会使的计算速度大大提高，每个出现的速度更加快，这样在同样的时间中可以出现更多的子代，对我们的选常有利；
2. 本题的算法基于MATLAB 的矩阵运算，由于在大量的调整和选择的时候过赖计算能力，使得我们编号的程序有待改进；
3. 可以加入基于对全局判断的逻辑判断条件，类似于人工排样的时候所用方法入带有人工智能性质的排样思路可以使得出现优良子代的概论大大提高。这们的模型可以进一步改进的地方。
4. 如果不对我们的模型进行大的变动，又希望可以得到更加优化的结果，可以条件的情况下，借助于商用超级计算机。
5.3问题二
由于按照我们在第一问达到的0.45 的利用率，40 张牛皮生产的沙发数为大把，这道题我们首先是设定程序中生产沙发的数量为7 个，餐椅数量为0 个，运
13 把、14 把、15 把，分别运行程序，对11 张餐椅进行排料，最后发现当生产餐数量为14 把时，使用的牛皮数正好是11 张，已经将所有牛皮用完，而且利用率了50%，在51%-52%之间。利用率有了部分提高。所以我们解决此道问题的最果即为可以增加的餐椅数量为14 把。
5.4 问题三
市场是“一双看不见的手”，它自动发挥着调节作用使市场趋于稳定，站在者一方来考虑，为了获得持续较高的利润，需要不断地根据供求关系，适时的调己的价格。在实际生活中，生产者可通过两种策略来制定、调整产品的价格。一略是根据所获利润来调价，即生产者或以利润目标为中心来制定产品的价格。比生产者出售一种产品的价格为p，由于生意不错，他打算适当提价；提价之后发得利润更大，于是继续提价；但再提价后因价格偏高，顾客减少使其利润下降，又决定适当降价；总之他不断地依利润增减调整产品的价格。另一种基于供需差调价策略，即根据产品供需情况来调价，使产品价格的升降与供需差额成正比。一种产品的需求量D大于供给量S，这将引起该产品的价格上升；反之，如果供求则将引起产品价格下降。在以供需差额为基础的调价策略中，价格的升降与供额成正比。【3】
对于此问题，我们定义价格和市场供需满足如下的关系：
1．本阶段的市场订单由上一阶段的产品定价决定，二者成反比关系；即若月的产品售价较低，则该月的订单数会较上个月有所增加，反之减少。
2．本阶段产品的价格有本阶段产品的供需差额决定，二者成反比关系：当于求时，价格下调；供小于求时，价格上升。
本题中，由于市场上沙发和餐椅的价格没有一个较为统一的标准，我们为和餐椅设定一个基准价格0 p ， 0 q ，每个月份产品的价格调整都是在基准价格上的，例如第i 个月沙发的调整价格i i 0 Δp = p − p 。
沙发第i 阶段的价格与当前阶段供求差额成一反比关系:
0 ( ) i s i i p = p −k S −D --------------------------------------------- 第i 阶段的产品需求量i D 与第i −1阶段的产品定价i 1 p − 有如下关系:
3 2 1
1 1 1 ( ) * * * i i i i i D f p a p b p c p d − − − = = − + − + ----------------------------- 由于我们无法确定每一次厂家生产皮件的增加量，为了简化问题，我们认为每一月的产量都在订单量的基础上增加10%，即
1.1 i i S = D --------------------------------------------------- 则(1)式即可简化为:
3 2
0 1 0 1 0 1 * ( 0.1* ) * ( 0.1* ) * ( 0.1* ) i i i i D a p D b p D c p D d − − − = − − + − − − + ---------- 简化为:
' 3 ' 2 ' '
1 1 1 * * * i i i i D a D b D c D d − − − = + + + ---------------------------- 该式即为要求解的式子，我们选用了2009年的12组数据，代入(6)式得到11元一次方程组，这是一个矛盾方程组，我们利用偏最小二成原理，编写C程序求对于餐椅求解思路一样，其模型如下:
q i= q0 −kc (Si −Di ) ---------------------------------------- 3 2 1
1 1 1 ( ) * * * i i c i c i c i c D f p a q b q c q d − − − = = − + − + -------------------- 程序运行结果如下
b = 0.181208, c = −11.862747 , d = 303.767693 ,并且可以看出这个系数可以很反映出这个月和上个月沙发订单的关系，曲线拟合的很好。然后对比（5）（6）可以得到沙发调整价格时的系数s k ，然后就可以得到第i 个月的沙发价格和基准价系， 进而可以得到沙发合理的价格范围； 同理， 对于餐椅其系a' = 0.000015,b' = 0.012189, c' = 3.895381, d' = −185.101609，比较（7）（8）两式可餐椅调整价格时的系数为c k ，则可得到第i 个月的餐椅价格和基准价格的关系如下，可知合理价格范围为。我们在计算时只选用2009 年的12 组数据，准备用2010 年的三组数据对得的结果进行验证。
六、模型的评价及推广应用
6.1问题一模型
6.1.1模型分析及评价
我们首先分析了现有的一些算法，比如矩形包络法，其基本思想就是用矩形边形将不规则零件包络起来，然后转化为矩形优化排料，由于矩形零件排料算法的比较成熟，接下来就可以选用相应的一些算法进行解决了。这种处理问题的思较好，一般在家具生产等领域都使用这种方法处理。但是这种处理方法有明显的因为牛皮属于比较稀有的原料，价格相对来说比较高，而用矩形包络法得到的结是很优化，也会有很多的原料浪费，因此我们没有选用这种方法；临界多边形法法思想即用用多边形的点和边来表示位置，优点是求解精度高，但存在明显的即算法设计太复杂，执行起来麻烦，而且不能保证得到比较理想的结果；凸包算其平移技术，这种方法是将二维不规则零件的排料问题转化为计算几何问题，要包首先要说凸性的定义，简单点说就是平面邻域中任意两点所在的线段上的点都邻域中，则该邻域具有凸性。简单推敲一下，就可以发现如果邻域中存在一阶导连续的点一定无法被某点集线性表示出来。一般的计算几何问题都是处理的离散形成的平面域，所以我们感兴趣的是怎样找一个包含这个点集的面积最小的凸形，这就是凸包。这种处理方式尚不太成熟，正处于研究阶段，而且要找到一个凸包就是相当麻烦了，而我们需要排的零件较多，而且有两张不一样的牛皮模生产中需要的牛皮数量比较多；针对此题智能优化算法是一种比较好的方法，而些年针对二维不规则零件的优化排料问题，使用智能优化算法研究的比较火热。文献[6]中介绍的在遗传算法的基础上可以用BL 算法、下台阶法、最低水平线法件进行编码并转化为样图，但是我们没有完全照搬这种方法进行解决，我们是基
排料优化过程中我们引入了遗传算法的变异和自然选择的思想进行编程种处理问题的思路比较新颖。
b) 我们在建模的过程中使用PHOTOSHOP CS3 的记录测量工具对所有模板处理，这种方式很好的解决了提供的模板出现的诸多问题，将所有模板统一化处理，并根据计算出的比例得到了餐椅的面积。
c) 我们想到用像素点来对模板进行0-1 编码处理，这种处理方式很方便将矩阵化，然后导入MATLAB 中。
d) 用离散的矩阵表示图形，能够实现正交化，使得每个皮板的摆放只有四位角度，降低了程序的负杂度；并且离散化会比包络矩形的利用率更高缺点：
1. 我们的模型理论上可以使牛皮达到很高的利用率，但由于受到计算机运度的限制，我们最后得到的结果很不理想。
2. 为了提高牛皮的利用率我们可以有两种方式：一、增加零件选择次数；提高像素点数，但由于每一种方式都会大量的增加程序的运行时间，所们不得不缩小这些方面，以降低牛皮利用率为代价来缩短程序运行时间我们首先分析了现有的一些算法，比如矩形包络法的优缺点，然后结合该问具体情况，选择了现有模型。
A．包络矩形法
优点：算法成熟，能够将二维问题转化为一维问题；矩形空间角度仅存在两况，降低了算法的复杂度。缺点：对原料的利用率低，尤其是在本题中牛皮模板规则程度较高的情况下，不容易得到较高的利用率。
B．临界多边形法
优点：用多边形的点和边来表示位置，求解精度高。缺点：算法设计复杂。
C．离散矩阵化
优点：用离散的矩阵表示图形，能够实现边的正交化，使得每个皮板的摆放四种方位角度，降低了程序的负杂度；并且离散化会比包络矩形的利用率更高。矩阵的阶数比较大，会使算法的时间复杂度比较大。
综合上述分析，我们最终选取离散矩阵化方法来求解。
6.1.2推广应用
1. 问题一模型适用于建议一个使用计算机对带有复杂逻辑判断的实际问题进行简单而有效的算法。这个算法理论上可以出现最优解，但根据实际情况需要的时间。本题中由于计算量过于巨大，排样的变异种类过多使得这个计算耗多，要是换做别的计算量较小的实际问题，我们给出的算法还是有很大的实用价值。
2. 基于遗传算法的计算机模拟算法可以在条件允许的情况下避免对个体间实际间不清楚的实际问题进行处理。避免对个体间关系的复杂的考虑分析是以大计算为代价的。
6.2问题三模型
6.2.1模型分析
针对本问建立的基于市场供需差额的调价模型是基于市场经济的自动调价建立的，具有很强的现实意义。模型对市场环境进行了粗略的模拟，分别构造了格变化的需求函数和随供需差额变化的价格函数；通过历史数据进行拟合估计，出两个函数的具体参数。缺点本题中忽略了市场中存在竞争情况和复杂的消费理，仅建立了一个简单的价格随供求差额改变的模型。因此我们的模型比较粗后也没有得到结果。
七、参考文献
[1] 计华,刘弘．优化排料算法的研究与实现．小型徽莹计算机系统．2001 年3 [2] 张英杰．二维不规则零件自动排料的优化算法．机械设计与研究．2009 年[3] 胡振华，聂艳晖．基于供需差额的调价策略的鲁棒性研究．管理工程学报．年第三期
[4] 唐玉霞．论导数在经济分析中的应用．财经管理．2009.7 上月刊
[5] 彭文丽等．优化排料算法的研究现状与趋势．模具工业．2006 年第32 卷第[6] 曹新明，蒋瑞斌．不规则零件最小包络矩形的求解研究．科技通报．2007 年第23 卷第一期
八、附录文件
[1].模板像素化处理结果；
[2].matlab 程序源代码；
[3].模板理论像素点数；
[4].曲线拟合程序代码；
[5].程序的运行结果；保存在MATLAB 的工作空间中，见附录文件中：
第一问.mat 第二问(1).mat 第二问(2).mat 的以date 命名的结构体当中其中是以0-1 矩阵形式表示的排列好的模版，date.precise 排好的模版的利用率
