文档介绍：第三节单纯形法原理
◆初始基可行解的确定
◆基可行解的转换
◆最优性检验
一、预备知识:凸集和顶点
凸集:如果集合中任意两个点X1、X2,其连线
上所有点也都是集合C中的点,称C为凸集。即
对任何X1∈ C 、X2 ∈ C ,有
a X1+(1-a) X2 ∈ C (0<a<1)
则称C为凸集。
顶点:凸集C中满足下列条件的点X称为顶点:如果C中不存在任何两个不同的点X1、X2,使得X成为这两个点连线上的一个点。
或者:对任何X1∈ C 、X2 ∈ C ,不存在X=a X1+(1-a) X2 (0<a<1),则X称是凸集C的顶点。
二、几个基本定理
定理1 若线性规划问题存在可行解,则问题
的可行域是凸集。
证明思路:要证C中任意两点X1、X2连线上任
意点X=a X1+(1-a) X2 (0<a<1)也在C中。
引理线性规划问题可行解(x1,x2,···,xn)T
为基可行解的充要条件是X的正分量所对应的系
数列向量是线性独立的。
定理2 线性规划问题的基可行解X对应线性规
划问题可行域(凸集)的顶点。
定理3 若线性规划问题有最优解,一定存在一
个基可行解是最优解。
启示
◆线性规划问题若存在最优解,一定可以在
基可行解中找到。
◆单纯形法的基本思路是先找到一个基可行
解,如果不是最优解,设法转换到另一个基可
行解,并使目标函数值不断增大,一直找到最
优解为止。
三、初始基可行解的确定 设给定线性规划问题:
在第i个约束条件上加上松弛变量xsi(i=1,···,m)
化为标准形式:
约束方程组系数矩阵为:
a11 a12 ··· a1n 1 0 ··· 0
a21 a22 ··· a2n 0 1 ··· 0
⋮⋮⋮⋮⋮⋮⋯⋮
am1 am2 ⋯ amn 0 0 ⋯ 1
由于这个系数矩阵中一个单位矩阵
(Ps1, Ps2,···, Psm),只要以这个单位矩阵作为基,就可以立即解出基变量值xsi=bi
(i=1 ,···,m),因为有bi ≥0 (i=1 ,···,m),即
(0, ···,0,b1 ···, bm )为一个基可行解。
不失一般设前m个坐标非零即
因有X(0)∈C,故有()
四、从初始基可行解转换为另一基可行解 设初始基可行解为
由上面三、中方法,总可以使基矩阵是单位矩阵形式, ()有增广矩阵
P1 P2···Pm Pm+1 ··· Pj ··· Pn b
1 0 ··· 0 a1,m+1 ··· a1j ··· a1n b1
0 1 ··· 0 a2,m+1 ··· a2j ··· a2n b2
⋮⋮⋮⋮⋮⋮⋯⋮⋮
0 0 ⋯ 1 am,m+1 ··· amj ⋯ amn bm