线性规划的对偶理论(第部分)

.,4、影子价格-对偶最优解的经济含义,说明：yi的值相当于在给定的生产条件下，bi每增加一个单位时目标函数的增量。,.,影子价格,第i个约束条件的影子价格的经济含义是：其它条件不变的情况下，该资源单位的变化所引起的目标函数最优值的变化量在现有的技术和管理条件下，某种资源的影子价格越大，说明该资源对目标增益的影响越大，同时该资源越紧缺和贵重，应该给与高度关注，通过降低消耗或设法补充，提高收益,.,某种资源的影子价格为零，说明该资源相对富裕；一方面可以转让该资源；另一方面，通过挖潜和增加对影子价格大于零资源的投入，使原有的剩余资源充分利用，甚至于成为新的紧缺资源影子价格不是市场价格，而是在现有技术和管理条件下，新增单位资源所能够创造的价值，是特定企业的一种边际价格；不同企业或同一企业不同时期，同种资源的影子价格可能不同；当市场价格高于影子价格，可以卖出；相反，则应买进，以获取更大收益,.,例：（第一章例2）,当第一个约束右端项增加1，变为最优解为若第二个约束右端项加1，变为最优解不变，即设备B的边际价格为零。若第三个约束的右端项加1，变为最优解为,.,综上，影子价格是灵敏度分析的一种形式，它通过获取一个单位的追加的产品因素，去测量放宽一个约束条件的价值，比较追加资源的价值和资源的实际成本，就能比较有把握地作出各种可行的决策。,.,5、对偶单纯形法一、什么是对偶单纯形法？对偶单纯形法是应用对偶原理求解原始线性规划的一种方法在原始问题的单纯形表格上进行对偶处理。注意：不是解对偶问题的单纯形法！,.,二、单纯形法的求解过程就是：在保持原始可行的前提下（b列保持0），通过逐步迭代实现对偶可行（检验数行0）。,对偶单纯形法思想：换个角度考虑LP求解过程：保持对偶可行的前提下（检验数行保持0），通过逐步迭代实现原始可行（b列0，从非可行解变成可行解）。,.,三、对偶单纯形法的实施1、使用条件：检验数全部0；资源列至少一个元素0,继续用单纯形法迭代得下表：,.,故新的解为：x1=3,x2=2,x6=1,z*=16,.,6、增加一个约束条件的分析：,若在第一章例2中，若增加一个约束条件3x1+2x214，试分析问题最优解的变化。,.,分析：增加一个约束条件，在实际问题中相当于增添一道工序；在计算过程中相当于系数阵A增加1行。首先将原最优解代入新增约束检查是否满足？是，则说明新增约束不影响最优解。否则再作下面的讨论：将新增约束标准化，添加到原最优表格中（相当于约束矩阵新增1行）；进行规格化处理用矩阵的行变换将当前基变成单位阵；,.,用适当方法（通常是对偶单纯形法）进行迭代求出新的最优解。,如在上例中增加约束：3x1+2x214,当前最优解x1=3,x2=3,有3X3+2X3=1514,不满足该约束，将约束条件标准化（加上松弛变量）后加入原最优表格，进行规格化处理，然后用对偶单纯形法迭代求出新的最优解.,.,为使由P1,P4,P2,P6,列组成单位矩阵，对表2-13中由各变量列组成的系数矩阵进行行的初等变换。将上表各行数字按以下对应关系进行变换：(1)=(1),(2)=(2)，(3)=(3),(4)=(4)-3(1)2(3)得下表：,.,.,因此增加约束条件后，问题的新的解为x1=8/3,x2=3,z*=43/3,.,练习1：现有线性规划问题：,先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？（1）约束条件的右端常数由20变为30；（2）约束条件的右端常数由90变为70；（3）目标函数中X3的系数由13变为8；（4）X1的系数列向量由变为；（5）增加一个约束条件,.,练习2：现有线性规划问题：,先用单纯形法求出最终单纯形表如右上表，然后分析在下列各种条件下，最优解分别有什么变