《规划数学对偶理论》PPT课件

《《规划数学对偶理论》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章线性规划线性规划模型及单纯形法（4学时）对偶理论及灵敏度分析（2学时）1《运筹学》第二章对偶理论和灵敏度分析第3讲对偶理论对偶问题的提出线性规划的对偶理论对偶问题的经济解释---影子价格重点：对偶问题，对偶理论，难点：对偶理论应用基本要求：掌握对偶关系，理解对偶性质，会求影子价格，2《运筹学》第二章对偶理论和灵敏度分析引例：经营策略问题。甲工厂有设备和原料A、B这些设备和原料可用于Ⅰ、Ⅱ两种产品的加工，每件产品加工所需机时数，原料A、B消耗量，每件产品的利润值及每种设备的可利用的机时数如下表。现在乙厂和甲厂协商，打算租用甲厂的设备购买资源A和B。问甲厂采取哪种

2、经营策略，是自己生产产品还是出租设备、出让原材料？如果出租设备、出让原材料，在和乙厂协商时出租设备和出让原材料A,B的底价应是多少？对偶问题的提出ⅠⅡ设备原料A原料B14020480台时160kg120kg23盈利3《运筹学》第二章对偶理论和灵敏度分析自己生产：原问题引例分析：4《运筹学》第二章对偶理论和灵敏度分析设y1,y2和y3分别表示出租单位设备台时的租金和出让单位原材料A,B的附加额ω=80y1+160y2+120y3出售资源对偶问题显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少目标函数min5《运筹学》第二章对偶理论和灵敏度分析例

3、1它的对偶问题是：YA≥Cminω=YbY≥0Y=（y1，y2，y3）6《运筹学》第二章对偶理论和灵敏度分析1原问题与对偶问题的关系(对称形式)线性规划的对偶理论7《运筹学》第二章对偶理论和灵敏度分析8《运筹学》第二章对偶理论和灵敏度分析原关系minw对偶关系maxzxy原问题与对偶问题的对称形式9《运筹学》第二章对偶理论和灵敏度分析标准(max,)型的对偶变换目标函数由max型变为min型对应原问题每个约束行有一个对偶变量yi，i=1,2,…,m对偶问题约束为型，有n行原问题的价值系数C变换为对偶问题的右端项原问题的右端项b变换为对偶问题的价值系数原问题的技术

4、系数矩阵A转置后成为对偶问题的技术系数矩阵原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义10《运筹学》第二章对偶理论和灵敏度分析原问题与对偶问题的结构关系原问题与对偶问题中的目标函数的优化方向相反（前者为极大，后者为极小）原问题的每个约束条件对应于对偶问题的一个决策变量，且约束条件的资源系数（右端的常数项）为相应决策变量的价值系数原问题的每个决策变量对应于对偶问题的一个约束条件，且决策变量的价值系数为相应约束条件的右端常数项对偶问题中的系数矩阵为原问题中的系数矩阵的转置原问题约束条件中的小于等于符号对应于对偶问题中的对偶变量

5、取非负约束，原问题中决策的对偶问题非负约束在对偶问题中体现为相应的约束条件取大于等于符号11《运筹学》第二章对偶理论和灵敏度分析非标准型的对偶变换12《运筹学》第二章对偶理论和灵敏度分析对偶变换的规则13《运筹学》第二章对偶理论和灵敏度分析maxω=5y1+4y2+6y3≥≤≤y1+2y2y1+y3-3y1+2y2+y3y1-y2+y3=23-51y1≥0，y2≤0,y3无约束对偶问题例3写出线性规划问题的对偶问题minz=2x1+3x2-5x3+x4原问题x1+x2-3x3+x4≥52x1+2x3-x4≤4x2+x3+x4=6x1≤0,x2,x3≥0,x4无约束1

6、4《运筹学》第二章对偶理论和灵敏度分析（1）对称性：对偶的对偶就是原始问题minω’=-CXs.t.-AX≥-bX≥0maxz’=-Ybs.t.-YA≤-CY≥0minω=Ybs.t.YA≥CY≥0maxz=CXs.t.AX≤bX≥0对偶的定义对偶的定义2对偶问题的基本性质为了便于讨论，下面不妨总是假设15《运筹学》第二章对偶理论和灵敏度分析(2)弱对偶性:若是原问题的可行解，是对偶问题的可行解。则存在对偶问题(min)的任何可行解Y，其目标函数值总是不小于原问题(max)任何可行解X的目标函数值16《运筹学》第二章对偶理论和灵敏度分析弱对偶定理推论原问题的任何可行

7、解目标函数值是其对偶问题目标函数值的下限；对偶问题的任何可行解目标函数值是原问题目标函数值的上限如果原(对偶)问题为无界解，则其对偶(原)问题无可行解如果原(对偶)问题有可行解，其对偶(原)问题无可行解，则原问题为无界解当原问题(对偶问题)为无可行解,其对偶问题(原问题)或具有无界解或无可行解17《运筹学》第二章对偶理论和灵敏度分析(3)强对偶性证：由弱对偶定理推论1，结论是显然的。若　是原问题的可行解，是对偶问题可行解，当,,分别是相应问题的最优解是使目标函数取最小值的解，因此是最优解可行解是最优解的性质(最优性准则定理)18《运筹学》第二章对偶理论和灵敏度分