对偶与灵敏度分析

1、§2 对偶与灵敏度分析§2.1LP的对偶问题无论从理论和实践角度，对偶理论是LP中的一个最重要和有趣的概念，支持对偶理论的基本思想是：每一个LP问题都存在一个与其对偶的问题，在求解一个问题解的时候，也同时给出了另一问题的解。一、问题的提出例2.1：设某工厂生产两种产品甲乙，生产过程需要4种设备ABCD进行加工，每件产品加工所需机时数，每件产品的利润值及每种设备的可利用机时如下表：设备产品ABCD利润甲21402乙22043总机时12816121.问：充分利用设备时，应怎样安排甲乙产品的生产数量，利润才能最大？2.问：如有另外一家公司想租用该厂设备加工生产，那么，这家公司应至

2、少对每台设备的机时价格为多少时，才能使该厂愿意出租设备？解：1.设甲乙产品各生产件LP1：2.设每台设备的机时最低价分别为：，LP2：二、原问题和对偶问题之间的关系：1.对称形式下的原问题与对偶问题对称形式下原问题的一般式：矩阵形式：若用代表第i种资源的估价，则其对偶问题的一般式为：2.非对称形式下原问题与对偶问题：方法一：将非对称形式转化为对称形式，求出对偶问题，然后再还原。例2.2写出下列LP问题的对偶问题：为写出基对偶问题，先将其转化为对称形式，再进行变化：因目标函数为，故约束条件全部转化为“”，所有变量均应为“”。将（1）式变为：。再将将（2）式两端同乘以“-1”，并令：得：所以，例2

3、.2可以变为：令对应上述四个约束条件的对偶变量为，则其对偶问题为：令，将第4与第5个不等式合并，将第三个不等式两端同乘以“-1”得：由以上的推导可以发现有以下规律：方法二：根据原问题与对偶问题之间的关系，可将其归纳如下表：原问题（或对偶问题）对偶问题（原问题）目标函数目标函数变量 约束条件约束条件变量A约束系数矩阵b约束条件右端项向量C目标函数中的价格系数向量约束系数矩阵的转置C目标函数中的价格系数向量b约束条件右端项向量§2.2 对偶问题的基本性质一、单纯形法计算的矩阵描述设线性规划问题的矩阵表达式为：，加上松弛变量后为：式中：。单纯形法计算时，总选取为初始基I，对应基变量为。设迭

4、代若干步后，基变量为，在初始单纯形表中的系数矩阵为B。将B在初始单纯形表中单独列出，而A中去掉B的若干列后组成矩阵N，同时将C也分为两块，是目标函数中基变量的系数行向量；是目标函数中非基变量的系数行向量。这样LP的初始单纯形表可列成如下形式：项目非基变量基变量0bBNI0于是原LP问题可以改写为：将约束条件移项并左乘后得到的表达式：代入目标函数得：所以，经过迭代之后，得出新的单纯形表为：项目基变量非基变量I0当为最优基时，在上述单纯形表中有：， 而的检验数可以写为：因此有：，称为单纯形乘子，若令则有：可以发现这时检验数行，若取其相反数恰好是其对偶问题的一个可行解。将这个解代入对偶问题的目标函数

5、值，有：即：当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值。（其实，这时对偶问题的解也为最优解。）二、本节讨论先假定原问题和对偶问题为对称形式的LP，即原问题为：其对偶问题为：然后说明对偶问题的基本性质在非对称形式也适用。1.对称性：对偶问题的对偶是原问题。证明：原问题与其对偶问题分别为：与2.弱对偶性：若是原问题可行解，是对偶问题的可行解，则存在。证明：设原问题为：原问题的对偶问题为：3.无界性：若原问题为无界解，则其对偶问题为无可行解。证明：由弱对偶性可得，本性质成立。4.可行解是最优解时的性质：若是原问题可行解，是对偶问题的可行解，当时，与是原问题与对偶问题的最优解

6、。证明：5.对偶定理：若原问题有最优解，那么其对偶问题也有最优解，且目标函数值相等。6.互补松弛性：若是原问题可行解，是对偶问题的可行解，那么，当且仅当为，最优解。（在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量值一定为零。）；。将互补松弛性质应用于其对偶问题时可以这样叙述：；。由互补松弛定理可知：若原问题最优解中的第j个变量为正，则其对偶问题中与之对应的第j个约束条件在最优情况下必呈严格等式（即其松弛变量为0）；而如果对偶问题中第j个约束条件在最优情况下呈严格不等式，则原问题最优解中第j个变量必为0。

7、类似地，若对偶问题最优解中第i个对偶变量为正，则其原问题中与之对应的第i个约束条件在最优情况下必呈严格等式（即其剩余变量为0）；而如果原问题中第i个约束条件在最优情况下呈严格不等式，则对偶问题最优解中第i个对偶变量必为0。互补松弛定量阐明了原问题及其对偶问题最优解各分量之间的关系，当已知一对对偶问题之一的最优解时，可利用该定量求出另一个问题的最优解。7.设原问题是：对偶问题为：则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如下表所示：0这里是对应原问题中基变量的剩余变量，是对应原问题中非基变量的剩余变量。证明：例2.3已知LP已知其对偶问题的最优解为：试用对偶理论找出原问题的最

