0307 第二次课 单纯形法

最优化方法 单纯形法

Page 1

线性规划的基本定理： 线性规划的基本定理：min s.t . z = CT X AX = b X ≥0

定理3.3 定理

(1)线性规划问题若有可行解，那么一定有基本 )线性规划问题若有可行解， 可行解。 可行解。 (2)线性规划问题若有最优解，那么一定有最优 )线性规划问题若有最优解， 的基本可行解。 的基本可行解。

最优化方法 单纯形法

单纯形法( 第三节 单纯形法(Simplex method) )一、基本思想从标准型的LP模型的一个基可行解出发， 从标准型的 模型的一个基可行解出发，判 模型的一个基可行解出发 断是否是最优。如果是最优解，结束运算； 断是否是最优。如果是最优解，结束运算； 否则，设法找到一个更优(目标函数值减小) 否则，设法找到一个更优(目标函数值减小) 的基本可行解。如此继续， 的基本可行解。如此继续，经过有限次迭代 的最优解或判别LP问题有 代，就可以找到LP的最优解或判别 问题有 就可以找到 的最优解或判别 没有最优解。 没有最优解。

Page 2

(1947) G.B.Dantzig

最优化方法 单纯形法

基本思想框图

如何找初始基本 Page 3 可行解？ 可行解？ 找出一个初始基本可行解 如何判断是 否最优解？ 否最优解？ 是 最优解 结束

是否最优 循 环 否

转移到另一个基本可行解 (找出更小的目标函数值) 找出更小的目标函数值) 如何转换基 可行解？ 可行解？

最优化方法 单纯形法

Page 4

回顾上一节例1: 回顾上一节例 ： 求 min z = x1 3x2 + 2x3 + 4x4

2x1 4 x3 + x4 = 3 s.t x1 + x2 + 3x3 =5 x … , j = 1, ,4 j 0的一个基本解和一个基本可行解. 的一个基本解和一个基本可行解.

最优化方法 单纯形法

约束方程的增广矩阵为： 解: 约束方程的增广矩阵为：

Page 5

2 0 4 1 6 ( A, b) = 1 1 3 0 5 注意到A是 矩阵,r(A) 注意到 是2×4矩阵,r(A)=2. 矩阵,r(A)= 由于第2列和第4列线性无关,构成一个2 由于第2列和第4列线性无关,构成一个2阶单位子块， 因此可构成一个基矩阵. 因此可构成一个基矩阵. 为基变量, 为自由变量, 取 x2 , x4 为基变量, x1 , x3 为自由变量,用自由变量表 表示基变量得如下同解方程组: 表示基变量得如下同解方程组:

x2

x4

最优化方法 单纯形法

Page 6

x2 = 5 + x1 3x3 x4 = 6 2x1 + 4x3令x1 = x3 = 0得: x2 = 5, x4 = 6 由此得一基本解：

x = ( 0, 5, 0, 6)

T

2 0 4 1 6 ( A, b) = 1 1 3 0 5

又因5>0, 6>0, 该解显然非负，因此这个解也是一 该解显然非负， 又因 个基本可行解。 个基本可行解。

最优化方法 单纯形法

基变量取为其他变量的情况

Page 7

为基变量, 为自由变量, 若取 x1 , x2为基变量, x3 , x4 为自由变量,由于基本解 中自由变量全取零,所以只需对第一列,第二列以及 中自由变量全取零, 常数项列组成的矩阵初等行变换至行最简形

: 常数项列组成的矩阵初等行变换至行最简形: 2 0 ( A, b) = 1 1 6 1 0 → 0 1 5 T

3 8

由此可得基本解: 由此可得基本解: x = ( 3, 8, 0, 0)

又因3>0, 8>0, 该解显然非负，因此这个解也是一 又因 该解显然非负， 个基本可行解。 个基本可行解。

最优化方法 单纯形法

结论: 结论:

Page 8

