列初始单纯形表.pptx

上页上页上页上页下页下页下页下页返回返回返回返回2.4 2.4 单纯形法的计算步骤单纯形法的计算步骤 为书写规范和便于计算，对单纯形法的计算设计了单纯形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。本节介绍用单纯形表计算线性规划问题的步骤。上页上页上页上页下页下页下页下页返回返回返回返回 在上一节单纯形法迭代原理中可知，每一次迭代计算只要表示出当前的约束方程组及目标函数即可。单纯形表上页上页上页上页下页下页下页下页返回返回返回返回 2 1 0 0 0 检验数单纯形表结构 单纯形表单纯形表 24/65/1C上页上页上页上页下页下页下页下页返回返回返回返回 2 1 0 0 0 24/65/1C检验数单纯形表结构 单纯形表单纯形表基可行解：上页上页上页上页下页下页下页下页返回返回返回返回单纯形表结构 单纯形表单纯形表 2 1 0 0 0 24/65/1C检验数有时不有时不写此项写此项求求求求上页上页上页上页下页下页下页下页返回返回返回返回单纯形表结构 单纯形表单纯形表 2 1 0 0 0 24/65/1C检验数求求上页上页上页上页下页下页下页下页返回返回返回返回单纯形表结构 单纯形表单纯形表 2 1 0 0 0 24/65/1C检验数求求不妨设此不妨设此为主列为主列主行主行上页上页上页上页下页下页下页下页返回返回返回返回单纯形表结构 单纯形表单纯形表 2 1 0 0 0 24/65/1C检验数主元主元上页上页上页上页下页下页下页下页返回返回返回返回用单纯形表求解LP问题例、用单纯形表求解例、用单纯形表求解LPLP问题问题上页上页上页上页下页下页下页下页返回返回返回返回解：化标准型上页上页上页上页下页下页下页下页返回返回返回返回 2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 24/65/1主元化为1主列单位向量 换出 换入表表1：列初始单纯形表：列初始单纯形表 （单位矩阵对应的变量为基变量）（单位矩阵对应的变量为基变量）正检验数中最大者对正检验数中最大者对应的列为主列应的列为主列最小的值对应最小的值对应最小的值对应最小的值对应的行为主行的行为主行的行为主行的行为主行上页上页上页上页下页下页下页下页返回返回返回返回 2 1 0 0 0 0 15 0 5 1 0 0 2 4 1 2/6 0 1/6 0 0 1 0 4/6 0 -1/6 1 0 1/3 0 -1/3 0 15/524/26/4 0*5 2*2/6 +0*4/61-2/3=表表2：换基：换基 （初等行变换，主列化为单位向量，主元为（初等行变换，主列化为单位向量，主元为1）检验数检验数0确定主列确定主列 最小最小确定主列确定主列主元主元上页上页上页上页下页下页下页下页返回返回返回返回 2 1 0 0 0 0 15/2 0 0 1 5/4 -15/2 2 7/2 1 0 0 1/4 -1/2 1 3/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 检验数0，则目标函数不可能实现最优。上页上页上页上页下页下页下页下页返回返回返回返回例:求解线性规划问题一、大 M 法上页上页上页上页下页下页下页下页返回返回返回返回 一、大 M 法解:l加入松弛变量和剩余变量进行标准加入松弛变量和剩余变量进行标准 化化,加入人工变量构造初始可行基加入人工变量构造初始可行基.上页上页上页上页下页下页下页下页返回返回返回返回求解结果出现检验数非正若基变量中含非零的人工变量，则无可行解；否则，有最优解。一、大 M 法l用单纯形法求解（见下页）。用单纯形法求解（见下页）。目标函数中添加“罚因子”-M为人工变量系数，只要人工变量0，则目标函数不可能实现最优。上页上页上页上页下页下页下页下页返回返回返回返回 1 -2 1 -4 1 2 -2 0 1 3-63-6M M-1 3M-1M M-1 3M-1 3 -1 -1 x x1 x x2 x x3 0 x x4 11-M x x6 3 -M x x7 1C j-Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x x4 x x5 11 3/2 1 0 0 1 0 0 1 0 0 -M-M x x6 x x7 表表1（初始单纯形表）（初始单纯形表）一、大 M 法（单纯形法求解）上页上页上页上页下页下页下页下页返回返回返回返回 3 -2 0 0 1 0 -2 0 1 1 1 M M-1-1 0 0 3 -1 -1x x1 x x2 x x3 0 x x4 10-M x x6 1 -1 x x3 1C j-Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x x4 x x5 1 0 -1 1 -2 0 1 0 1 1-3 3M M-M-M x x6 x x7 一、大 M 法（单纯形法求解）表表2上页上页上页上页下页下页下页下页返回返回返回返回 3 0 0 0 1 0 -2 0 1 1 0 0 3 -1 -1 x x1 x x2 x x3 0 x x4 12-1 x x2 1 -1 x x3 1C j-Z j C j CB XB b 1 -2 0 -1 0 0 0 -1 0 0 x x4 x x5 4 2 -5 1 -2 0 1 1-1-M-1M-1-M-M-M-M x x6 x x7 表表3一、大 M 法（单纯形法求解）上页上页上页上页下页下页下页下页返回返回返回返回 1 0 0 0 1 0 0 0 1 0 0 0 3 -1 -1 x x1 x x2 x x3 3 x x1 4-1 x x2 1 -1 x x3 9 2 C j CB XB b1/3 -2/3 0 -1 2/3 -4/3-1/3 -1/3 0 0 x x4 x x5 2/3 -5/3 1 -2 4/3 -7/3 1/3-1/3-M 2/3-MM 2/3-M-M-M x x6 x x7 表表4一、大 M 法（单纯形法求解）最优解为最优解为最优解为最优解为目标函数目标函数目标函数目标函数值值值值 z=2z=2检验数均非正，此检验数均非正，此为最终单纯形表为最终单纯形表上页上页上页上页下页下页下页下页返回返回返回返回M在计算机上处理困难。分阶段处理先求初始基，再求解。二、两阶段法二、两阶段法上页上页上页上页下页下页下页下页返回返回返回返回二、两阶段法第一阶段:构造如下的线性规划问题人工变量的人工变量的系数矩阵为系数矩阵为单位矩阵，单位矩阵，可构成初始可构成初始可行基。可行基。目标函数仅含目标函数仅含目标函数仅含目标函数仅含人工变量，并要求人工变量，并要求人工变量，并要求人工变量，并要求实现最小化。实现最小化。实现最小化。实现最小化。若其最优解的若其最优解的若其最优解的若其最优解的目标函数值不为目标函数值不为目标函数值不为目标函数值不为0 0，也即最优解的基，也即最优解的基，也即最优解的基，也即最优解的基变量中含有非零的变量中含有非零的变量中含有非零的变量中含有非零的人工变量，则原线人工变量，则原线人工变量，则原线人工变量，则原线性规划问题无可行性规划问题无可行性规划问题无可行性规划问题无可行解。解。解。解。上页上页上页上页下页下页下页下页返回返回返回返回 用单纯形法求解上述问题用单纯形法求解上述问题,若若=0,进进入第二阶段入第二阶段,否则否则,原问题无可行解。原问题无可行解。第二阶段：去掉人工变量，还原目标函第二阶段：去掉人工变量，还原目标函数系数，做出初始单纯形表。数系数，做出初始单纯形表。用单纯形法求解即可。用单纯形法求解即可。二、两阶段法二、两阶段法下面举例说明，仍用大M法的例。上页上页上页上页下页下页下页下页返回返回返回返回例：二、两阶段法二、两阶段法上页上页上页上页下页下页下页下页返回返回返回返回 二、两阶段法二、两阶段法l构造第一阶段问题并求解构造第一阶段问题并求解解：解：用单纯形法求解用单纯形法求解上页上页上页上页下页下页下页下页返回返回返回返回二、两阶段法二、两阶段法（第一阶段、求第一阶段、求min min ）1 -2 1-4 1 2 -2 0 1 -6 1 3 0 0 0 x x1 x x2 x x3 0 x x4 11-1 x x6 3 -1 x x7 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 -1 x x4 x x5 x x6 0 11 0 3/2 1 1 0 -1 x x7 表表1上页上页上页上页下页下页下页下页返回返回返回返回 -1 -2 1 1 -3 -1 x x7 3 -2 0 0 1 0 -2 0 1 0 1 0 0 0 0 x x1 x x2 x x3 0 x x4 10-1 x x6 1 0 x x3 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 x x4 x x5 x x6二、两阶段法二、两阶段法（第一阶段、求第一阶段、求min min ）表表2上页上页上页上页下页下页下页下页返回返回返回返回 -5 4 -2 -1 -1 -1 x x7 3 0 0 0 1 0 -2 0 1 0 0 0 0 0 0 x x1 x x2 x x3 0 x x4 12 0 x x2 1 0 x x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 -1 0 0 -1 x x4 x x5 x x6二、两阶段法二、两阶段法（第一阶段、求第一阶段、求min min ）表表3：最终单纯形表：最终单纯形表第第二二阶阶段段ts不含人工不含人工变量且变量且=0=0上页上页上页上页下页下页下页下页返回返回返回返回二、两阶段法二、两阶段法第二阶段第二阶段 将将将将去去去去掉掉掉掉人人人人工工工工变变变变量量量量，还还还还原原原原目目目目标标标标函函函函数数数数系系系系数数数数，做做做做出出出出初初初初始始始始单单单单纯纯纯纯形形形形表表表表。3 0 0 0 1 0 -2 0 1 3 -1 -1 x x1 x x2 x x3 0 x x4 12-1 x x2 1-1 x x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 x x4 x x5 1 0 0 0 -1上页上页上页上页下页下页下页下页返回返回返回返回二、两阶段法二、两阶段法 1 0 0 0 1 0 0 0 1 3 -1 -1 x x1 x x2 x x3 3 x x1 4-1 x x2 1-1 x x3 9 C i CB XB b 1/3 -2/3 0 -1 2/3 -4/3 0 0 x x4 x x5 第二阶段第二阶段 0 0 0 -1/3 -1/3最优解为最优解为最优解为最优解为目标函数目标函数目标函数目标函数值值值值 z=2z=2上页上页上页上页下页下页下页下页返回返回返回返回单纯形法计算中的几个问题l1、目标函数极小化时解的最优性判断、目标函数极小化时解的最优性判断 只需用检验数 作为最优性的标志。l2、无可行解的判断、无可行解的判断 当求解结果出现所有 时，如基变量仍 含有非零的人工变量（两阶段法求解时第一阶 段目标函数值不等于0），则问题无可行解。上页上页上页上页下页下页下页下页返回返回返回返回退化 基可行解中存在基变量=0的解退化解 换入变量和换出变量的换入变量和换出变量的BlandBland规则规则选择 中下标最小的非基变量 为换入变量,这里:当按 规则计算存在两个和两个以上最小比值时,选下标最小的基变量为换出变量。单纯形法计算中的几个问题单纯形法计算中的几个问题上页上页上页上页下页下页下页下页返回返回返回返回2.5.1 2.5.1 单纯形法的进一步讨论单纯形法的进一步讨论