单纯形法的计算步骤.ppt

单纯形法的计算步骤例1.10用单纯形法求下列线性规划的最优解单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。单纯形法的计算步骤3）进行最优性检验单纯形法的计算步骤用换入变量Xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。 单纯形法的计算步骤单纯形法的计算步骤例1.11用单纯形法求解单纯形法的计算步骤单纯形法的进一步讨论－人工变量法一、人工变量法： 前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初始基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。单纯形法的进一步讨论－人工变量法例1.10用大M法解下列线性规划单纯形法的进一步讨论－人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：单纯形法的进一步讨论－人工变量法单纯形法的进一步讨论－人工变量法单纯形法小结线性规划模型的应用 一般而言，一个经济、管理问题需要满足以下条件时，才能建立线性规划模型。*Page**解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:b3040θi00cB0043cj1031x40112x3x4x3x2x1XB检验数003？如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表确定换入基的变量。选择，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。确定换出变量。根据下式计算并选择θ，选最小的θ对应基变量作为换出变量。 确保在增加产品产量的过程中，不超过现在的资源限量。确保在迭代过程中所有变量的值非负，即每步得到的解均为基可行解。最小比值θj单位产品产量增加带来的净利润变化值单位变量增加带来目标函数变化值检验数σj经济解释数学解释x2x1x2x34300043b3040θi00cB0043cj41031x40112x3x4x3x2x1基变量换入列bi/ai2，ai204010换出行将3化为15/311801/301/3101－1/3303005/30－4/3乘以3/5后得到103/5－1/51801－1/5－2/5400－1－1最优解：最优值：解：将数学模型化为标准形式：不难看出x4、x5可作为初始基变量，列单纯形表计算。x22x400012110511/320x50012-3215x40x5x4x3x2x1b基变量cBθi00121cj20－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3最优解：最优值：1、大M法通过引进人工变量，构造一个辅助的线性规划问题，然后由辅助的线性规划问题找出原问题的第一个初始可行基，在此基础上，利用单纯形方法求出原问题的最优解。解：首先将数学模型化为标准形式系数矩阵中不存在单位矩阵，无法建立初始单纯形表。其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。-25/3-50002/3010019/3x3-15/3100131/3x132101013x2200005↑31/313/5003/531/5x5-M——0－2/510－2/511/5x3-1——0－1/501－6/53/5x2200－M05M↑5-6M——0001－221x3