1
学习要点
理解线性规划算法模型
掌握解线性规划问题的单纯形算法
理解网络与网络流的基本概念
掌握网络最大流的增广路算法
掌握网络最大流的预流推进算法
掌握网络最小费用流的消圈算法
掌握网络最小费用流的最小费用路算法
掌握网络最小费用流的网络单纯形算法
第 8 章 线性规划与网络流
2
8.1 线性规划问题和单纯形算法
•
线性规划问题及其表示
•
线性规划问题可表示为如下形式：
s.t.
)1.8(max
1
n
j
jj
xc
)5.8(,,2,10
)4.8(,,1
)3.8(,,1
)2.8(,,2,1
32121
1
211
1
1
1
ntx
mmmmmkbxa
mmmjbxa
mibxa
t
n
t
ktkt
n
t
jtjt
n
t
itit
3
•
变量满足约束条件 (8.2)-(8.5) 式的一组值称为线性规划问题的一个可行解。
•
所有可行解构成的集合称为线性规划问题的可行区域。
•
使目标函数取得极值的可行解称为最优解。
•
在最优解处目标函数的值称为最优值。
•
有些情况下可能不存在最优解。
•
通常有两种情况：
•
(1) 根本没有可行解，即给定的约束条件之间是相互排斥的，可行区域为空集；
•
(2) 目标函数没有极值，也就是说在 n 维空间中的某个方向上，目标函数值可以无限增
大，而仍满足约束条件，此时目标函数值无界。
4
•
这个问题的解为 (x1,x2,x3,x4) = (0,3.5,4.5,1) ；最优值为 16 。
4321
3max xxxxz
12
9
072
182
432
4321
42
31
xxx
xxxx
xx
xx
4,3,2,10 ix
i
5
线性规划基本定理
•
约束条件 (8.2)-(8.5) 中 n 个约束以等号满足的可行解称为线性规划问题的基本可行解。
•
若 n>m ，则基本可行解中至少有 n-m 个分量为 0 ，也就是说，基本可行解中最多有 m
个分量非零。
•
线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。
•
上述定理的重要意义在于，它把一个最优化问题转化为一个组合问题，即在 (8.2) -(8.5)
式的 m+n 个约束条件中，确定最优解应满足其中哪 n 个约束条件的问题。
•
由此可知，只要对各种不同的组合进行测试，并比较每种情况下的目标函数值，直到找
到最优解。
•
Dantzig 于 1948 年提出了线性规划问题的单纯形算法。
•
单纯形算法的特点是：
•
（ 1 ）只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加；
•
（ 2 ）一般经过不大于 m 或 n 次迭代就可求得最优解。
