线性规划解的概念.ppt

一、线性规划解的概念 1. 可行解(Feasible solution)：满足约束条件和非负条件的决策变量的一组取值。 2. 最优解(Optimal solution)：使目标函数达到最优值的可行解。 3. 基(Base Matrix): m＜n，且m个方程线性无关，即矩阵A的秩为m；根据线性代数定理可知，n＞m，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。 线性规划解的概念 线性方程组的增广矩阵 线性规划解的概念 基矩阵： 系数矩阵A中任意m列所组成的m阶非奇异子矩阵，称为该线性规划问题的一个基矩阵。 或称为一个基，用B表示。 称基矩阵的列为基向量，用Pj表示(j=1,2,…,m) 。 线性规划解的概念 基变量(Base variables)： 与基向量Pj相对应的m个变量xj称为基变量， 其余的n-m个变量为非基变量。 基解(Base solution)： 令所有非基变量等于零，对m个基变量所求的解， 对应一个特定的基矩阵能求得一组唯一解，称之为对应于这个基的基解。 结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。 5. 基可行解 (Feasible base solution)（对应的基为可行基）：满足非负条件的基解。6. 基最优解 (Optimal base solution)（对应的基为最优基）：使目标函数达到最优值的基可行解。 * * 运 筹 帷 幄 之 中 决 胜 千 里 之 外 线 性 规 划 Linear Programming 运 筹 学 Operations Research 1-4 线性规划问题  解的概念和性质 《线性代数》 下页 结束 返回 求解非齐次线性方程组流程图 下页 增广矩阵(Ab) 阶梯形矩阵B r(Ab)=r(A) 方程组无解 行最简形矩阵C 确定自由未知量及约 束未知量,给出一般解 求AX=o的基础解系 写出通解 初等行变换 N Y r(Ab)=n 唯一解 初等行变换 Y N 求AX=b的一个特解 例 解线性方程组 x1 x1 x1 x2 x2 x2 x3 x3 2x3 x4 3x4 3x4 0 4 2 = = =- - - - - + - + - + 解： (A b)= 1 -1 1 4 1 -1 -2 -2 1 -1 -1 0 -3 3 1 ? 0 0 1 2 0 0 0 0 1 -1 0 2 ， -2 0 -1 (x2，x4为自由未知量)， x1 x3 x2 x2 x4 +2x4 = = + + 2 2 + + 得方程组的特解为 ， 2 0 2 0 由于 ， 令 所以方程组有无穷多组解， 其一般解为 对应齐次方程组的一般解为 x1 x3 x2 x2 x4 +2x4 = = + + 令 例5．解线性方程组 x1 x1 x1 x2 x2 x2 x3 x3 2x3 x4 3x4 3x4 0 4 2 = = =- - - - - + - + - + 得基础解系为 得方程组的特解为 ， 2 0 2 0 令 对应齐次方程组的一般解为 x1 x3 x2 x2 x4 +2x4 = = + + 令 方程的通解为 x1 x2 x3 x4 + k2 = + k1 2 0 2 0 1 0 2 1 1 1 0 0 (k1，k2是任意常数) . 例 max Z= 3x1 +5 x2 +0x3 +0x4+0x5 s.t. x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 ≥0 x1 x2 x3 x4 x5 单位矩阵 的基矩阵B最多C53=10，如下： x3 x4 x5 x1 x4 x5 x2 x4 x5 x3 x1 x5 x3 x2 x5 x3 x4 x1 x3 x4 x2 x1 x2 x5 x1 x2 x4 x1 x2 x5 x3 x4 x5 基变量是x3, x4, x5 非基变量是x1, x2 令非基变量x1=x2=0，得到基变量的解 x3=8，x4=12， x5=36 于是相应的基解为:X=(0,0,8,12,3