第一章 线性规划及单纯形法2-单纯形法原理2006.pptVIP

* 对于一般线性规划问题 目标函数 约束条件 （1） （2） （3） 可行解：满足（2）（3）的解称为线性规划问题的可行解 可行域：全体可行解的集合 最优解：使目标函数（1）达到最大值的可行解 基：设A为（2）的系数矩阵（nm)，R(A)=m，B是A的一个m阶的满秩子矩阵，称B是线性规划问题的一个基 第三节 单纯形法原理 不失一般性，设 B中的每一个列向量 称为基向量，与基向量对应的变量 称为基变量，其余的称为非基变量。 基解：在约束方程（2）中，令所有的非基变量为0，可求出m 个基变量的唯一解 ，则称 为线性规划问题的基解 基可行解：满足非负约束条件（3）的基解 可行基：对应基可行解的基称为可行基 各种解之间的关系： 可行域的性质 线性规划的可行域是凸集 凸集：如果C中任意两个点连线上的所有点也都在C中，称C为凸集。 线性规划的最优解在顶点上 凸集 凸集 不是凸集 顶点 线性规划的基本概念 线性规划的基矩阵、基变量、非基变量 = = 目标函数 约束条件 行列式≠0 基矩阵 右边常数 max Z = 2x 1 +3x 2 +x 3 s.t. x 1 +3x 2 +x 3 ￡ 15 2x 1 +3x 2 - x 3 ￡ 18 x 1 - x 2 +x 3 ￡ 3 x 1 , x 2 , x 3 3 0 max Z = 2x 1 +3x 2 +x 3 st x 1 +3x 2 +x 3 +x 4 =15 2x 1 +3x 2 -x 3 +x 5 =18 x 1 -x 2 +x 3 +x 6 =3 x 1 , x 2 , x 3 , x 4 , x 5 , x 6 3 0 例：求出下列线性规划问题的全部基解，指出基可行解，并求出最优解 化为标准形式 基变量x1、x2、x3，非基变量x4、x5、x6 基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0） 是基可行解，表示可行域的一个顶点。 目标函数值为：z=20 基变量x1、x2、x4，非基变量x3、x5、x6 基解为 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基可行解，表示可行域的一个顶点。 目标函数值为：z=18 基变量x1、x2、x5，非基变量x3、x4、x6 基解为 （x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0） 是基解，但不是基可行解，不是一个顶点。 基变量x1、x2、x6，非基变量x3、x4、x5 基解为 （x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4） 是基可行解，表示可行域的一个顶点。 目标函数值为：z=18 基变量x2、x3、x4，非基变量x1、x5、x6 基解为 （x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0） 是基解，但不是基可行解。 基变量x1、x2、x3，非基变量x4、x5、x6 基解为 （x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0） 是基可行解，表示可行域的一个顶点。 目标函数值为：z=15 基变量x1、x2、x3，非基变量x4、x5、x6 基解为 （x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10） 是基解但不是可行解。 继续 …… 基解、基可行解 max z=x1+3x2 D s.t. x1+ x2+x3 =6 B -x1+2x2 +x4 =8 x4=0 C x3=0 x1, x2,x3,x4≥0 x1=0 E O x2=0 A 练习：求出下列线性规划问题的全部基解，指出基可行解，并求出最优解 定理1：若线性规划问题存在可行解，则问题的可行域是凸集 定理2：线性规划问题的基可行解，对应线性规划问题的可行域（凸集）的顶点 定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解 单纯形迭代原理 找出一个基可行解 判断其是否最优 结束 是 否 转换到相邻的基可行解，并使目标函数值增大 相邻的基可行解：两个基可行解称为相邻基可行解，如果它们之间变换且仅变换一个基变量。 单纯形迭代原理 1 确定初始基可行解 对于一般标准型的线性规划问题 （1） （