8、优解。练习：1. 已知LP写出其对偶问题；已知原问题的最优解为试根据对偶理论求出对偶问题最优解。2. 已知LP写出其对偶问题；已知原问题的最优解为试根据对偶理论求出对偶问题最优解。§2.3对偶问题的经济解释影子价格由对偶问题的性质可知，当LP原问题求得最优解时，其对偶问题也得到最优解，且代入各自目标函数后有：，在式中是LP原问题约束条件的右端项，它代表第i种资源的拥有量，对偶变量的意义代表在资源最优利用条件下，对单位第i种资源的估价。这种估价还是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见称为影子价格。其特点如下：1.资源的市场价格是已知数，相对比较稳定，而它

9、的影子价格则有赖于资源的利用情况，是未知的。由于企业的生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。2.影子价格是一种边际价格，在上式中对求的偏导数得：。说明的值相当于在资源得到最优利用的生产条件下，每增加一单位时目标函数的增量。3.资源的影子价格实际上又是一种机会成本。当某种资源的市场价格低于影子价格时，企业可以买进该资源用于扩大生产；而当某种资源的市场价格高于影子价格时，则企业的决策者应卖出已有资源，可见影子价格对市场有调节作用。4.由对偶问题互补的松弛性有：；，这表明生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为0，又当资源的影子价格不为0时，表明该种资源在生

10、产中已耗费完毕。5.从影子价格的含义上来考察单纯形表的计算。，式中代表第种产品的产值；是生产该种产品所消耗各项资源的影子价格的总和，即产品的隐含成本。当产品产值大于隐含成本时，表明生产该种产品有利，可在计划中安排生产；否则用这些资料来生产别的产品更有利，就不在生产计划中安排。这就是单纯形表中各个检验数的经济意义。6.一般来说，对LP的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效的利用，如在一个大公司内部，可借助于资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。又如在社会上可借助影子价格规定使用这种

11、资源一单位时必须上缴的利润额，以控制一些经济效益低的企业自学地节约紧缺资源，使有限资源发挥最大的经济效益。§2.4对偶单纯形法一、对偶单纯形法的理论依据：根据对偶问题的基本性质7，在单纯形表进行迭代求解时，在b列中得到的是原问题的基本可行解，在检验数行得到的是对偶问题的基可行解，根据最优性定理，原问题有最优解时，对偶问题也达到最优解。根据其对称性，也可以这样考虑，若保持对偶问题的解是基可行解，即，而原问题是在非可行解的基础上，通过逐步迭代的方式达到基可行解，这样也可以得到最优解。其优点是原问题的初始解不一定要是基可行解，可从非基可行解的基础上开始迭代。二、基本步骤：1.根据LP问题，

12、列出初始单纯形表，检查b列数字若都非负，检验数都为非正，则已得到最优解，停止计算；否则，转入下一步。2.确定换出变量：因为总存在，令，其对应变量为换出变量。3. 确定换入变量：在单纯形表中检查所在行的各系数，若所有，则无可行解，停止计算；若存在，计算：，按规则所对应的列的非基变量为换入变量。4. 以为主元素，进行迭代运算。5. 得到新单纯形表，返回步骤1。例：2.4用对偶形法求解下列LP解： 从以上表中看出，用对偶单纯形法求解LP时的优点：1.初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，可以简化计算。2.当约束条件为“”时，不必引进人工变量，可以使计算

13、简化。3.当变量多于约束条件，对这样的线性规划问题，用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。4.但在初始单纯形表中其对偶问题应是其可行解这一点很多LP很难实现，因此，对偶单纯形法一般不单独使用，而主要用于灵敏度分析及整数规划等有关章节。§2.5灵敏度分析灵敏度分析是指对系统或事物因周围条件变化显示出来的敏感程度的分析。在以前讲的LP问题中，总是假定问题中的是已知常数，但实际上这些参数往往是一些估计和预测的数字。如果市场条件变化，的值就会变化；是随着工艺技术条件的改变而改变，而值则是根据资源投入

14、后能产生多大的经济效果来决定的一种决策选择。因此，灵敏度分析要解决如下问题：l 当这些参数中的一个或几个发生变化时，问题最优解有什么变化；l 这些在多大范围内变化时，问题的最优解不变。灵敏度分析的步骤可归纳如下：1.将参数的改变计算反映到最终单纯形表上来：2.检查原问题是否仍为可行解。3.检查对偶问题是否仍为可行解。4.按下表所列情况得出结论和决定继续计算的步骤。原问题对偶问题结论或继续计算步骤可行解可行解问题最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表重新计算一、分析的变化LP目标函数中价

15、值系数的变化仅仅影响到检验数的变化，所以将的变化直接反映到最终单纯形表中，只可能出现上表中前两种情况。例2.5，在第一章中例1.7中，假设产品的市场利润变化为，在最优解保持不变前提下，确定的变化范围。解：利用前面计算出的最终单纯形表进行计算：230002410000400-2132010000当变为后，上表变为如下单纯形表：23+0002410000400-213+2010000为了使原最优解保持不变：则，解之得：说明产品的市场利润可以在0,4之间变化，而不影响最优解。二、分析的变化资源系数的变化反映到最终单纯形表上将引起b列数字的变化，在上表中可能出现第一或第三两种情况。出现第一种情况时，问题的最优基不变，变化后的b列值为最优解。出现第三种情况时，用对偶单纯形法迭代继续找出最优解。当发生变化时，即，并假设规划中的其它系数都不变，这样使最终表中原问题的解