基于CPLEX的最小费用网络流的求解与应用.doc

摘要:网络流是组合优化的一个重要研究课题，在生产和社会实践中有着广泛的应用。网络上的优化问题涉及多个科学领域，包括应用数学，计算机科学，管理学以及运筹学等。最小费用网络流问题作为网络流问题的一个最为基本的模型，已经有了丰富的研究成果。关于最小费用网络流问题我们可以这样来简单地描述：现要找到一个花费最小的运输方案将某种货物通过一个网络从供应地发送到需求定点，并使之满足这些定点的需求量。最小费用网络流问题可分为线性费用和凹（凸）费用，本文所考虑的最小费用网络流问题是指线性费用问题。关于最小费用网络流问题的求解有一系列特殊的方法，但是看懂这些方法并设计出来需要有一定的数学基础和能力，是相当困难的。事实上线性费用的最小费用网络流问题可视为一种特殊的线性规划问题，所以我们可以直接使用一些优化软件对其进行求解。CPLEX是当今世界领先的数学规划优化程序，提供了解决实际的大型优化问题所需的能力。在本文中，我们首先通过简单的例子来介绍一下如何用CPLEX来求解最小费用网络流问题，然后利用MATLAB语言编写程序设计出一些具体的最小费用网络流问题，并基于CPLEX进行求解，最后通过具体的实际问题的求解来谈谈最小费用网络流问题的应用。

关键词：最小费用网络流；线性费用；线性规划；MATLAB；CPLEX/AMPL

目录

摘要

Abstract

1绪论-1

2.最小费用网络流问题的介绍-2

2.1网络流简介-2

2.1.1基本概念-2

2.1.2网络流定义-2

2.2最小费用网络流问题的简介-3

2.2.1问题的描述-3

2.2.2问题的特征-3

2.2.3模型的建立-4

2.2.4问题的线性规划模型-4

2.2.5问题的性质-4

3 利用CPLEX求解最小成本网络流问题-5

3.1关于 AMPL/CPLEX的介绍-5

3.2用CPLEX求解最小费用网络流问题简例-5

3.2 用MATLAB设计最小费用网络流问题并基于CPLEX求解-8

4 最小费用网络流问题的应用-11

结论-17

致谢-18

参考文献-19