对偶问题与灵敏度分析

《对偶问题与灵敏度分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章线性规划的对偶理论与灵敏度分析3.1对偶问题的一般概念1.对偶问题的提出对偶理论是线性规划的内容之一。任何一个线性规划都有一个伴生的线性规划，称之为原规划的对偶规划问题。下面通过实例引出对偶问题，然后给出对偶线性规划的定义。对偶问题的经济意义：第一章例1提出的线性规划问题为：某工厂生产Ⅰ、Ⅱ两种型号的计算机，每生产一台Ⅰ型和Ⅱ型计算机所需的原料、工时和提供的利润以及资源的限制量如下表：资料产品ⅠⅡ总量原料23100工时42120利润64　试确定获利最大的生产方案。该问题的线性规划数学模型为：假如现在工厂自己不生产Ⅰ、Ⅱ，而将可利用的资源都出让给其他企业，试确定这些资源的最低可

2、接受价格。最低可接受价格是指按这种价格转让资源比自己生产Ⅰ、Ⅱ合算的价格。设，为这两种资源的价格，为了使工厂出让资源合算，显然应该使出让原来生产一台Ⅰ的资源所得收入不低于自己生产一台产品Ⅰ的利润，即，对于产品Ⅱ类似，即。显然在满足这两个约束的条件下，价格越高，该工厂越合算，但价格太高，接受方面又不会愿意购买。因此，我们需要确定的价格是使工厂合算的最低价格，故应建立目标函数：。综上所述，出让资源问题的数学模型如下：工厂决策者所面临的两个问题的数学模型都是线性规划，它们在结构上具有某种对称性，称后一个线性规划为原规划的对偶问题。定义称线性规划为原线性规划的对偶是一个行向量，它的每一个分

3、量称为对偶变量。例：写出下列线性规划问题的对偶问题：解：则下面考虑标准形式的线性规划问题的对偶问题：现将问题改写成等价形式设对偶变量向量为，其中u，v均为m维行向量，因此写出它的对偶问题令，则上式又可写成其中的分量无符号限制。即标准形式的线性规划问题的对偶问题和标准型线性规划问题的不同之处在于对偶变量无符号限制，所以称为一对非对称的对偶问题。混合形式的对偶问题转化原问题（或对偶问题）对偶问题（或原问题）目标函数目标函数价值系数C资源系数资源系数b价值系数行约束的个数m对偶变量的个数为m第i个行约束为“”第i个变量为“”第i个行约束为“=”第i个变量无限制原变量的个数为n行约束的个数

4、为n第j个变量为“”第j行约束为“”第k个变量无限制第k行约束为“=”例：写出下列线性规划问题的对偶问题解：设对应于3个约束条件的对偶变量分别为，3.2对偶问题的基本性质Th1（对称性定理）对偶问题（D）的对偶是原问题（L）证：原规划为对偶规划为得得Th2(弱对偶问题)若和分别是原问题和对偶问题的可行解，则证:因为,所以，即又因为所以。推论1若和分别是原问题和对偶问题的可行解，则是原问题的最小值的一个下界，是对偶问题的最大值的一个上界。推论2若原（对偶）问题可行，但目标函数无解，则对偶（原）问题不可行。推论3若原（对偶）问题可行，而对偶（原）问题不可行，则原（对偶）问题的目标函数无

5、界。Th3（最优性）若和分别为互为对偶线性规划问题和原线性规划问题的可行解,，则，分别是原问题和对偶问题的最优解。Th4（主对偶定理）若互为对偶的线性规划问题都有可行解，则他们都有最优解，且最优值相等。Th5（对偶定理）若互为对偶的线性规划问题中的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。证：设，是原问题的最优基的最优解，记则有即（证明Y为原问题的可行解）；再有,可得即(证明最优性)知是原问题的最优解。可知：对偶最优解实际是原问题松弛变量检验数的相反数。原问题最优解求得最优解的同时其对偶问题的最优解也应运而生。3.3对偶问题的经济解释——影子价格在单纯性算法中，

6、设,是最优解：最优基取则是对偶最优解。下面讨论的经济含义。设有单位增量，其它参数不b变，则：即.所以表示在原问题已取得最优解的情况下，第种资源改变一个单位时总收益的变化值，也可以说是对第种资源的一种价格估计。这种价格估计并不是第种资源的实际价值或成本，而是由该企业在制产品的收益来估计所用资源的单位价值，称为影子价格。与具体企业有关，同一资源，产品不同，影子价格不同，企业不同，影子价格不同。利用工艺条件来估计的资源的单位价值，影子是潜在的，不是实际价格，跟在企业后面的价格估计。由于影子价格是指资源增加时对最优效益的贡献，所以，也称它为资源的机会成本或边际产品，它表示资源在最优产品组合

7、时，具有的“潜在价值”或“贡献”。资源的影子价格是与具体的企业及产品有关的，同一种资源，在不同企业，或生产不同产品时对应的影子价格并不相同。从对偶问题引出的实例中，可以看出，影子价格也是企业出让资源的最低价格，企业按这种价格出让资源与利用这种资源自己生产所获得的收益是相等的。影子价格是经济学中的重要概念，将一个企业拥有的资源的影子价格与市场价格比较，可以决定是购入还是出让该种资源。当某种资源的市场价格低于影子价格时，企业应该买进资源，用于扩大生产；而当市场价格高于影子