对偶规划与灵敏度分析PPT讲稿.ppt
《对偶规划与灵敏度分析PPT讲稿.ppt》由会员分享,可在线阅读,更多相关《对偶规划与灵敏度分析PPT讲稿.ppt(60页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、对偶规划与灵敏度分析1第1页,共60页,编辑于2022年,星期六 对偶理论对偶理论是线性规划的重要内容之一。对应于每是线性规划的重要内容之一。对应于每个线性规划问题都伴生一个相应的线性规划问题。个线性规划问题都伴生一个相应的线性规划问题。原问题和对偶问题紧密关联,它们不但有原问题和对偶问题紧密关联,它们不但有相同的相同的数据集合数据集合,相同的最优目标函数值相同的最优目标函数值,而且在,而且在求得一个线性求得一个线性规划的最优解的同时,也同步得到对偶线性规划的最优解规划的最优解的同时,也同步得到对偶线性规划的最优解。由对偶问题引伸出来的对偶解还有着重要的由对偶问题引伸出来的对偶解还有着重要的经
2、济意义经济意义,是研究经济学的重要概念和工具之一。是研究经济学的重要概念和工具之一。2第2页,共60页,编辑于2022年,星期六n对偶问题的提出对偶问题的提出例例1 1、某工厂生产甲、某工厂生产甲,乙两种产品,这两种产品需要在乙两种产品,这两种产品需要在A,B,CA,B,C三种不同设备上加工。三种不同设备上加工。每吨甲、乙产品在不同设备上加工所需的台时,它们销售后所能获得的利润,每吨甲、乙产品在不同设备上加工所需的台时,它们销售后所能获得的利润,以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产计划,即甲计划
3、,即甲,乙两种产品各生产多少吨,可使该厂所获得利润达到最大。乙两种产品各生产多少吨,可使该厂所获得利润达到最大。1对偶线性规划对偶线性规划设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44 48 8 3636404076 76 利润(元利润(元/吨)吨)32 32 30 30 3第3页,共60页,编辑于2022年,星期六 假设计划期内甲乙两种产品各生产假设计划期内甲乙两种产品各生产 吨,吨,设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44
4、 48 8 3636404076 76 利润(元利润(元/吨)吨)32 32 30 30 用图解法或单纯形法可求得最优解用图解法或单纯形法可求得最优解 (元元)即在计划期内甲产品生产即在计划期内甲产品生产 吨,乙产品生产吨,乙产品生产8 8吨,可以使总利润达吨,可以使总利润达到最大,为到最大,为 元元。4第4页,共60页,编辑于2022年,星期六 现在从另一个角度来考虑该工厂的生产问题现在从另一个角度来考虑该工厂的生产问题:假设该厂的决策者打算不再自己生产甲假设该厂的决策者打算不再自己生产甲,乙产品,而是把各种设备乙产品,而是把各种设备的有限台时数租让给其他工厂使用,这时工厂的决策者应该如何确
5、定各的有限台时数租让给其他工厂使用,这时工厂的决策者应该如何确定各种设备的租价。种设备的租价。设设 分别为设备分别为设备A A,B B,C C每台时的租价,每台时的租价,约束条件:约束条件:把设备租出去所获得的租金不应低于利用这些设备自把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润行生产所获得的利润目标函数:所获租金总额尽量少目标函数:所获租金总额尽量少5第5页,共60页,编辑于2022年,星期六由此可得两个对称的线性规划:由此可得两个对称的线性规划:6第6页,共60页,编辑于2022年,星期六矩阵形式矩阵形式:7第7页,共60页,编辑于2022年,星期六可以得到另一个线性规
6、划可以得到另一个线性规划:称之为原线性规划问题的对偶问题称之为原线性规划问题的对偶问题,n对偶线性规划对偶线性规划考虑如下具有不等式约束的线性规划问题考虑如下具有不等式约束的线性规划问题8第8页,共60页,编辑于2022年,星期六9第9页,共60页,编辑于2022年,星期六10第10页,共60页,编辑于2022年,星期六11第11页,共60页,编辑于2022年,星期六若令若令线性规划标准型线性规划标准型的对偶规划为:的对偶规划为:n线性规划问题标准型的对偶问题线性规划问题标准型的对偶问题考虑一个标准形式的线性规划问题考虑一个标准形式的线性规划问题 由于任何一个等式约束都可以用两个不等式约束等价
7、地表示,所以由于任何一个等式约束都可以用两个不等式约束等价地表示,所以标准形线性规划问题可等价表示为:标准形线性规划问题可等价表示为:它的对偶规划为:它的对偶规划为:12第12页,共60页,编辑于2022年,星期六n对偶线性规划的求法对偶线性规划的求法从任何一个线性规划出发,都可以求出相应的对偶规划,在实际求解过程中,从任何一个线性规划出发,都可以求出相应的对偶规划,在实际求解过程中,通常不通过求标准型,而是利用如下反映原始问题与对偶问题对应关系的原始通常不通过求标准型,而是利用如下反映原始问题与对偶问题对应关系的原始对偶表:对偶表:目标函数变量系数目标函数变量系数约束条件右端项约束条件右端项
8、 约束条件右端项约束条件右端项目标函数变量系数目标函数变量系数 约束条件约束条件个数:个数:n n个个 变量变量个数:个数:n n个个 变量变量个数:个数:m m个个 约束条件约束条件个数:个数:m m个个 目标函数目标函数minW minW 目标函数目标函数maxZ maxZ 对偶问题(或原问题)对偶问题(或原问题)原问题(或对偶问题)原问题(或对偶问题)13第13页,共60页,编辑于2022年,星期六解:对偶规划:解:对偶规划:例例2 2 写出下列线性规划的对偶问题写出下列线性规划的对偶问题14第14页,共60页,编辑于2022年,星期六例例3 3 写出下列线性规划的对偶问题写出下列线性规
9、划的对偶问题解:上述问题的对偶规划:解:上述问题的对偶规划:15第15页,共60页,编辑于2022年,星期六本节讨论几条重要的对偶定理,这些定理揭示了原始问题的解和对偶本节讨论几条重要的对偶定理,这些定理揭示了原始问题的解和对偶问题的解之间的基本关系。问题的解之间的基本关系。定理定理1 1:(:(对合性对合性)对偶问题的对偶是原问题。)对偶问题的对偶是原问题。证明:设原问题为对偶问题为证明:设原问题为对偶问题为改写对偶问题为对偶问题的对偶为改写对偶问题为对偶问题的对偶为2对偶定理对偶定理16第16页,共60页,编辑于2022年,星期六 定理定理2 2:弱对偶定理弱对偶定理 若是原(极小化)问题
10、的可行解,是对偶(极大化)问题的可行解,若是原(极小化)问题的可行解,是对偶(极大化)问题的可行解,那么那么 证明:因为是对偶问题的可行解,所以满足约束条件证明:因为是对偶问题的可行解,所以满足约束条件 又因为是原问题的可行解,可得,又因为是原问题的可行解,可得,,所以所以 。注:原(极小化)问题的最优目标函数值以对偶问题任一可注:原(极小化)问题的最优目标函数值以对偶问题任一可行解的目标函数值为下界。行解的目标函数值为下界。对偶(极大化)问题的最优目标函数值以原问题任一可行解对偶(极大化)问题的最优目标函数值以原问题任一可行解的目标函数值为上界。的目标函数值为上界。推论推论1 1:如果原问题
11、没有下界(即如果原问题没有下界(即minZminZ),则对偶问题),则对偶问题不可行。不可行。如果对偶问题没有上界(即如果对偶问题没有上界(即maxWmaxW),则原问题不可行。),则原问题不可行。若原问题与对偶问题之一无界,则另一个无可行解。若原问题与对偶问题之一无界,则另一个无可行解。17第17页,共60页,编辑于2022年,星期六证明:由弱对偶定理,对于原始问题的证明:由弱对偶定理,对于原始问题的所有可行解所有可行解,都有,都有 因此是原问题的因此是原问题的最优解最优解。同理,对于对偶问题的同理,对于对偶问题的所有可行解所有可行解 ,都有,都有 所以所以 是对偶问题的是对偶问题的最优解最
12、优解。推论推论2 2:最优性定理最优性定理若若是是原原问问题题的的可可行行解解,是是对对偶偶问问题题的的可可行行解解,而而且两者的目标函数值相等,即,则和且两者的目标函数值相等,即,则和分别是原问题和对偶问题的最优解。分别是原问题和对偶问题的最优解。18第18页,共60页,编辑于2022年,星期六证明:设是原问题证明:设是原问题(min)(min)的最优解,则对应的基必有的最优解,则对应的基必有。若定义,则若定义,则 ,因此为对偶问题的可行解,而且因此为对偶问题的可行解,而且 ,由最优性,由最优性定理,是对偶问题的最优解。定理,是对偶问题的最优解。定理定理3:3:强对偶定理强对偶定理 如果原问
13、题(如果原问题(min)min)与对偶问题与对偶问题(max)(max)之一有最优解,那么之一有最优解,那么另一个也有最优解,而且目标函数值另一个也有最优解,而且目标函数值相等相等。19第19页,共60页,编辑于2022年,星期六证证明明:设设满满足足原原问问题题(min)(min)的的最最优优性性条条件件,则则对对应应的的基基必有必有。若定义若定义 ,则,则 ,因此为对偶问题的基本可行解。因此为对偶问题的基本可行解。定理定理4 4:设满足原问题设满足原问题(min)的的最优性条件最优性条件的一个的一个基本解基本解,则,则其对应的线性规划问题其对应的线性规划问题(min)(min)的的检验数检
14、验数对应对应对偶问题对偶问题的一个的一个基本可基本可行解行解。20第20页,共60页,编辑于2022年,星期六原问题与对偶问题可能出现的情况(1)两者都有最优解,且最优值相等;(2)一个有可行解,但无界,则另一个无可行解;(3)两者都无可行解。21第21页,共60页,编辑于2022年,星期六定理定理5 5:互补松弛定理互补松弛定理如果如果 分别是原问题分别是原问题(min)(min)和对偶问题(和对偶问题(max)max)的可行解,那的可行解,那么么 和和 为最优解的充要条件是为最优解的充要条件是 通常称通常称 为互补松弛条件。为互补松弛条件。证明:充分性证明:充分性必要性必要性22第22页,
15、共60页,编辑于2022年,星期六例例5 5、已知线性规划问题、已知线性规划问题:其对偶问题的最优解。其对偶问题的最优解。试用试用互补松弛定理互补松弛定理找出原问题的最优解。找出原问题的最优解。解:原问题的对偶问题为:解:原问题的对偶问题为:由对偶问题最优解可知,由对偶问题最优解可知,由互补松弛定理,由互补松弛定理,解方程组解方程组 所以原问题最优解所以原问题最优解23第23页,共60页,编辑于2022年,星期六 假设计划期内甲乙两种产品各生产假设计划期内甲乙两种产品各生产 吨,吨,设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 5
16、9 9 4 44 48 8 3636404076 76 利润(元利润(元/吨)吨)32 32 30 30 用图解法或单纯形法可求得最优解用图解法或单纯形法可求得最优解 (元元)即在计划期内甲产品生产即在计划期内甲产品生产 吨,乙产品生产吨,乙产品生产8 8吨,可以使总利润达吨,可以使总利润达到最大,为到最大,为 元元。例:例:对偶最优解的经济解释对偶最优解的经济解释影子价格影子价格 24第24页,共60页,编辑于2022年,星期六25第25页,共60页,编辑于2022年,星期六由由强强对对偶偶定定理理可可知知,如如果果原原问问题题有有最最优优解解,那那么么对对偶偶问题也有最优解,而且它们的目标
17、函数值相等,即有:问题也有最优解,而且它们的目标函数值相等,即有:其其中中是是线线性性规规划划原原问问题题约约束束条条件件的的右右端端数据向量,它代表各种资源的拥有量。数据向量,它代表各种资源的拥有量。为为对对偶偶问问题题最最优优解解,它它代代表表在在资资源源最最优优利利用用条条件件下下对对各各种种单单位位资资源源的的估估价价,这这种种估估计计不不是是资资源源的的市市场场价价格格,而而是是根根据据资资源源在在生生产产中中所所作作出出的的贡贡献献(如如创创造造利利润润,产产值值等等)而而作作出出估估价价,为为区区别别起起见见,称称之之为为影影子子价价格格(shadow(shadow price)
18、price)。26第26页,共60页,编辑于2022年,星期六影影子子价价格格的的大大小小客客观观地地反反映映了了各各种种不不同同资资源源在在系系统统内内的的稀稀缺缺程程度度。如如果果第第i i种种资资源源供供大大于于求求,即即在在达达到到最最优优解解时时,该该种种资资源源没没有有用用完完,或或松松弛弛变变量量,由由互互补补松松弛弛定定理理,在在对对偶偶最最优优解解中中,第第i i种种资资源源的的影影子子价价格格。反反之之如如果果第第i i种种资资源源的的影影子子价价格格,那那么么由由互互补补松松弛弛定定理理,原原问问题题的的第第i i个个约约束束为为严严格格等等式式,即即,这这表表明明第第i
19、 i种种资源已经用完资源已经用完,成为稀缺资源。,成为稀缺资源。资资源源的的影影子子价价格格同同时时也也是是一一种种机机会会成成本本,在在市市场场经经济济的的条条件件下下,当当某某种种资资源源的的市市场场价价格格低低于于影影子子价价格格时时,企企业业应应买买进进这这种种资资源源用用于于扩扩大大生生产产;相相反反当当某某种种资资源源的的市市场场价价格格高高于于影影子子价价格格时时,企企业业应应卖卖出出这这种种资资源源。随随着着资资源源的的买买进进卖卖出出,企企业业资资源源的的影影子子价价格格也也将将随随之之发发生生变变化化,一一直直到到影影子子价价格格与与市市场场价格保持同等水平价格保持同等水平
20、时,才处于时,才处于平衡状态平衡状态。27第27页,共60页,编辑于2022年,星期六设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44 48 8 3636404076 76 利润(元利润(元/吨)吨)32 32 30 30 例:例:对偶最优解对偶最优解其中为其中为设备设备A A的影子价格的影子价格,在资源最优利用的条件下,设备在资源最优利用的条件下,设备A A每每增加增加一个单位台时一个单位台时,可以使,可以使总利润增加总利润增加元。元。若设备可供台时数,则若设备可供台时数,则28第28页,共60页,编辑于2022
21、年,星期六3对偶单纯形法对偶单纯形法单单纯纯形形法法是是以以保保持持原原问问题题可可行行为为条条件件,即即不不论论进进行行怎怎样样的的基基变换,常数列必须保持非负。变换,常数列必须保持非负。利利用用对对偶偶问问题题的的对对称称性性,我我们们从从另另一一个个角角度度来来考考虑虑求求解解原原问问题题最最优优解解的的方方法法,这这种种方方法法以以保保持持对对偶偶问问题题可可行行为为条条件件,即即不不论论进进行行何何种种基基变变换换,必必须须保保持持所所有有的的检检验验数数非非负负,同同时时取取消消原原问问题题必必须须可可行行的的要要求求,即即取取消消常常数数列列的的非非负负限限制制,通通过过基基变变
22、换换使使原原问问题题在在非非可可行行解解的的基基础础上上逐逐步步转转换换成成基基本本可可行行解解,一一旦旦原原问问题题的的基基本本解解可可行行,则则该该基基本本可可行行解解也也就就是是最最优优解解,这这就就是是对对偶偶单单纯纯形形法法的基本思想。的基本思想。单纯形法:单纯形法:可行性可行性最优性最优性对偶单纯形法:对偶单纯形法:最优性最优性可行性可行性29第29页,共60页,编辑于2022年,星期六例例6求解下列线性规划min z=5x1+2x2+6x32x1+4x2+8x3 244x1+x2+4x38x1、x2,x30解解min z=5x1+2x2+6x32x1+4x2+8x3-x4 =24
23、4x1+x2+4x3 -x5=8x1、x2,x3,x4,x50min z=5x1+2x2+6x32x1 4x28x3+x4 =244x1 x2 4x3 +x5=8x1、x2,x3,x4,x5030第30页,共60页,编辑于2022年,星期六Cj52600bCBXBx1x2x3x4x50 x4-2-4-810-240 x5-4-1-401-85260005/-22/-46/-80031第31页,共60页,编辑于2022年,星期六对偶单纯形法基变换的次序和一般单纯形法不同:对偶单纯形法基变换的次序和一般单纯形法不同:一一般般单单纯纯形形法法首首先先由由最最大大减减少少原原则则确确定定换换入入变变量
24、量,然然而而用最小比值原则确定用最小比值原则确定换出变量换出变量 。对对偶偶单单纯纯形形法法则则是是先先将将具具有有负负分分量量的的基基变变量量 取取出出,作作为为换换出出变变量量,然然后后确确定定某某个个非非基基变变量量作作为为换换入入变变量量。其其变变换换目目的的是是在在保保持持对对偶偶问问题题可可行行性性的的前前提提下下,使使原原问问题题的的基基本本解解向可行解靠拢。向可行解靠拢。32第32页,共60页,编辑于2022年,星期六对偶单纯形法对偶单纯形法的计算步骤如下:的计算步骤如下:(4 4)以以 为为主主元元进进行行旋旋转转变变换换,得得新新的的单单纯纯形形表表,返返回(回(2 2)。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 对偶 规划 灵敏度 分析 PPT 讲稿
限制150内