2018年全国大学生数学建模大赛D题及三篇优秀论文精选

2018年高教社杯全国大学生数学建模竞赛D题目及优秀论文D题汽车总装线的配置问题一．问题背景某汽车公司生产多种型号的汽车，每种型号由品牌、配置、动力、驱动、颜色5种属性确定。品牌分为A1和A2两种，配置分为B1、B2、B3、B4、B5和B6六种，动力分为汽油和柴油2种，驱动分为两驱和四驱2种，颜色分为黑、白、蓝、黄、红、银、棕、灰、金9种。公司每天可装配各种型号的汽车460辆，其中白班、晚班（每班12小时）各230辆。每天生产各种型号车辆的具体数量根据市场需求和销售情况确定。附件给出了该企业2018年9月17日至9月23日一周的生产计划。公司的装配流程如图1所示。待装配车辆按一定顺序排成一列，首先匀速通过总装线依次进行总装作业，随后按序分为C1、C2线进行喷涂作业。图1汽车总装线的装配流程图二．装配要求由于工艺流程的制约和质量控制的需要以及降低成本的考虑，总装和喷涂作业对经过生产线车辆型号有多种要求：（1）每天白班和晚班都是按照先A1后A2的品牌顺序，装配当天两种品牌各一半数量的汽车。如9月17日需装配的A1和A2的汽车分别为364和96辆，则该日每班首先装配182辆A1汽车，随后装配48辆A2汽车。（2）四驱汽车连续装配数量不得超过2辆，两批四驱汽车之间间隔的两驱汽车的数量至少是10辆；柴油汽车连续装配数量不得超过2辆，两批柴油汽车之间间隔的汽油汽车的数量至少10辆。若间隔数量无法满足要求，仍希望间隔数量越多越好。间隔数量在5-9辆仍是可以接受的，但代价很高。（3）同一品牌下相同配置车辆尽量连续，减少不同配置车辆之间的切换次数。（4）对于颜色有如下要求：1）蓝、黄、红三种颜色汽车的喷涂只能在C1线上进行，金色汽车的喷涂只能在C2线上进行，其他颜色汽车的喷涂可以在C1和C2任意一条喷涂线上进行。2）除黑、白两种颜色外，在同一条喷涂线上，同种颜色的汽车应尽量连续喷涂作业。3）喷涂线上不同颜色汽车之间的切换次数尽可能少，特别地，黑色汽车与其它颜色的汽车之间的切换代价很高。4）不同颜色汽车在总装线上排列时的具体要求如下：（a）黑色汽车连续排列的数量在50-70辆之间，两批黑色汽车在总装线上需间隔至少20辆。（b）白色汽车可以连续排列，也可以与颜色为蓝或棕的汽车间隔排列；（c）颜色为黄或红的汽车必须与颜色为银、灰、棕、金中的一种颜色的汽车间隔排列；（d）蓝色汽车必须与白色汽车间隔排列；（e）金色汽车要求与颜色为黄或红的汽车间隔排列；若无法满足要求，也可以与颜色为灰、棕、银中的一种颜色的汽车间隔排列；（f）颜色为灰或银的汽车可以连续排列，也可以与颜色为黄、红、金中的一种颜色的汽车间隔排列；（g）棕色汽车可以连续排列，也可以与颜色为黄、红、金、白中的一种颜色的汽车间隔排列。（h）关于其他颜色的搭配，遵循“没有允许即为禁止”的原则。由于该公司的生产线24小时不间断作业，以上总装线和喷涂线的各项要求对相邻班次（包括当日晚班与次日白班）的车辆同样适用。三．需要解决的问题（1）根据问题的背景、装配要求以及附件中的数据，建立数学模型或者设计算法，使其能给出符合要求、且具有较低生产成本的装配顺序。（2）根据（1）中的数学模型或算法，针对附件中的数据，给出你们的计算结果：（a）将9月20日的装配顺序按照下表格式填写在表中，并将此表放在论文的附录中。9月20日的装配顺序装配顺序品牌配置动力驱动颜色喷涂线123……460（b）按照上表的格式给出9月17日至9月23日每天的装配顺序，文件以“schedule.xlsx”命名，作为论文的支撑材料与论文同时提交。优秀论文第一篇汽车总装线配置的优化模型研究第二篇汽车总装线配置方案第三篇确定汽车装配顺序问题的算法1汽车总装线配置的优化模型研究摘要生产具有品牌、配置、动力、驱动、颜色等属性的多种型号的汽车，对总装线和喷涂线上的装配顺序各项提出了各种不同形式的要求，而且不同的装配顺序造成的生产成本也不尽相同。本文主要通过建立数学模型并设计算法，给出符合生产要求、且具有较低生产成本的装配顺序。首先是数据处理，使用python将原附件数据中的生产计划整理成方便数据读取的规范形式，设计Excel表格存储每日的装配顺序，并与生产计划数据联动形成相互校验，保证装配顺序的准确性；接着，通过分析总装线和喷涂线的各项要求，根据汽车的颜色分类情况，先将黑色的汽车手工填入装配顺序表。在确定一些初值后，减小装配顺序问题求解的搜索规模后，建立生产成本最小优化模型，再使用计算机搜索四驱、柴油汽车等关键属性汽车的位置；然后，配置白色和棕色等可以连续排列的颜色，此时注意蓝色汽车只能与白色间隔等关键要求，尽可能多地将这些汽车连续地填入装配顺序表；最后，装配顺序表中通常只含有数量不多的连续空余位置，对应着剩余尚未分配的、颜色成分复杂的汽车。按照颜色是否符合在总装线上排列时的具体要求，将符合颜色衔接要求的汽车作为顶点相互连接起来，构成了一个有向图，装配顺序的问题转化成了图的遍历问题。使用基于遗传算法的TSP问题和广度优先搜索算法搜索有向图中经过指定起点和终点的所有路径。采用Matlab验证各个路径上的特殊颜色能否按顺序分配在指定的C1或C2喷涂线上，计算各种路径上切换配置和颜色的代价，并且取代价最小的路径填入装配顺序表。本文在进行充分的理论分析的基础上，综合利用多种计算机工具，在计算结果展示、人工经验介入、计算过程衔接方面取得了较好效果。关键词：汽车装配顺序优化模型邻接矩阵路径搜索遗传算法TSP问题21.问题的重述某汽车公司生产以下型号的汽车，每种型号由品牌、配置、动力、驱动、颜色5种属性确定。品牌分为A1和A2两种，配置分为B1、B2、B3、B4、B5和B6六种，动力分为汽油和柴油2种，驱动分为两驱和四驱2种，颜色分为黑、白、蓝、黄、红、银、棕、灰、金9种。公司每天可装配各种型号的汽车460辆，其中白班、晚班（每班12小时）各230辆。每天生产各种型号车辆的具体数量根据市场需求和销售情况确定。待装配车辆按一定顺序排成一列，首先匀速通过总装线依次进行总装作业，随后按序分为C1、C2线进行喷涂作业。由于工艺流程的制约和质量控制的需要以及降低成本的考虑，总装和喷涂作业对经过生产线车辆型号有多种要求。1.1装配要求1.每天白班和晚班都是按照先A1后A2的品牌顺序，装配当天两种品牌各一半数量的汽车。2.四驱汽车和柴油汽车连续装配数量不得超过2辆，并且两批之间间隔的汽车的数量至少是10辆。若间隔数量无法满足要求，仍希望间隔数量越多越好。间隔数量在5-9辆仍是可以接受的，但代价很高。3.黑色汽车连续排列的数量在50-70辆之间，两批黑色汽车在总装线上需间隔至少20辆。4.装配线上的汽车颜色间隔需要满足一定的规则。1.2喷涂要求1.蓝、黄、红三种颜色汽车的喷涂只能在C1线上进行，金色汽车的喷涂只能在C2线上进行。2.喷涂线上不同颜色汽车之间的切换次数尽可能少，黑色汽车与其它颜色的汽车之间的切换代价很高。1.3需要解决的问题1.建立数学模型或者设计算法，使其能给出符合要求、且具有较低生产成本的装配顺序。2.给出9月17日至9月23日每天的装配顺序。32.问题的假设1.生产成本只是由题目中所指的装配线上不同汽车配置切换、喷涂线上不同汽车颜色的切换构成。汽车配置切换和普通的颜色切换代价设为1，黑色切换为其他颜色成本耗费较高，设为10。2.在无法满足柴油、四驱汽车的批次间隔k至少是10的情况下，间隔k必须大于5，而且间隔越小代价越高，设为10-k。3.9月23日A1和A2品牌数量为奇数，在尽可能均衡的情况下，允许白班和晚班装配的汽车数量相差1辆。4.在考虑不同工作日的装配顺序时，总装线和喷涂线的各项要求对当日晚班与次日白班交接同样适用。5.不考虑其他主观或其他题目中未涉及的因素。3.符号的说明符号含义𝐼A1品牌下标集合，如20日𝐼={1,⋯181,231,⋯,411}𝐽A2品牌下标集合，如20日𝐽={182,⋯230,412,⋯,460}𝑥𝑘𝑘是黑车𝑥𝑘=1，否则𝑥𝑘=0，𝑘∈𝐼⋃𝐽𝑦𝑘𝑘是四驱车𝑦𝑘=1，否则𝑦𝑘=0，𝑘∈𝐼⋃𝐽𝑧𝑘𝑘是柴油车𝑧𝑘=1，否则𝑧𝑘=0，𝑘∈𝐼⋃𝐽4.问题的分析与数据处理4.1问题的分析题目所要解决的最终问题是每天460个汽车装配的顺序，初步估算寻求可行解的问题规模，460的阶乘是一个1027位数。即使可以设计精巧的约束条件建立通用的数学模型，但在使用计算机搜索可行解时可能会遇到无法及时给出答案的问题。4通过分析9月17日至9月23日每天的生产计划可以发现，所产汽车的颜色可以分为黑色、白色与棕色、其他数量较少的颜色等三种情况。根据总装线和喷涂线的各项要求，这几种颜色的汽车有着如下的不同特征：黑色汽车需要连续生产，尽量不要与其他颜色切换，除非付出较高代价切换成其他颜色白色、银色、灰色或棕色可以连续排列且有时数量较多，特别是棕色可以与许多的其他颜色切换其他颜色数量较少，却有复杂的切换规则根据以上特征，尝试以下逐步按顺序求解的过程首先，手动排黑色汽车的装配位置，此时尽可能按顺序排列相同配置的汽车，在确定一些初值后，再使用计算机搜索四驱、柴油汽车等较少量的特殊属性汽车的位置；接着，配置白色和棕色等可以连续排列的颜色，此时注意蓝色汽车只能与白色间隔；最后，剩余未确定配置顺序的颜色数量较少，并且因为以上两步都是连续排列的，只需将它们按一定的顺序排在剩余的连续空间内，可以使用计算机直接搜索可能的顺序。4.2数据处理以上过程需要计算机搜索和手工介入同步进行，需要设计合适的表格对数据整理。python中的模块xlwt和xlrd可以方便快捷地读写、操纵excel单元格，将附件“CUMCM-2018-Problem-D-Chinese-Appendix.xlsx”中的生产计划数据整理成规范形式，程序文件名“problem_D_Data.py”，具体见附件1-2。设计有关表格如下。表1是使用python整理得到的生产计划表（数据文件夹中excel文件“schedule.xlsx”的“sheet1”表单），列举了每日所有不同种类汽车的生产数量，添加的最后一列“装配剩余”使用以下公式，统计还没安排装配顺序的剩余汽车数量（以9月17日为例）。H2=G2-COUNTIFS('9.17'!A:A,sheet1!A2,'9.17'!C:C,sheet1!B2,'9.17'!D:D,sheet1!C2,'9.17'!E:E,sheet1!D2,'9.17'!F:F,sheet1!E2,'9.17'!G:G,sheet1!F2)5表1生产计划表表2是9月17日的装配顺序（数据文件夹中excel文件“schedule.xlsx”的“9.17”表单，其他日期的表单类似），在喷涂线后添加了“装配代价”、“喷涂代价”、“其他代价”、“总代价”、“装配校验”、“喷涂校对”等列，对应公式和作用如下装配代价：统计同一品牌下，装配线上不同汽车配置切换代价I5=IF(C5=C4,1,0)*IF(D5D4,1,0)喷涂代价：统计喷涂线上的颜色切换代价，其中黑色切换为10J5=IF(G3=黑,10,1)*IF(G5G3,1,0)其他代价：柴油和四驱汽车的批次间隔k小于10，代价为10-k特殊情况总代价：累计以上三种代价L2=SUMIF(A:A,A2,I:I)+SUMIF(A:A,A2,J:J)+SUMIF(A:A,A2,K:K)6装配校对：校对装配顺序中的配置是否是出现在计划表中的有效配置O5=COUNTIFS(sheet1!A:A,'9.17'!A5,sheet1!B:B,'9.17'!C5,sheet1!C:C,'9.17'!D5,sheet1!D:D,'9.17'!E5,sheet1!E:E,'9.17'!F5,sheet1!F:F,'9.17'!G5)喷涂校对：校对装配顺序上的汽车是否交替分配到喷涂线C1和C2上P5=IF(H5=H3,1,0)表29月17日的装配顺序上述设计的表格在整理装配