线性规划问题的单纯形解法

§6线性规划问题的单纯形解法目标函数最大值例1、将下面的线性规划问题化为标准形式于是所给线性规划问题化为标准形式例2、将下面的线性规划问题化为标准形式于是所给线性规划问题化为标准形式于是所给线性规划问题化为标准形式例3、将下面的线性规划问题化为标准形式解：将约束条件中第一个线性方程式乘以-1，于是所给线性规划问题化为标准形式例4、将下面的线性规划问题化为标准形式例5、将下面的线性规划问题化为标准形式于是所给线性规划问题化为标准形式定义6.3：已知线性规划问题，将它化为标准形式后，写出约束条件中线性方程组的增广矩阵，在下面添加检验数和常数项，得到的矩阵称为单纯形矩阵，记作T，单纯形矩阵最下面一行称为检验行下面通过例子说明求解的一般方法于是此线性规划问题化为标准形式：问题关键：目标函数的表达式中只显含自由未知量（非基变量），且其系数皆为负数自由未知量称为非基变量，非自由未知量称为基变量基变量特征：在线性方程组的系数中只有一个是1，其余都是0基本线性规划问题的单纯形矩阵为判断此初始基本可行解是否是最优解，方法如下：下面通过具体例子说明如何寻找新的基变量例1、解线性规划问题解：引进松弛变量于是所给线性规划问题化为标准形式得到单纯形矩阵基变量用圆圈标出检验数绝对值大的为主列正元素种比值小者为主元例2、解线性规划问题得到单纯形矩阵解得：所以无穷多解为：最优值为检验行的常数项maxS=1