对偶单纯形法+灵敏度分析ppt课件.ppt

第二章 线性规划的对偶理论与灵敏度分析,第四节 对偶单纯形法,对偶单纯形法并不是求对偶问题解的方法，而是利用单纯形法求解规划问题时运用了对偶理论。 也就是说：对偶单纯形法与单纯形法一样都是是求解线性规划的一种基本方法。它是根据对偶原理和单纯形法原理设计出来的，因此称为对偶单纯形法。,在了解对偶单纯形法的实质之前，我们回顾一下单纯形法。,单纯形法开始于初始基可行解。如果不满足最优性条件，则要换基迭代转到能使目标函数值得到改善的邻近顶点上。在这个转换过程中，存在两个原则: 一是首先保持原问题的解仍是可行的，另一个是要求目标函数值有改善。,如何保证可行？,初始单纯形表,CB,CN,0,单纯形法是在保持所有约束条件常数项总是保持大于等于零的情况（保证可行），通过迭代，使所有检验数小于等于零（求最大值），求得最优解。,1、当原问题达到最优时，松弛变量经过上述转换后构成的检验数的相反数为其对偶问题的一个可行解，反之亦成立,原问题表中的检验数满足最优性条件,CN-CB B-1 N0 -CB B-1 0;,ATY CT; Y0 YT= CB B-1,从上面可以看出：,也就是说，当原问题达到最优时，对偶问题的解可行。并且根据对偶的性质，我们可以确定此时对偶问题也达到最优,CB:1m B-1：m mCB B-1：1 m Y： m 1,初始单纯形表,也就是：单纯形法计算时只要原问题可行（B-1b 0），对偶问题可行（即检验数小于0），解就是最优解。单纯形法的基本过程就是保证原问题解可行的情况下，不停迭代，直至对偶问题也达到可行，此时原问题达到最优，对偶问题也达到最优,根据刚才所说，单纯形法只要单纯形法计算时只要原问题可行（B-1b 0），对偶问题可行（即检验数小于0），解就是最优解。所以，我们利用单纯形法对原问题求解时，如果首先保持对偶问题的可行性（即原问题检验数0），然后再看原问题是否可行，如果此时原问题的解不可行，则换基迭代，换基过程中保证对偶可行（检验数0 ），直至原问题由不可行解变为可行解，此时就得到它的最优解，这就是对偶单纯形法的基本思想。,第四节 对偶单纯形法,也就是说：对偶单纯形法是在保持原问题所有检验数都小于等于零的基础上，通过迭代，使原问题的解（即右边常数项）都大于等于零，从而求得最优解。,第四节 对偶单纯形法,（2）初始解不可行，即右端常数项有负分量（如果原问题可行，则直接用单纯形法）,使用对偶单纯形法必须满足两个条件：,（1）单纯形表中的所有检验数必须符合对偶可行，即小于等于0, 先找一个基，建立初始对偶单纯形表，使检验数全部非正，即C全部为非正； 若b列元素非负，则已经是最优基。反之，则换基迭代，直至原问题可行。,第四节 对偶单纯形法,怎么做呢？,例 用对偶单纯形法求解,该问题用单纯形法求解时，需要先化标准型，此时约束方程两边左边需要减去剩余变量，同时为了构造单位阵，需要添加人工变量，采用大M法求解。,第四节 对偶单纯形法,思考：上面约束方程化为标准型后，两边乘以-1，就可得到单位阵。此时能否用单纯形法？原因?,答：不能。因为此时右边常数项为负数，解不可行。为了保证初始解可行,例 用对偶单纯形法求解,第四节 对偶单纯形法,能否用对偶单纯形法呢？,对偶单纯形法初始对偶单纯形表只要保证对偶可行，即检验数全部非正即可。并不要求初始解可行，所以右边常数项可以非负，此题目价值系数均为负，意味着初始单纯形表格的检验数为负，而右端常数项又有负数，正好满足对偶单纯形法的要求。,例 用对偶单纯形法求解,将约束方程化为标准型，再用（-1）乘不等式两边,第四节 对偶单纯形法,此时，初始单纯形表检验数均小于等于0，对偶可行，但原问题初始解不可行,第四节 对偶单纯形法,初始对偶单纯形表,先选出基变量后选进基变量,原问题不可行，应该换基迭代。但按对偶单纯形法的思想，每次均应保证检验数均非正,最优解X*=（7，0，4，0）TZ*=-7,例6 用对偶单纯形法求解,（P）,1 - 4/3 - -,-1 0 -5/2 1/2 1 -1/2 2 1 -1/2 3/2 0 -1/2 0 -4 -1 0 -1,- 8/5 - - 2,2/5 0 1 -1/5 -2/5 1/5 11/5 1 0 7/5 -1/5 -2/5 0 0 -3/5 -8/5 -1/5, , ,单纯形表,第四节 对偶单纯形法,使用对偶单纯形法求初始解时右边常数项可以为负，所以对于一些大于等于号的约束表达式不需要添加人工变量，只要两边同时乘上-1，就可用对偶单纯形法求解，简化计算，这是该方法的优点。缺点是很难找到一个初始解使得所有检验数都小于等于零，因而很少单独使用。,1、什么是灵敏度分析？ 灵敏度分析是指系统或事物因为周围条件变化而显示出来的敏感程度分析。,一、含义和研究对象,第五节 灵敏度分析,在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。 在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。,第五节 灵敏度分析,1、什么是灵敏度分析？ 是指研究线性规划模型的某些参数(bi, cj, aij）或限制量（xj, 约束条件）的变化对最优解的影响及其程度的分析过程。,一、含义和研究对象,s.t.,第五节 灵敏度分析,回答两个问题：,这些系数在什么范围内发生变化时，最优解不变？系数变化超出上述范围，如何用最简便的方法求出新的最优解？,2、灵敏度分析的研究对象： 目标函数的系数 cj 变化对最优解的影响； 约束方程右端系数 bi 变化对最优解的影响； 约束方程组系数矩阵 A 变化对最优解的影响 ；,一、含义和研究对象,1、在最终单纯形表的基础上进行； 2、尽量减少附加的计算工作量；,二、进行灵敏度分析的基本原则,三、灵敏度分析的步骤,先求问题的最优解.将参数的改变通过计算反映到最终单纯形表上来.检查原问题的可行解和检验数是否满足最优.4. 依据不同情况决定继续计算或得到结论.,4. 分析增加一个约束条件的变化,四、灵敏度分析的主要内容,1. 分析 cj 的变化,2. 分析 bi 的变化,3. 分析系数 aij 的变化,5. 分析增加一个变量 xj 的变化,s.t.,对偶问题决策变量的最优解：,初始单纯形表,最优单纯形表,X*=B-1b,CNCBB-1N 0,CBB-1 0,原问题基变量的最优解：,Z*=CBB-1b,最优值：,Y*T= CBB-1,Y*T= CBB-1,XB,I,0,基变量,非基变量,XB,CNCBB-1N,B-1N B-1,XN Xs,B-1b,CB,B-1b,CBB-1,Z*=CBB-1b,分析 cj 的变化,最优值可能已变,当2=0时，将1 反映在最终单纯形表中，可得,从而，表中解仍为最优解的条件是,即当时问题的最优解不变。,例1-1,分析1和2分别在什么范围变化时，最优解不变？,当1=0时，将2 反映在最终单纯形表中，可得,从而，表中解仍为最优解的条件是,即当时问题的最优解不变。,例1-1,分析1和2分别在什么范围变化时，最优解不变？,美佳公司计划生产I、II两种产品，每天生产条件如表，问 (1)该公司应如何安排生产计划才能使总利润最多? (2)若产品的利润不变，则产品的利润在什么范围内变 化时，该公司的最优生产计划将不发生变化？ (3)若产品的利润降至1.5百元/单位，而产品的利润增 至2百元/单位，最优生产计划有何变化 ？,例2-1,例2-1,如何安排生产计划才能使总利润最多？,解：,(1) 设x1, x2分别表示、两种产品的生产数量，得LP模型,用单纯形法求解得最终单纯形表,例2-1,如何安排生产计划才能使总利润最多？,解：,(1) 设x1, x2分别表示、两种产品的生产数量，得LP模型,用单纯形法求解得最终单纯形表,得最优解为：,X*=(7/2, 3/2, 15/2, 0, 0)T,zmax=8.5(百元)。,即每天生产3.5单位产品，1.5单位产品时总利润最多，且,例2-1,解：,(2) 将产品的利润变化反映在最终单纯形表中，可得,表中解仍为最优解的条件是,产品的利润在什么范围内变化时，最优生产计划不会发生变化？,即故当产品的利润在 范围变化时，最优生产计划不变。,11+c2,例2-1,产品利润降至1.5百元/单位，产品的利润增至2百元/单位，生产计划如何变化？,解：,(3) 将产品、的利润变化反映在最终单纯形表中，可得,因有非基变量的检验数大于零,需继续用单纯形法迭代计算,例2-1,产品利润降至1.5百元/单位，产品的利润增至2百元/单位，生产计划如何变化？,需继续用单纯形法迭代计算,得最优解为：,X*=(2, 3, 0, 6, 0)T,说明随产品利润的改变，为获得最高利润，应将生产计划调整为每天生产2单位产品，3单位产品，且,zmax=9(百元)。,Y*T= CBB-1,XB,I,0,基变量,非基变量,XB,CNCBB-1N,B-1N B-1,XN Xs,B-1b,CB,B-1b,CBB-1,Z*=CBB-1b,分析 cj 的变化,B-1N B-1,Y*T= CBB-1,XB,I,0,基变量,非基变量,XB,CNCBB-1N,XN Xs,B-1b,CB,B-1b,CBB-1,Z*=CBB-1b,分析 bi 的变化,最优解或最优值可能已变,分析i分别在什么范围变化时，最优基不变？,例1-2,例1-2,解：,先分析1的变化范围:,为使最优基不变，则需 , 即,从而得到,同理可得2与3的取值范围,分析i分别在什么范围变化时，最优基不变？,美佳公司计划生产I、II两种产品，每天生产条件如表，问 (4)若设备A和B的能力不变，调试工序能力在什么范围内变化时，问题的最优基不变？ (5)设备A和调试工序每天能力不变，而设备B能力增加到32，问最优生产计划如何变化？,例2-2,得最优解为：,X*=(7/2, 3/2, 15/2, 0, 0)T,例2-2,解：,调试工序能力在什么范围变化，最优基不变？,(4) 由 最终单纯形表，可得,例2-2,解：,(4) 由 最终单纯形表，可得,由 ，计算得,调试工序能力在什么范围变化，最优基不变？,例2-2,因此当调试工序能力在 范围变化时，问题的最优基不变。,调试工序能力在什么范围变化，最优基不变？,为使最优基不变，则需 , 即,从而得到,55+b3,例2-2,解：,(5) 由最终单纯形表，可得,设备B可用能力增加到32，生产计划如何变化？,例2-2,解：,(5) 由最终单纯形表，可得,设备B可用能力增加到32，生产计划如何变化？,反映到最终单纯形表可得,例2-2,解：,(5) 由最终单纯形表，可得,设备B可用能力增加到32，生产计划如何变化？,反映到最终单纯形表可得,例2-2,解：,(5) 由最终单纯形表，可得,设备B可用能力增加到32，生产计划如何变化？,表中原问题为非可行解，用,对偶单纯形法继续计算得,最优解为：,X*=(5, 0, 15, 2, 0)T,zmax=10(百元)。,B-1N B-1,Y*T= CBB-1,XB,I,0,基变量,非基变量,XB,CNCBB-1N,XN Xs,B-1b,CB,B-1b,CBB-1,Z*=CBB-1b,分析 bi 的变化,4. 分析增加一个约束条件的变化,四、灵敏度分析的主要内容,1. 分析 cj 的变化,2. 分析 bi 的变化,3.分析系数 aij 的变化,5. 分析增加一个变量 xj 的变化,s.t.,增加一个新变量 xj 的分析,若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。,增加一个新变量 xj 的分析,Xj,Pj,Cj,Xj,B-1Pj,Cj CBB-1Pj,增加一个新变量 xj 的分析,项 目,基变量,非基变量,CB XB B 1 b,XB,XN Xs,I,B 1 N B 1,检验数,0,( CN - CB B 1 N ) -CB B 1,Xj,B-1Pj,Cj CBB-1Pj,此时,如果检验数小于0，原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。,增加一个新变量 xj 的分析,计算步骤：,项 目,基变量,非基变量,CB XB B 1 b,XB,XN Xs,I,B 1 N B 1,检验数,0,Xj,B-1Pj,Cj CBB-1Pj,( CN - CB B 1 N ) -CB B 1,例 美嘉公司例子,如果该厂计划推出新产品3，生产一件所需要设备A,B 以及调试工序的时间分别是3h,4h,2h，该产品的预期利润3元/件，分析该种产品是否值得投产？如投产，对该公司的最优生产计划有何改变？,是否值得生产，看检验数，大于0，值得生产（影子价格特点）,解：设该厂生产新产品3为x6件，C=3,P6=(3,4,2)T,检验数大于0，值得生产,分析该种产品是否值得投产？,解：设该厂生产新产品3为x6件，C=3,P6=(3,4,2)T,如投产，对该公司的最优生产计划有何改变？,因为检验数大于0，值得生产。也说明要投产的话，最优计划会改变，如何变，要通过计算，将结果反映到最终单纯形表上。,新的最优生产计划为每天生产1产品：7/2件生产2产品：0件；生产3产品：3/4件。,参数 aij的变化导致系数阵A的元素发生变化。相当于增加1个新变量（系数阵A增加1列），如果 xj在最终单纯形表中为基变量，则aij的变化会使相应的B ,B-1发生变化，有可能出现原问题与对偶问题无可行解的情况。引进人工变量，使用单纯形法计算。,如果该厂生产的产品2，生产一件所需要设备A,B 以及调试工序的时间分别变为8h,4h,1h，该产品的利润变为3元/件，对该公司的最优生产计划有何改变？,分析参数 aij的变化,解：将改变的产品看作是一件新的产品，生产量X2,将其反映到单纯形表,分析参数 aij的变化,删除X2所在列,原问题与对偶问题均为非可行解，先使原问题转化为可行解第一行的约束：x3+4x4-24x5=-9,乘以（-1），加上人工变量 -x3-4x4+24x5 +x6 =9,对偶问题为非可行解，单纯形法继续计算,最优生产计划每天生产1产品11/4件；新产品15/8件。,相当于系数阵A增加1行,首先将原最优解代入新增约束检查是否满足？是，则说明新增约束不影响最优解。否则再作下面的讨论：将新增约束标准化，添加到原最优表格中（相当于约束矩阵新增1行）；用矩阵的初等行变换将当前基变成单位阵；,增加1个约束条件,进行迭代求出新的最优解。,设产品1，2经过调试后，必须增加环境调试工序，1产品每件须环境调试3h， 2产品每件须环境调试2h，环境调试可用能力12h，分析增加工序后的最优生产计划。增加约束：3x1+2x212,当前最优解x1=7/2,x2=3/2代入约束条件3 (7/2)+2 (3/2)=27/212，不满足该约束，所以原问题的最优解不是现在LP的最优解；将约束条件标准化后加入原最优表格， 3x1+2x2 +x6 =12，进行初等行变换，然后用对偶单纯形法迭代求出新的最优解。,X1,x2列非单位向量,r2x(-3)+r4r3x(-2)+r4,3x1+2x2 +x6 =12,对偶问题为可行解，原问题为非可行解，采用对偶单纯形法计算。,添加试验工序后，最优的生产计划仅生产1产品4件。,1、P77 2.9,本次作业,结束END,