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