计算机算法设计与分析第8章

王晓东算法设计与分析的课件,很详细的!

第8章

线性规划与网络流

学习要点 理解线性规划算法模型 掌握解线性规划问题的单纯形算法 理解网络与网络流的基本概念 掌握网络最大流的增广路算法

掌握网络最大流的预流推进算法掌握网络最小费用流的消圈算法 掌握网络最小费用流的最小费用路算法

掌握网络最小费用流的网络单纯形算法

王晓东算法设计与分析的课件,很详细的!

8.1 线性规划问题和单纯形算法

线性规划问题及其表示 线性规划问题可表示为如下形式：

maxs.t.

c xj 1 j

n

j

(8.1)

a x a at 1 t 1 n t 1 n

n

it t

bi

i 1,2, , m1 j m1 1, , m1 m2

(8.2) (8.3)

jt t

x bj

kt t

x bk

k m1 m2 1, , m1 m2 m3 (8.4) t 1,2, , n (8.5)

xt 0

王晓东算法设计与分析的课件,很详细的!

变量满足约束条件(8.2)-(8.5)式的一组值称为线性规划问题的一个可行解。 所有可行解构成的集合称为线性规划问题的可行区域。 使目标函数取得极值的可行解称为最优解。 在最优解处目标函数的值称为最优值。 有些情况下可能不存在最优解。 通常有两种情况： (1)根本没有可行解，即给定的约束条件之间是相互排斥的，可行区域为空集； (2)目标函数没有极值，也就是说在n 维空间中的某个方向上，目标函数值可以无限增 大，而仍满足约束条件，此时目标函数值无界。

王晓东算法设计与分析的课件,很详细的!

maxx1 2 x3 2 x2 7 x4 x1 x 2 x3 x 4 x 2 x3 2 x 4xi 0

z x1 x2 3x3 x4 18 0 9 1

i 1, 2,3,4

这个问题的解为 (x1,x2,x3,x4) = (0,3.5,4.5,1);最优值为16。

王晓东算法设计与分析的课件,很详细的!

线性规划基本定理

约束条件(8.2)-(8.5)中n个约束以等号满足的可行解称为线性规划问题的基本可行解。 若n>m,则基本可行解中至少有n-m个分量为0,也就是说，基本可行解中最多有m个 分量非零。 线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。 上述定理的重要意义在于，它把一个最优化问题转化为一个组合问题，即在(8.2) -(8.5) 式的m+n个约束条件中，确定最优解应满足其中哪n个约束条件的问题。 由此可知，只要对各种不同的组合进行测试，并比较每种情况下的目标函数值，直到 找到最优解。

Dantzig于1948年提出了线性规划问题的单纯形算法。

单纯形算法的特点是：(1)只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加； (2)一般经过不大于m或n次迭代就可求得最优解。

王晓东算法设计与分析的课件,很详细的!

约束标准型线性规划问题的单纯形算法

当线性规划问题中没有不等式约束(8.2)和(8.4)式，而只有等式约束(8.3)和变量非负约束

(8.5)时，称该线性规划问题具有标准形式。

为便于讨论，不妨先考察一类更特殊的标准形式线性规划问题。这一类线性规划问题中， 每一个等式约束中，至少有一个变量的系数为正，且这个变量只在该约束中出现。 在每一约束方程中选择一个这样的变量，并以它作为变量求解该约束方程。这样选出来的 变量称为左端变量或基本变量，其总数为m个。剩下的n-m个变量称为右端变量或非基本 变量。

这一类特殊的标准形式线性规划问题称为约束标准型线性规划问题。 虽然约束标准型线性规划问题非常特殊，但是对于理解线性规划问题的单纯形算法是非常 重要的。 稍后将看到，任意一个线性规划问题可以转换为约束标准型线性规划问题。

王晓东算法设计与分析的课件,很详细的!

max

z x2 3x3 2x5 7 12 10

x1 3x2 x3 2 x5 x4 2 x2 4 x3 x6 4 x2 3x3 8x5

xi 0

i 1, 2,3,4,5,6

x2 z x1 x4 0 7 12 -1 3 -2

x3 3 -1 4

x5 -2 2 0

x6

10

-4

3

87

王晓东算法设计与分析的课件,很详细的!

任何约束标准型线性规划问题，只要将所有非基本变量都置为0,从约束方程式中解出满 足约束的基本变量的值，可求得一个基本可行解。

单纯形算法的基本思想就是从一个基本可行解出发，进行一系列的基本可行解的变换。每次变换将一个非基本变量与一个基本变量互调位置，且保持当前的线性规划问题是一个 与原问题完全等价的标准线性规划问题。 基本可行解x=(7,0,0,12,0,10)。 单纯形算法的第1步：选出使目标函数增加的非基本变量作为入基变量。 查看单纯形表的第1行(也称之为z行)中标有非基本变量的各列中的值。 选出使目标函数增加的非基本变量作为入基变量。 z行中的正系数非基本变量都满足要求。 在上面单纯形表的z行中只有1列为正，即非基本变量相应的列，其值为3。 选取非基本变量x3作为入基变量。 单纯形算法的第2步：选取离基变量。

在单纯形表中考察由第1步选出的入基变量所相应的列。在一个基本变量变为负值之前，入基变量可以增到多大。8

王晓东算法设计与分析的课件,很详细的!

如果入基变量所在的列与基本变量所在行交叉处的表元素为负数，那么该元素将不受任何限制，相应的基本变量只会越变越大。 如果入基变量所在列的所有元素都是负值，则目标函数无界，已经得到了问题的无界解。 如果选出的列中有一个或多个元素为正数，要弄清是哪个数限制了入基变量值的增加。 受限的增加量可以用入基变量所在列的元素(称为主元素)来除主元素所在行的“常数列” (最左边的列)中元素而得到。所得到数值越小说明受到限制越多。 应该选取受到限制最多的基本变量作为离基变量，才能

保证将入基变量与离基变量互调位 置后，仍满足约束条件。 上例中，惟一的一个值为正的z行元素是3,它所在列中有2个正元素，即4和3。 min{12/4,10/3}=4,应该选取x4为离基变量； 入基变量x3取值为3。 单纯形算法的第3步：转轴变换。 转轴变换的目的是将入基变量与离基变量互调位置。 给入基变量一个增值，使之成为基本变量； 修改离基变量，让入基变量所在列中，离基变量所在行的元素值减为零，而使之成为非基

本变量。9

王晓东算法设计与分析的课件,很详细的!

解离基变量所相应的方程，将入基变量x3用离基变量x4表示为 再将其代入其他基本变量和所在的行中消去x3 ,5 1 x 2 x 4 2 x5 10 2 4 5 3 x 6 x 2 x 4 8 x5 1 2 4 1 3 z 9 x 2 x 4 2 x5 2 4 x1

x3

1 1 x2 x4 3 2 4

代入目标函数得到 形成新单纯形表

x2 z x1 x3 x6 9 10 3 1 1/2 5/2 -1/2 -5/2

x4 -3/4 1/2 1/4 -3/4

x5 -2 2 0 810

王晓东算法设计与分析的课件,很详细的!

单纯形算法的第4步：转回并重复第1步，进一步改进目标函数值。 不断重复上述过程，直到z行的所有非基本变量系数都变成负值为止。这表明目标函数不

可能再增加了。在上面的单纯形表中，惟一的值为正的z行元素是非基本 …… 此处隐藏：3220字，全部文档内容请下载后查看。喜欢就下载吧 ……