单纯形法-人工变量法.ppt
人工变量的引入及其解法人工变量的引入及其解法 当约束条件为当约束条件为“”型，引入剩余变量和人工变量型，引入剩余变量和人工变量由于所添加的剩余变量的技术系数为由于所添加的剩余变量的技术系数为 1，不能作为初，不能作为初始可行基变量，为此引入一个人为的变量（注意，此始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为时约束条件已为“=”型），以便取得初始基变量，故型），以便取得初始基变量，故称为人工变量称为人工变量由于人工变量在原问题的解中是不能存在的，应尽快由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定法而定两种方法两种方法大大M法法二阶段法二阶段法其中第其中第2、3个约束方程中无明显基变量，分别加上人工变量个约束方程中无明显基变量，分别加上人工变量x6,x7,约束方程为约束方程为“=”或或“=”的情形的情形（加人工变量）这时，初始基和初始基可行解很明显。这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可不满足原来的约束条件。如何使得可从从X(0)开始，经迭代逐步得到开始，经迭代逐步得到x6=0，x7=0 的基可行解，的基可行解，从而求得问题的最优解，有两种方法：从而求得问题的最优解，有两种方法：反反之之，若若加加了了人人工工变变量量的的问问题题解解后后最最优优解解中中仍仍含含人人工工变变量量为基变量，便说明原问题无可行解。例的单纯形表格为：为基变量，便说明原问题无可行解。例的单纯形表格为：只只要要原原问问题题有有可可行行解解，随随着着目目标标函函数数向向最最大大化化方方向向的的改改善善，人人工工变变量量一一定定会会逐逐步步换换出出基基，从从而而得得到到原原问问题题的的基基可可行行解解，进进而得到基最优解。而得到基最优解。大大M法法在目标函数中加上惩罚项。在目标函数中加上惩罚项。max=3 3x1-x2-x3-Mx6-Mx7其中其中M为充分大的正数。为充分大的正数。3-6M M-13M-1 0-M 0 0 0 x4 10 3 -2 0 1 0 0 -1 -M x6 1 0 1 0 0 -1 1 -2 1-1 x3 1 -2 0 1 0 0 0 1 1 1-1+M 0 0-M 0 -3M+1 0 x4 12 3 0 0 1 -2 -1 x2 1 0 1 0 0 -1 4-1 x3 1 -2 0 1 0 0 1 0 0 0-13 x1 4 1 0 0 1/3 -2/3 -1 x2 1 0 1 0 0 -1 -1 x3 9 0 0 1 2/3 -4/3 -2 0 0 0 -1/3 -1/3X X*=(4=(4，1 1，9 9，0 0，0)0)T T,z,z*=2=2113/2 1 两阶段法两阶段法第一阶段第一阶段：以：以人工变量之和人工变量之和最小化为目标函数。最小化为目标函数。min min =x6+x7 第二阶段第二阶段：以第一阶段的最优解：以第一阶段的最优解(不含人工变量不含人工变量)为初始解，为初始解，以原目标函数为目标函数。以原目标函数为目标函数。约束方程为约束方程为“=”或或“=”的情形的情形（加人工变量）人工变量法（确定初始可行基）：原约束方程：AX=b加入人工变量：xn+1，xn+m人人工工变变量量是是虚虚拟拟变变量量，加加入入原原方方程程中中是是作作为为临临时时基基变变量量，经经过过基基的的旋旋转转变变换换，将将人人工工变变量量均均能能换换成成非非基基变变量量，所所得得解解是是最最优优解解；若若在在最最终终表表中中检检验验数数小小于于零零，而而且且基基变变量量中中还有某个非零的人工变量，原问题无可行解。还有某个非零的人工变量，原问题无可行解。Max Z=2x1+x 2+x 3 s.t.4x1+2x2+2x 34 2x1+4x2 20 4x1+8x2+2x 316 x1，x2，x 30 用两阶段法求下面线性规划问题的解用两阶段法求下面线性规划问题的解线性规划问题解的讨论线性规划问题解的讨论一、无可行解一、无可行解 max z=2x1+4x2 x1+x2 10 2x1+x2 40 x1,x2 0人工变量不能从基底人工变量不能从基底人工变量不能从基底人工变量不能从基底换出，此时原线性规换出，此时原线性规换出，此时原线性规换出，此时原线性规划问题无可行解。划问题无可行解。划问题无可行解。划问题无可行解。x1x2CBXBbX3 x5x5 0-1 0 0 0 0 -1 x1 x2 x3 x4 x540 2 1 0 -1 110 1 1 1 0 0cj1040/2x1 x5 0-1 20 0 -1 -2 -1 110 1 1 1 0 0 cj-zj0 -1 -2 -1 0cj-zj2 1 0 -1 0 Z0=-40Z1=-20两阶段法两阶段法例例:max z=3x1+4x2 x1+x2 40 2x1+x2 60 x1-x2 =0 x1,x2 0此题初始解是退化的。此题初始解是退化的。此题初始解是退化的。此题初始解是退化的。最优解也是退化解。最优解也是退化解。最优解也是退化解。最优解也是退化解。退化解迭代中，当换入退化解迭代中，当换入退化解迭代中，当换入退化解迭代中，当换入变量取零值时目标函数变量取零值时目标函数变量取零值时目标函数变量取零值时目标函数值没有改进，值没有改进，值没有改进，值没有改进，x1x2 0 x3 40 1 1 1 0 0 0 x4 60 2 1 0 1 -1 -M x5 0 1 -1 0 0 1 0 x3 40 0 2 1 0 0 x4 60 0 3 0 1 3 x1 0 1 -1 0 0 3+M 4-M 0 0 0 zj-cj 0 0 0 -7/3 zj-cj 0 x3 0 0 0 1 -1/3 4 x2 20 0 1 0 1/3 3 x1 20 1 0 0 1/3 cj 3 4 0 0 -M CB XB b x5 x1 x2 x3 x4 0 7 0 0 zj-cj 0 0 -3.5 0 zj-cj 4 x2 20 0 1 1/2 0 0 x4 0 0 0-3/2 1 3 x1 20 1 0 1/2 0 例例 max z=3x1+5x2 3x1+5x2 15 2x1+x2 5 2x1+2x2 11 x1,x2 0如果将如果将x x1 1换入基底，得换入基底，得另一解，由可行域凸性另一解，由可行域凸性易知，有两个最优解必易知，有两个最优解必有无穷多组最优解有无穷多组最优解当非基底变量的检验数当非基底变量的检验数中有取零值，或检验数中有取零值，或检验数中零的个数大于基变量中零的个数大于基变量个数时，有无穷多解个数时，有无穷多解。CBXBbx3 x4x4x5x5 000 3 5 0 0 0 x1 x2 x3 x4 x5 5 2 1 0 1 015 3 5 1 0 035 11/2x2 x4x5 5003 3/5 1 1/5 0 02 7/5 0 -1/5 1 0 5 4/5 0 -2/5 0 1 cj-zj 0 0 -1 0 0cj-zj3 5 0 0 0 Z0=011 2 2 0 0 1Z1=15x1x2四、无（有）界解四、无（有）界解 max z=x1+x2 -2x1+x2 4 x1-x2 2 -3x1+x2 3 x1,x2 0若检验数有大于若检验数有大于若检验数有大于若检验数有大于0 0，而对应系数列，而对应系数列，而对应系数列，而对应系数列中元素全部小于中元素全部小于中元素全部小于中元素全部小于或等于零（无换或等于零（无换或等于零（无换或等于零（无换出变量）则原问出变量）则原问出变量）则原问出变量）则原问题有无界解。题有无界解。题有无界解。题有无界解。练习：写出单纯形表练习：写出单纯形表,分析检验数分析检验数 与系数关系并画图验证。与系数关系并画图验证。线性规划解除有线性规划解除有唯一最优解唯一最优解的情况外，还有的情况外，还有如下几种情况如下几种情况 无可行解无可行解无可行解无可行解 退化退化退化退化 无穷多解无穷多解无穷多解无穷多解 无界解无界解无界解无界解人工人工变量变量不能不能从基从基底中底中换出换出基可行基可行解中非解中非零元素零元素个数小个数小于基变于基变量数量数检验数检验数中零的中零的个数多个数多于基变于基变量的个量的个数数检验数大检验数大于零，但于零，但对应列元对应列元素小于等素小于等于零，无于零，无换出变量换出变量唯一最优解唯一最优解 否 否否 是是是添添加加松松弛弛变变量量、人人工工变变量量 列出初始单纯形表列出初始单纯形表计算非基变量计算非基变量各列的检验数各列的检验数j所有所有j 0基变量中基变量中有非零的有非零的人工变量人工变量某非基某非基变量检变量检验数为验数为零零无可行解无可行解无穷多最优解无穷多最优解对任一对任一j0有有aik0无界解无界解令令k=maxjx xk k为换入变量为换入变量对对 所所 有有 aik 0计计 算算i i=bi/aik令令l=min=mini i 第第l l个个基基变变量量为为换换出出变变量，量，alk为主元素为主元素 迭代运算迭代运算.用非基变量用非基变量xk替换换出变量替换换出变量 .对主元素行对主元素行(第第l行行)令令 bl/alkbl;alj/alkajl对主元素列对主元素列(第第k列列)令令1aalklk;0;0其它其它元素表中其它行列元素元素表中其它行列元素令令 aij-ali/alkaikaaijij b bi i-b bl l/a/alklkaaikikbbi i j-alj/alk k j否对目标函数求极大值标准型线性规划对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图：问题，单纯形法计算步骤的框图：
