对偶理论与灵敏度分析课件.ppt

《对偶理论与灵敏度分析课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

第三章对偶理论与灵敏度分析对偶线性规划对偶定理对偶最优解的经济解释—影子价格对偶单纯形法灵敏度分析1 对偶理论是线性规划的重要内容之一。随着线性规划问题研究的深入，人们发现对应于每个线性规划问题都伴生一个相应的线性规划问题。前者是由矩阵Ａ，右端向量ｂ和价值向量Ｃ定义的，称之为原问题；后者也是由相同的数据集合Ａ，ｂ和Ｃ构成的，称之为原文题的对偶问题。一对原问题和对偶问题是紧密关联的，它们不但有相同的数据集合，相同的最优目标函数值，而且在求得一个线性规划的最优解的同时，也同步得到对偶线性规划的最优解。对偶理论深刻地指示了原问题和对偶问题的内在联系，由对偶问题引伸出来的对偶解还有着重要的经济意义，是研究经济学的重要概念和工具之一。2 对偶问题的提出例1、某工厂生产甲,乙两种产品，这两种产品需要在A,B,C三种不同设备上加工。每种甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润，以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产计划，即甲,乙两种产品各生产多少吨，可使该厂所获得利润达到最大。对偶线性规划设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）32303 假设计划期内甲乙两种产品各生产吨，用图解法或单纯形法可求得最优解(元)即在计划期内甲产品生产吨，乙产品生产8吨，可以使总利润达到最大，为元。设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）32304 现在从另一个角度来考虑该工厂的生产问题:假设该厂的决策者打算不再自己生产甲,乙产品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价。设分别为设备A，B，C每台时的租价，约束条件：把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润目标函数：所获租金总额尽量少．5 由此可得两个对称的线性规划：矩阵形式：6 对偶线性规划考虑如下具有“≤”不等式约束的线性规划问题加入松弛变量XS=(xn+1,xn+2,…,xn+m)T以后可得标准型若B是系数矩阵（A,I）中的一个可行基，并假设（A,I）可表示为（B,N），则线性规划问题可改写为可得基本可行解,目标函数值　　　　　　，若非基变量检验数　　　　　　　　　则　　　　　为最优解7 因为基变量检验数　　　　　　　　,最优解判别准则又可表述为　　　　　　　　　　　　　。上述表达式又可写成即　　　　　　　　　　　　，其中　　　称为单纯形乘子。所以当　　　　　为最优解，且单纯形乘子　　　用符号Ｙ示时，可以推得：①②③且由　　　　　　　　　　　　　，所以　　只存在最小值。由此可以得到另一个线性规划：称之为原线性规划问题的对偶问题，8 线性规划问题标准型的对偶问题考虑一个标准形式的线性规划问题由于任何一个等式约束都可以用两个不等式约束等价地表示，所以标准形线性规划问题可等价表示为：它的对偶规划为：若令线性规划标准型的对偶规划为：9 对偶线性规划的求法从任何一个线性规划出发，都可以求出相应的对偶规划，在实际求解过程中，通常不通过求标准型，而是利用如下反映原始问题与对偶问题对应关系的原始─对偶表：目标函数变量系数约束条件右端项约束条件右端项目标函数变量系数约束条件个数：n个决策变量个数：n个对偶变量个数：m个约束条件个数：m个目标函数minW目标函数maxZ对偶问题（或原问题）原问题（或对偶问题）10 例2写出下列线性规划的对偶问题解：设对于原问题4个约束条件的对偶变量分别为由4个约束条件的类型，可知4个对偶变量分别为≤0，≥0，≥0和无约束；又因为原问题有3个决策变量　　　　　，因此对偶规划有3个约束条件，由3个决策变量的符号，可知对偶规划3个约束条件的类型分别为≥，≤，=。由此可得上述问题的对偶规划：11 本节讨论几条重要的对偶定理，这些定理揭示了原始问题的解和对偶问题的解之间的基本关系。定理1：对偶问题的对偶是原问题。证明：设原问题为　　　　　　　　对偶问题为改写对偶问题为　　　对偶问题的对偶为对偶定理12 定理2：弱对偶定理若　　是原（极大化）问题的可行解，　　是对偶（极小化）问题的可行解，那么证明：因为　　是对偶问题的可行解，所以满足约束条且；又因为　　是原问题的可行解，可得　　　，　　　　,所以　　　　　　　　　。推论1：原（极大化）问题的最优目标函数值以对偶问题任一可行解的目标函数值为上界。对偶（极小化）问题的最优目标函数值以原问题任一可行解的目标函数值为下界。推论2：如果原问题没有上界（即maxZ→+∞），则对偶问题不可行。如果对偶问题没有下界（即minW→-∞），则原问题不可行。13 定理3：最优性定理若　　是原问题的可行解，　是对偶问题的可行解，而且两者的目标函数值相等，即　　　　，则　　和分别是原问题和对偶问题的最优解。证明：由弱对偶定理，对于原始问题的所有可行解　　，都有　　　　　　　因此　是原问题的最优解。同理，对于对偶问题的所有可行解，都有所以是对偶问题的最优解。14 定理4:强对偶定理如果原问题有最优解，那么对偶问题也有最优解，而且目标函数值相等。证明：设　　是原问题的最优解，则它们对应的基Ｂ必有，且松弛变量检验数　　　　　。若定义　　　　，则　　　　，且　　　，因此　　　　　为对偶问题的可行解，而且　　　　　　　　　，由最优性定理，　　　　是对偶问题的最优解。推论1：若原问题有一个对应于基Ｂ的最优解，那么此时的单纯形乘子　　　　　是对偶问题的一个最优解。根据这个推论我们可以在原问题的最优单纯形表中直接找到对偶问题的最优解，即松弛变量检验数的相反数。15 例4、利用单纯形表求例1中原问题的最优解，并由最优单纯形表推出对偶问题的最优解。解：原问题线性规划模型为：引入松弛变量　　　　　，化标准形得:16 10-2/301/34/3x132001/31-2/33/4X404/21002-14x1324/30013-24X308/4/514/501/508x13212/8/508/51-3/5012X3040/55401040x4036/33410036X3000-7/60-19/6Z013/40-1/48x2300007/2-11/2278Z010-9/45/45x230022/50-32/50256Z4/4/504/50-9/514x5032300000Z76/99800176x50x1x2x3x4x5bXBCBΘ3230000C17 由最优表可知，原问题最优解同时不难得到原问题的最优基由强对偶定理的推论可得此时的单纯形乘子为对偶问题的最优解,即松弛变量检验数的相反数。C3230000CBXBbx1x2x3x4x503230x4x1x23/44/38001/31-2/310-2/301/3013/40-1/4Z00-7/60-19/618 定理5：互补松弛定理如果　　分别是原问题的对偶问题的可行解，那么和为最优解的充要条件是其中　　为原问题的松弛变量，　是对偶问题的剩余变量。通常称　　　　　　　　　　为互补松弛条件。若令则　　　　的含义是：要么　　　，要么若令则　　　　的含义是：要么　　　，要么19 例5、已知线性规划问题:其对偶问题的最优解。试用互补松弛定理找出原问题的最优解。解：原问题的对偶问题为：由对偶问题最优解　　　　　　　　可知　　　　　　　，由互补松弛定理，原问题的松弛变量解方程组　　　　　　　　　　　　所以原问题最优解20 对偶问题可改写为定理6：原问题的检验数对应对偶问题的一个基本解。证明：设Ｂ是原问题的一个可行基，且则原问题可以写为其中　分别为原问题决策变量中基变量和非基变量所对应的对偶约束的剩余变量。对偶问题也可等价表示为：对原问题可行基Ｂ，可得可行解对应于　　　　　　　　　　　　的检验数分别为。不难验证，为对偶问题的一个基本解。21 由强对偶定理可知，如果原问题有最优解　　，那么对偶问题也有最优解　　，而且它们的目标函数值相等，即有：其中　　　　　　　　　　是线性规划原问题约束条件的右端数据向量，它代表各种资源的拥有量。为对偶问题最优解，它代表在资源最优利用条件下对各种单位资源的估价，这种估计不是资源的市场价格，而是根据资源在生产中所作出的贡献（如创造利润，产值等）而作出估价，为区别起见，称之为影子价格(shadowprice)。对偶最优解的经济解释—影子价格22 影子价格的大小客观地反映了各种不同资源在系统内的稀缺程度。如果第i种资源供大于求，即在达到最优解时，该种资源没有用完，或松弛变量　　　，由互补松弛定理，在对偶最优解　　中，第i种资源的影子价格　　　。反之如果第i种资源的影子价格　　　，那么由互补松弛定理，原问题的第i个约束为严格等式，即　　　，这表明第i种资源已经用完，成为稀缺资源。资源的影子价格同时也是一种机会成本，在市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应买进这种资源用于扩大生产；相反当某种资源的市场价格高于影子价格时，企业应卖出这种资源。随着资源的买进卖出，企业资源的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。23 设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）3230例１：对偶最优解其中　　　　为设备A的影子价格，在资源最优利用的条件下，设备A每增加一个单位台时，可以使总利润增加　元。若设备Ａ可供台时数＝３７，则24 第2章介绍的单纯形法是以保持原问题可行为条件，即不论进行怎样的基变换，常数列　　　必须保持非负。利用对偶问题的对称性，我们从另一个角度来考虑求解原问题最优解的方法，这种方法以保持对偶问题可行为条件，即不论进行何种基变换，必须保持所有的检验数非正，同时取消原问题必须可行的要求，即取消常数列的非负限制，通过基变换使原问题在非可行解的基础上逐步转换成基本可行解，一旦原问题的基本解可行，则该基本可行解也就是最优解，这就是对偶单纯形法的基本思想。原问题：　　基本解　→　基本可行解（已为最优解）对偶问题：　可行解　→　可行解（保持所有的检验数非正）对偶单纯形法25 对偶单纯形法基变换的次序和一般单纯形法不同：一般单纯形法首先由最大增加原则确定换入变量，然而用最小比值原则确定换出变量。对偶单纯形法则是先将具有负分量的基变换取出，作为换出变量，然后确定某个非基变量　　作为换入变量。其变换目的是在保持对偶问题可行性的前提下，使原问题的基本解向可行解靠拢。26 对偶单纯形法的计算步骤如下：（1）根据原始线性规划，列出初始单纯形表，检查b列数字和检验行元素，若b列数字全部非负，检验数全部非正，则已经求得最优解，停止计算。若b列中至少有一个负分量，检验数全部非正，则转入（2）,（2）确定换出变量根据　，确定基变量作为换出变量。检验　　所在行各元素若所有　　　　,则无可行解，停止计算。否则转入(３)，（3）确定换入变量按最小比值原则，若确定非基变量为换入变量。（4）以为主元进行旋转变换，得新的单纯形表，重复（2）-（4），直到求得最优解。27 例6用对偶单纯形法求解解：先化为标准型对偶单纯形允许约束方程右端为负，因此可将方程2，3两端同乘-1，可得含单位矩阵的标准型：28 据此列出初始单纯形表，并施行对偶单纯形法迭代步骤如下：-5/4-7/4000-16-W-1/41/40102x2-2-1/4-3/40014x1-35/43/41004x30-2/3000-7/3-20/3-W-1/30011/310/3x2-21/3100-4/3-16/3x40101018x30000-2-30-W100-3-1-10x500101-1-2x400013218x30x5x4x3x2x1bXBCB000-2-3C可得最优解29 灵敏度分析一个标准形式的线性规划问题可由约束矩阵Ａ，右端项向量b，和价值向量Ｃ完全确定，假如一个线性规划问题对于给定的数据集合Ａ，b，Ｃ有最优解，则最优解　　　　　。最优目标函数值　　　　　　，其中Ｂ为最优基。但是线性规划问题所对应的数据集合Ａ，b，Ｃ常常是通过预测或估计所得到的统计数据，在实际使用中，不免会有一定的误差。而且随着市场环境，工艺条件和资源数量的改变，这些数据完全可能发生变化。因此有必要来分析一下当这些数据发生波动时，对目前的最优解，最优值或者最优基会产生什么影响，这就是所谓的灵敏度分析。30 灵敏度分析主要讨论如下二类问题：线性规划的数据集合在什么范围内波动将不影响最优解或最优基？若最优解发生变化，应如何用最简单的方法找到新的最优解。为讨论方便，以下列出标准型线性规划问题最优单纯形表的一般形式，其中B为线性规划问题的最优基：CC1C2…CnCBXBbx1x2…xnCB1XB1B-1bB-1A=B-1(P1，P2，…，Pn)CB2XB2::CBmXBmZCBB-1bC-CBB-1A31 价值向量C的改变当价值向量由　　　　　　　　　　　　　　　　　　　　时，最优单纯形表发生变化的只是检验行的有关数据，其中基变量检验数保持为零。非基变量检验数应修改为：目标函数值应为　　　　　　　　。只要变化以后的非基变量检验数那么原最优解仍然为最优。至于目标函数值是否改变，取决于基变量价值系数的改变量以下分别就价值系数对应非基变量或基变量两种情况加以讨论：32 若是非基变量的价值系数，　为该价值系数的改变量。那么在最优表中只有的检验数发生变化。由　　　　　　　　　　　　只要即就可以保持现行最优解仍为最优，由此可以确定价值系数的可变化范围。若超出稳定范围，那么的检验数，当前解已不是最优解。此时必须以修改后的单纯形表出发，重新进行单纯形迭代，直至求出新的最优解。非基变量价值系数的变化，可能使最优基Ｂ改变，从而导致最优解　　　　和最优值　　　　　　的改变。33 若是某基变量的价值系数，为价值系数的改变量。由于为基变量，所以在最优表中所有的非基变量检验数均发生了变化，由　　　　　　　　　　　　　只要非基变量检验数：或即可最优解仍然保持为最优，其中为原最优表中非基变量检验数，为最优表系数矩阵中基变量所在行中所有非基变量对应的系数。由上式可得到一个联列不等式组，求解该不等式组就可得到价值系数　的可变动范围。基变量价值系数的变化，可能使最优基Ｂ改变，从而导致最优解　　　　的改变。而最优值　　　　　　　　　则一定改变。34 例7、某工厂用甲乙两种原料生产A，B，C，D四种产品，每种产品的利润，现有原料数及每种产品消耗原料定额如表3-6所示：原料（公斤）产品（万件）供应量ABCD甲乙321040021/2183利润（万元/万件）985019问应该怎样组织生产，才能使总利润最大，若产品Ａ或Ｃ的利润产生波动，波动范围多大时，原最优解保持不变？解：设生产Ａ，Ｂ，Ｃ，Ｄ四种产品各　　　　　　万件，则此问题的线性规划模型为：35 标准化，引入松弛变量x5,x6，，利用单纯形表求解：-4-2/300-13/3-10/388Z24/3012/3-10/3-1/2-1/310-1/64/321x4x319500202-3-1084Z2612/301/21/3-5/30011/401/213/2x1x395098013/20-2575Z1-3203/21-50011/401/233/2x5x3050985019000Z9/53/232104100021/201183x5x600x1x2x3x4x5x6BXBCBθ98501900C即最优生产方案是生产Ｃ产品1万件，Ｄ产品2万件，不生产Ａ,Ｂ两种产品。可得最大利润为88万元。36 C98501900θCBXBBx1x2x3x4x5x61950x4x32124/3012/3-10/3-1/2-1/310-1/64/3Z88-4-2/300-13/3-10/3最优表：(1)若Ａ产品的利润　　　，有改变量　　。因为　为非基变量，由　　　　　　推得　　　　　　　　或　　　　（万元）时原最优解　　　　　　　不变，最优利润值　　　　　　（万元）也不变。(２)若Ｃ产品的利润　　　，有改变量　　。因为　为基变量，由　　　　　　　　推得即当　　　　　　　或　　　　　　　　时原最优解不变，最优利润值　　　　　　　　　　　　　　　（万元）37 右端项向量b的改变当右端项向量b由时，改变的只是表中右端常数列。此时基变量，目标函数值。而检验行的检验向量保持不变。右端项向量b的波动会使最优解和最优目标函数值发生变化，但原最优解的检验向量仍能保持非正。为了使B可行，只要或若，因为检验向量仍保持非正，因此可用对偶单纯形法再次进行迭代，直到求得新最优解。右端列向量b变化时，最优解　　　　　　和最优值　　　　　　一定改变。因此我们主要讨论右端列向量b变化时，最优基Ｂ是否改变38 例8、在例7中，若想增加甲种原料，问增加多少时原最优基不变？解：设甲种原料的改变量为,则由即由此可以推得，即当时，原最优基不变。此时最优解或最优目标函数值(万元)39 约束矩阵A的改变约束矩阵A的改变可能导致不同的最优解和最优基.以下只涉及两种较简单的情形：增加或减少一个变量，增加或减少一个约束条件。以下讨论假设原线性规划问题有一个最优解　　　　　　其中Ｂ为最优基，且约束矩阵被划分为40 增加或减少一个变量（1）增加一个新变量假设在获得原线性规划的最优解之后，又发现了一个新变量，其对应的价值系数为，在新的约束矩阵中对应的系数列向量为，于是可得如下新的线性规划问题：设　　　　，则为新线性规划问题的一个可行解。因此可在此基础上开始单纯形法，求新的最优解。如果　　，则含　　　　的当前解　　　是新问题的最优解。否则以　　　为换入变量进行基变换，继续使用单纯形算法为新的线性规划寻求一个最优解。41 （2）减少一个变量如果必须把某个变量　　从决策变量中去掉，那么原最优解在新的线性规划中一定发生改变。我们讨论的目标是如何用最小的工作量去寻求新的最优解。如果原最优解中的　　　　，则只需将从原最优解中剔除即可保持最优。如果原最优解中的（此时必为基变量），则必须重新计算新的解。为此可建立一个辅助线性规划：由于约束方程组没有改变，因此原最优解在辅助线性规划中可以作为初始基本可行解用于单纯形算法。如果辅助线性规划最优解的目标函数值为零，则用此最优解剔除　　　以后，可得新的线性规划问题的一个初始基本可行解，经有限次迭代，即可求出新问题的最优解。否则从原来问题中去除而得到的新的线性规划必定是不可行的。42 增加或减少一个约束（1）     增加一个约束如果在原来的线性规划的基础上再加入一个新的约束条件，不妨假设此附加的约束条件为不等式形式，即其中是n维行向量，为右端项系数，于是新的线性规划变成为了求解有附加约束条件的新问题，可以在附加不等式约束左端加上一个松弛变量　　,并考虑如下线性规划问题：43 其中　　　,　　　是　　中对应于基变量　　和非基变量的子向量，由此可以在原来最优基Ｂ的基础上定义一个新的基。易证　是非奇异矩阵，其逆阵按新基可以定义有附加约束条件新问题的一个基本解该基本解不一定是可行解，因为不一定满足非负条件，但是由于Ｂ是原线性规划问题的最优解，因此不难证明，即使对有附加约束条件的线性规划是不可行的，但都能保证该线性规划的对偶规划是可行的。44 因为对应于　的非基变量检验数结论：如果由新基定义的基本解是非负的。那么该基本解就是有附加约束条件的新线性规划问题的最优解。不满足非负条件。那么至少有一个基变量小于零，此时可用对偶单纯形法求出新问题的最优解。45 减少一个约束在原来线性规划的基础上，去掉一个约束条件的情况比较复杂，因为单纯形法是通过旋转运算实现基变换的，线性规划的旋转运算使每行元素成为其它各行元素的线性组合。因此如果要减少一个约束条件，那么原来的运算结果很难加以利用。一般情况下将不得不重头求解减少了一个约束条件的新的线性规划问题，好在减少一个约束条件可以大大地简化计算步骤。46 例9、在例7中，若考虑生产另一种产品Ｅ，已知每生产1万件Ｅ产品要消耗甲原料3公斤，乙原料1公斤，那么，Ｅ产品的每万件利润为多少时才有利于该种产品投产？若假设该工厂又增加了用电量不超过9千瓦的限制，已知生产Ａ，Ｂ，Ｃ，Ｄ四种产品各1万件分别耗电4，3，5，2千瓦，问此约束是否改变了原最优决策方案？解：（1）设生产Ｅ产品x7万件，1万件E产品的利润为c7万元，则数学模型变为：47 已知　　　　　　　是原问题的最优解，若令　　　　，则　　　　是现问题的一个可行解，但未必是最优解。若要Ｅ产品投产，即　　　，则其检验数,即得每万件E产品利润　　　　万元时，有利于生产E产品。48 由此可的新的最优解　　　　　　　　　　　，即最优生产方案为生产　　万件Ｄ产品和　　件Ｅ产品，总利润为　　　万元。C9850190017θCBXBBx1x2x3x4x5x6x719X4224/3012/3-10/3-4/350x31-1/2-1/310-1/64/35/6Z88-4-2/300-13/3-10/32/319X418/56/54/58/512/5-6/5017x76/5-3/5-2/56/50-1/58/51Z-18/5-2/5-4/50-21/5-22/50例如当万元时，代入原线性规划的最优单纯形表，得增加新变量的单纯形表，其中49 （２）假设工厂又增加了用电量不超过9千瓦，且生产Ａ，Ｂ，Ｃ，Ｄ四种产品各1万件分别耗电4，3，5，2千瓦用电量限制，则相当于原问题约束方程组增加了一个约束方程增加松弛变量　，得利用原线性规划最优单纯形表，增加一行和一列得一张新表，施行初等变换，使基变量　　　　对应的系数列向量为单位矩阵，若变换结果使基变量取了负值，则对应的基不是可行基，要用对偶单纯形法进行了基变换，并求得最优解，否则变换结果已为最优解。50 -20100-2-52-1/34/3001-1-4/34/34/3-10/30104-16/32/3X4x3x51950010-1/20025/2-104/3-1/601-1/3-1/210-10/32/3104/322X4x3x71950010025348x7004/3-1/601-1/3-1/21x3500-10/32/3104/322X419-26/3-10/3000-18-77/3z0-10/3-13/300-2/3-488z0-10/3-13/300-2/3-488zx7x6x5x4x3x2x1BXBCBθ000195089c可见增加用电约束以后，最优生产方案是万件Ｃ产品，万件Ｄ产品，总利润为万元，比原问题的最大利润减少。51