运筹学5单纯形法.ppt

第五章单纯形法

1.线性规划问题的解

2单纯形法

3求初始基的人工变量法

1.线性规划问题的解

定义在线性规划问题中，约束方程组(2)

的系数矩阵A(假定)的任意一个

阶的非奇异(可逆)的子方阵B(即)，

称为线性规划问题的一个基阵或基。

(1)解的基本概念

基阵非基阵

非

基

基向

向量

量

基变量非基变量

STEP1STEP2STEP3

令则定义在约束方程组

(2)中，对于一个选

定的基B，令所有的

非基变量为零得到的

解，称为相应于基B

的基本解。

基本解中最多有m个非零分量。

123

定义在基本解中，若该定义在线性规划问题的基本解的数目不超过

基本解满足非负约束，一个基本可行解中，如果所个。

即，则称有的基变量都取正值，则称

此基本解为基本可行解，简它为非退化解，如果所有的

基本可行解都是非退化解。

称基可行解；对应的基B称

称该问题为非退化的线性规

为可行基。

划问题；若基本可行解中，

有基变量为零，则称为退化

解，该问题称为退化的线性

规划问题。

解的集合：

非可行

可行解基本解

解

基本可

最优解解空间

行解

01例现有线性规划问题

02试求其基本解、基本可行解并判断是否为退化解。

0102

l解:(1)首先将原问题