管理运筹学对偶问题

运筹学2对偶问题运筹学教程运筹学Operations Research Chapter 2 对偶问题Dual Problem1. 线性规划的对偶模型Dual Model of LP2.对偶性质对偶性质3.对偶单纯形法对偶单纯形法4.灵敏度分析灵敏度分析Dual property Dual Simplex Method Sensitivity Analysis 运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dual model of LPCh2 Dual Problem2022年11月26日星期五Page 2 of 19在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。

【例2.1】某企业用四种资源生产三种产品，工艺系数、例资源限量及价值系数如下表：产品资源Ⅰ Ⅱ Ⅲ Ⅳ 每件产品利润9 5 8 7 100 8 4 3 6 80 6 7 2 4 70 500 450 300 550 A B C 资源限量建立总收益最大的数学模型。

运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dualmodel of LPCh2 Dual Problem2022年11月26日星期五Page 3 of 19 设x1,x2,x3分别为产品A,B,C的产量，则线性规划数学模解型为：m Z = 100x + 80x + 70x ax1 2 39x1 + 8x2 + 6x3 ≤ 500 5x + 4x + 7x ≤ 450 2 3 1 8x1 + 3x2 + 2x3 ≤ 300 7x + 6x + 4x ≤ 550 2 3 1 x1, x2, x3 ≥ 0 现在从另一个角度来考虑企业的决策问题。

假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？价格太高对方不愿意接受，价格太低本单位收益又太少。

第二章线性规划的对偶理论与灵敏度分析一、学习目的与要求 1、掌握对偶理论及其性质 2、掌握对偶单纯形法3、熟悉灵敏度分析的概念和内容4、掌握限制常数与价值系数、约束条件系数的变化对原最优解的影响5、掌握增加新变量和增加新的约束条件对原最优解的影响，并求出相应因素的灵敏度范围6、了解参数线性规划的解法 二、课时 6学时第一节 线性规划的对偶问题一、对偶问题的提出定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题，在求出一个问题的解时，也同时给出了另一问题的解。

应用：在某些情况下，解对偶问题比解原问题更加容易；对偶变量有重要的经济解释(影子价格)；作为灵敏度分析的工具；对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解)；避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量)。

例：某家具厂木器车间生产木门与木窗；两种产品。

加工木门收入为56元/扇，加工木窗收入为30元/扇。

生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。

问：(1)该车间应如何安排生产才能使每日收入最大？(2)假若有一个个体经营者，手中有一批木器家具生产订单。

他想利用该木器车间的木工与油漆工来加工完成他的订单。

他就要考虑付给该车间每个工时的价格。

他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。

解(1)：设该车间每日安排生产木门x1扇，木窗x2扇，则数学模型为⎪⎩⎪⎨⎧≥≤+≤++=-0502120343056max 21212121x x x x x x x zX*=(15,20)’ Z*=1440元解(2)：设y 1为付给木工每个工时的价格，y 2为付给油工每个工时的价格⎪⎩⎪⎨⎧≥≥+≥++=-0303562450120min 21212121y y y y y y y wY*=(2,24)’ W*=1440元将上述问题1与问题2称为一对对偶问题，两者之间存在着紧密的联系与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同。

运筹学对偶问题的直观描述
运筹学中的对偶问题是指原始线性规划问题和对应的对偶线性规划问题之间的关系。

直观描述对偶问题可以从几个方面来理解。

首先，可以从成本和效益的角度来理解。

原始线性规划问题通常涉及最小化成本或者最大化利润，而对偶线性规划问题则涉及最大化成本或者最小化利润。

这种对偶关系可以被解释为在资源有限的情况下，通过最小化成本来实现最大化效益，或者通过最大化效益来实现最小化成本。

其次，可以从约束条件的角度来理解。

原始线性规划问题的约束条件对应着对偶线性规划问题的变量，而对偶线性规划问题的约束条件对应着原始线性规划问题的变量。

这种对偶关系可以被理解为在资源分配和利用的过程中，对约束条件和变量之间的转换和对应关系。

另外，可以从几何图形的角度来理解。

原始线性规划问题的最优解和对偶线性规划问题的最优解之间存在着一种对偶关系，即原始问题的最优解和对偶问题的最优解分别对应着凸集的两个相对的极值点，它们之间的距离可以被理解为对偶问题的最优值和原始问
题的最优值之间的关系。

总的来说，对偶问题在运筹学中具有重要的意义，它不仅可以帮助我们理解原始问题和对偶问题之间的关系，还可以为我们寻找最优解提供了一种新的视角和方法。

通过对偶问题的研究和理解，我们可以更好地解决实际生产和管理中的复杂问题。

在运筹学中，对偶问题是一个与原问题相对应的问题。

以线性规划问题为例，每一个线性规划问题必然有与之相伴而生的另一个线性规划问题，即任何一个求maxz的LP1都有一个求minw的LP2。

将LP1称为“原问题”，记为P；将LP2称为“对偶问题”，记为D。

对偶问题的经济学解释——影子价格又称影子利率，用线性规则方法计算出来的反映资源最优使用效果的价格。

用微积分描述资源的影子价格，即当资源增加一个数量而得到目标函数新的最大值时，目标函数最大值的增量与资源的增量的比值，就是目标函数对约束条件（即资源）的一阶偏导数。

用线性规划方法求解资源最优利用时，即在解决如何使有限资源的总产出最大的过程中，得出相应的极小值，其解就是对偶解，极小值作为对资源的经济评价，表现为影子价格。