列初始单纯形表.ppt

上页上页上页上页下页下页下页下页返回返回返回返回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 单纯形法的形法的进一步一步讨论