摘 要

随着社会的发展，煤炭行业依变至买方市场，当前煤炭供应链被赋予了更多的责任和更高的要求。从企业角度来看，煤炭供应链管理改善已然刻不容缓。但由于煤炭供应链的复杂性，经验调度已然不足以达到要求，结合当下急速发展的计算机技术，将优化理论予以实现已成必然趋势。

当下运用于运输优化的理论十分丰富，本文立足于实际，从煤炭供应链中抽象出网络问题，对网络流与调度混合理论的使用作进一步拓展研究。于前人研究基础上，本文先对网络流、调度、混合的研究作出综述，选择部分与本文课题相近的分支课题论文做细致研读，后构建带分流限制的特殊最大流网络模型。使用ILOG MATLAB工具软件随机生成有向容量网络，模拟现实情况下的运输需求，而后使用LINGO自带优化器求解优化，寻求最优解，求解过程中记录部分指标，呈现问题复杂程度。本文在实验时控制变量法，选择性生成实验所需数组，在保持实验完整性的前提下，最大限度的保留实验数据的随机性，使得该理论研究更具普遍性。

关于实验结果的指数爆炸情况，本文中作出了解释，表明该问题属于NP-HARD型，并提出“枚举法 Ford-Fulkerson”、遗传算法等启发式算法、剪枝策略等求解方案，为进一步研究提供思路。

关键词：网络流；调度；NP-HARD；优化决策

Abstract

With the development of society, the coal industry has changed to the buyer's market, SO the current coal supply chain has been given more responsibilities and higher requirements. From the corporate perspective, the improvement of coal supply chain management is urgently needed. However, due to the complexity of the coal supply chain, empirical scheduling is already insufficient to meet the requirements. Combining the rapid development of computer technology, it has become an inevitable trend to optimize the theory.

The current theory of transport optimization is very rich. Based on reality, this paper abstracts network problems from the coal supply chain and further studies the use of the mixed theory of network flow and scheduling. Based on previous research, this paper first summarizes the study of network flow, scheduling, and blending, and selects the branch topic papers that are similar to the topic of this paper to do a detailed study, and then construct a special maximum flow network model with a flow restriction. Using ILOG MATLAB tool software to randomly generate directed capacity network to simulate the transport requirements in real-world situations, then use LINGO's own optimizer to solve the optimization, seek the optimal solution, record some indicators during the solution process, and present the complexity of the problem. This article controls the variable method in the experiment, selects and produces the array required for the experiment selectively, preserve the randomness of the experimental data to the maximum extent on the premise of keeping the experimental integrity, make this theory research more universal.

The exponential explosion of the experimental results is explained in this paper, which shows that the problem belongs to the NP-HARD type, and proposes solutions such as "enumeration method Ford-Fulkerson", heuristic algorithms such as genetic algorithms, and pruning strategies. Further study to provide ideas.

Key word：Network flow; Scheduling; NP-HARD; Optimization decision

目录

摘 要 4

Abstract 5

第1章 绪论 7

1.1研究背景与意义 7

1.2研究目的与意义 7

1.3国内外研究现状 8

1.3.1调度问题研究现状 8

1.3.2网络流问题综述 9

1.3.3网络流与调度混合问题综述 10

1.4问题难点及本文思路 10

1.5论文思路 11

第2章 网络流与调度混合问题的应用 12

2.1《基于逐次确定换班机会的乘务调度列生成方法》 12

2.2《基于拓展网络流方法的跨区跨省交易路径优化》 12

2.3《应用网络流理论的停电系统恢复路径混合整数线性优化模型》 13

2.4《NBAJ：一种基于网络流的工作流资源分配合理性判定方法》 13

2.5《可压缩网络流的输送策略研究》 13

第3章 建模 15

3.1建模背景 15

3.2数学模型及容量网络 15

第4章 实验设置及数据源 17

4.1随机生成网络 17

4.2算例求解 18

第5章 结果分析 19

5.1实验结果及分析 19

5.2实验反思 20

5.2.1 枚举法 Ford-Fulkerson方法。 20

5.2.2 元启发算法 22

5.3研究展望 22

第6章 总结展望 23

6.1课题的经济性与环保性分析 23

6.2个人小结 23

参考文献 24

致 谢 26

第1章 绪论

1.1研究背景与意义

随着社会的发展、科技的进步，生产力的提高，使得人们的生活水平有着巨大的提升。为满足社会日益增长的需求，让人民享受到便捷的生活服务，企业对产品生产至流通环节的整体协同性有着越来越高的要求，其中尤其以煤炭能源企业为甚。对煤炭企业调查发现，供应管理的概念在企业中已经得到普及，供应链系统优化成为了各大企业的迫切需求。

煤炭物流与供应链是指从煤矿坑口，一直到消费客户手中的煤炭供应链服务网络。广义的讲，煤炭物流供应链包括煤炭企业对原煤洗选加工、运输、储存、分销以及废弃物的综合利用多个环节。而我国煤炭市场由于计划经济时期的影响，导致本身存在先天不足，此外铁路运力的制约，更是提高了我国煤炭供应链管理上的难度。对于煤炭行业来说，近些年或许不再像以前的那么景气，究其原因来说，是煤炭市场的改变影响了各大煤炭企业的“业绩”。随着国家经济转型，某些“去产能”的政策得到贯彻落实，许多传统行业的低端产过剩产能被削减，例如：近年的钢铁行业，武钢宝钢合并事件。这些事件的发生无时不刻的在告诉煤炭企业，市场风向已经转变，大环境由当初的卖方市场，变成现在的买方市场。在日益激烈的市场竞争中，企业必须对自身的产品服务提出更高的要求，改进煤炭供应链，以应对新的一轮挑战。

1.2研究目的与意义

供应链体系的优化已然成为煤炭企业的迫切需要。何谓供应链管理？它是指在对供应链体系的的管理中，考虑整个供应链的整体效率和整个系统成本的有效性，在此基础上尽量减少系统的总成本。因此，供应链管理不是简单地将单个供应链成员的运输成本降到最低或减少库存，而是采用系统的方法来协调供应链成员，使整个供应链的总成本最低，保证整个供应链系统处于运行平稳流畅的状态中。另外，随着中国经济结构调整的深入，企业对节能减排的要求也越来越严格，供应链系统的优化可以最大限度地减少整个供应链对资源消耗和环境的负作用，并且可以有效地满足不断增长的绿色消费需求，这将大幅度增加供应链的竞争力。