《规划数学对偶理论和灵敏度分析精选PPT.ppt》由会员分享,可在线阅读,更多相关《规划数学对偶理论和灵敏度分析精选PPT.ppt(40页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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 型变为型变为 mi
5、n 型型对应原问题每个约束行有一个对偶变量对应原问题每个约束行有一个对偶变量 yi,i=1,2,m对偶问题约束为对偶问题约束为 型,有型,有 n 行行原问题的价值系数原问题的价值系数 C 变换为对偶问题的右端项变换为对偶问题的右端项原问题的右端项原问题的右端项 b 变换为对偶问题的价值系数变换为对偶问题的价值系数原问题的技术系数矩阵原问题的技术系数矩阵 A 转置后成为对偶问题的技术系数矩转置后成为对偶问题的技术系数矩阵阵原问题与对偶问题互为对偶原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义对偶问题还有很多理论和实际应用的意义
6、第10页,讲稿共40张,创作于星期三原问题与对偶问题的结构关系原问题与对偶问题中的目标函数的优化方向相反(前者为极大,原问题与对偶问题中的目标函数的优化方向相反(前者为极大,后者为极小)后者为极小)原问题的每个约束条件对应于对偶问题的一个决策变量,且约原问题的每个约束条件对应于对偶问题的一个决策变量,且约束条件的资源系数(右端的常数项)为相应决策变量的价值系束条件的资源系数(右端的常数项)为相应决策变量的价值系数数原问题的每个决策变量对应于对偶问题的一个约束条件,原问题的每个决策变量对应于对偶问题的一个约束条件,且决策变量的价值系数为相应约束条件的右端常数项且决策变量的价值系数为相应约束条件的
7、右端常数项对偶问题中的系数矩阵为原问题中的系数矩阵的转置对偶问题中的系数矩阵为原问题中的系数矩阵的转置原问题约束条件中的小于等于符号对应于对偶问题中的对偶变量原问题约束条件中的小于等于符号对应于对偶问题中的对偶变量取非负约束,原问题中决策的对偶问题非负约束在对偶问题中体取非负约束,原问题中决策的对偶问题非负约束在对偶问题中体现为相应的约束条件取大于等于符号现为相应的约束条件取大于等于符号第11页,讲稿共40张,创作于星期三 非标准型的对偶变换第12页,讲稿共40张,创作于星期三 对偶变换的规则第13页,讲稿共40张,创作于星期三max=5y1+4y2+6y3y1+2y2y1+y3-3y1+2y
8、2+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无约束第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,结论是显然的。,结论是显
11、然的。若是原问题的可行解,是对偶问题可行解,当若是原问题的可行解,是对偶问题可行解,当 ,分别是相应问题的最优解分别是相应问题的最优解是使目标函数取最小值的解,因此是最优解是使目标函数取最小值的解,因此是最优解 可行解是最优解的性质可行解是最优解的性质(最优性准则定理最优性准则定理)第18页,讲稿共40张,创作于星期三(4)对偶定理 若原问题和对偶问题两者皆可行若原问题和对偶问题两者皆可行,则两者均则两者均有最优解有最优解,且此时目标函数值相等且此时目标函数值相等.第第1部分部分:证明两者均有最优解证明两者均有最优解证明分两部分证明分两部分由于原问题和对偶问题均可行由于原问题和对偶问题均可行,
12、根据弱对根据弱对偶性偶性,可知两者均有界可知两者均有界,于是均有最优解于是均有最优解.第19页,讲稿共40张,创作于星期三第2部分:证明有相同的目标函数值 设设 为原问题的最优解为原问题的最优解它所对应的基矩阵是它所对应的基矩阵是B B,则其检验数满足则其检验数满足 C C C CB BB B 1 1A A 0 0 因此有对偶问题目标函数值因此有对偶问题目标函数值而原问题最优解的目标函数值为而原问题最优解的目标函数值为显然显然 为对偶问题的可行解。为对偶问题的可行解。证毕故由最优解准则定理可知故由最优解准则定理可知 为对偶问题的最优解为对偶问题的最优解.第20页,讲稿共40张,创作于星期三对偶
13、定理推论根据对偶定理第根据对偶定理第2部分的证明部分的证明,可以得出可以得出:若互为对偶的若互为对偶的线性规划问题中的任一个有最优解线性规划问题中的任一个有最优解,则另一个也有最优则另一个也有最优解解,且目标函数值相等且目标函数值相等.综上所述综上所述,一对对偶问题的解必然是下列三种情况之一对对偶问题的解必然是下列三种情况之一一:原问题和对偶问题都有最优解原问题和对偶问题都有最优解一个问题具有无界解一个问题具有无界解,另一个问题无可行解另一个问题无可行解原问题和对偶问题都无可行解原问题和对偶问题都无可行解第21页,讲稿共40张,创作于星期三 (5)互补松弛定理证:由定理所设,可知有 设设 ,分
14、别是原问题和对偶问题的可行解,分别是原问题和对偶问题的可行解,为为原问题的松弛变量的值,为对偶问题剩余变量的原问题的松弛变量的值,为对偶问题剩余变量的值。值。,分别是原问题和对偶问题最优解的充分分别是原问题和对偶问题最优解的充分必要条件是必要条件是分别以分别以 左乘左乘(1)(1)式,以式,以 右乘右乘(2)(2)式后,两式相减,得式后,两式相减,得 根据最优解判别定理,根据最优解判别定理,分别是原问题和对偶问题最优分别是原问题和对偶问题最优解。反之亦然。解。反之亦然。证毕。(1)(2)第22页,讲稿共40张,创作于星期三max z=CXs.t.AX+XS=bX,XS 0min w=Ybs.t
15、.AY-YS=CY,YS 0XYS=0YXS=0mn=YYSA-ICn=AXSIbnmmX原始问题和对偶问题变量、松弛变量的维数原始问题和对偶问题变量、松弛变量的维数第23页,讲稿共40张,创作于星期三原始问题和对偶问题最优解之间的互补松弛关系原始问题和对偶问题最优解之间的互补松弛关系maxz=CX s.t.AX+XS=b X,XS0min w=bYs.t.AY-YS=C Y,YS0maxz=CXs.t.AXb X 0min w=bYs.t.AYC Y0对偶引进松弛变量引进松弛变量XYS=0 YXS=0互补松弛关系互补松弛关系互补松弛关系互补松弛关系X,XsY,Ys第24页,讲稿共40张,创作
16、于星期三y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中,其中一个大于0,另一个一定等于0原始问题的变量原始问题的变量对偶问题的松弛变量对偶问题的松弛变量第25页,讲稿共40张,创作于星期三(6)原问题单纯形表检验数行与对偶问题解的关系原问题单纯形表检验数的相反数对应对偶原问题单纯形表检验数的相反数对应对偶问题的一个基解问题的一个基解.显然显然,原问题最终单纯形原问题最终单纯形表检验数的相反数对应对偶问题的
17、一个基表检验数的相反数对应对偶问题的一个基可行解可行解0第26页,讲稿共40张,创作于星期三证:标准化后的原问题和对偶问题的表达式为:若若B B是是A A中的一个基,中的一个基,A=A=(B B,N N)第27页,讲稿共40张,创作于星期三原问题解为XB=B-1b,N=CN-CBB-1N,Z=CBB-1b对偶问题的约束条件:对偶问题的约束条件:0检验数:检验数:B=CB-CBB-1B=0,N=CN-CBB-1N,S=CBB-1原问题单纯形表检验数行与对偶问题解的关系原问题单纯形表检验数行与对偶问题解的关系第28页,讲稿共40张,创作于星期三结论:v单纯形表中的检验数行和对偶问题的解单纯形表中的
18、检验数行和对偶问题的解仅差一个符号vyi等于原问题的第等于原问题的第i个方程中的松弛变量所对应的检验个方程中的松弛变量所对应的检验 数的负数数的负数v单纯形法迭代时,原问题解为基可行解,相应的检验数单纯形法迭代时,原问题解为基可行解,相应的检验数对应对偶问题的一个解,在原问题没有得到最优解之前,对应对偶问题的一个解,在原问题没有得到最优解之前,对偶问题的解为非可行解对偶问题的解为非可行解基可行解基可行解非可行解基可行解目标函数对偶问题原问题无可行解无界解第29页,讲稿共40张,创作于星期三例4试用对偶理论证明该线性规试用对偶理论证明该线性规划问题无最优解。划问题无最优解。证:证:该问题存在可行
19、解,该问题存在可行解,X=(0,0,0););对偶问题为:对偶问题为:由第一个约束条件可知对偶由第一个约束条件可知对偶问题无可行解,因此,原问问题无可行解,因此,原问题有可行解,无最优解。题有可行解,无最优解。第30页,讲稿共40张,创作于星期三例5:试用对偶理论找出原问题的最优解。试用对偶理论找出原问题的最优解。解:解:原问题的对偶问题为:原问题的对偶问题为:已知其对偶问题的最优解为:已知其对偶问题的最优解为:第31页,讲稿共40张,创作于星期三代入对偶问题的约束条件,代入对偶问题的约束条件,得得2,3,4式为严格不等式,由互补松弛性得式为严格不等式,由互补松弛性得因因原问题的约束条件应取等
20、式为:原问题的约束条件应取等式为:求解后得到求解后得到原问题的最优解为原问题的最优解为:第32页,讲稿共40张,创作于星期三原问题的最优解为原问题的最优解为:Z*=CBB-1b=CX*=Y*b对偶问题的经济解释对偶问题的经济解释-影子价格影子价格z=CX=Cz=CX=CB BB B-1-1b b+N NX XN N=C=CB BB B-1-1b bN N=C CN N-C-CB BB B-1-1N NY=CY=CB BB B-1-1为单纯形乘子为单纯形乘子当当b为变量的情况下为变量的情况下,当当bi发生变化发生变化:yi的经济意义是:在其它条件不变的情况下,单位资源变化所引起的目标函数的最优值
21、的变化.yi是bi的一种估价,估价是有条件的替代方案.第33页,讲稿共40张,创作于星期三1.5.3 对偶单纯形法对偶单纯形法单纯形法单纯形法原问题基可行解,对偶问题基解(非可行解)原问题基可行解,对偶问题基可行解.原问题基可行解,对偶问题基可行解原问题基解,对偶问题基可行解.对偶单纯形法对偶单纯形法第34页,讲稿共40张,创作于星期三第35页,讲稿共40张,创作于星期三例例1-21 1-21 用对偶单纯形法求解下述LP问题解:引入松弛变量转换成如下的标准形式:第36页,讲稿共40张,创作于星期三第37页,讲稿共40张,创作于星期三第38页,讲稿共40张,创作于星期三第39页,讲稿共40张,创作于星期三感感谢谢大大家家观观看看第40页,讲稿共40张,创作于星期三