单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,经济应用数学教程线性代数及其应用,经济应用数学教程线性代数及其应用,单纯形解法,在单纯形法被使用之前，线性规划问题迟迟未能被广泛使用，在计算方法上存在困难就是一个很主要的原因,.,单纯形法是线性规划问题的一般解法,.,它使线性规划问题在各个领域得到了广泛的应用,.,为了运用单纯形法解线性规划问题，首先要将线性规划问题的一般形式化为,标准形式,.,一、线性规划问题的标准形式,线性规划问题的,一般形式,：,线性规划问题的,标准形式：,标准形式的三个特征：,若目标函数已经是求最大值，则满足标准形式的要求；,若目标函数是求最小值，则,引进新目标函数,：,（,1,）目标函数为求最大值,最优解相同，最优值：,若某约束条件为等式，则满足标准形式的要求；,若某约束条件为不等式，则：,若某不等式是“,”,，则左边减去一个非负变量（称为松弛变量），使两边相等,.,若某不等式为“,”，则左边加上一个非负变量，使两边相等.,（,2,）约束条件为等式,若某常数项为非负数，则满足标准形式的要求；,若某,常数项为负数,，则该等式,两边同时乘以,-1,，,常数项就变为正数,.,（,3,）常数项为非负数,例,1,将线性规划问题化为标准形式,.,例,2,将线性规划问题化为标准形式,.,例,3,将线性规划问题化为标准形式,.,例,4,将线性规划问题化为标准形式,.,则线性规划问题的,标准形式可写成如下矩阵形式,：,线性规划问题化为标准形式以后，就可以讨论其单纯形解法,.,单纯形原理,二、有初始可行基的单纯形解法,检验关系式,单纯形矩阵,基本线性规划问题,单纯形解法的思想与步骤,(1),将基本线性规划问题化为标准形式；,(2),确定基变量与非基变量；,基变量的特征：增广矩阵中，这一列有一个元素为,1,，其余元素为,0,；（回忆简化阶梯形矩阵）,(3),调整基变量与非基变量，使得非基变量对应的检验数全为非负为止；,找主列：绝对值最大的负检验数所在的列；,找主元：常数项除以主列中的正元素，使得比值最小的元素就是主元；,利用矩阵初等行变换，主元化为,1,，主元所在列的其它元素化为,0.,例,5,解线性规划问题,（,1,）将线性规划问题,化为标准形式,，,写出其单纯形矩阵,；,（,2,）,按最优标准检查其检验数,，若全为非负，此时的基可行解即为最优解，求出最优值；若有负的，则需要换基；,（,3,）由负检验数中最小者（否则，目标函数值增加较少，达到最优值的速度将不是最快）先选出主列，再按照最小比值原则确定主元；,（,4,）,换基,：主元确定后，利用矩阵的初等行变换先将之变成,1,，再利用此,1,将该列所在的其他元素通过矩阵初等行变换变为,0,；,（,5,）,回到步骤（,2,），,直到检验数全是非负为止，再由此单纯形矩阵可得线性规划问题的最优解及最优值,.,单纯形法解线性规划问题的步骤：,例,6,解线性规划问题,例,7,解线性规划问题,例,8,解线性规划问题,例,9,解线性规划问题,。