天然肠衣搭配问题的优化模型

1天然肠衣搭配问题的优化模型摘要我们国家天然肠衣的出口量占世界首位，产品加工的过程就尤为重要。为了提高生产效率，要把肠衣进行最佳的搭配。本文主要解决的问题是设计一个最佳的肠衣搭配方案使其最大程度的满足公司的要求。对此，我们建立了基于线性规划的优化模型。通过分析得出，公司首先希望对于现有原料能得到的成品捆数最多，在此基础上尽量使最短长度最长的成品的数量最多。由此，我们在保证捆数最大情况下，进一步优化模型，满足了公司的该项要求。第一步，确定各规格捆数的最大理论值：利用题目中的数据，采用极限取值法容易计算出各种规格成品捆数的理论最大值。因为会有降级使用的可能，所以可将理论值适当扩大，作为下一步规划模型中的捆数上限。第二步，确定各规格的最大捆数及相应分配方案：以捆数上限作为总捆数，用零一变量对实际成立的捆数进行计数，这样，就可以以零一变量的最大总和作为目标函数，在满足成品规格条件下，建立了优化模型。利用该模型，对于所给数据，分别计算出各种规格成品的最大捆数及具体分配方案。计算时，因为考虑到规格高的肠衣可以降级使用，所以先从规格最高的原料进行搭配，将其剩余原料归到下一规格中，按该规格最长的肠衣计数，利用LINGO软件依次计算出了每种规格的最大捆数，并给出了具体搭配方案：第三种规格的成品的最大捆数为3135n捆，第二种规格的成品的最大捆数为239n捆，第一种规格的成品的最大捆数为117n捆，总计123191nnn捆。具体的分配方案见附表。第三步，在捆数最多的基础上，考虑使成品捆数中最短长度最长的捆数最多，建立了优化模型：在捆数为最大的前提下，以每捆出现的最短长度之和最大为目标函数，以满足成品规格条件为约束，建立新的规划模型，实现使成品中最短长度最长的最多的要求。并对实际数据进行了求解，得到了最优解，给出了具体分配方案。关键词：线性规划优化模型LINGO2一、问题重述天然肠衣（以下简称肠衣）制作加工是我国的一个传统产业，出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段（原料），进入组装工序。传统的生产方式依靠人工，边丈量原料长度边心算，将原材料按指定根数和总长度组装出成品（捆）。原料按长度分档，通常以0.5米为一档，如：3-3.4米按3米计算，3.5米-3.9米按3.5米计算，其余的依此类推。表1是几种常见成品的规格，长度单位为米，∞表示没有上限，但实际长度小于26米。表1成品规格表最短长度最大长度根数总长度36.52089713.588914∞589为了提高生产效率，公司计划改变组装工艺，先丈量所有原料，建立一个原料表。表2为某批次原料描述。表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-13.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根据以上成品和原料描述，设计一个原料搭配方案，工人根据这个方案“照方抓药”进行生产。公司对搭配方案有以下具体要求：(1)对于给定的一批原料，装出的成品捆数越多越好；(2)对于成品捆数相同的方案，最短长度最长的成品越多，方案越好；(3)为提高原料使用率，总长度允许有±0.5米的误差，总根数允许比标准少1根；(4)某种规格对应原料如果出现剩余，可以降级使用。如长度为14米的原料可以和长度介于7-13.5米的进行捆扎，成品属于7-13.5米的规格；(5)为了食品保鲜,要求在30分钟内产生方案。请建立上述问题的数学模型，给出求解方法，并对表1、表2给出的实际数据进行求解，给出搭配方案。3二、模型假设1.上一规格分配中出现的剩余原料，全部看做下一规格的最长原料；2.给定的原料中没有因破损，导致不能扎捆的；3.原料丈量准确，数据完全可靠；4.按原料长度由短到长依次标以1——46档次；5.每种档次原料皆以该档最小长度为计算长度；三、符号说明n：每种规格的求出的最多捆数；ix：第i档次原料使用的总根数，(1,,46i)；ia：第i档成品的计算长度，(1,,46i)；jks：0-1变量，1代表第j捆存在，0代表不存在；ic：第i种成品规格中每捆成品的标准长度，(1,2,3i)；ig：第i种成品规格中每捆原料的标准根数，(1,2,3i)；m：某种成品规格的档次上限；f：某种成品规格的档次下限；h：某种成品规格的最大捆数；ijy：第i档成品在第j捆中的数目；ijk：当0ijy时，取值为100；当0ijy时，取值为1。四、问题分析为了求给定原料搭配出的最多捆数，以及每捆如何分配，我们采用了线性规划进行优化，利用0-1变量，建立模型，并用LINGO软件和表格进行求解。首先，确定出每种成品规格所扎捆数的上限，即用各档总长的和除以每捆总长度的下限88.5，考虑剩余材料降级使用的问题，所以可将上限适当放宽。首先，在给定原料的情况下，使装出的成品捆数最多。把捆数上限作为总捆数，以成品捆数最多为目标，用每捆的总根数和总长度为约束，利用0-1变量（当此捆存在时为1，不存在时为0）对实际成立的捆数进行计数，这样，就可以以零一变量的最大总和作为目标函数，建立数学模型，计算出捆数的最大情况。但是，考虑到最大限度的利用原料，即当某种规格的对应原料出现剩余时，可以降级使用的情况，我们采用对各种规格的成品依次按照由高到低方法进行规划计算，即：在对表1、表2给出的实际数据进行求解时，先对表1中第三种规格中的数据进行处理，用LINGO软件求解，即可得出原料的剩余情况，然后再将剩余的原料根数全部加到下一级长度最大的原料里计算第二种规格的分配情况，以此类推，即可算出各个规格的成品搭配方案。其次，当成品捆数相同时，最短长度最长的成品越多，方案越好。基于这一条件，在捆数为最大的前提下，以每捆出现的最短长度之和最大为目标函数，仍以满足成品规格条件为约束，建立新的规划模型，实现使成品中最短长度最长的最多的要求。并且对表1、表2中的所给数据进行求解，可得出最优方案。五、模型建立与求解41.第一步：为了使得在原料给定的条件下，装出的成品捆数最多。应用线性规划的方法，求得在捆数最多的情况下原料的搭配方案。利用模型对所给数据求解前，先确定一下捆数的理论上限，即用各档总长的和除以每捆总长度的下限88.5所得的值。考虑到原料的充分利用，以及剩余材料降级使用的情况，可适当放宽上限。对成品规格进行规范化处理，得到数据如表5、表6、表7所示，其中档次号为原料按长度划分的不同的档，档次号随划分长度的递增而增大。表5第一种成品规格的各种数据档次号实际长度计算长度根数各档总长13-3.434312923.5-3.93.559206.534-4.443915644.5-4.94.541184.555-5.452713565.5-5.95.52815476-6.463420486.5-6.96.521136.5总数12921305.5表6第二种成品规格的各种数据档次号实际长度计算长度根数各档总长97-7.4724168107.5-7.97.524180118-8.4820160128.5-8.98.525212.5139-9.4921189149.5-9.99.523218.51510-10.410212101610.5-10.910.5181891711-11.411313411811.5-11.911.523264.51912-12.412222642012.5-12.912.559737.52113-13.413182342213.5-13.913.525337.5总数23543705.5表7第三种成品规格的各种数据档次号实际长度计算长度根数各档总长2314-14.4143549052414.5-14.914.529420.52515-15.415304502615.5-15.915.5426512716-16.416284482816.5-16.916.5426932917-17.417457653017.5-17.917.549857.53118-18.418509003218.5-18.918.56411843319-19.419529883419.5-19.919.5631228.53520-20.420499803620.5-20.920.535717.53721-21.421275673821.5-21.921.5163443922-22.422122644022.5-22.922.52454123-23.423004223.5-23.923.561414324-24.424004424.5-24.924.5004525-25.425004625.5-25.925.5125.5总数367712159.5通过分析可确定第一种成品规格的上限不超过25，第二种成品规格的上限不超过50，第三种成品规格的上限不超过138。第二步：以捆数最多为目标函数，此捆是否存在为0-1变量，此捆存在时为1，不存在时为0。建立的数学模型如下所示：1maxhjjks6.st1*(1)(1)10000.5)0.5)(1,,)0,1,mijjiifmijijifmijijiifmijiijifhijijjijyksgygksyakscyacksjhyxjksjyN第捆不存在第捆存在模型中可利用LINGO软件求解。因为当某规格对应的原料出现剩余时，可降级使用。所以在对实际数据进行处理时，应先从第三种规格的数据开始。若出现剩余，则把剩余的根数加到下一级长度最长的原料中。由表2可知第三种成品规格的捆数上限为138，再将表1、表2中的数据代入模型中可得：1381maxjjzks.st46234623462346231381*5(1)100089.511380,1,ijjiijjiijijiijijiijijjijyksyksyaksyaksjyxjksjyN第捆不存在第捆存在利用LINGO软件可以解出原料装出的第三种成品规格的捆数为135捆，具体分配方案见附表一。同时原料使用和剩余根数如表8：7表8原料使用和剩余根数档次原料根数使用根数剩余根数2335350242929025303002642420272827128423482945450304949031505003264640335252034636303549490363535037272703816160391212140220410004266043000440004500046110总值6776689然后，将剩余的原材料的根数9加到下一级长度最长的原料中，计算第二种成品规格的捆数及分配方案的方法，和计算第三种成品规格的捆数及分配方案的方法相同。把第三种捆扎成品所剩的原料加到下一级长度最长的原料中。将数据代入模型中可得：501maxjjzks82292292292295015022221*8(1)100089.59,190,1,