运筹学经典模型

从上述求解过程来看，两种软件的计算结果 是相同的，但由于LINGO软件中采用集、数据段 和循环函数的编写方式，因此更便于程序推广到 一般形式使用.例如，只需修改运输问题中产地 和销地的个数，以及参数a,b,c的值，就可以求解 任何运输问题.所以，从程序通用性的角度来看, 推荐大家采用LINGO软件来求解运输问题.
! 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
二、 指派问题
ห้องสมุดไป่ตู้
返 回 导 航
（指派问题）设有n个人, 计划作n项工作, 其中 c 表示第i个人做第j项工作的收益, 现求一种指派方 式，使得每个人完成一项工作，使总收益最大. 例7.3就是指派问题(Assignment Problem).指派 问题也是图论中的重要问题，有相应的求解方法，如 匈牙利算法.从问题的形式来看，指派问题是运输问 题的特例，也可以看成0-1规划问题.
j 1 n
xij 1, j 1, 2, , n, (每项工作有一个人去做) (7)
i 1
xij 0或1, j 1, 2, , n.
(8)
2. 指派问题的求解过程 分别用LINDO软件和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);
17]! The supply constraints; 18]@for( Warehouse(i): [SUP] 19] @sum( Customer(j): x(i,j)) <= a(i)); 20]! The demand constraints; 21]@for( Customer(j): [DEM] 22] @sum( Warehouse(i): x(i,j)) = b(j)); END
例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
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
X13 1.000000 0.000000 X21 13.000000 0.000000 X24 12.000000 0.000000 X33 21.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 3) 0.000000 2.000000 4) 0.000000 5.000000 5) 0.000000 -6.000000 6) 0.000000 -2.000000 7) 0.000000 -6.000000 8) 0.000000 -5.000000 NO. ITERATIONS= 6
一、运输问题
返 回 导 航
运输问题(Transportation Problem)是图论与 网络中的一个重要问题，也是一个典型的线性 规划问题. 例1 （运输问题）
例1 就是典型的运输问题，图7-1给出了 m 个产地，n 个销地运输问题的图形.关于它的求 解方法有两类，一类是按照图论的方法求解， 另一类是化成线性规划问题.这里介绍第二类方 法，即用LINDO或LINGO软件求解运输问题. 但为便于后面的叙述，先给出图论中有关图的 部分定义.
事实上，我们关心更多的是那些非零变量，因此, 可选择LINDO中的命令，只列出非零变量.
OBJECTIVE FUNCTION VALUE 1) 161.0000 VARIABLE VALUE REDUCED COST X11 2.000000 0.000000 X12 17.000000 0.000000
在上述程序中，第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
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软件或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
LINDO软件虽然给出最优解，但上述模型还存在 着缺点，例如，上述方法不便于推广的一般情况，特 别是当产地和销地的个数较多时，情况更为突出. 下面写出求解该问题的LINGO程序，并在程序中 用到在第三章介绍的集与数据段，以及相关的循环函 数. 写出相应的LINGO程序，程序名： exam0702.lg4
图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是偶图.
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， (每个人做一项工作)
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 .
因此，运输问题的数学表达式为:
称具有形如式
X24
12.000000 0.000000 X31 0.000000 7.000000 X32 0.000000 11.000000 X33 21.000000 0.000000 X34 0.000000 5.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 10.000000 0.000000 3) 0.000000 2.000000 4) 0.000000 5.000000 5) 0.000000 -6.000000 6) 0.000000 -2.000000 7) 0.000000 -6.000000 8) 0.000000 -5.000000 NO. ITERATIONS= 6
(1) ~ (4)
的线性规划问题为运输问题.
3. 运输问题的求解过程 为了便于讨论，以一个运输问题实例的求解过 程来介绍如何用LINDO或LINGO软件求解运输问 题模型. 例7.2(继例7.1) 设 m 3, n 4 即为有3个产地和 4个销地的运输问题，其产量、销量及单位运费如 表7-1所示.试求总运费最少的运输方案，以及总 运费.