第02章-对偶问题与灵敏度分析.ppt

运筹学第2章线性规划的对偶理论与灵敏度分析①建立初始单纯形表，对应一个基解，所有检验数均非正，转②；②若bi≥0，则得到最优解，停止；否则，若有bi＜0则br＝min{bi｜bi＜0}选第r行的基变量为出基变量，转③；③若所有arj≥0(j=1,2,…,n)，则原问题无可行解，停止；否则，xs为进基变量，转④；④以ars为主元素，作初等行变换使其变为1，该列其他元变为0，转②。□由此，美佳公司最优生产计划应为每天生产家电Ⅰ7/2件；家电Ⅲ3/4件□此时，z*=9.250-1/20-1/8-5/4007/213/8-9/401001/4-1/2001/20-1/83/4151/27/23/4x3x1x6023x1x2x3x4x5x6b基CB210003cj5灵敏度分析5.1简介5.2分析cj的变化5.3分析bi的变化5.4增加一个变量xj的变化5.5分析参数aij的变化5.6增加一个约束条件的分析□aij的变化使线性规划的约束系数矩阵A发生变化。①若变量xj在最终单纯形表中为非基变量，其约束条件中系数aij的变化分析步骤可以参照5.4节（增加一个变量xj的变化）。②若变量xj在最终单纯行表中为基变量，则在计算反映到最终单纯形表后，需要对其作高斯消元，保证得到恰当的形式（properformfromGaussianelimination）5.5分析参数aij的变化注：对第二种情况，高斯消元后可能出现原问题和对偶问题均无可行解的情况。出现这种情况时，需要引进人工变量先将原问题转化为可行解，再用单纯形法求解。P57例9在美佳公司的例子中，若家电Ⅱ每件需设备A、B和调试工时变为8h、4h、1h，该产品的利润变为3元/件，试重新确定该公司最优生产计划。1521Ⅱ3841Ⅱ2利润（元）15245061设备A（h）设备B（h）调试工序（h）每天可用能力Ⅰ项目1、计算解：先将生产工时变化后的家电Ⅱ看作时一种新产品，仿照前面小节的计算步骤，计算出σ2′P2′和将其反映到最终单纯形表中得下表：000-1/4-1/20015/4-15/21001/4-1/2010-1/43/215/27/23/2x3x1x2021x1x2x3x4x5x2b基CB21000cj311/21/21/2σj3/2[]′□因x2已变换为x2′，故用单纯形算法将x2′替换出基变量中的x2，并在下一个表中不再保留x2，如下表2、计算σj＝cj－CB·B-1·Pj′000-1/4-1/20015/4-15/21001/4-1/2010-1/43/215/27/23/2x3x1x2021x1x2x3x4x5x2b基CB21000cj311/21/21/2σj3/2′001/2-5014