规划数学对偶理论和灵敏度分析课件.ppt
《规划数学对偶理论和灵敏度分析课件.ppt》由会员分享,可在线阅读,更多相关《规划数学对偶理论和灵敏度分析课件.ppt(40页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、关于规划数学对偶理论和灵敏度分析现在学习的是第1页,共40页第第3讲讲 对偶理论对偶理论对偶问题的提出对偶问题的提出线性规划的对偶理论线性规划的对偶理论线性规划的对偶理论线性规划的对偶理论对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法对偶问题的经济解释对偶问题的经济解释-影子价格影子价格重重 点:对偶理论,对偶单纯形法点:对偶理论,对偶单纯形法 难难 点:对偶理论点:对偶理论基本要求:掌握对偶关系,理解对偶性质,掌握对偶基本要求:掌握对偶关系,理解对偶性质,掌握对偶单纯形法,单纯形法,会求影子价格,会求影子价格,现在学习的是第2页,共40页引例:经营策略问题。甲工厂有设备和原料引例:经营策略
2、问题。甲工厂有设备和原料A、B 这些设备和原这些设备和原料可用于料可用于、两种产品的加工,每件产品加工所需机时数,原两种产品的加工,每件产品加工所需机时数,原料料A、B消耗量,每件产品的利润值及每种设备的可利用的机时数消耗量,每件产品的利润值及每种设备的可利用的机时数如下表。现在乙厂和甲厂协商,打算租用甲厂的设备如下表。现在乙厂和甲厂协商,打算租用甲厂的设备购买资源购买资源A和和B。问甲厂采取哪种经营策略,是自己生产产品还是出租。问甲厂采取哪种经营策略,是自己生产产品还是出租设备、出让原材料?如果出租设备、出让原材料,在和乙厂设备、出让原材料?如果出租设备、出让原材料,在和乙厂协商时出租设备和
3、出让原材料协商时出租设备和出让原材料A,B的底价应是多少?的底价应是多少?对偶问题的提出对偶问题的提出 设设 备备原料原料A原料原料B 1 4 0 2 0 4 80台时 160kg 120kg23盈利盈利现在学习的是第3页,共40页自己生产:自己生产:原问题原问题引例分析:现在学习的是第4页,共40页设设y1,y2和和y3分别表示出租单位设备台时的租分别表示出租单位设备台时的租金和出让单位原材料金和出让单位原材料A,B的附加额的附加额=80y1+160y2+120y3出售资源l显然商人希望总的收购价越小越好显然商人希望总的收购价越小越好l工厂希望出售资源后所得不应比生产产品所得少工厂希望出售资
4、源后所得不应比生产产品所得少 目标函数目标函数 min现在学习的是第5页,共40页例例1它的对偶问题是:它的对偶问题是:YAYA Cmin=YbYbY Y0 0Y Y=(y1,y2,y3)现在学习的是第6页,共40页1.5.1 原问题与对偶问题的关系(对称形式)线性规划的对偶理论线性规划的对偶理论现在学习的是第7页,共40页现在学习的是第8页,共40页原关系minw对偶关系maxzxy原问题与对偶问题的对称形式原问题与对偶问题的对称形式现在学习的是第9页,共40页 标准(max,)型的对偶变换目标函数由目标函数由 max 型变为型变为 min 型型对应原问题每个约束行有一个对偶变量对应原问题每
5、个约束行有一个对偶变量 yi,i=1,2,m对偶问题约束为对偶问题约束为 型,有型,有 n 行行原问题的价值系数原问题的价值系数 C 变换为对偶问题的右端项变换为对偶问题的右端项原问题的右端项原问题的右端项 b 变换为对偶问题的价值系数变换为对偶问题的价值系数原问题的技术系数矩阵原问题的技术系数矩阵 A 转置后成为对偶问题的技术系数矩阵转置后成为对偶问题的技术系数矩阵原问题与对偶问题互为对偶原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义对偶问题还有很多理论和实际应用的意义现在学习的是第10页,共40页原问题与对偶问题的结构关
6、系原问题与对偶问题中的目标函数的优化方向相反(前者为极大,原问题与对偶问题中的目标函数的优化方向相反(前者为极大,后者为极小)后者为极小)原问题的每个约束条件对应于对偶问题的一个决策变量,原问题的每个约束条件对应于对偶问题的一个决策变量,且约束条件的资源系数(右端的常数项)为相应决策变且约束条件的资源系数(右端的常数项)为相应决策变量的价值系数量的价值系数原问题的每个决策变量对应于对偶问题的一个约束条件,原问题的每个决策变量对应于对偶问题的一个约束条件,且决策变量的价值系数为相应约束条件的右端常数项且决策变量的价值系数为相应约束条件的右端常数项对偶问题中的系数矩阵为原问题中的系数矩阵的转置对偶
7、问题中的系数矩阵为原问题中的系数矩阵的转置原问题约束条件中的小于等于符号对应于对偶问题中的对原问题约束条件中的小于等于符号对应于对偶问题中的对偶变量取非负约束,原问题中决策的对偶问题非负约束在偶变量取非负约束,原问题中决策的对偶问题非负约束在对偶问题中体现为相应的约束条件取大于等于符号对偶问题中体现为相应的约束条件取大于等于符号现在学习的是第11页,共40页 非标准型的对偶变换现在学习的是第12页,共40页 对偶变换的规则现在学习的是第13页,共40页max=5y1+4y2+6y3y1+2y2y1+y3-3y1+2y2+y3y1-y2+y3=23-5 1y1 0,y2 0,y3无约束无约束对偶
8、问题例例3 3 写出线性规划问题的对偶问题写出线性规划问题的对偶问题minz=2x1+3x2-5x3+x4原问题原问题 x1+x2-3x3+x4 5 2x1+2x3 -x44 x2+x3 +x4=6 x1 0,x2,x3 0,x4无约束现在学习的是第14页,共40页(1)对称性:对偶的对偶就是原始问题min=-CXs.t.-AX -bX 0max z=-Ybs.t.-YA -CY 0min=Ybs.t.YA C Y 0max z=CXs.t.AX bX 0对偶的定义对偶的定义对偶的定义对偶的定义1.5.2 对偶问题的基本性质对偶问题的基本性质 为了便于讨论,下面不妨总是假设为了便于讨论,下面不
9、妨总是假设现在学习的是第15页,共40页(2)弱对偶性:若若 是原问题的可行解,是对偶问是原问题的可行解,是对偶问题的可行解。则存在题的可行解。则存在对偶问题对偶问题(min)min)的任何可行解的任何可行解Y Y,其目标函数值总是其目标函数值总是不小于原问题不小于原问题(max)max)任何可行解任何可行解X X的目标函数值的目标函数值现在学习的是第16页,共40页 弱对偶定理推论原问题的任何可行解目标函数值是其对偶问题目标函数值原问题的任何可行解目标函数值是其对偶问题目标函数值的下限;对偶问题的任何可行解目标函数值是原问题目的下限;对偶问题的任何可行解目标函数值是原问题目标函数值的上限标函
10、数值的上限如果原如果原(对偶对偶)问题为无界解,则其对偶问题为无界解,则其对偶(原原)问题无问题无可行解可行解如果原如果原(对偶对偶)问题有可行解,其对偶问题有可行解,其对偶(原原)问题无可行问题无可行解,则原问题为无界解解,则原问题为无界解当原问题当原问题(对偶问题对偶问题)为无可行解为无可行解,其对偶问题其对偶问题(原问题原问题)或或具有无界解或无可行解具有无界解或无可行解现在学习的是第17页,共40页 (3)强对偶性证:由弱对偶定理推论证:由弱对偶定理推论1 1,结论是显然的。,结论是显然的。若是原问题的可行解,是对偶问题可行解,当若是原问题的可行解,是对偶问题可行解,当 ,分别是相应问
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 规划 数学 对偶 理论 灵敏度 分析 课件
限制150内