《数学模型》课件-第五章 第三讲 图论模型 汽车排序模型

汽车总装线排序问题——改编2018年全国大学生数学建模竞赛D题日期型号黑红黄蓝金灰白棕银彩色总数17A1260353091390742617A261602203648418A11673430131420633818A267301114528419A11883430131180533419A267301002538120A11754540111420334420A262602304628521A122534201311401037121A2336048291147722A12223400121110936122A2326048242248223A122134001211201036223A23160482825387总计1811583033309091280723116附件给出了该企业2018年9月17日至9月23日一周的生产计划。1.1模型数据总数：13051.2原理图

待装配车辆按一定顺序排成一列，首先匀速通过总装线依次进行总装作业，随后按序分为C1、C2线进行喷涂作业。1.3颜色要求1.3颜色要求：1.3颜色要求：1.3颜色要求：1.3颜色要求：1.3颜色要求：1.3颜色要求：1.3颜色要求：1.3颜色要求：1.3颜色要求：50至70辆其他颜色至少20辆其他颜色的搭配，遵循“没有允许即为禁止”的原则。1.4优化目标(1)除黑、白两种颜色外，在同一条喷涂线上，同种颜色的汽车应尽量连续喷涂作业。(2)喷涂线上不同颜色汽车之间的切换次数尽可能少，特别地，黑色汽车与其它颜色的汽车之间的切换代价很高。（2）根据（1）中的数学模型或算法，针对附件中的数据，给出计算结果。

（1）根据问题的背景、颜色要求以及附件中的数据，建立数学模型或者设计算法，使其能给出符合要求、且具有较低生产成本的排列顺序。建模目的1.5提出问题2.问题分析重难点2.不同日期，不同颜色数量不同，总量大。1.颜色多，要求多，关系复杂。

图论〔GraphTheory〕是数学的一个分支。它以图为研究对象。2.问题分析2.问题分析：模型假设

(1)假设，总装线上汽车排序只考虑颜色约束，其他影响因素，可以在模型改进中继续研究。(2)黑色汽车的要求比较独特，和其他颜色关系也简单，因此不作为们模型排列对象。

其次，以一天的同型号、同配置的同种颜色汽车总量为该颜色数量。首先，以不同颜色作为端点，如图，颜色排序为：黑色（独立），红色，黄色，蓝色，白金色，灰色，白色，棕色，银色。记为点集G。3.1.1模型建立和求解：生成图m1m0“蓝色汽车必须与白色汽车间隔相连”，所以蓝色与白色有边相连。“白、灰、银或棕可以连续排列”，所以，白、灰、银和棕有自循环边。3.1.2模型建立和求解：构图之建立关联边v1

v2

v3

v4

v5

v6v7v8

v1

v2

v3

v4

v5

v6v7v8

图一图二当金色无法排完，启用的备用图3.1.3模型建立与求解：底图路径法则

选点：边少初始，边同数少，否则任意。路径规律：来回走。第一段路：v6-v3-v6-v3-v6-v3-v6-v3v14v25v3

4v40v511142v60v73v8

链条连接参数k=6W={45 401114203}数量：取较少数量.3.1.4模型建立与求解：探索路径初始：链条连接参数k=0.第二段路：V14v25v34-4=0v40v511v60v7v83v6-v6-v6-v6-v6-v6......-v6-v6-v6142-4=138链条链接参数k=0W={45 0

01113803}路径法则

选点：边少初始，边同数少，否则任意。路径规律：来回走。数量：取较少数量.初始：链条连接参数k=6.3.1.4模型建立与求解：探索路径第三段路：v1

4v25v30

v40v511v600v73v8v1-v8-v1-v8-v1-v8链条链接参数k=1.路径法则

选点：边少初始，边同数少，否则任意。路径规律：来回走。数量：取较少数量.初始：链条连接参数k=0.W={45 0

0110

0

3}3.1.4模型建立与求解：探索路径第四段路：v14-3=1v25v30v4

0v511v600v73-3=0v8v1-v5链条连接参数k=5路径法则

选点：边少初始，边同数少，否则任意。路径规律：来回走。数量：取较少数量.初始：链条连接参数k=1.W={15 0

0110

0

0}3.1.4模型建立与求解：探索路径第五段路：V10v25v30v40v510v600v7v80v5-v2-v5-v2-v5-v2-v5-v2-v5-v2链条连接参数：结束初始：链条连接参数k=5更改k=0.W={05 0

0110

0

0}v5-v5-v5-v5-……..-v5-v5第六段路：链条连接参数k=5。3.1.4模型建立与求解：探索路径V14v2

3v3

0v40v511v60v7v830

孤立点3.1.5模型建立与求解：特殊情况的处理v25v3

0v40v511v60v7v83142-4=138v13（2）如果初始点和唯一相连的点是同一个点，即自循环，标注“连续排列段落”。3.1.5模型建立与求解：特殊情况的处理

v11v25v3