解：从前面的分析来看，运输问题属于线性规划问 题，因此，不论是LINDO软件或LINGO软件都可以对 该问题求解.为了便于比较两种软件的优缺点，以及各 自的特点，我们用两种软件分别求解该运输问题. 首先写出LINDO软件的模型（程序），程序名： Exam3.1.ltx.
! 3 Warehouse, 4 Customer Transportation Problem ! The objective min 6x11 + 2x12 + 6x13 + 7x14 + 4x21 + 9x22 + 5x23 + 3x24 + 8x31 + 8x32 + x33 + 5x34 subject to 2013-10-23
一、运输问题
返 回 导 航
运输问题(Transportation Problem)是图论与 网络中的一个重要问题，也是一个典型的线性 规划问题. 例1 （运输问题）
例1 就是典型的运输问题，图7-1给出了 m 个产地，n 个销地运输问题的图形.关于它的求 解方法有绍第二类方 法，即用LINDO或LINGO软件求解运输问题. 但为便于后面的叙述，先给出图论中有关图的 部分定义.
1 2 1 2 1
2. 运输问题的数学表达式
c
i 1 j 1
m
n
ij
xij .
第 i 个产地的运出量应小于或等于该地的生产量，即：

j 1 n
xij ai .
第 j 个销地的运入量应等于该地的需求量，即：

i 1 m
xij b j .
因此，运输问题的数学表达式为:
称具有形如式
! Each person must be assigned to some job x11 + x12 + x13 + x14 + x15 + x16 = 1 x21 + x22 + x23 + x24 + x25 + x26 = 1 x31 + x32 + x33 + x34 + x35 + x36 = 1 x41 + x42 + x43 + x44 + x45 + x46 = 1 x51 + x52 + x53 + x54 + x55 + x56 = 1 x61 + x62 + x63 + x64 + x65 + x66 = 1 ! Each job must receive an assignment x11 + x21 + x31 + x41 + x51 + x61 = 1 x12 + x22 + x32 + x42 + x52 + x62 = 1 x13 + x23 + x33 + x43 + x53 + x63 = 1 x14 + x24 + x34 + x44 + x54 + x64 = 1 x15 + x25 + x35 + x45 + x55 + x65 = 1 x16 + x26 + x36 + x46 + x56 + x66 = 1 end
2013-10-23 9
LINDO软件的计算结果如下： LP OPTIMUM FOUND AT STEP 6 OBJECTIVE FUNCTION VALUE 1) 161.0000 VARIABLE VALUE REDUCED COST X11 2.000000 0.000000 X12 17.000000 0.000000 X13 1.000000 0.000000 X14 0.000000 2.000000 X21 13.000000 0.000000 X22 0.000000 9.000000 X23 0.000000 1.000000
事实上，我们关心更多的是那些非零变量，因此, 可选择LINDO中的命令，只列出非零变量.
OBJECTIVE FUNCTION VALUE 1) 161.0000 VARIABLE VALUE REDUCED COST X11 2.000000 0.000000 X12 17.000000 0.000000
LINDO软件虽然给出最优解，但上述模型还存在 着缺点，例如，上述方法不便于推广的一般情况，特 别是当产地和销地的个数较多时，情况更为突出. 下面写出求解该问题的LINGO程序，并在程序中 用到在第三章介绍的集与数据段，以及相关的循环函 数. 写出相应的LINGO程序，程序名： exam0702.lg4
从上述求解过程来看，两种软件的计算结果 是相同的，但由于LINGO软件中采用集、数据段 和循环函数的编写方式，因此更便于程序推广到 一般形式使用.例如，只需修改运输问题中产地 和销地的个数，以及参数a,b,c的值，就可以求解 任何运输问题.所以，从程序通用性的角度来看, 推荐大家采用LINGO软件来求解运输问题.
MODEL: 1]! 3 Warehouse, 4 Customer Transportation Problem; 2]sets: 3] Warehouse /1..3/: a; 4] Customer /1..4/: b;
5] Routes( Warehouse, Customer) : c, x; 6]endsets 7]! Here are the parameters; 8]data: 9] a = 30, 25, 21 10] b = 15, 17, 22, 12; 11] c = 6, 2, 6, 7, 12] 4, 9, 5, 3, 13] 8, 8, 1, 5; 14]enddata 15]! The objective; 16][OBJ] min = @sum( Routes: c * x);
图7-1: m个产地,
n 个销售地运输问题的图形
1. 图的基本定义 从直观上看, 所谓图是由点和边组成的图形, 如 图7-1所示.下面我们给出图的定义.
注：通常有向图的边称为弧，由弧构成的集记为 A, 因此，有向图记为 G(V , A) , 而无向图记为 G(V , E ) . 为 方便起见，在后面的论述中，有时也用 G(V , E ) 表示有 向图. 在无向图中, 每条至多有一条边的图称为简单图 (Simple Graph). 若每一对不同的顶点都有一条边相 连的简单图称为完全图(Complete Graph). 若一个图 中的顶点集可以分解为两个子集 V 和 V , 使得任何一 条边都有一个端点在 V 中, 另一个端点在 V 中, 这种图 V 称为二部图或偶图(Bipartite Graph). 运输问题所构成 的图7-1是偶图.
例7.4（继例7.3） 考虑例7.3中 n 6 的情况,即 6个人做6项工作的最优指派问题，其收益矩阵如 表7-2所示.
解：与运输问题一样，先用LINDO软件求解. 再给出LINGO程序。
! Assignment model ! Maximize valve of assignments max 20x11 + 15x12 + 16x13 + 5x14 + 4x15 + 7x16 + 17x21 + 15x22 + 33x23 + 12x24 + 8x25 + 6x26 + 9x31 + 12x32 + 18x33 + 16x34 + 30x35 + 13x36 + 12x41 + 8x42 + 11x43 + 27x44 + 19x45 + 14x46 - 99x51 + 7x52 + 10x53 + 21x54 + 10x55 + 32x56 - 99x61 - 99x62 - 99x63 + 6x64 + 11x65 + 13x66 subject to
ij
1. 指派问题的数学表达式 设变量为 xij ,当第 i 个人作第 j 项工作时，xij 1 , 否则 xij 0 . 因此，相应的线性规划问题为
min cij xij；
i 1 n j 1
m
n
(5) (6)
s.t. xij 1, i 1, 2, , n， (每个人做一项工作)
在上述程序中，第16]表示运输问题中目标函数 (7.1). 第18] ~ 19]行表示约束条件(7.2), 第21] ~ 22]行 表示约束条件(7.3).
下面列出LINGO软件的求解结果（仅保留非零变量）
Global optimal solution found at iteration: 6 Objective value: 161.0000 Variable Value Reduced Cost X( 1, 1) 2.000000 0.000000 X( 1, 2) 17.00000 0.000000 X( 1, 3) 1.000000 0.000000 X( 2, 1) 13.00000 0.000000 X( 2, 4) 12.00000 0.000000 X( 3, 3) 21.00000 0.000000 Row Slack or Surplus Dual Price OBJ 161.0000 -1.000000 SUP( 1) 10.00000 0.000000
8
! The supply constraints 2) x11 + x12 + x13 + x14 <= 30 3) x21 + x22 + x23 + x24 <= 25 4) x31 + x32 + x33 + x34 <= 21 ! The demand constraints 5) x11 + x21 + x31 = 15 6) x12 + x22 + x32 = 17 7) x13 + x23 + x33 = 22 8) x14 + x24 + x34 = 12 end