2018年国赛高教杯数学建模
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）每天白班和晚班都是按照先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日的装配顺序按照下表格式填写在表中，并将此表放在论文的附录中。
（b）按照上表的格式给出9月17日至9月23日每天的装配顺序，文件以“schedule.xlsx”命名，作为论文的支撑材料与论文同时提交。
整体求解过程概述(摘要)
汽车是当前运用最为广泛的交通工具。为了减少汽车的生产成本以及能方便得出汽车生产线上的装配顺序，需对原有的汽车生产线进行优化。本文针对工艺要求、质量控制的需要和成本，关于调整生产线上的汽车品牌、颜色等顺序，设计了确定汽车装配顺序问题的算法。
针对问题一，需要一个能得出生产成本较低的汽车装配顺序的算法。因为属性和工艺要求的多样性，难以找到使所有目标达到最佳的方案，于是采用多目标规划，用了序贯算法的思想，根据品牌、配置、动力、驱动、颜色这5个属性的优先级，将目标规划问题分解成一系列的单目标规划问题，然后根据优先级依次求解。
对于品牌A1和A2，两班分别装配当天两种品牌各一半数量的汽车（总数460辆）。用Excel 软件根据附件所给数据制作A1和A2每天汽车总量表（见附录1.1）,可知7天内每天生产A1的数量均超过350辆，A2的数量均少于105辆。
对于汽车颜色属性如何确定装配顺序的问题，分析各颜色之间的间隔关系与数量，结合换色成本的考虑，采用分类思想先分为黑车和其他颜色的车，建立求黑车最小组数的最优化模型，并且根据最优化模型得出各天黑车组数最小值均为4组，并且求出黑色车各组的具体数量。再将其他颜色的车进行分类，设计五步确色法来确定颜色装配顺序。结合了颜色装配流程图（见图3），建立了各颜色装配顺序的模型。
对于动力属性如何确定装配顺序的问题，尽量使柴油车在白班内完成装配，通过求基本最优解的方法，计算式（7）， 若计算得到的结果大于或等于5，则直接得到两批柴油汽车之间的汽油汽车数量。若计算得到的结果小于5，则柴油汽车不能在白班完成装配，需要分配一部分到夜班，用式（8）计算出两批柴油汽车之间的汽油汽车数量，得到每个班次的柴油车组数和每组需要用来间隔的汽油车数量。
对于驱动属性如何确定装配顺序问题，考虑情况与动力属性相似，尽量使四驱汽车在白班内完成装配，通过求基本最优解的方法，计算得到每个班次的组数、每组需要装配四驱车与两驱车的数量，由此得出两批四驱车之间数量的公式见式（5）。
对于配置属性与其他属性之间的关系，将配置与品牌、动力、驱动、颜色等属性结合分析。将配置与动力共同分析得表3，可知7天内每天生产各类汽车的数量分布较均匀。将配置与颜色共同分析得表5，得到黑色B1配置的汽车总量为33辆。将配置与驱动共同分析得到表6，可知7天内生产的B1配置两驱汽车和四驱汽车的数量相似，两驱车在270辆到240辆之间，四驱车在30辆到10辆之间。得到7天内B1配置四驱车数量变化小。
将配置与品牌共同分析得表7，可知B1配置的汽车数量最多，品牌A1的汽车每天产量可超过220辆，A2的汽车每天产量在60辆以内。 计算方案中所产生代价，利用层次分析法思想，确定各品牌、配置、动力、驱动、颜色这5个属性对代码权重，建立权重计算模型，根据文献所查到非黑色换色成本，得出第20日颜色切换、驱动切换、配置切换、动力切换的代价约为4550元。
模型假设：
1、假设各色车辆的数量不会发生很大的变化。
2、假设黑车数量大于200辆并且少于280辆。
3、假设没有新的型号、品牌出现。
4、假设红色、黄色车为同一类车，定义为R型车。
5、假设银色、灰色车为同一类车，定义为S型车。
问题分析：
汽车生产线优化有一系列不同要求，分析附件，得知要解决的问题为最优化问题及数据排序。建立汽车装配模型，并根据不同的要求进行修改，使汽车装配模型符合题目要求。
因为属性和工艺要求的多样性，难以找到使所有目标达到最佳的方案，于是采用多目标规划。而序贯式算法是求解目标规划的一种早期算法，其核心是根据优先级的先后次序，将目标规划问题分解成一系列的单目标规划问题，然后再依次求解，所以可以使用序贯算法的思想。
使用然后使用序贯算法的思想，根据品牌、配置、动力、驱动、颜色这5个属性的优先级，将目标规划问题分解成一系列的单目标规划问题，然后根据优先级依次求解。 针对问题一，考虑到符合要求且有较低生产成本的装配顺序。这是最优化求解问题。根据装配要求可知，汽车生产线有白班和晚班两个班次，总装线和喷涂线的各项要求对相邻班次的车辆同样适用。所以模型只考虑白班计划。
使用序贯算法将品牌、驱动、动力、颜色、配置属性逐一分析。 针对品牌属性，计划将汽车总数一分为二减少计算量，先加工 A1 型号后加工 A2型号。配置方面利用Excel软件制作配置与各个属性结合的表格，并依次对表格进行具体数据分析。
针对配置属性，考虑到同一品牌的相同配置车辆尽量连续，减少切换次数这一要求。 针对颜色属性，用Excel软件统计出各种颜色的汽车数量。以减少成本为前提，将数量最多的颜色与其它颜色在进行衔接考虑；根据题目所给要求，考虑将蓝色车辆与白色车辆分开，将金色车与红色车或黄色车分开，由于银色、灰色和棕色都可以用于相互间隔，但是棕色车与白车间隔可降低成本。所以在减少相应代价降低生产线成本的基础上安排合适的装配顺序。
针对驱动属性，根据问题要求，考虑将四驱车在白班内全部完成，同时计算其所需要装配的组数和两驱车需要装配的数量，最后得到两批四驱车之间间隔的两驱车数量，若四驱车不能在白班内全部完成，就将四驱车平均分配在两个班次内，再计算其结果。 针对动力属性，根据问题要求，同样考虑将柴油车在白班内完成，计算出各个量后，计算出其结果，若符合问题要求则得出结果，若不符合，则将柴油车平均分配在两个班次内，再计算其结果。
将分析后得出的品牌、配置、颜色、驱动、动力等的5种属性数据进行归类，在考虑生产成本的基础上安排合适的装配顺序，设计出算法，并写出代码。 针对问题二，在使用C-Free软件上运行代码，用Excel软件对表格进行归类排序。制作17日到23日的装配顺序表。
模型的建立与求解整体论文缩略图
全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可
程序代码：(代码和文档not free)
import xlwt
import xlrd
data=xlrd.open_workbook('Problem_D_Data.xlsx')
sheet=data.sheet_by_name('Sheet1')
cols = sheet.col_values(0)
riqi_index=([x for x in range(len(cols)) if cols[x] == '日期'])
workbook = xlwt.Workbook(encoding='utf-8')
sheet1 = workbook.add_sheet('sheet1',cell_overwrite_ok=True)
#为样式创建字体
style = xlwt.XFStyle()
font = xlwt.Font()
font.name = 'Times New Roman'
font.bold = False
#设置样式的字体
style.font = font
sheet1.write(0, 0, '日期', style)
sheet1.write(0, 1, '品牌', style)
sheet1.write(0, 2, '配置', style)
sheet1.write(0, 3, '动力', style)
sheet1.write(0, 4, '驱动', style)
sheet1.write(0, 5, '颜色', style)
sheet1.write(0, 6, '数量', style)
idx=0
for k in range(len(riqi_index)-1):
for t in range(riqi_index[k+1]-riqi_index[k]-2):
for s in range(5):
if sheet.cell_value(riqi_index[k]+t+1,s+4) !=0:
idx = idx + 1
#每找到一项非0的生产计划就记录一行
sheet1.write(idx, 0, sheet.cell_value(riqi_index[k]+t+1,0), style)
#日期在原表中位置为第1列
sheet1.write(idx, 1, sheet.cell_value(riqi_index[k]+t+1,1), style)
#品牌在原表中位置为第2列
sheet1.write(idx, 2, sheet.cell_value(riqi_index[k],s+4), style)
#配置在原表中位置为上方的第2行
sheet1.write(idx, 3, sheet.cell_value(riqi_index[k]-1,s+4), style)
#动力在原表中位置为上方的第1行
sheet1.write(idx, 4, sheet.cell_value(riqi_index[k]+t+1,2), style)
#驱动在原表中位置为第3列
sheet1.write(idx, 5, sheet.cell_value(riqi_index[k]+t+1,3), style)
#颜色在原表中位置为第4列
sheet1.write(idx, 6, sheet.cell_value(riqi_index[k]+t+1,s+4), style)
#对应以上属性的汽车生产需求
workbook.save('Problem_D_Data_Chuli.xls')
model:
sets:
xiaobiao/1..460/:A1_,A2_,y,z,x;
shuzhi/1..10/:SL;
!A1黑色四驱、A2黑色四驱、 A1非黑色四驱、
A2非黑色四驱、A1柴油、A2柴油、A1黑色柴油
……等特殊汽车数值;
endsets
init:
y,z=@ole('LingoData.xlsx');
endinit
data:
!打开Excel文件'LingoData.xlsx'读取相关数据;
A1_,A2_,x,SL=@ole('LingoData.xlsx');
enddata
min=@sum(xiaobiao(k) | k #GE# 12:
y(k)*(10-@sum(xiaobiao(t) | (t #GE# k-11) #AND# (t #LE# k) :
(1-y(t))))
+z(k)*(10-@sum(xiaobiao(t) | (t #GE# k-11) #AND# (t #LE# k) :
(1-z(t))))
);
@sum(xiaobiao(I):A1_(I)*x(I)*y(I))=SL(1);
@sum(xiaobiao(I):A2_(I)*x(I)*y(I))=SL(2);
@sum(xiaobiao(I):A1_(I)*y(I)*(1-x(I)))=SL(3);
@sum(xiaobiao(I):A2_(I)*y(I)*(1-x(I)))=SL(4);
@sum(xiaobiao(I):A1_(I)*z(I))=SL(5);
@sum(xiaobiao(I):A2_(I)*z(I))=SL(6);
@sum(xiaobiao(I):A1_(I)*x(I)*z(I))=SL(7);
@sum(xiaobiao(I):A2_(I)*x(I)*z(I))=SL(8);
@sum(xiaobiao(I):A1_(I)*y(I)*z(I))=SL(9);
@sum(xiaobiao(I):A2_(I)*y(I)*z(I))=SL(10);
@for(xiaobiao(I) | (I #GE# 2) #AND# (I #LE# 459) :
3-y(I-1)-y(I)-y(I+1) >= y(I);
3-z(I-1)-z(I)-z(I+1) >= z(I);
);
@for(xiaobiao(k) | k #GE# 7 :
@sum(xiaobiao(t) | (t #GE# k-6) #AND# (t #LE# k) :
(1-y(t)))>=5;
@sum(xiaobiao(t) | (t #GE# k-6) #AND# (t #LE# k) :
(1-z(t)))>=5;
);
@for(xiaobiao(I):
@bin(A1_(I));
@bin(A2_(I));
@bin(y(I));
@bin(z(I));
);
end
function Graph=genGraph(config,color,num)
N=sum(num);
Graph=ones(N)*inf; %连接图共有N个顶点
idx=zeros(N,1); %用来记录每个顶点的属性类表序号
s=1;
for k = 1:length(num)
idx(s:(s+num(k)-1))=k;
s=s+num(k);
end
for k = 1:N
for t = 1:N
if t==k
Graph(k,t) = 0;
end
if t ~= k
if strcmp(color{idx(k)},'白') %白色汽车在装配线上的允许连接情况
if strcmp(color{idx(t)},'白')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'蓝')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'棕')
Graph(k,t) = 1;
end
end
if strcmp(color{idx(k)},'黄') %黄色汽车在装配线上的允许连接情况
if strcmp(color{idx(t)},'银')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'灰')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'棕')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'金')
Graph(k,t) = 1;
end
end
if strcmp(color{idx(k)},'红') %红色汽车在装配线上的允许连接情况
if strcmp(color{idx(t)},'银')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'灰')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'棕')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'金')
Graph(k,t) = 1;
end
end
if strcmp(color{idx(k)},'蓝') %蓝色汽车在装配线上的允许连接情况
if strcmp(color{idx(t)},'白')
Graph(k,t) = 1;
end
end
if strcmp(color{idx(k)},'金') %金色汽车在装配线上的允许连接情况
if strcmp(color{idx(t)},'黄')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'红')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'灰')
Graph(k,t) = 10; %金色汽车优先与黄、红汽车连接
end
if strcmp(color{idx(t)},'棕')
Graph(k,t) = 10;
end
if strcmp(color{idx(t)},'银')
Graph(k,t) = 10;
end
end
if strcmp(color{idx(k)},'灰') %灰色汽车在装配线上的允许连接情况
if strcmp(color{idx(t)},'灰')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'银')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'黄')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'红')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'金')
Graph(k,t) = 1;
end
end
if strcmp(color{idx(k)},'银') %银色汽车在装配线上的允许连接情况
if strcmp(color{idx(t)},'灰')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'银')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'黄')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'红')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'金')
Graph(k,t) = 1;
end
end
if strcmp(color{idx(k)},'棕') %棕色汽车在装配线上的允许连接情况
if strcmp(color{idx(t)},'棕')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'白')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'黄')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'红')
Graph(k,t) = 1;
end
if strcmp(color{idx(t)},'金')
Graph(k,t) = 1;
end
end
end
end
end