《运筹学》胡运权 第版 第二章线性规划的对偶理论及灵敏度分析

.,第二章线性规划的对偶理论及灵敏度分析,OperationalResearch(OR),线性规划的对偶问题与灵敏度分析,线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划,对偶原理,对偶问题概念：任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。,问题的导出,例2-1,我们引用第一章中美佳公司的例子，如表1,其线性规划问题为：,？,假定有某个公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源？,（LP1）,问题的导出,例2-1条件：出让代价应不低于用同等数量资源由自己组织生产活动时获取的赢利。,y1,y2,y3分别代表单位时间（h）设备A、设备B和调试工序的出让代价。y1,y2,y3的取值应满足：,美佳公司用6h设备B和1h调试可生产一件家电I,赢利2元,用5h设备A,2h设备B及1h调试可生产一件家电，赢利1元,该公司希望用最小代价把美佳公司的全部资源收买过来，即：,问题的导出,例2-1,综上所述，,（LP2）,LP1和LP2两个线性规划问题，通常称LP1为原问题，LP2为前者的对偶问题。,对偶问题的定义,对称形式的对偶问题,对偶问题的定义,对称形式的对偶问题,对偶问题的定义,对偶问题的特点若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。,对偶问题的定义,一般线性规划问题的对偶问题,对偶问题的定义,对偶问题对应表,对称形式下的对偶问题,例22标准型对偶问题,对称形式下的对偶问题,例23,非对偶形式的原-对偶问题,例2-4写出下列问题的对偶问题,（2.4a）（2.4b）（2.4c）（2.4d）,对偶变量y1y2y2y3,先转换成对称形式，如下：,非对偶形式的原-对偶问题,例2-4令各约束对应的对偶变量分别为y1、y2、y2、-y3,令y2=y2-y2，y3=-y3，原问题的对偶问题为,对应关系总结,线性规划的对偶问题与灵敏度分析,线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划,对偶问题的基本性质,单纯形法计算的矩阵描述对称形式线性规划矩阵表达式加上松弛变量Xs后为：,其中松弛变量Xs=（xn+1,xn+2,.,xn+m）,I为mm单位矩阵,选取I为初始基，对应基变量为Xs。设迭代若干步后，基变量为XB，XB在初始单纯形表中的系数矩阵为B。A中去掉B的若干列后剩下的列组成矩阵N。,进一步迭代,新的单纯形表如下：,对偶问题的基本性质,对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1初始单纯形表中基变量Xs=b，迭代后的表中XB=B-1b初始单纯形表中约束系数矩阵为A,I=B,N,I，迭代后的表中约束系数矩阵为B-1A,B-1I=B-1B,B-1N,B-1I=I,B-1N,B-1若初始矩阵中变量xj的系数向量为Pj，迭代后为Pj，则有Pj=B-1Pj当B为最优基时，表中应有CN-CBB-1N0,-CBB-10,对偶问题的基本性质,例2-5参看例2-1中的原问题和对偶问题，并分别加上松弛变量和剩余变量，如下：,对偶变量y1y2y3,对偶变量x1x2,对偶问题的基本性质,两个问题的最终单纯形表如下：,对偶问题的基本性质,1.弱对偶性如果xj（j=1，.，n）是原问题的可行解，yi（i=1，.，m）是其对偶问题的可行解，则恒有,对偶问题的基本性质,弱对偶性的推论：(1)原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,(2)如原问题有可行解且目标函数值无界(具有无界解)，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然。,对偶问题的基本性质,(3)若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,对偶问题的基本性质,对偶问题的基本性质,最优性如果(j=1,.,n)是原问题的可行解，(i=1,.,m)是其对偶问题的可行解，且有,则(j=1,.,n)是原问题的最优解，(i=1,.,m)是其对偶问题的最优解。,对偶问题的基本性质,强对偶性(或称对偶定理)若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。,对偶问题的基本性质,互补松弛性在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。也即,若0，则有，即,若，即，则有,因此一定有，,线性规划的对偶问题与灵敏度分析,线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划,影子价格,对偶最优解的经济含义影子价格,代表着当第i个右端常数增加一个单位时，最优目标函数值的相应增量。其含义是在目前已给定的情况下，最优目标值随资源数量变化的变化率；其经济含义是为约束条件所付出的代价。当B是原问题的最优基时，Y=CBB-1就是影子价格向量。,影子价格,资源的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。影子价格是一种边际价格。资源的影子价格实际上又是一种机会成本。随着资源的买进卖出，其影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。,影子价格,生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。影子价格反映单纯形表中各个检验数的经济意义。一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用。,影子价格举例,y1=5/3,y2=1/3即工时的影子价格为5/3，材料的影子价格为1/3。如果目前市场上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉部分材料。如果有客户以高于5/3的价格购买工时，则可以出售一些工时，反之则反,线性规划的对偶问题与灵敏度分析,线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划,对偶单纯形法,对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。求解单纯形法的基本思路：对原问题的一个基可行解，判别是否所有检验数cj-zj0(j=1,n)。若是，又基变量中无非零人工变量，即找到了问题最优解；若为否，再找出相邻的目标函数值更大的基可行解，并继续判别，只要最优解存在，就一直循环进行到找出最优解为止。,对偶单纯形法,对于标准线性规划问题：,可行基B若B对应的基本解是可行解最优基B若B对应的基本解是最优解对偶可行基B若CBB-1是对偶问题可行解即C-CBB-1A0或检验数0,对偶单纯形法,对于标准线性规划问题：,对偶单纯形法,对于标准线性规划问题：,找一个基，建立初始对偶单纯形表，检验数全部非正；若b列元素非负，则已经是最优基。反之，则取相应行的基变量为出基变量；为保证能对基的可行性有所改进，则将来的主元应该为负数；为保证下一个基还能是对偶可行基，应使检验数仍为非正的。主元变换,对偶单纯形法举例,例26用对偶单纯形法求解：,对偶单纯形法举例,对偶单纯形法,练习：用对偶单纯形法求解,线性规划的对偶问题与灵敏度分析,线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划,灵敏度分析,在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。,灵敏度分析的步骤,灵敏度分析的步骤可归纳如下：1.将参数的改变通过计算反映到最终单纯形表上来。2.检查原问题是否仍为可行解。3.检查对偶问题是否仍为可行解。4.按下表所列情况得出结论或决定继续计算的步骤。,灵敏度分析,若B是最优基，则最优表形式如下,灵敏度分析总是在最优表上进行,灵敏度分析,当系数A，b，C发生改变时，目前最优基是否还最优？为保持目前最优基还是最优，系数A，b，C的允许变化范围是什么？假设每次只有一种系数变化目标系数C变化基变量系数发生变化；非基变量系数发生变化；右端常数b变化增加一个变量增加一个约束技术系数A发生变化,灵敏度分析举例,分析cj的变化例2-7在第一章例1的美佳公司例子中：（1）若家电的利润降至1.5元/件，而家电的利润增至2元/件时，美佳公司最优生产计划有何变化?,即美佳公司随家电，的利润变化应调整为生产2件，生产3件。,（2）若家电的利润不变，则家电的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？设家电的利润为（1+）元，如下,为保证最优解，-1/4+1/40，-1/2-3/20解得-1/31即家电的利润c2的变化范围应满足2/3c22,灵敏度分析举例,分析bi的变化例2-8在美佳公司的例子中：（1）若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32h，分析公司最优计划的变化；,灵敏度分析举例,灵敏度分析举例,例2-8（2）设设备A和设备B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。设调试工序每天可用能力为（5+）h，因有,最终单纯形表中b列数字为,因b0时最优基不变，故-11。调试工序的能力应在4h6h之间。,增加一个变量xj的分析若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。,增加一个变量xj的分析,灵敏度分析举例,增加一个变量在实际问题中反映为增加一种新的产品。其分析步骤为：,3.若j0，原最优解不变，只需将计算得到的Pj和j直接写入最终单纯形表中；若j0，则按单纯形法继续迭代计算找出最优。,例2-9设美佳公司又计划推出新型号的家电，生产一件所需设备A、B及调试工序的时间分别为3h、4h、2h，该产品的预期盈利为3元/件，试分析该产品是否值得投产；如投产，对该公司的最优生产计划有何影响。设生产x6件家电，有c6=3，P6=（3，4，2）T,灵敏度分析举例,灵敏度分析举例,最优生产计划应为每天生产7/2件家电，51/4件家电。,灵敏度分析举例,分析参数aij的变化,例2-10在美佳公司的例子中，若家电每件需设备A,B和调试工时变为8h、4h、1h，该产品的利润变为3元/件，试重新确定该公司最优生产计划。设生产工时变化后的新家电的生产量为x2，其中：,灵敏度分析举例,原问题和对偶问题均为非可行解,上表中第二阶段第一行的约束为：x3+4x4-24x5=-9-x3-4x4+24x5+x6=9替换后重新得表：,灵敏度分析举例,最优生产计划为每天生产11/4台家电，15/8台家电,灵敏度分析举例,增加一个约束条件在企业的生产过程中，经常有一些突发事件产生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响。若把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束对最优解不构成影响，即不影响最优生产计划的实施。若当前最优解不满足新增加的约束，则应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。,增加一个约束条件,灵敏度分析举例,例2-11设家电，经调试后，还需经过一道环境试验工序。家电每件需环境试验3h，家电每件需2h，又环境试验工序每天生产能力为12h。试分析增加该工序后的美佳公司最优生产计划。,（1）检验原问题的最优解是否仍适用。将x1=7/2，x2=3/2代入3x1+2x212，27/212，所以不适用。（2）加入松弛变量x6，得3x1+2x2+x6=12（3）单纯形表求解。,灵敏度分析举例,注：表中同，=-3-2。,线性规划的对偶问题与灵敏度分析,线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划,参数线性规划,当目标函数中cj值连续变化时，其参数线性规划的形式为：,当约束条件右端项连续变化时，其参数线性规划的形式为：,参数线性规划分析步骤,分析步骤：（1）令=0求解得最终单纯形表；（2）将C*或b*项反映到最终单纯形表中去；（3）随值的增大或减小，观察原问题或对偶问题，一是确定表中现