运筹学对偶理论和灵敏度分析.pptVIP

一、对偶单纯形法的步骤(1)化LP问题的约束条件为“≤”形式,引入松弛变量,建立初始表;(2)若所有常数项bi≥0，则最优解已经达到，否则bl=Min{bi|bi0}，选取bl所对应的变量为出基变量；(3)计算θk=Min{σj/alj|alj0}，选取θk所对应的变量为进基变量；(4)以alk为主元素进行旋转运算，转第二步。建初始表结束选择出基和进基变量，进行旋转运算YN所有bi≥0第四节对偶单纯形法*第29页，共61页，星期日，2025年，2月5日例9用对偶单纯形法求解下列LP问题解：原问题变形为MinZ=x1+2x2+3x3?s.t.x1-x2+x3≥4x1+x2+2x3≤8x2-x3≥2x1,x2,x3≥0?MaxZ’=-x1-2x2-3x3?s.t.-x1+x2-x3≤-4x1+x2+2x3≤8-x2+x3≤-2x1,x2,x3≥0?MaxZ’=-x1-2x2-3x3?s.t.-x1+x2-x3+x4=-4x1+x2+2x3+x5=8-x2+x3+x6=-2x1,x2,x3,x4,x5,x6≥0?二、对偶单纯形法的算例*第30页，共61页，星期日，2025年，2月5日cjCBXBbx1x2x3x4x5x6σj0x40x50x6-48-2-11-11001120100-110010-1-2-3000cj-1-2-3000CBXBbx1x2x3x4x5x6-1x141-11-1000x540211100x6-20-11001σj40-3-2-100-1-2-3000*第31页，共61页，星期日，2025年，2月5日cj-1-2-3000CBXBbx1x2x3x4x5x6-1x16100-10-10x50003112-2x2201-100-1σj1000-5-10-3*第32页，共61页，星期日，2025年，2月5日三、几个问题的讨论1.对偶单纯形法只适用于具有正则解的LP问题。正则解：若LP问题存在基解X，且对应于此基解的检验数均≤0(对于极大化问题)，则称X为LP问题的正则解。2.若最小比值原则失效，则无可行解。3.对偶单纯形法所包含的创新思想。*第33页，共61页，星期日，2025年，2月5日1.最优性：?j＝cj-CBTB-1Pj≤0（Max）2.可行性：XB*＝B-1b≥0二、灵敏度分析常用的两个公式当LP问题中的某些参数发生变化时，对最优解的变化情况进行分析。MaxZ=CTXs.t.AX≤bX≥0一、灵敏度分析的定义三、灵敏度分析的几种可能结果1.最优解保持不变2.最优基不变，但最优解改变3.最优基改变第五节线性规划的灵敏度分析*第34页，共61页，星期日，2025年，2月5日1.直接用单纯形表求B-1四、右端项b的变化分析——求B-1由AX≤b→AX+IXS=b（初始表）两边左乘B-1得B-1AX+B-1XS=B-1b（最优表）例1LP问题MaxZ=