摘 要

近几十年，网络流理论是运筹学理论中发展最快的分支之一，其中最小费用流在社会生产和实践中都有着很广泛的应用。因此，最小费用网络流具有很大的研究价值。随着科学技术的发展进步，人类活动日益复杂，对于许多实际的新网络，传统的网络最优化的模型不再适用。它促进网络流理论进一步发展，从而出现了多商品流、非线性网络流等新课题，故研究非线性最小费用网络流问题就更具现实意义了。

本文首先对国内外网络流的研究成果以及非线性网络流理论展开了介绍；其次分析了三种常见的基本运输网络模式，并给出了相应的最优化模型；然后针对近年来发展迅猛的冷链物流中的易腐品运输，提出了腐败率非线性变化的易腐品运输网络流问题，并给出了它的非线性最小费用网络流模型；接着讨论了多品种易腐品运输网络流问题，并建立模型；最后，在考虑腐败率是时间的多阶段离散递增函数的基础上，利用LINGO对具体算例求出了最小费用流。

关键词：非线性网络；腐败率；运输网络；最小费用网络流；LINGO

Abstract

In recent decades, the network flow theory is one of the fastest growing branch of operational research, in which the minimum cost flow in social production and in practice have a very wide range of applications. Thus, the minimum cost network flow is of great research value. With the development of science and technology, human activities have become increasingly complex, for many practical new networks, the traditional network optimization model is no longer applicable. It promotes the further development of the theory of network flow, thus the emergence of new multi-commodity flow problem, nonlinear network flow, etc. So it has more practical significance to study the nonlinear minimum cost network flow problem.

The research achievements at home and abroad based on network flow and nonlinear network flow theory is introduced, then this paper analyzes three common basic transport network model and gives the corresponding optimization model. Then, due to the rapid development of cold chain logistics, this paper studies the transportation network flow problem of perishables. Corruption rate of nonlinear change is described and gives its nonlinear minimum cost network flow model. Then this paper discusses the case of many varieties of perishable goods transport and sets up the model. Finally, considering the rate of corruption is a multi-stage time discrete increasing function, we use LINGO for specific example to calculate the minimum cost flow.

Key words: nonlinear network; corruption rate; transportation networks; minimum cost network flow; LINGO

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1 研究背景 1

1.2 研究目的及意义 1

1.3 国内外相关研究综述 2

1.3.1 最小费用网络流 2

1.3.2 易腐品物流网络 3

1.4 研究目的及研究方法 3

1.4.1 研究目的 3

1.4.2 研究方法 3

1.5 研究内容及技术路线 4

1.5.1 研究内容 4

1.5.2 技术路线 5

第2章 非线性网络流相关概念及理论基础 6

2.1 网络流问题 6

2.1.1 网络与网络流 6

2.1.2 可行流与最小费用流 6

2.2 线性规划与非线性规划 7

2.2.1 线性规划的定义 7

2.2.2 非线性规划的定义及特点 8

2.2.3 非线性规划的类型 8

第3章 运输网络模式及其优化模型 10

3.1 运输网络 10

3.2 运输网络基本模式 10

3.2.1 直达运输模式 10

3.2.2 “送奶路线”运输模式 11

3.2.3 通过中转站的运输模式 13

第4章 非线性的易腐品运输网络优化 15

4.1 易腐品的定义 15

4.2 易腐品的腐败率 15

4.3 易腐品运输网络建模 16

4.3.1 问题描述 16

4.3.2 单品种易腐品运输网络模型 17

4.3.3 多品种易腐品运输网络模型 18

4.3.4 模型分析与求解 19

第5章 易腐品运输网络算例分析 21

5.1 单品种易腐品运输 21

5.1.1 算例介绍 21

5.1.2 算例求解 22

5.1.3 结果分析 22

5.2 多品种易腐品运输 23

5.2.1 算例介绍 23

5.2.1 算例求解 24

第6章 结论与展望 25

6.1结论 25

6.2进一步展望 25

参考文献 27

附录 29

致谢 34

第1章 绪论

1.1 研究背景

网络流理论是组合最优化和图论结合的产物，它为有效使用已有的网络以及合理设计新网络提供一套科学方法。最优化问题是它的主要研究方向，其中的两个基本问题是最短路和最小费用流问题。现代社会可以被看成是一个由生产分配网络、物资运输网络、通讯网络组成的复杂系统，其中生产分配网络的规划，运输网络的构建，通讯网络的设计和性能评估等，均是网络流理论的应用领域。

最小费用流（minimum cost network flow，简写为MCNF）是在一个网络中求从源点到汇点的流值为某个常数的流，并使其费用最小。由于最小费用流问题是组合优化中的一个常见问题，故目前对于最小费用流模型已经有了较丰富的研究成果，并且在实践中已有广泛的应用。事实上，各类网络流问题如运输问题、最大流问题、指派问题等，都能简单地转化成该问题并顺利求解。但是随着社会不断发展，人类活动日益复杂，新问题不断出现，如存在运量的价格折扣，使得运费与运量非线性相关；冷链物流兴起，易腐品由于在运输过程的非线性腐败造成大量货损成本等。这些因素都将可能使整个网络流规划的最优方案发生改变，也对原有的网络流模型构成了挑战。在如今新的情形下，非线性最小费用网络流问题越来越受人关注。目前，该理论在电力系统经济调度、水库群系统的优化调度、城市交通规划等许多领域中都获得了广泛地研究与应用。

1.2 研究目的及意义

近几年以来，我国物流业的发展逐渐成为了经济生活的一个热点。随着交通运输的迅猛发展和人们生活水平的普遍提高，中国乳制品消费的年均增长率保持在10%－20%，对冷饮、速冻食品、蔬果等各类易腐品的消费也进入了一个高速发展时期，因此与其息息相关的冷链物流，也将进入一个全新的发展阶段^[1]。然而相比较于发达国家，我国易腐品运输的成本较高。一方面是冷链运输在我国起步较晚，冷链运输的基础设施还相当落后，并且在较长的一段时间内没有引起足够的重视所致；另一方面，由于易腐食品非线性损耗的特点，随着运输时间的增加，耗费成本大幅增加，因此通过延长运输时间而降低单位商品成本的效益并不明显。在运输网络中，网络流连接着供应点和需求点，是两者之间的桥梁，故选择最优的网络流能保证货物的流通的同时，节省费用，增加企业的收益。