单纯形法ppt课件.ppt

《单纯形法ppt课件.ppt》由会员分享，可在线阅读，更多相关《单纯形法ppt课件.ppt（9页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Page 1单纯形法ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望Page 2单纯形法的计算步骤单纯形法的计算步骤用换入变量用换入变量Xk替换基变量中的换出变量，得到一个新的替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。可以画出一个新的单纯形表。5）重复）重复3）、）、4）步直到计算结束为止。）步直到计算结束为止。数学解释经济解释检验数j单位

2、变量增加带来目标函数变化值单位产品产量增加带来的净利润变化值最小比值j确保在迭代过程中所有变量的值非负，即每步得到的解均为基可行解。确保在增加产品产量的过程中，不超过现在的资源限量。Page 3单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法一、人工变量法：一、人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初始基可行解，在约束条件的等式左端为了得到一组基向量和初始基可行解，在约束条件的等式左端加

3、一组虚拟变量，得到一组基变量。这种人为加的变量称为人加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为工变量，构成的可行基称为人工基人工基，用，用大大MM法法或或两阶段法两阶段法求解，求解，这种用人工变量作桥梁的求解方法称为这种用人工变量作桥梁的求解方法称为人工变量法人工变量法。1 1、大、大M M 法法通通过过引引进进人人工工变变量量，构构造造一一个个辅辅助助的的线线性性规规划划问问题题，然然后后由由辅辅助助的的线线性性规规划划问问题题找出原问题的第一个初始可行基，在此基础上，利用单纯形方法求出原问题的最优解。找出原问题的第一个初始可行基，在此基础上，利用单纯形方

4、法求出原问题的最优解。2、两阶段法、两阶段法在原来问题引入人工变量后分两个阶段求解线性在原来问题引入人工变量后分两个阶段求解线性规划问题的方法。其中，第一阶段在原来问题中引入规划问题的方法。其中，第一阶段在原来问题中引入人工变量，设法构造一个单位阵的初始可行基，另外人工变量，设法构造一个单位阵的初始可行基，另外在目标函数中令非人工变量的系数全部为在目标函数中令非人工变量的系数全部为0，人工变量，人工变量的系数为的系数为1，构造一个新的辅助目标函数。在此基础上，构造一个新的辅助目标函数。在此基础上，建立辅助线性规划问题。然后运用单纯形方法求解，建立辅助线性规划问题。然后运用单纯形方法求解，直到辅

5、助目标函数值为直到辅助目标函数值为0时为止时为止。第二阶段重新回到原第二阶段重新回到原来的问题，以第一阶段得到的可行基为初始可行基，来的问题，以第一阶段得到的可行基为初始可行基，运用单纯形方法以求出原来问题的解。运用单纯形方法以求出原来问题的解。3)两阶段法的计算步骤两阶段法的计算步骤（1）不考虑原问题是否存在基可行解，）不考虑原问题是否存在基可行解，引进人工变引进人工变量，构造辅助线性规划问题。量，构造辅助线性规划问题。（2）用单纯形方法求解辅助问题，若辅助问题的目标）用单纯形方法求解辅助问题，若辅助问题的目标函数值函数值w 0，则原问题无可行解，停止计算。，则原问题无可行解，停止计算。（3

6、）若辅助问题目标函数的值）若辅助问题目标函数的值w=0，则将第一阶段，则将第一阶段计算得到的最终表，除去人工变量，计算得到的最终表，除去人工变量，将目标函数行的将目标函数行的系数换原问题的目标函数系数，作为第二阶段的初始系数换原问题的目标函数系数，作为第二阶段的初始表。表。4）解的判断同单纯形法）解的判断同单纯形法Page 6单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法解的判别：解的判别：1）唯一最优解判别：）唯一最优解判别：最优表最优表中所有非基变量的检验数非零中所有非基变量的检验数非零,且基变量中无非零且基变量中无非零的人工变量，则线规划具有唯一最优解。的人工变量，则线规划

7、具有唯一最优解。2）多重最优解判别：）多重最优解判别：最优表最优表中存在非基变量的检验数为零中存在非基变量的检验数为零,且基变量中无非零且基变量中无非零的人工变量，则线则性规划具有多重最优解（或无穷多最优解）。的人工变量，则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个）无界解判别：某个k0且且aik（i=1，2,m）则线性规划具有无界解。）则线性规划具有无界解。4）无无可可行行解解的的判判断断：当当用用大大M单单纯纯形形法法计计算算得得到到最最优优解解并并且且存存在在人人工工变变量量0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变

8、量为零的基本可行解。）退化解的判别：存在某个基变量为零的基本可行解。二、二、退化、循环及其处理方法退化、循环及其处理方法退化、循环及其处理方法退化、循环及其处理方法 1、退化、退化 单纯形法计算中用单纯形法计算中用规则确定换出变量时，有时存规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。就有一个或几个基变量等于零，这就出现退化解。2、退化迭代的特点、退化迭代的特点（1）退化解的基变量中至少有一个取值为）退化解的基变量中至少有一个取值为0。（2）退化迭代中基在不断变化但解始终不变。）退化

9、迭代中基在不断变化但解始终不变。（3）退化迭代不会引起目标函数值的改进。）退化迭代不会引起目标函数值的改进。3、防止循环迭代的方法、防止循环迭代的方法（1）摄动法）摄动法（2）字典顺序法）字典顺序法（3）最小下标法）最小下标法Page 8单纯形法小结单纯形法小结建立模型个 数取 值右 端 项等式或不等式极大或极小新加变量目标系数两个三个以上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-M11/2/2022A A