第二章 单纯型法.ppt

1、第二章 单纯形法,线性规划问题的矩阵表示 单纯形表的结构和性质 单纯形表的运算 初始基可行解的确定 基可行解的判别和改进,非基变量,基变量,1、线性规划的矩阵表示,B,N,I,I,B-1b,非基变量,基变量=CBB-1B-CB=0,Z+( CBB-1N-CN) XN= CBB-1b XB+B-1N XN=B-1b,Z+（CBB-1A-C）X= CBB-1b B-1AX= B-1b,基变量在目标函数中的系数等于0， 基变量在约束条件中的系数是一个单位矩阵 约束条件的右端B非负,2、单纯形表的结构和性质,注意： Z行中有m 个0，它们与基变量相对应。一般情况下，这m个0分散在Z行的各列中，并与基变

2、量相对应。 其余m行中有一个m阶单位矩阵I，其各列与基变量相对应。一般情况下，组成I的各列分散在表的各列中，它们与基变量相对应。,单纯形表的结构,我们将用单纯形表解决以下三个问题： 如何找出第一个（初始的）基可行解？ 如何判断这个初始基可行解是不是最优解？ 如果不是，怎样将它调整成一个“更好的”基可行解，以致最终求出最优解？,3、单纯形表的运算,当线性规划问题的约束条件全为“小于等于约束”，并且右边常数全部“大于等于0”，化标准问题时在每个约束中添加的松弛变量恰构成一个单位矩阵，这单位矩阵可作为初始可行基。添加的松弛变量即为基变量，其他变量为非基变量。 对于不能直接获得初始可行基的问题，可以用

3、引入人工变量的方法构造一初始可行基。这将在“人工变量法”中作介绍。,（1）初始基可行解的确定,用检验数j=Zj Cj 进行判断，若所有检验数j0，则X是最优解。 若存在某个检验数j 0,它所对应的列向量全部分量为非正，则所给问题的目标函数值无下界，因而无最优解。 若存在j 0,且它（们）所对应的列向量中都有正分量，则这时可进行基变换。,（2）基可行解的判别和改进,若存在j 0,且它（们）所对应的列向量中都有正分量，则这时可进行基变换。取max=1.。j 所对应的非基变量为进基变量。 将“右端”列中各数分别和“进基变量列”的各数作比式（只对进基变量列中的正数作比式），并以记这些比式中最小一个。获

4、得行所对应的基变量即为离基变量。 进基变量列和离基变量行相交处的元素成为“主元”，在其上加以圆圈。 进行单纯形变换，即令主元为1，主元所在列的其他元素为0。即得一新的单纯形表，继续进行判断。,（3）基可行解的基变换,目标函数,约束条件,基矩阵,右边常数,进基变量、离基变量、基变换,=,基变量,进基变量,离基变量,目标函数,约束条件,右边常数,=,目标函数,约束条件,新的基矩阵,右边常数,=,进基变量,离基变量,目标函数,约束条件,基矩阵,=,目标函数,约束条件,新的基矩阵,右边常数,=,单纯形表法的运算步骤,单纯形表的运算 Step 0 获得一个初始的单纯形表，确定基变量和非基变量 Step

5、1 检查基变量在目标函数中的系数是否等于0，在约束条件中的系数是否是一个单位矩阵 Step 2 如果表中非基变量在目标函数中的系数全为负数，则已得到最优解。停止。否则选择系数为正数且绝对值最大的变量进基。 Step 3 如果进基变量在约束条件中的系数全为负数或0，可行域开放，目标函数无界。停止。否则选取右边常数和正的系数的最小比值，对应的基变量离基。 Step 4 确定进基变量的列和离基变量的行交叉的元素为“主元”，对单纯形表进行行变换，使主元变为1，主元所在列的其他元素变为0。将离基的基变量的位置用进基的非基变量代替。转Step 1。,设X1表示I型饼干日产量，X2表示II型饼干日产量（单位

