第二讲对偶理论与灵敏度分析.ppt

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

1、第二讲对偶理论与灵敏度分析运筹学OperationsResearch对偶理论是线性规划发展的重要成果之一。每一线性规划问题(称其为原问题)都有一个与之相对应的线性规划问题(称其为对偶问题)，两个问题互为对偶问题。对偶理论是研究线性规划的对偶关系和解的特征理论，根据对偶理论，我们在求解线性规划问题时同时得到其对偶问题的最优解以及相对各个约束的影子价格等信息在实际问题中有着广泛的应用。此外，应用对偶理论还可提出求解线性规划问题的另一种单纯形法。【例1】某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：建立总收益最大的数学模

2、型。产品资源ABC资源限量Ⅰ986500Ⅱ547450Ⅲ832300Ⅳ764550单件产品利润1008070线性规划的对偶模型DualmodelofLP线性规划的对偶模型【解】设x1，x2，x3分别为产品A，B，C的产量，则线性规划数学模型为：现在从另一个角度来考虑企业的决策问题。假如企业不考虑自己生产产品，而将现有的资源标价出售，问题：决策者应怎样给定资源一个合理的价格？线性规划的对偶模型DualmodelofLP设y1，y2，y3及y4分别表示四种资源的单位增值价格(售价＝成本＋增值)，总增值最低可用minw=500y1+450y

3、2+300y3+550y4表示。企业生产一件产品A用了四种资源的数量分别是9，5，8和7个单位，利润是100,企业出售这些数量的资源所得的利润不能少于100，即同理，对产品B和C有线性规划的对偶模型DualmodelofLP称上述线性规划模型是前面生产计划模型的对偶线性规划模型,这一问题称为对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。价格不可能小于零，即有yi≥0(i=1,…,4),从而企业的资源价格模型为线性规划的对偶模型DualmodelofLP注：以上两问题是同一组数据参数，只是位置有所不同，所描述的问题实际上

4、是从两个不同的角度去描述。原始线性规划问题考虑的是充分利用现有资源，以产品数量和单位产品的利润来决定企业的总利润，没有考虑资源的价格，实际上在构成产品的利润中，不同的资源对利润的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格。线性规划的对偶模型DualmodelofLP线性规划问题(2.2)就是原线性规划问题(2.1)的对偶线性规划问题，反之，(2.2)的对偶问题就是(2.1)．原问题与对偶问题有如下关系(假设原问题(2.1))：(1)原问题的约束个数(不含非负约束)等于对偶变量的个数(2)原问题的目标函数系数

5、对应于对偶问题的右端项(3)原问题的右端项对应于对偶问题的目标函数系数(4)原问题的约束矩阵转置就是对偶问题系数矩阵(5)原问题求最大，对偶问题是求最小(6)原问题不等式约束符号为“≤”,对偶问题不等式约束符号为“≥”线性规划的对偶模型DualmodelofLP【例2】写出该线性规划的对偶问题【解】线性规划的对偶模型DualmodelofLP线性规划问题的规范形式(或叫对称形式)：定义：目标函数求极大值时，所有约束条件为≤号，变量非负；目标函数求极小值时，所有约束条件为≥号，变量非负。注：(1)线性规划规范形式与标准型是两种不同形式，

6、但可以相互转换。(2)规范形式的线性规划问题的对偶仍然是规范形式．线性规划的对偶模型DualmodelofLP对于一般的线性规划问题：其中为矩阵，为维列向量，为维向量，为维列向量(i=1,2,3;j=1,2)且令，此问题可化为线性规划的对偶模型DualmodelofLP用分别表示以上四组约束的对偶问题，则原问题的对偶问题是令，整理得对偶问题为将原问题与对偶问题的对应关系列于表2。原问题(或对偶问题)对偶问题(或原问题)目标函数max目标函数系数(资源限量)约束条件系数矩阵A(AT)目标函数min资源限量(目标函数系数)约束条件系数矩阵

7、AT(A)变量n个变量第j个变量≥0第j个变量≤0第j个变量无约束约束n个约束第j个约束为≥第j个约束为≤第j个约束为=约束m个约束第i个约束≤第i个约束≥第i个约束为=变量m个变量第i个变量≥0第i个变量≤0第i个变量无约束表2线性规划的对偶模型DualmodelofLP【例3】写出下列线性规划的对偶问题【解】=≥≤≤y1≤0，y2≥0，y3无约束线性规划的对偶模型DualmodelofLP对偶问题是(记为DP)：这里A是m×n矩阵,X是n×1列向量,Y是1×m行向量。【性质1】对称性:对偶问题的对偶是原问题。设原问题是(记为LP)

8、：对偶性质Dualproperty对偶性质【性质2】弱对偶性:设X*、Y*分别为LP(max)与DP(min)的可行解，则对偶性质Dualproperty由这个性质可得到下面几个结论：(LP)的任一可行解的目标值是(DP