i 1 j 1 n m n
(5) (6)
s.t. xij 1, i 1, 2, , n， (每个人做一项工作)
j 1 n
xij 1, j 1, 2, , n, (每项工作有一个人去做) (7)
i 1
xij 0或1, j 1, 2, , n.
优化 建 模 优化建模 优 化 建模
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
下面列出LINGO软件的求解结果（仅保留非零变量）
从上述求解过程来看，两种软件的计算结果是相同的， 但由于LINGO软件中采用集、数据段和循环函数的编写 方式，因此更便于程序推广到一般形式使用.例如，只需 修改运输问题中产地和销地的个数，以及参数a,b,c的值， 就可以求解任何运输问题.所以，从程序通用性的角度来 看,推荐大家采用LINGO软件来求解运输问题.
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
至15]行定义的cI是工厂 到仓库的运费，由16]至18]行定义的cII是仓库到顾 客的运费.我们的目标是求最小运费，因此当两点无 道路时，认为是运费无穷大.为了便于计算，只要取 较大的数值就可以了，这里的取值为100. LINGO软件的计算结果（仅保留非零变量）如 下:
优化 建 模 优化建模 优 化 建模
返 回 导 航
一 运输问题
运输问题(Transportation Problem)是图论与 网络中的一个重要问题，也是一个典型的线性 规划问题. 例7.1 （运输问题）
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
上一页 下一页
新余学院
建模组
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
3. 运输问题的求解过程 为了便于讨论，以一个运输问题实例的求解过 程来介绍如何用LINDO或LINGO软件求解运输问 题模型. 例7.2(继例7.1) 设 m 3, n 4 即为有3个产地和 4个销地的运输问题，其产量、销量及单位运费如 表7-1所示.试求总运费最少的运输方案，以及总 运费.
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
即工厂A向仓库x, y, z分别运输3, 6, 0个单 位，工厂B向仓库x, y, z分别运输0, 3, 5个单位， 仓库x向顾客1运输3个单位，仓库y向顾客2, 3分 别运输5, 4个单位，仓库z向顾客4运输5个单位. 总运费为121个单位.
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
7.2
最短路问题和最大流问题
本节内容导航
7.2.1 7.2.2 7.2.3
2013-7-16
本节概述 最短路问题 最大流问题 最小费与最大流问题
新余学院
建模组
上一页
下一页
Xinyu University MCM
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
1.转运问题的数学表达式
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
min s.t.
c x c 2 x 2 ; jk jk
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
按第1章所列的规划问题写出相应的LINGO程序， 程序名：exam0705.lg4. 下面列出LINGO软件计算结果（仅保留非零变 量）:
2013-7-16
即甲游自由泳，乙游蝶泳，丙游仰泳，丁游蛙泳,没有被选拔 上.平均成绩为. 4ˊ13〞2.
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
例7.5（继例1.5）用LINGO软件求解例1.5. 解：在第二章的例2.7给出了该问题的LINDO软 件求解方法，这里给出LINGO软件的求解方法，读 者可根据问题的求解过程来考查两种软件求解问题的 方法，以及每种软件各自的特点. 为了便于编写程序，将5名队员的4种泳姿的百米 平均成绩重新列在表7-3中.
图7-1: m 个产地,
建模组
n 个销售地运输问题的图形
上一页 下一页
新余学院
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
运输问题的数学表达式
c
i 1 j 1
m
n
ij
xij .
第 i 个产地的运出量应小于或等于该地的生产量，即：
x
j 1
n
ij
ai .
例7.1 就是典型的运输问题，图7-1给出了 m 个产地，n 个销地运输问题的图形.关于它的求 解方法有两类，一类是按照图论的方法求解， 另一类是化成线性规划问题.这里介绍第二类方 法，即用LINDO或LINGO软件求解运输问题. 但为便于后面的叙述，先给出图论中有关图的 部分定义.
2013-7-16
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
7.1
运输问题与转运问题
本节内容导航
7.1.1 7.1.2 7.1.3 运输问题 指派问题 转运问题
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
下面写出求解该问题的LINGO程序，并在程序中 用到在第三章介绍的集与数据段，以及相关的循环函 数. 写出相应的LINGO程序，程序为：
在上述程序中，第16]表示运输问题中目标函数 (7.1). 第18] 19]行表示约束条件(7.2), 第21] 22]行 表示约束条件(7.3).
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
下面用LINGO程序再求解此问题，程序中仍然 用到集、数据段和循环函数. 写出相应的LINGO程序，程序名 程序中第12] 13]行中的-99意义与LINDO程序 中的意义相同，当某人无法做某项工作时，取一个 数值较大的负值. LINGO软件计算结果如下（只列出非零变量）:
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
第7讲:图与网络模型(一)
概述
运输问题与转运问题 最短路问题和最大流问题
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
本章内容概述
本章介绍图论与网络(Graph Theory and Network)的 有关优化问题模型。在这里，我们并不打算全面系统介绍 图论与网络的知识，而着重介绍与LINDO、LINGO软件有 关的组合优化模型和相应的求解过程。如果读者打算深入 地了解图论与网络的更全面的知识，请参阅图论或运筹学 中的有关书籍. LINDO软件和LINGO软件可以求解一些著名的组合优 化问题，这包括最短路问题、最大流问题、运输和转运问 题、最优匹配和最优指派问题、最优连线或最小生成树问 题、旅行商问题、关键路线法与计划评审方法等。
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
表7-4
工厂到仓库 、仓库到顾客的运费单价
x y z
A 1 2 －
B ３ １ ２
1 5 ９ －
2 ７ ６ ６
3 － ７ ７
4 － － ４
说明：其中--表示两地无道路通行.
解：写出相应的LINGO程序，程序名： exam0706a.lg4.
第 j个销地的运入量应等于该地的需求量，即：

i 1
2013-7-16
m
xi j b j .
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模
因此，运输问题的数学表达式为:
称具有形如式
2013-7-16
(1) ~ (4)
的线性规划问题为运输问题.
x x
1 ij k 1
x
j 1
2 jk
bk ,
x1 0, x 2 0.
2013-7-16
新余学院
建模组
上一页
下一页
Xinyu University MCM
优化 建 模 优化建模 优 化 建模