单纯形法,大m法.ppt

:1)将问题化为标准型,加入松驰变量x3、x4则标准型为:Date单纯形法的计算步骤2)求出线性规划的初始基可行解,列出初始单纯形表。cj3400θicBXBbx1x2x3x40x34021100x4301301检验数003?Date单纯形法的计算步骤3)进行最优性检验如果表中所有检验数,则表中的基可行解就是问题的最优解,计算停止。否则继续下一步。4)从一个基可行解转换到另一个目标值更大的基可行解,列出新的单纯形表确定换入基的变量。选择,对应的变量xj作为换入变量,当有一个以上检验数大于0时,一般选择最大的一个检验数,即:,其对应的xk作为换入变量。确定换出变量。根据下式计算并选择θ,选最小的θ对应基变量作为换出变量。Date单纯形法的计算步骤用换入变量Xk替换基变量中的换出变量,得到一个新的基。对应新的基可以找出一个新的基可行解,并相应地可以画出一个新的单纯形表。5)重复3)、4)步直到计算结束为止。数学解释经济解释检验数σj单位变量增加带来目标函数变化值单位产品产量增加带来的净利润变化值最小比值θj确保在迭代过程中所有变量的值非负,即每步得到的解均为基可行解。确保在增加产品产量的过程中,不超过现在的资源限量。Date单纯形法的计算步骤cj3400θicB基变量bx1x2x3x40x34021100x430130134000x34x23x14x2换入列bi/ai2,ai2>04010换出行将3化为15/311801/301/3101-1/3303005/30-4/3乘以3/5后得到103/5-1/51801-1/5-2/5400-1-1最优解:最优值::将数学模型化为标准形式:不难看出x4、x5可作为初始基变量,列单纯形表计算。Date单纯形法的计算步骤cj12100θicB基变量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220-x221/3150120753017131/30-90-22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3最优解:最优值:Date单纯形法的进一步讨论-人工变量法一、人工变量法: 前面讨论了在标准型中系数矩阵有单位矩阵,很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵,为了得到一组基向量和初始基可行解,在约束条件的等式左端加一组虚拟变量,得到一组基变量。这种人为加的变量称为人工变量,构成的可行基称为人工基,用大M法或两阶段法求解,这种用人工变量作桥梁的求解方法称为人工变量法。1、大M法通过引进人工变量,构造一个辅助的线性规划问题,然后由辅助的线性规划问题找出原问题的第一个初始可行基,在此基础上,利用单纯形方法求出原问题的最优解。Date单纯形法的进一步讨论-:首先将数学模型化为标准形式系数矩阵中不存在单位矩阵,无法建立初始单纯形表。Date单纯形法的进一步讨论-人工变量法故人为添加两个单位向量,得到人工变量单纯形法数学模型:其中:M是一个很大的抽象的数,不需要给出具体的数值,可以理解为它能大于给定的任何一个确定数值;再用前面介绍的单纯形法求解该模型,计算结果见下表。Date