第三章 线性规划的对偶理论及灵敏度分析

《第三章 线性规划的对偶理论及灵敏度分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章线性规划的对偶理论及灵敏度分析主要内容：1、对偶问题及其性质；2、对偶单纯形法；3、灵敏度分析。重点与难点：对偶问题与原问题的对应关系，对偶问题的基本性质，对偶单纯形法的求解步骤，灵敏度分析的方法。要求：理解线性规划对偶问题的性质，熟练掌握对偶单纯形法的求解步骤和灵敏度分析的方法和技巧，能够用这些数学方法解决实际问题。§1对偶问题的对称形式一、对偶问题引例，某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备台时及A、B两种原材料的消耗，该工厂每生产一件产品甲可获利2元，每生产一件

2、产品乙可获利3元，问应如何安排计划才能使该工厂获利最多？甲乙设备原材料A原材料B1402048台时16kg12kg解：设、分别为甲、乙两种产品的产量则目标函数约束条件(1)假设该工厂决定不再生产甲、乙产品，而将其出租或出售。这时要考虑每种资源的定价问题，设分别为出租单位设备台时的租金和出让单位原材料A、B的附加额。作一比较：若用一个单位台时和4个单位原材料A生产一件产品甲，可获利2元，那么生产每件产品甲的设备台时和原材料出租和出让的收入应不低于生产一件甲产品的利润。即：同理，将生产每件乙产品的设备台时和原

3、材料出租和出让的收入应不低于生产一件乙产品的利润。即：将工厂所有设备台时和资源都出租和出让，其收入为对工厂来说，越大越好；但对接受者来说，支付的愈少愈好，所以工厂只能在满足≥所有产品的利润前提下，使其总收入尽可能小，才能实现其愿望。为此，得到如下模型：(2)我们就称(2)为模型(1)的对偶问题。一般地，设原问题为则其对偶问题为：矩阵形式：原问题对偶问题二、原问题与对偶问题的关系原问题（或对偶问题）对偶问题（或原问题）目标函数maxz目标函数min变量n个00无约束n个=约束条件约束条件m个=m个00无约束

4、变量约束条件右端项目标函数变量的系数目标函数变量的系数约束条件的右端项例1求下列问题的对偶问题解：§2对偶问题的基本性质一、对称性：对偶问题的对偶是原问题。证：设原问题为则其对偶问题为：对上式两边取负号，得上式的对偶问题为（两边同取负号）二、弱对偶性：若是原问题的可行解，是对偶问题的可行解，则存在。证：是原问题的可行解有已知是对偶问题的可行解，用左乘上式得同理，用右乘之得,故三、无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。注意：此性质不可逆。四、可行解是最优解时的性质最优性：设是

5、原问题的可行解，是对偶问题的可行解，当时，、是最优解。五、对偶定理（强对偶性）：若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。反之，若其一无最优解，则另一也无最优解。六、互补松弛性：若、分别是原问题和对偶问题的可行解，那么和，当且仅当、为最优解。证：设原问题和对偶问题的标准型是将分别代入原问题和对偶问题目标函数得，若；则由性质4知，、为最优解。又如果、为原问题和对偶问题的最优解，由性质4有即必有例2已知线性规划问题试用对偶理论证明上述线性规划问题无最优解。证：原问题存在可行解，如上述问题的对

6、偶问题为由第一个约束条件知，对偶问题无可行解，所以，由对偶定理知，原问题无最优解。七、对偶问题的经济解释----影子价格由对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等，即有求z对b的偏导数得：即其经济学意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。的值代表对第i种资源的估价，这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。影子价格随具体情况而异，在完全市场经济条件下，当某种资源的市场价格低于影子价格时，企业应买进该资源用于扩大生产；

7、而当某种资源的市场价格高于企业影子价格时，则企业应把已有的资源卖掉。可见，影子价格对市场有调节作用。§3对偶单纯形法一、基本思路对偶单纯形法是运用对偶原理求解原问题的一种方法，而不是求解对偶问题的单纯形法。首先讨论这样一个问题：设原问题：则其对偶问题：化为标准型：设B是原问题的一个可行基，于是A=(B

8、N)，原问题可改写为：相应地对偶问题可以表示为min这里----对应原问题中基变量的剩余变量----对应原问题中非变量的剩余变量当求得原问题的一个基解，其相应的检验数为与。现分析这些检验数与对偶问题的解之间

9、的关系：令代入(1)、(2)得由此可得出：原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如下：0说明：在单纯形表中若在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解，当在检验数行得到对偶问题的解也是基可行解时，根据性质知，已知到最优解，即原问题与对偶问题是最优解。根据对偶问题的对称性，可这样考虑：若保持对偶问题的解是基可行解，即，而原问题在非可行解的基础上，逐步迭代达到基可行解，这样也得到了最