中存在m阶单位子块, 若约束系数矩阵A中存在m阶单位子块, 且对应 的常数项非负,那么很容易看出一个基本可行解. 的常数项非负,那么很容易看出一个基本可行解. 其中,基变量的取值为单位子块中1 其中,基变量的取值为单位子块中1所对应的右边常 数项的值, 自由变量取值全为零. 数项的值, 自由变量取值全为零. 得到基本可行解之后,如何判断它是否是最优解呢? 得到基本可行解之后,如何判断它是否是最优解呢?

最优化方法 单纯形法

该解是否最优呢? 该解是否最优呢?将 x = 5 + x1 3x3 代入目标函数表达式中消去 x4 = 6 2x1 + 4x32

Page 9

x2 , x4 得

z = 9 10x1 + 27x3

的系数为-10<0,而可行域中 注意到 x1 的系数为-10<0,而可行域中 x1 ≥ 0, x3 ≥ 0 可见,当 x1 > 0 时,目标函数值减小, 所以 目标函数值减小, 可见, 不是最优解. 不是最优解.x = ( 0, 5, 0, 6)T

思考: 的系数均大于零, 思考:若此时目标函数中自由变量 x1 , x3 的系数均大于零, 那么这个解是否是最优解? 那么这个解是否是最优解?

最优化方法 单纯形法

二、单纯形表及容许的运算 1.单纯形表 1.单纯形表min z = CT x s.t. Ax = b x≥0r (A)=m =

Page 10

中心部位

右列

底线

ACT

b 0右下端

底行(检验行) 底行(检验行)

目标函数中常数项的相反数 目标函数中变量的系数

最优化方法 单纯形法

2. 容许运算中心部位 底行 ACT

Page 11

b 0

右列 右下端

底线

1)底线以上的行可进行初等行变换(三种); 1)底线以上的行可进行初等行变换(三种); 底线以上的行可进行初等行变换 2)底线以上的行乘常数后加至底行(包括右下端). 2)底线以上的行乘常数后加至底行(包括右下端). 底线以上的行乘常数后加至底行

使表具备下面四个特点: 使表具备下面四个特点: ① ② ③ ④

最优化方法 单纯形法

终止条件(最优性条件) 3. 终止条件(最优性条件)当表格具备如下特点: 当表格具备如下特点:① 中心部位具有 m 阶单位子块 ② 右列元素非负

Page 12

满足① 满足① ②时,可 可 读出基本可行解

③底行中相应于单位子块位置的元素 满足① ② ③时,判 满足① 判 0(基变量对应的底行元素为零 基变量对应的底行元素为零) 为0(基变量对应的底行元素为零) 断该解是否最优. 断该解是否最优 底行其他元素非负(自由变量对应的元素非负) ④ 底行其他元素非负(自由变量对应的元素非负) 则从表格中即可读得LP问题的最优解和最优值. 则从表格中即可读得

LP问题的最优解和最优值. LP问题的最优解和最优值满足① 可断定该基本可行解是最优解. 满足① ② ③ ④时,可断定该基本可行解是最优解 可断定该基本可行解是最优解

最优化方法 单纯形法

最优解( 最优解(值)的读法: 的读法:

Page 13

单位子块中1所在列对应的变量(基变量) 单位子块中1所在列对应的变量(基变量)取相应 右列的值,其余变量(自由变量)取值为零, 右列的值,其余变量(自由变量)取值为零,将它们写 在一起即是一个最优解. 在一起即是一个最优解. 而此时右下端元素的相反数即为相应的最优值. 而此时右下端元素的相反数即为相应的最优值. 右下端元素的相反数即为相应的最优值

最优化方法 单纯形法

4. 举例x2 x4

min z = x1 3x2 + 2x3 + 4x4

2 -1 1 2 -1

0 1 -3 0 1

-4 3 2 -4 3 27

1 0 4 1 0 0

6 5 0 6 5 -9

2x1 4 x3 + x4 = 6 s.t x1 + x2 + 3x3 =5 x … , j = 1, ,4 0 j

Page 14

满 足 ① ② 满 足 ① ② ③

基本可行解

x = ( 0, 5, 0, 6)

T

-10 0

但 ④ …… 此处隐藏：2573字，全部文档内容请下载后查看。喜欢就下载吧 ……