天然肠衣的分配问题.doc

天然肠衣搭配模型 摘要 本文讨论了天然肠衣搭配问题，在模型合理假设下，将三种不同规格成品分开单独计算，并同时考虑三个要求：组装出的成品捆数越多越好；对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；在三十分钟内得到结果。由此得到各规格满足的约束条件，并将要求进行合理的转化，建立了整数线性规划模型，将完美的理论最优解代之以实用的局部最优解。通过相关的软件分析与计算，如lingo与C++编程语言计算得到既满足精度又满足计算量限制的搭配方案。这样既减少了劳动强度、又能提高原料使用率。 通过求解可以得到规格一最大捆数为14捆，原料的利用率为95.11%，剩余原料共10根；规格二最大捆数为36捆，原料的利用率为88.38%，剩余原料共55根；规格三最大捆数为128捆，原料的利用率为93.57%，剩余原料共35根。三种规格总的最大捆数为178捆，总体利用率92.58%。所得到的分配方案利用率较高。 与将计算过程分解为多个子问题相比，本文结合“试探法”的算法得到的方案更加接近最优，且同时也能满足时间上的要求。 关键词：整数线性规划 离散优化 lingo 一.问题重述 天然肠衣加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。这种方式很大程度上依赖于员工的经验，且随机性较大，很难保证原料的利用率，造成了较多的浪费。 某公司实际加工时，原料按长度分档，成品按原料根数和总长度分为三种不同规格。为了提高生产效率，该公司计划先丈量所有原料，建立一个原料表。根据成品和原料描述，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。这样既可以减少劳动强度、又能提高原料使用率。公司对搭配方案的要求为： 对于给定的一批原料，装出的成品捆数越多越好； 对于成品捆数相同的方案，最短长度最长的成品越多，方案越好； 为了食品保鲜，要求在30分钟内产生方案。 二.问题分析 不同规格的肠衣根数和总长度的要求不同，而且满足某一确定规格的档次搭配方式也有多种。在建立数学优化模型时，主要考虑采用何种组装方式进行搭配才为最优方案，从而使得公司在天然肠衣的组装过程中的效率提高，并满足实际情况的要求。 本问题实质上类似于装箱问题，均为整数线性规划。 公司的要求可以分为三个层次理解。对于所定给的不同档次等级的肠衣数量，首先要求达到最终组装的成品捆数越多越好，这是最基本的利益最大化要求。其次在这个条件上，若多个方案的成品捆数相同，最短长度最长的成品数量越多，高档次的肠衣利用率越高，方案越好。要求在30分钟内产生方案是为了保证食品保鲜，减少损失。 对于第一个要求，各档次原料应满足相应规格条件的约束以及原料总量的限制，且使成品捆数最大。由于三种规格的成品之间无相互关联，一次因此可以分解为依次分别求各个规格捆数的最大值，结果直接相加为最终结果。这可以通过建立满足相关要求的线性规划模型，使用软件编程求解得到。 对于第二个要求，可以在满足条件一的情况下，进行筛选，使得最短长度最长的成品数量尽量多。但是对于满足规格条件的肠衣搭配方式太多，通过C++编程计算可以得到第一种规格成品的组合方式一共有15646种，若要在其中进行筛选，难度相当大且很难满足第三个时间上的要求。于是把条件二和条件一综合考虑，将最短长度最长的成品最多的要求，转化为剩余原料尽量少。从而将一个从理论上精确但难以实现的最优目标转化为可行的优化目标。虽然结果的精度没有直接筛选高，但是能在有限时间内完成分配方式的产生。 对于第三个要求，优化算法可以节约计算时间。 三.模型假设 1、每类原料不能进行进一步裁剪； 2、每类原料只能用于一种规格的组装； 3、原料在计算得到方案期间不存在任何变质损失； 四.符号说明 符号 符号说明 备注或单位 第规格成品第档原料的根数 根 第规格成品第档原料的长度 米 第一种规格成品第捆第种原料的根数 根 第二种规格成品第捆第种原料的根数 根 第三种规格成品第捆第种原料的根数 根 第规格成品最大捆数 捆 总的成品最大捆数 捆 五.模型建立 5.1数据分析 为了使得捆数最大， 首先对所给数据进行分析计算。根据原料已知数据以及原料规格上的要求可以按可能的最大值估算。 规格一的可能最大捆数应满足以下约束： 可能最大捆数乘以每捆长度89不大于所有原料的总长度； 可能最大捆数乘以每捆根数20不大于所有原料的总根数； 可能最大捆数为整数； 即可能最大捆数为： 同样对于其他两种规格类似处理可得： 5.2模型建