线性规划图解法几何意.ppt

**********************************************************************三.单纯形法原理1.确定初始基可行解：对标准型的LP问题在约束条件(1.1)的变量的系数矩阵中总会存在一个单位矩阵。(2)当线性规划的约束条件都为≤号时，其松弛变量对应的系数列向量构成的矩阵即为单位阵；(3)当线性规划的约束条件为≥或＝的情况，引入人工变量后也可实现。(1)系数矩阵中可以直接观察得到一个单位子矩阵；第31页，讲稿共59页，2023年5月2日，星期三三.单纯形法原理（2）2.从一个基可行解转换为相邻的基可行解：定义：两个基可行解称为相邻的，如果他们之间变换且仅变换一个基变量。设初始基可行解为：可知：其对应的系数矩阵的增广矩阵为：第32页，讲稿共59页，2023年5月2日，星期三三.单纯形法原理（3）易得：(1.3)+(1.4)×θ(θ0),得令：显然：为使X(1)成为可行解，令：可证明:将(1.6)式代回到X(1)中,X(1)为基可行解，此时完成了从一个基可行解到另一个与其相邻的基可行解的转换。第33页，讲稿共59页，2023年5月2日，星期三三.单纯形法原理（4）证明：将与变量x1,…,xl-1,xl+1…,xm,xj对应的列向量，经重新排列后加上b列有如下形式：因为P1,P2,…,Pl-1，Pj,Pl+1,…Pm线性无关，故X(1)为基可行解。第34页，讲稿共59页，2023年5月2日，星期三三.单纯形法原理（5）3.最优性检验与解的判别：将2中的基可行解X(0)与X(1)分别代入目标函数，得称为检验数第35页，讲稿共59页，2023年5月2日，星期三三.单纯形法原理（6）(1)当所有的λj≤0时，现行基可行解为最优解；①当所有的λj0时，该线性规划问题有唯一最优解；②当所有的λj≤0，且对某个非基变量xk，有λk=0,该线性规划问题有无穷多最优解。(2)当存在某个λj0且对应的列向量Pj≤0时，该线性规划问题有无界解；(4)对线性规划问题无可行解的判别将在后面讨论。(2)当存在某个λj0且对应的列向量Pj中有正分量时，说明目标函数值还可以增大，需要进行基变换；第36页，讲稿共59页，2023年5月2日，星期三第4节

单纯形法的计算步骤第37页，讲稿共59页，2023年5月2日，星期三一.单纯形法的计算步骤第一步：求初始基可行解，列出初始单纯形表XBbx1x2...xmxm+1...xj...xnx1x2...xmb1b2...bm10...0a1,m+1...a1j...a1n01...0a2,m+1...a2j...a2n...........................00...1am,m+1...amj...amncc1c2...cmcm+1...cj...cn首先写出关于价值系数的表：（非单纯形表）第38页，讲稿共59页，2023年5月2日，星期三一.单纯形法的计算步骤（2）将基变量下方的价值系数通过变换化为零，得初始单纯形表XBbx1x2...xmxm+1...xj...xnx1x2...xmb1b2...bm10...0a1,m+1...a1j...a1n01...0a2,m+1...a2j...a2n...........................00...1am,m+1...amj...amn-z00...0