《天然肠衣的搭配问题(3).doc》由会员分享，可在线阅读，更多相关《天然肠衣的搭配问题(3).doc（10页珍藏版）》请在金锄头文库上搜索。
1、天然肠衣的搭配问题摘要本文针对肠衣原料的搭配方案问题，为保证原料使用率，首先对三种规格的产品进行排序，并用枚举法，简化工序，在满足生产条件的基础上给出快速的一系列可行方案组。 在文中第二部分，我们用遗传算法，利用枚举法所得到的可行解作为初始种群，编制在给定的材料下，以成品捆数为基数的适应函数。同时，设计了种群的选择、交叉及变异，使种群在遗传过程中，快速有效的寻找出最可行方案组。 最后，我们针对文中给出来的具体数据计算，利用遗传算法得到一些最优的原料搭配方案组合，并得到给定：A规格的产品的最多捆数为14捆；B规格的产品的最多捆数为44捆； C规格的产品的最多捆数为132捆。关键词：遗传算法、搭配
2、问题、最优化、matlab7一、 问题重述 天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。 为了提高生产效率，降低成本，某公司计划改变组装工艺，先丈量所有原料的长度，然后设计一个原料搭配方案投入实际生产。 表1最短长度最长长度根数总长度36.52089713.588914589表1给出三种规格产品生产的原料根数和长度范围；表2提供了现有原材料的根数和长度。根据这些要求和现有原料的相关信息，我们需要采用数学模型的方法提出
3、符合以下的要求的生产方案；（1） 对于给定的一批原料，装出的成品捆数越多越好；（2） 对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；（3） 为提高原料的使用率，总长度允许有0.5米的误差，总根数允许比标准少1根；（4） 某种规格对应原料如果出现剩余，可降级使用，如长度为14米的原料可以和长度介于713.5米的进行捆扎，成品属于713.5米的规格；（5） 为了食品保鲜，要求在30分钟内产生方案。 二、 问题分析及符号说明 根据要求，为了食品保鲜，要求在30分钟内产生有效肠衣搭配方案，我们先做如下符号说明：A ：表示肠衣长度范围在36.5米范围的规格产品；B ：表示肠衣长度范围在713
4、.5米范围的产品产品；C ：表示肠衣长度范围在14米范围的产品产品；：表示各分档原材料的长度，以0.5米为一档；:表示满足生产条件的可搭配方案； ：表示某一个满足生产条件可搭配方案中第个分档原料的提取的根数； : 各种分档原料所对应的根数。表2长度3-3.43.5-3.94-4.44.5-4.95-5.45.5-5.96-6.46.5-6.9根数4359394127283421长度7-7.47.5-7.98-8.48.5-8.99-9.49.5-9.910-10.410.5-10.9根数2424202521232118长度11-11.411.5-11.912-12.412.5-12.913-1
5、3.413.5-13.914-14.414.5-14.9根数3123225918253529长度15-15.415.5-15.916-16.416.5-16.917-17.417.5-17.918-18.418.5-18.9根数3042284245495064长度19-19.419.5-19.920-20.420.5-20.921-21.421.5-21.922-22.422.5-22.9根数526349352716122长度23-23.423.5-23.924-24.424.5-24.925-25.425.5-25.9根数060001为设计高效的原料搭配方案，我们根据文中要求（4），对A、B
6、、C三种可搭配生产规格排一个序，先考虑C规格肠衣的搭配方案，再考虑B及A的搭配方案，这样可以减少剩余原料，尽可能满足实际给出原料的搭配方案组合，使装出成品的捆数越多。三 模型的分析与建立3.1 搭配策略初步分析 我们观察表2，C规格肠衣的原料有24个分档，要从24个分档中找出符合要求的搭配方案是不现实的（共有种组合方式）。为提高解题效率，我们先考虑约束条件，如下： 设（）为满足生产C规格肠衣条件的某一组方案，则需满足： （1）这是一个整数规划问题，本文即是要找出最优的搭配方案策略，使得既有实际的可操作性，又能尽可能使在给定的原料下，装出的成品捆数越多越好。考虑到实际操作，在短时间内给出可行搭配
7、方案并提高生产效率，我们尽可能使用到的搭配方案所用到的原料尽可能少，先对使用两种原料搭配的方案进行分析，然后再考虑三种及三种以上搭配方案。对只用两种原料的搭配方案，我们可用枚举法来分析，我们计算出，C规格用两种原料进行搭配的可行方案共有36种。然后再比较这36种条件的优劣，找出最优的搭配组合方案。找出的搭配组合方案需要尽量满足下面几个条件：（1） 组合策略要在给定原料下，装出的成品捆数越多；（2） 对于成品捆数相同的方案，最短长度最长的成品越多，方案越好； 枚举法对于搭配组合较少的情况下容易处理，但不具有一般性，对基数大的组合方案是不好处理的，为此我们对于三种以上原料搭配方案我们采用遗传算法来
8、筛选最优的搭配策略。3.2 遗传算法模型【1】 遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法。和传统的搜索算法不同，遗传算法从一组随机产生的初始解，称为“种群”。种群中的每个个体是问题的一个解，称为“染色体”。这些染色体在后续迭代中不断进化，称为“遗传”。在每一代中用“适值”来测量染色体的好坏。生成的下一代染色体，称为后代。后代是由前一代染色体通过交叉或者变异运算形成的。根据适值的大小选择部分后代，淘汰部分后代，从而保持种群大小是常数。适值高的染色体被选中的概率较高。这样，经过若干年代之后，算法收敛于最好的染色体。（1） 种群的选取 初始种群的选取至关重要，我们采用两种方式来选取种群
9、。第一，通过前面初步分析，我们用枚举法列出一些较优的可行搭配方案作为一部分初始种群；另外一部分则通过随机数来产生（满足（1）式的条件）。用pop记为种群，pop_size 表示种群数。通过matlab【2】编制程序pop=pop_cy(L,G,pop_size)实现。（2） 适应函数的建立 我们评估初始种群（搭配方案）的优劣主要是2个方面，:一是给定原料下，装出的成品捆数多；二是成品捆数相同的方案，最短长度最长的成品越多越好。基于这两点我们构造适应函数： （2） 利用matlab软件【3】编制适应函数程序pop=pop_cy(L,G,pop_size)实现。（3） 选择过程 步骤1：在0, 1
10、区间内产生一个均匀分布的随机数。 步骤2：计算适应值函数，对初始种群进行估值并按优劣排序。 步骤3：按概率比照随机数选择种群交叉及变异，并构造新的种群。 通过以上过程我们编制遗传算法程序对上面的模型进行计算。具体数据如下表3： 表3 C规格原料表1414.51515.51616.51717.51818.51919.53529304228424549506452632020.52121.52222.52323.52424.52525.549352716122060001通过程序计算C规格的原料得到：表4 C规格的最优搭配方案 方案使用材料捆数=1, =1, =2, =132=1,=1, =2,
11、=126=1, =2, =1,=124=2, =2, =116=2, =1, =211=2, =1, =28=1, =3, =16=3, =14=2, =1, =1, =12=1, =2, =1, =12=1, =2, =21剩料=1， =1，=1，=1，=11，=5，=1132如表4，所描述的搭配方案，可以使C规格的产品的捆数最多为132捆，剩料最少。剩下的材料根数；根据要求四，为节约原材料我们可以将这些剩余的材料降级同B规格的原料使用。 表5 B规格原料表77.588.599.51010.51111.5242420252123211831231212.51313.51417.52020.5
12、2125.52259182511111513.3 B及A规格原料搭配优化方案 B及A规格原料搭配优化方案的处理方法与C规格所用的算法是一致的；利用表5所给的数据运行遗传算法程序得到下表6表6 B规格的最优搭配方案方案使用材料捆数148754111111剩料44如表6所示，通过程序运算获得最优搭配方案，使B规格的捆数最多为44捆，剩料最少。剩下的材料根数；根据要求四，为节约原材料我们可以将这些剩余的材料降级同A规格的原料使用。表7 A规格的原料表33.544.555.566.543593941272834217.588.591010.51115.5841021211同理，运用遗传算法，运算表7的数据得到表8。表8 A规格的最优搭配方案方案使用材料捆数=9, =1, =6, =46=7,=7, =6, 5=1, =2, =3,=132=6, =1, =,3，=101剩料14如表8所示，使A规格的产品的捆数最多为14捆，剩料最少。剩下的材料根数。表9 最终剩料55.566.5711842127.58.599.57331六、 模型的优缺点评价6.1 模型的优点：本论文主要特色是运用
