chapter2对偶理论及灵敏度分析

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

1、线性规划的对偶理论与灵敏度分析第二章介绍对偶问题的写法、基本性质及对偶单纯形法；介绍影子价格的概念；介绍灵敏度分析的基本方法8/29/20211本章目录§2-1线性规划的对偶问题§2-2对偶问题的基本性质§2-3影子价格§2-4对偶单纯形法§2-5灵敏度分析§2-6参数线性规划8/29/20212§2-1线性规划的对偶问题引言一、对偶问题二、对称形式对偶问题的一般形式三、非对称形式的原-对偶问题四、对偶问题的写法返回本章目录8/29/20213引言在实际问题中，一个问题的优化往往可以从不同的两个角度提出问题。譬如，

2、要求在有限资源条件下生产利润最大；或在一定生产能力条件下使资源消耗最少。所以，在线性规划中，对任一给定的求最大值问题，相应也存在一个求最小值的问题。且两者包括有相同的数据。若称前者为原问题，则后者便称为对偶问题；或称前者为对偶问题，而称后者为原问题。两者互为对偶，具有密切的关系。只要得到其中一个问题的解，也就能够得到另一个问题的解。因而，从中选一个问题求解就可以了。8/29/20214一、对偶问题例1美佳公司利用该公司资源生产两种家电产品的线性规划模型为：设y1，y2，y3分别表示设备A、B和调试工序单位时间的价格。

3、则0y1+6y2+y3≥25y1+2y2+y3≥1对生产Ⅰ产品的全部资源的定价。假如另一公司想收购美佳公司的资源，美佳公司出让自己资源的条件是什么？出让代价不低于用同等资源组织生产两种产品所能获得的利润。对生产Ⅱ产品的全部资源的定价。产品Ⅰ的利润产品Ⅱ的利润8/29/20215原问题与对偶问题的数据比较原问题对偶问题x1x2原关系minwy105≤15y262≤24y311≤5对偶关系maxz=minwmaxz21≥≥8/29/20216二、对称形式对偶问题的一般形式定义：满足下列条件的线性规划问题称为具有对称形式：

4、其变量均具有非负约束，其约束条件当目标函数求极大时取“≤”号，当目标函数求极小时均取“≥”号。则其对偶问题的一般形式为：若原问题的一般形式为：yi(i=1,2,…，m)代表第i种资源的估价。8/29/20217矩阵形式表示的原问题与对偶问题原问题：对偶问题：令w′＝－w对偶问题令z＝－z′对偶问题的对偶是原问题8/29/20218三、非对称形式的原-对偶问题考虑标准形式的线性规划：maxz=CXAX=bX≥0maxz=CXAX≤bAX≥bX≥0minw=bT(Y′－Y″)AT(Y′－Y″)≤CTY′≥0，Y″≥0令Y

5、=Y′－Y″minw=bTYATY≤CTY为自由变量这就是非对称形式的对偶关系。在这种形式中，Y不要求非负。maxz=CXAX≤b－AX≤－bX≥0Y′Y″minw=Y′bA′Y≤C′Y为自由变量8/29/20219四、对偶问题的写法在写对偶问题时，要特别注意上表中原问题与其对偶问题的对应关系。8/29/202110写对偶问题的步骤：第一步：根据原问题数学模型的形式统一符号。若原问题目标函数求极大，则将其约束条件统一成“≤”或“＝”的形式；若原问题目标函数为求极小，则将其约束条件统一成“≥”或“＝”的形式。第二步：假

6、设对偶变量。对偶变量与原问题的约束条件一一对应，每一个约束条件都有一个对偶变量与它相对应。所以，对偶变量数等于原问题的约束方程数。第三步：根据原问题与对偶问题的关系写出对偶规划模型。8/29/202111例:写出下面规划问题的对偶规划问题。原问题：maxz=4x1+x2-5x3-4x4-2x52x2+x3+3x4+4x5=-63x1+x2-x3-x4≥2-4x1+2x3-2x4≤-5-6≤x1≤18x2≤25x3,x4≥0;x5不受限制统一符号（因求max,故约束统一成“≤”的形式：maxz=4x1+x2-5x3-4

7、x4-2x52x2+x3+3x4+4x5=-6-3x1-x2+x3+x4≤-2-4x1+2x3-2x4≤-5x1≤18-x1≤6x2≤25x3,x4≥0;x1,x2,x5不受限制y1y2y3y4y6y5minw=-6y1-2y2-5y3+18y4+6y5+25y6-3y2-4y3+y4-y5=42y1-y2+y6=1y1+y2+2y3≥-53y1+y2-2y3≥-44y1=-2yi≥0(i=2,3,4,5,6);y1为自由变量对偶问题第一步：统一符号第二步：假设变量第三步：写对偶问题8/29/202112例2写出下述

8、线性规划问题的对偶问题原问题：令x2＝－x4，x4≥0统一约束符号：y1y2y3对偶问题：令y2＝－y4，可得到教材上的形式：8/29/202113教材上例2的解法：原问题：令x2′＝－x2；x3′－x3″＝x3用两个不等式约束表示等式约束：统一约束符号：8/29/202114假设变量：写对偶问题：令y2′＝－y2；y3′－y3″＝y38/29