0307 第二次课 单纯形法
时间:2025-07-10
时间:2025-07-10
最优化方法 单纯形法
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. 终止条件(最优性条件 …… 此处隐藏:3340字,全部文档内容请下载后查看。喜欢就下载吧 ……