第六章 线性规划的对偶理论及灵敏度分析(3).pptVIP

线性规划的对偶理论与灵敏度分析 灵敏度分析一词的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析。 在这以前讲的线性规划问题中，都假定问题中的aij，bi，cj是已知常数。但实际上这些数往往是一些估计和预测的数字，如市场条件一变, cj值就会变化。 aij是随工艺技术条件的改变而改变，而bi值则是根据资源投入后能产生多大经济效果来决定的一种决策选择。因此就会提出以下问题：当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化，或者这些参数在一个多大范围内变化时，问题的最优解不变。这就是灵敏度分析所要研究解决的问题。 当线性规划问题中的一个或几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。因为前面已经讲到，单纯形法的迭代计算是从一组基向量变换为另一组基向量，表中每步迭代得到的数字只随基向量的不同选择而改变，因此有可能把个别参数的变化直接在计算得到最优解的最终单纯形表上反映出来。这样就不需要从头计算，而直接对计算得到最优解的单纯形表进行审查，看一些数字变化后，是否仍满足最优解的条件，如果不满足的话，再从这个表开始进行迭代计算，求得最优解。 灵敏度分析的步骤 1.将参数的改变计算反映到最终单纯形表上来 灵敏度分析的步骤 2.检查原问题是否仍为可行解 3.检查对偶问题是否仍为可行解 4.按下表所列情况得出结论和决定继续计算的步骤 一、分析cj的变化 在前面讲的美佳公司例子中， (1)若家电Ⅰ的利润降至1.5元／件，而家电Ⅱ的利润增至2元／件时，美佳公司最优生产计划有何变化；(2)若家电I的利润不变，则家电Ⅱ的利润在什么范围内变化时，则该公司的最优生产计划将不发生变化。 (1)若家电Ⅰ的利润降至1.5元／件，而家电Ⅱ的利润增至2元／件时，美佳公司最优生产计划有何变化；(2)若家电I的利润不变，则家电Ⅱ的利润在什么范围内变化时，则该公司的最优生产计划将不发生变化。 二、分析 的变化 例6 在上述美佳公司的例子中(1)若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化；(2)若设备A和B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。 二、分析 的变化 例6 在上述美佳公司的例子中(1)若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化；(2)若设备A和B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。 三、增加一个变量xj的分析——增加一个变量在实际问题中反映为增加一种新的产品。 1.计算 2.若σj≤0原最优解不变，只需将计算得到的Pj’和σj直接写入最终单纯形表中，若σj≥0计算Pj’=B-1Pj则按单纯形法继续迭代计算找出最优。 三、增加一个变量xj的分析 在美佳公司例子中，设该公司又计划推出新型号的家电Ⅲ，生产一件所需设备A、B以及调试工序的时间分别为3小时、4小时、2小时，该产品的预期盈利为3元/件，试分析该种产品是否值得投产，如投产，对该公司的最优生产计划有何变化？ 五、增加一个约束条件的分析 增加一个约束条件在实际问题中相当增添一道工序。分析的方法也是先将原问题最优解的变量值代入新增的约束条件，如满足，说明新增的约束未起到限制作用，原最优解不变。否则，将新增的约束直接反映到最终单纯形表中再进一步分析。 五、增加一个约束条件的分析 仍以美佳公司为例，设家电Ⅰ，Ⅱ经调试后、还需经过一道环境试验上序。家电Ⅰ每件须环境试验3小时,家电Ⅱ每件2小时，又环境试验工序每天生产能力为12小时。试分析增加该工序后的美佳公司最优生产计划。 练习1：已知线型规划问题： 用单纯形法求解的最终单纯形表如下所示，试分别说明发生下列变化时，新的最优解是什么？ （1）目标函数变为maxz=2x1+3x2+x3 练习2：某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据如表所示。要求： （1）确定获利最大的产品生产计划 （2）产品A的利润在什么范围内变动时，上述最优计划不变 （3）如果设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？ 课堂练习：某厂生产I、Ⅱ、Ⅲ三种产品，分别经过A、B、C三种设备加工。已知生产单位某种产品所需的设备态势、设备的现有加工能力及每件产品的预期利润如表所示： 课堂练习：某厂生产I、Ⅱ、Ⅲ三种产品，分别经过A、B、C三种设备加工。已知生产单位某种产品所需的设备态势、设备的现有加工能力及每件产品的预期利润如表所示： * * DUAL 或 引进人工变量，编制新的单纯形表迭代求最优解 非可行解 非可