单纯形法、大M法.ppt

Page 1单纯形法的计算步骤单纯形法的计算步骤例例1.10 用单纯形法求下列线性规划的最优解用单纯形法求下列线性规划的最优解解：解：1）将问题化为标准型，加入松驰变量将问题化为标准型，加入松驰变量x3、x4则标准型为则标准型为:4/15/2024Page 2单纯形法的计算步骤单纯形法的计算步骤2）求出线性规划的初始基可行解，）求出线性规划的初始基可行解，列出初始单纯形表。列出初始单纯形表。cj3400icBXBbx1x2x3x40 x34021100 x4301301检验数检验数003？4/15/2024Page 3单纯形法的计算步骤单纯形法的计算步骤3）进行最优性检验）进行最优性检验如果表中所有检验数如果表中所有检验数 ，则表中的基可行解就是问题，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。的最优解，计算停止。否则继续下一步。4）从一个基可行解转换到另一个目标值更大的基可行解，）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表列出新的单纯形表确定换入基的变量。选择确定换入基的变量。选择 ，对应的变量，对应的变量xj作为换入变作为换入变量，当有一个以上检验数大于量，当有一个以上检验数大于0时，一般选择最大的一个检时，一般选择最大的一个检验数，即：验数，即：，其对应的，其对应的xk作为换入变作为换入变量。量。确定换出变量。根据下式计算并选择确定换出变量。根据下式计算并选择，选最小的选最小的对应基对应基变量作为换出变量。变量作为换出变量。4/15/2024Page 4单纯形法的计算步骤单纯形法的计算步骤用换入变量用换入变量Xk替换基变量中的换出变量，得到一个新的替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。可以画出一个新的单纯形表。5）重复）重复3）、）、4）步直到计算结束为止。）步直到计算结束为止。数学解释数学解释经济解释经济解释检验数检验数j单位变量增加带来目标单位变量增加带来目标函数变化值函数变化值单位产品产量增加带来单位产品产量增加带来的净利润变化值的净利润变化值最小比值最小比值j确保在迭代过程中所有确保在迭代过程中所有变量的值非负，即每步变量的值非负，即每步得到的解均为基可行解。得到的解均为基可行解。确保在增加产品产量的确保在增加产品产量的过程中，不超过现在的过程中，不超过现在的资源限量。资源限量。4/15/2024Page 5单纯形法的计算步骤单纯形法的计算步骤cj3400icB基变量基变量bx1x2x3x40 x34021100 x430130134000 x34x23x14x2换入列换入列bi/ai2，ai204010换换出出行行将将3化为化为15/311801/301/31011/3303005/304/3乘乘以以3/5后后得得到到103/51/518011/52/540011最优解：最优解：最优值：最优值：4/15/2024Page 6单纯形法的计算步骤单纯形法的计算步骤例例1.11 用单纯形法求解用单纯形法求解解：将数学模型化为标准形式：解：将数学模型化为标准形式：不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。4/15/2024Page 7单纯形法的计算步骤单纯形法的计算步骤cj12100icB基变量基变量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x220 x x2 22 21/3150120753017131/309022560 x x1 111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3最优解：最优解：最优值：最优值：4/15/2024Page 8单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法一、人工变量法：一、人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初始基可行解，在约束条件的等式左端为了得到一组基向量和初始基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为工变量，构成的可行基称为人工基人工基，用，用大大MM法法或或两阶段法两阶段法求解，求解，这种用人工变量作桥梁的求解方法称为这种用人工变量作桥梁的求解方法称为人工变量法人工变量法。1 1、大、大M M 法法通通过过引引进进人人工工变变量量，构构造造一一个个辅辅助助的的线线性性规规划划问问题题，然然后后由由辅辅助助的的线线性性规规划划问问题题找找出出原原问问题题的的第第一一个个初初始始可可行行基基，在在此此基基础础上，利用单纯形方法求出原问题的最优解。上，利用单纯形方法求出原问题的最优解。4/15/2024Page 9单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法例例1.10 用大用大M法解下列线性规划法解下列线性规划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。4/15/2024Page 10单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。4/15/2024Page 11单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i0 x64-43110104-Mx51011201005-Mx712210001132M2+M1+2MM0 x636501013/5-Mx583300108/3-1x312210005-6M5M0M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/34/15/2024 2、两阶段法、两阶段法在原来问题引入人工变量后分两个阶段求解线性在原来问题引入人工变量后分两个阶段求解线性规划问题的方法。其中，第一阶段在原来问题中引入规划问题的方法。其中，第一阶段在原来问题中引入人工变量，设法构造一个单位阵的初始可行基，另外人工变量，设法构造一个单位阵的初始可行基，另外在目标函数中令非人工变量的系数全部为在目标函数中令非人工变量的系数全部为0，人工变量，人工变量的系数为的系数为1，构造一个新的辅助目标函数。在此基础上，构造一个新的辅助目标函数。在此基础上，建立辅助线性规划问题。然后运用单纯形方法求解，建立辅助线性规划问题。然后运用单纯形方法求解，直到辅助目标函数值为直到辅助目标函数值为0时为止时为止。第二阶段重新回到原第二阶段重新回到原来的问题，以第一阶段得到的可行基为初始可行基，来的问题，以第一阶段得到的可行基为初始可行基，运用单纯形方法以求出原来问题的解。运用单纯形方法以求出原来问题的解。4/15/2024 3)两阶段法的计算步骤两阶段法的计算步骤（1）不考虑原问题是否存在基可行解，）不考虑原问题是否存在基可行解，引进人工变引进人工变量，构造辅助线性规划问题。量，构造辅助线性规划问题。（2）用单纯形方法求解辅助问题，若辅助问题的目标）用单纯形方法求解辅助问题，若辅助问题的目标函数值函数值w 0，则原问题无可行解，停止计算。则原问题无可行解，停止计算。（3）若辅助问题目标函数的）若辅助问题目标函数的值值w=0，则将第一阶段则将第一阶段计算得到的最终表，除去人工变量，计算得到的最终表，除去人工变量，将目标函数行的将目标函数行的系数换原问题的目标函数系数，作为第二阶段的初始系数换原问题的目标函数系数，作为第二阶段的初始表。表。4）解的判断同单纯形法）解的判断同单纯形法4/15/2024 例例4.24.2用两阶段法求解线性规划问题用两阶段法求解线性规划问题min=-3xmin=-3x1 1+x+x2 2+x+x3 3 s.t.x s.t.x1 1-2x-2x2 2+x+x3 3 11 11 -4x -4x1 1+x+x2 2+2x+2x3 3 3 3 -2x -2x1 1 +x+x3 3 =1=1 x x1 1,x,x2 2,x,x3 3,0,0解：解：先在约束条件中加入人工变量，写出辅助规划问先在约束条件中加入人工变量，写出辅助规划问题。题。Min W=xMin W=x6 6+x+x7 7 s.t.x s.t.x1 1-2x-2x2 2+x+x3 3+x+x4 4 =11 =11 -4x -4x1 1+x+x2 2+2x+2x3 3 -x -x5 5+x+x6 6 =3=3 -2x -2x1 1 +x+x3 3 +x+x7 7=1=1 x xi i0,i=1,2,70,i=1,2,74/15/2024 用用单纯形法进行第一阶段的计算如下表单纯形法进行第一阶段的计算如下表4/15/2024 人工变量x x6 6=x x7 7 0 0，第一阶段目标函数第一阶段目标函数W=0W=0，则则(0，1，1，12，0)T是是原原线线性性规规划划问问题题的的基基可可行行解解，转转第第二阶段的计算二阶段的计算4/15/2024 由表可得最优解由表可得最优解为：为：x x1 1=4=4，x x2 2=1=1，x x3 3=9=9；目标函数值目标函数值 Z=-2Z=-24/15/2024Page 18单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法解的判别：解的判别：1）唯一最优解判别：）唯一最优解判别：最优表最优表中所有非基变量的检验数非零中所有非基变量的检验数非零,且基变量中无非零的人工变量，则线规划具有唯一最优解。且基变量中无非零的人工变量，则线规划具有唯一最优解。2）多重最优解判别：）多重最优解判别：最优表最优表中存在非基变量的检验数为零中存在非基变量的检验数为零,且且基变量中无非零的人工变量，基变量中无非零的人工变量，则线则性规划具有多重最则线则性规划具有多重最优解（或无穷多最优解）。优解（或无穷多最优解）。3）无界解判别：某个）无界解判别：某个k0且且aik（i=1，2,m）则线性）则线性规划具有无界解。规划具有无界解。4）无无可可行行解解的的判判断断：当当用用大大M单单纯纯形形法法计计算算得得到到最最优优解解并并且存在且存在人工变量人工变量0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：）退化解的判别：存在某个基变量为零的基本可行解。存在某个基变量为零的基本可行解。4/15/2024 二、二、退化、循环及其处理方法退化、循环及其处理方法退化、循环及其处理方法退化、循环及其处理方法 1、退化、退化 单纯形法计算中用单纯形法计算中用规则确定换出变量时，有时存规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。就有一个或几个基变量等于零，这就出现退化解。2、退化迭代的特点、退化迭代的特点（1）退化解的基变量中至少有一个取值为）退化解的基变量中至少有一个取值为0。（2）退化迭代中基在不断变化但解始终不变。）退化迭代中基在不断变化但解始终不变。（3）退化迭代不会引起目标函数值的改进。）退化迭代不会引起目标函数值的改进。3、防止循环迭代的方法、防止循环迭代的方法（1）摄动法）摄动法（2）字典顺序法）字典顺序法（3）最小下标法）最小下标法4/15/2024Page 20单纯形法小结单纯形法小结建建立立模模型型个个 数数取取 值值右右 端端 项项等式或等式或不等式不等式极大或极小极大或极小新加变新加变量目标量目标系数系数两两个个三个三个以上以上xj0 xj无无约束约束xj 0 bi 0bi 0=maxZminZxs xa求求解解图图解解法、法、单单纯纯形形法法单纯单纯形法形法不不处处理理令令xj=xj-xj xj 0 xj 0令令 xj=-xj不不处处理理约束条约束条件两端件两端同乘以同乘以-1加加松松弛弛变变量量xs加加入入人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=-ZminZ=max z0-M4/15/2024A A4/15/2024Page 22 线性规划模型的应用线性规划模型的应用一般而言，一个经济、管理问题需要满足以一般而言，一个经济、管理问题需要满足以下条件时，才能建立线性规划模型。下条件时，才能建立线性规划模型。要求解问题的目标函数能用数值指标来反映，且要求解问题的目标函数能用数值指标来反映，且为线性函数为线性函数 存在着多种方案存在着多种方案 要求达到的目标是在一定条件下实现的，这些约要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述束可用线性等式或不等式描述4/15/2024