03.3单纯形法的原理

《03.3单纯形法的原理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三节单纯形法的原理线性规划解的概念单纯形法原理一、线性规划解的概念可行解最优解基基向量基变量非基变量基本解基本可行解基本最优解1、可行解把满足约束条件的一组决策变量值x1，x2，…，xn称为该线性规划问题的可行解。2、最优解在可行解集中，使目标函数达到最优值的可行解称为最优解。3、基若矩阵A的秩为m，B为A中的m*m阶子阵且

2、B

3、≠0，则称B为线性规划问题的一个基。例：研究下面的约束条件标准化约束方程组系数矩阵如下x1x2x3x4秩r=3则基的个数最多为秩r=3则基的个数最多为4、基向量B矩阵中P

4、j向量称为基向量。基基向量P1P2P3P1P2P4P1P3P4P2P3P45、基变量基基向量基变量P1P2P3X1X2X3P1P2P4X1X2X4P1P3P4X1X3X4P2P3P4X2X3X4与基向量Pj相对应的变量Xj（j=1,2,…,m）称为基变量。6、非基变量基基向量基变量非基变量P1P2P3X1X2X3X4P1P2P4X1X2X4X3P1P3P4X1X3X4X2P2P3P4X2X3X4X1与基向量Pj相对应的变量Xj（j=1,2,…,m）称为基变量。其余的n-m个变量称为非基变量。7、基本

5、解若令所有非基变量取值为零，所得的约束方程组AX=b的解称为方程组AX=b关于基B的基本解，也称为线性规划问题的一个基本解。如基基变量为x1、x2、x3，非基变量为x4回到约束方程组，将基变量集中于等式左边，非基变量集中于等式右边回到约束方程组，将基变量集中于等式左边，非基变量集中于等式右边令非基变量x4=0，则令非基变量x4=0，则这就是基本解之一解得同理基基变量为x1、x2、x4，非基变量为x3回到约束方程组，将基变量集中于等式左边，非基变量集中于等式右边令非基变量x3=0，则令非基变量x3=0

6、，则这也是基本解之一同理，可得其他基本解（只考虑约束条件，不考虑符号条件）8、基本可行解满足非负条件的基本解称为基本可行解。以上基本解中，同时考虑符号条件，只有Ⅹ3、Ⅹ4为基本可行解，Ⅹ1、Ⅹ2不是基本可行解。9、基本最优解使目标函数达到最优值的基本可行解。将以上基本可行解X1、X2代入目标函数中，使得目标函数取得最优值的解为最优解。解的关系非可行解可行解基本基本解可行解最优解基本最优解二、单纯形法原理设线性规划标准如下观察模型中A矩阵系数的特点。相当于加入新变量（松弛变量、剩余变量或人工变量）系数

7、矩阵如下上述A中存在一个m阶单位子阵B，B为初始可行基，B所对应的变量即初始基变量（Xn-m+1，Xn-m+2，…，Xn）基变量可用非基变量表示如下基变量可用非基变量表示如下令所有非基变量取零，则得到初始基本可行解即：或将初始基本可行解代入目标函数，得即：则：令：讨论若，则S的最大值是S0，即目标函数达到最优值maxS=S0此时，最优解为否则，目标函数值就还有继续改善的可能。比如有某个（若j=k即）。若对应的非基变量xk变成基变量，则称变量xk为调入变量，那么，从取值的角度看，xk就会从零变成某一个

8、正数（非基变量为0，基变量一般不为0），则λk的值为正值，从而会使S值从S0变大，即目标函数得到进一步改善。确定调入变量xk后，如何确定调出变量呢？分析以下式子假设有λk>0，因此，可以选xk（1≤k≤n-m）作为调入变量，xk的取值将从0变成一个正数，但不可能无限制的增大，因为上式中所有变量应保证非负（即保证解的可行性），即有由于其他非基变量保持不变，取值仍为零，上式即可简写成所以，即当xk的值增加到时，原基变量的取值首先变成零，这样就选变量为调出变量。确定调入变量和调出变量后，继续整理目标函数

9、，分析新的检验数的符号，若存在不满足符号条件的检验数，继续调整调入变量和调出变量，直至所有检验数均满足符号条件（意味着目标函数值不可能进一步改善）。练习题P.96第1、2、3题