6、为吨），z表示I型和II型饼干所创造的日总利润,目标： max z = 5X1 +4X2,约束条件： 3X1 +5X2 15 （搅拌机的限制） 2X1 + X2 5 （成形机的限制） 2X1 +2X2 11 （烘箱的限制） X1 0 ， X2 0,例题：饼干生产问题,转化为标准模型 设z= - z, 引入松弛变量X3 , X4 , X5 0,目标： min z = -5X1 -4X2,约束条件： 3X1 +5X2 + X3 = 15 （搅拌机的限制） 2X1 + X2 + X4 = 5 （成形机的限制） 2X1 +2X2 + X5 = 11 （烘箱的限制） X1, X2, X3 , X4 ,

7、X5 0,写出初始单纯形表,15/3,5/2,x4离基,x1进基,11/2,x1,0,1/2,0,5/2,1/2,1,0,-5/2,0,-25/2,3/2,0,1,-3/2,0,15/2,7/2,0,0,-1,1,6,1,0,15/7,5,6,x2进基,x3离基,得到最优解，最优解为：,（x1，x2，x3，x4，x5）=（10/7，15/7，0，0，0，27/7） min z=-110/7，max z=110/7,x2,2/7,-3/7,0,15/7,1,0,-3/7,-13/7,0,-110/7,0,0,-1/7,5/7,0,10/7,0,1,-2/7,-4/7,1,27/7,0,0,某工厂

8、生产A、B、C三种产品，目标是这三种产品的总利润最大化。和利润有关的因素有原材料的消耗、排放的污染，产品的销售总额和三种产品的产量。有关数据如下表所示。设生产的产品全部销售，要求安排使总利润最大的生产计划，使得耗用原料不超过38吨，排放污染不超过25立方米，销售总额不低于100万元，三种产品的总产量不低于12吨。这是一个利润目标最大化的单目标线性规划问题。,两阶段法举例,人工变量法 如果约束条件全为“”，且右边常数全为非负，则引进的松弛变量就可以作为初始的基变量，得到一个初始的基础可行解。 如果约束条件有“=” ，右边常数全为非负，则需要加上非负人工变量，建立辅助问题。 如果约束条件有“”，右

9、边常数全为非负，则需要减去非负人工变量，建立辅助问题。,4、人工变量法,人工变量法举例,思路人为构造一个单位矩阵,人工变量,人工变量,大M法的步骤 引进松弛变量，使约束条件全为等式。 引进人工变量，令人工变量在目标函数中的系数为大M （任意大的正数） 用单纯形法求解，得到原问题的最优解。 若基变量中有非零的人工变量，则该LP无可行解。,(1)大M法的步骤,求解以下LP问题(大M法),化为标准型后加入人工变量，得到辅助问题,Minz=x1+3x2 s.t. 2x1+x2 =4 3x1+4x2-x3 =6 x1+3x2+x4 =3 x1,x2,x3,x4 0,+mr1+mr2,r1,r2,+r2,

10、+r1,最优解x1=2, x2=0, x4=1,r1=r2=x3=0, minz=2,练习：用大m法求解下列线性规划问题,引进松弛变量，使约束条件全为等式。 引进人工变量，建立辅助问题。辅助问题的目标函数为各人工变量之和（仅含人工变量）。 用人工变量作为辅助问题的初始基变量，用单纯形法求解辅助问题，得到辅助问题的最优解和最优解的目标函数值。 如果辅助问题最优解的目标函数值大于0，原问题可行域为空集，无可行解。如果辅助问题最优解的目标函数值等于0，辅助问题的最优解是原问题的初始基础可行解。 将第一阶段得到的最终表除去人工变量，将目标函数行的系数换原问题的目标函数系数，作为第二阶段计算的初始表，用单纯形法求解，得到原问题的最优解。,(2)两阶段法的步骤,求解以下LP问题(两阶段法),minZ=X1+3X2 s.t. 2x1+ x2 =4 3x1+4x2-x3 =6 x1+3x2+ x4 =3 x