对偶和灵敏度分析PPT讲稿.ppt
《对偶和灵敏度分析PPT讲稿.ppt》由会员分享,可在线阅读,更多相关《对偶和灵敏度分析PPT讲稿.ppt(105页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第1页,共105页,编辑于2022年,星期六第第三三章章 内容提要内容提要3.1 单纯形法的矩阵描述3.2 对偶问题的提出3.3 线性规划的对偶理论3.4 影子价格3.5 对偶单纯形法3.6 灵敏度分析第2页,共105页,编辑于2022年,星期六3.1 3.1 单纯形法的矩阵描述单纯形法的矩阵描述介绍用矩阵来描述单纯形法的计算过程,有助于加深对单纯形法的理解,和学习对偶理论。第3页,共105页,编辑于2022年,星期六设线性规划问题:Max z=CXAX=bX 0其中松驰变量 Xs=(xn+1,xn+2,xn+m)TI 是mm 阶单位矩阵化为标准型:Max z=CX+0Xs (3.1)AX+I
2、Xs=b (3.2)X 0,Xs 0 (3.3)第4页,共105页,编辑于2022年,星期六设B是一个可行基,则可将系数矩阵(A,I)分为两块(B,N),N 是非基变量的系数矩阵。对应于B的变量xB1,xB2,xBm 是基变量,用向量 XB=(xB1,xB2,xBm)T 表示其它为非基变量,则第5页,共105页,编辑于2022年,星期六同时将 C 也分为两块(CB,CN),则第6页,共105页,编辑于2022年,星期六这时可将(3.1),(3.2),(3.3)式改写为 Max z=CBXB+CNXN (3.4)BXB+NXN=b (3.5)XB 0,XN 0 (3.6)将(3.5)式移项后,得
3、到 BXB=b-NXN (3.7)给(3.7)式左乘B-1后,得到XB的表达式 XB=B-1 b-B-1 NXN (3.8)将(3.8)式代入目标函数,得 z=CB B-1 b+(CN-CBB-1 N)XN (3.9)第7页,共105页,编辑于2022年,星期六 XB=B-1 b-B-1 NXN (3.8)z=CB B-1 b+(CN-CBB-1 N)XN (3.9)令非基变量XN=0,得到一个基可行解则,目标函数值 z=CB B-1 b第8页,共105页,编辑于2022年,星期六 XB=B-1 b-B-1 NXN (3.8)z=CB B-1 b+(CN-CBB-1 N)XN (3.9)从上式
4、中可以看到:非基变量 XN 的系数CN-CBB-1 N 就是检验数,即N=CN-CBB-1 N 因为 XB 在式(2.9)中的系数是0,即CB-CBB-1 B=0 故包括基变量在内的所有检验数可用 C-CBB-1A0表示。松驰变量检验数为-CBB-1,故所有检验数可用 C-CBB-1A和-CBB-1,即 C-YA和-Y 表示。第9页,共105页,编辑于2022年,星期六将式(3.8)和(3.9)综合写成矩阵式如下:XB=B-1 b-B-1 NXN (3.8)z=CB B-1 b+(CN-CBB-1 N)XN (3.9)右端项RHS基变量非基变量XBXN1XsB-1bIB-1N1B-1-CBB-
5、1b0CN1-CBB-1N1-CBB-1在单纯形表中表示如下:第10页,共105页,编辑于2022年,星期六3.2 3.2 对偶问题的提出对偶问题的提出在第1章例1中讨论了工厂生产计划模型及其解法,现从另一个角度来讨论这个问题。假设该工厂的决策者决定不生产产品I,II,而将其所有资源出租或外售,这时工厂的决策者就要考虑给每种资源如何定价的问题。第11页,共105页,编辑于2022年,星期六某工厂在计划期内要安排生产I、II两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表所示:III合计设备128 台时原材料A4016 千克原材料B0412 千克该工厂每生产一件 I 可获得
6、2元,每生产一件产品II可获得3元。问应如何安排计划使该工厂获得最多?第12页,共105页,编辑于2022年,星期六其数学模型归结为:目标函数 Max z=2 x1+3 x2约束条件 x1+2 x28 4 x1 16 s.t.4 x2 12 x1,x20第13页,共105页,编辑于2022年,星期六设用 y1,y2,y3 分别表示出租单位设备台时的租金和出让单位原材料A,B的利润。若用一个单位设备台时和4个单位原材料A可以生产一件产品I可获得2元,那么生产每件产品I的设备台时和原材料出租和出让的所有收入不应低于生产一件产品I的利润,即 y1+4y22换一种思维的角度第14页,共105页,编辑于
7、2022年,星期六同理,将每生产每件产品II的设备台时和材料出租和出让的所有收入不应低于生产一件产品II的利润,即 2y1+4y33把工厂所有设备台时和资源都出租或出让,其收入为 w=8y1+16y2+12y3第15页,共105页,编辑于2022年,星期六从工厂的决策者来看,当然 w 越大越好,但从接受者来看他的支付越少越好。因此决策者只能在满足所有产品利润的条件下,使其总收入尽可能地小。即解如下线性规划问题 Min w=8y1+16y2+12y3 y1+4y2 2 2y1 +4y33 y1,y2,y3 0这个问题即为原问题的对偶问题。第16页,共105页,编辑于2022年,星期六矩阵形式的对
8、偶问题矩阵形式的对偶问题从前面知检验数C-CBB-1A和-CBB-1均非正时,线性规划问题达到最优解,即 C-YA0和-Y 0则Y 0,YA C对单纯形因子Y=CBB-1两边同乘b得Yb=CBB-1b=z因Y 的上界为无限大,所以只存在最小值。由此得另一个线性规划问题:Min w=Yb YA C Y 0此即原问题Max z=CX|AXb,X0的对偶问题第17页,共105页,编辑于2022年,星期六3.3 3.3 线性规划的对偶理论线性规划的对偶理论原问题与对偶问题的关系第18页,共105页,编辑于2022年,星期六3.3.1 3.3.1 原问题与对偶问题的关系原问题与对偶问题的关系左右不对称,
9、左右 右左 阅读p54-56原问题P(或对偶问题)对偶问题D(或原问题)目标函数 max z 目标函数 min w 变量 n 个 约束条件 n 个 变量0 约束条件 变量0 约束条件 变量无约束 约束条件=变量 m 个 约束条件 m 个 变量 0 约束条件 变量 0 约束条件 变量无约束 约束条件=约束条件右端项 目标函数变量的系数 约束条件右端项 目标函数变量的系数第19页,共105页,编辑于2022年,星期六例 写出下述线形规划问题的对偶问题Max Z=5x1+4x2+6x3 x1+2x2 2 x1 +x33-3x1+2x2+x3-5 x1-x2+x31x10;x20,;x3无约束minW
10、=2y1+3y2-5y3+y4 y1+y2-3y3+y45 2y1 +2y3-y44 y2+y3+y4=6y10,y2,y3 0,y4无约束第20页,共105页,编辑于2022年,星期六例 写出下述线形规划问题的对偶问题minZ=2x1+3x2-5x3+x4 x1+x2-3x3+x45 2x1 +2x3-x44 x2+x3+x46x10,x2,x30;x4无约束maxZ=5y1+4y2+6y3 y1+2y2 2 y1 +y33-3y1+2y2+y3-5 y1-y2+y3=1y10,y20,y3无约束第21页,共105页,编辑于2022年,星期六写出下列问题的对偶问题:写出下列问题的对偶问题:解
11、解:先将先将约束约束条件变形为条件变形为“”形式形式 第22页,共105页,编辑于2022年,星期六第23页,共105页,编辑于2022年,星期六再根据非对称形式的对应关系,直接写出对偶规划 第24页,共105页,编辑于2022年,星期六3.3.2 3.3.2 对偶问题的基本性质对偶问题的基本性质1.1.对称性对称性2.2.弱对偶性弱对偶性3.3.无界性无界性4.4.可行解是最优解时的性质可行解是最优解时的性质5.5.对偶定理对偶定理6.6.互补松驰性互补松驰性7.7.解的关系解的关系第25页,共105页,编辑于2022年,星期六1 1 对称性对称性 对偶问题的对偶是原问题。对偶问题的对偶是原
12、问题。对原问题:Max z=CXAXbX0对(1)式两边取负号有 -Min w=-Yb又因Min w=-Max(-w)故可得 Max(-w)=-Yb -YA-C Y0其对偶问题:Min w=Yb (1)YACY0它的对偶问题是:Min-w=-CX;-AX-b;X0又因Min w=-Max(w)故可得 Max w=Max z=CX AXb X0第26页,共105页,编辑于2022年,星期六2 2 弱对偶性弱对偶性若若 是原问题的可行解,是原问题的可行解,是对偶问题的可行解,则存在是对偶问题的可行解,则存在第27页,共105页,编辑于2022年,星期六3 3 无界性无界性若原问题若原问题(对偶问题
13、对偶问题)无界解,则对偶问题无界解,则对偶问题(原问题原问题)无可行解。无可行解。第28页,共105页,编辑于2022年,星期六4 4 可行解是最优解的性质可行解是最优解的性质若 是原问题的可行解,是对偶问题的可行解,则当 ,是最优解。第29页,共105页,编辑于2022年,星期六5 5 对偶定理对偶定理若原问题有最优解,那么对偶问题也有最优解;且目标函若原问题有最优解,那么对偶问题也有最优解;且目标函数值相等。数值相等。第30页,共105页,编辑于2022年,星期六试用对偶理论判断下面线性规划是否有最优解试用对偶理论判断下面线性规划是否有最优解 解解解解:此规划存在可行解此规划存在可行解 ,
14、其对偶规划为,其对偶规划为 第31页,共105页,编辑于2022年,星期六显然,对偶规划没有可行解,因此,原规划没有最优解。显然,对偶规划没有可行解,因此,原规划没有最优解。第32页,共105页,编辑于2022年,星期六推论推论 若原问题有一个对应于基若原问题有一个对应于基B B的最优解,那么此时的最优解,那么此时的单纯形乘子的单纯形乘子Y YC CB BB B-1-1是对偶问题的一个最优解是对偶问题的一个最优解第33页,共105页,编辑于2022年,星期六 maxZ=3x1+5 x2 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 例例Cj比值CBXBb检验数jx
15、1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9第34页,共105页,编辑于2022年,星期六Cj35000比值CBXBbx1x2x3x4x50 x340012/3-1/35x260101/203x14100-2/31/3检验数j-42000-1/2-1最终单纯型表最终单纯型表求其对偶问题的最优解?求其对偶问题的最优解?第35页,共105页,编辑于2022年,星期六求解下面线性规划问题,并根据最优单纯形表中的检验求解下面线性规划问题,并根据最优单纯形表中的检验数,给出其对偶问题的最优解。数,给出其对偶问题的最优解。解解
16、 引入松弛变量、将模型化为标准型,经求解后得引入松弛变量、将模型化为标准型,经求解后得到其最优单纯形表到其最优单纯形表 第36页,共105页,编辑于2022年,星期六c 4 3 7 0 0 cB xB B-1b x1 x2 x3 x4 x5 3 x2 25 -3/4 1 0 3/4 -1/2 7 x3 25 5/4 0 1 -1/4 1/2 Z 250 -10/4 0 0 -1/2 -2对偶规划的最优解为对偶规划的最优解为 :第37页,共105页,编辑于2022年,星期六6 6 互补松驰性互补松驰性 若若 X*X*和和 Y*Y*分别是原问题和对偶问题的可行解,那么它分别是原问题和对偶问题的可行
17、解,那么它们为最优解的充要条件是们为最优解的充要条件是 (C-Y*AC-Y*A)X X=0=0 和和Y Y(b-AX*b-AX*)=0)=0若由最优解得约束条件为绝对不等式,则对偶问题对若由最优解得约束条件为绝对不等式,则对偶问题对应变量为零。应变量为零。变量最优解值大于零,对偶问题对应约束条件取等号。变量最优解值大于零,对偶问题对应约束条件取等号。Key第38页,共105页,编辑于2022年,星期六例 已知线性规划问题Min z=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x5 4 2x1-x2+3x3+x4+x5 3 x1,x2,x3,x4,x5 0其对偶问题的最优
18、解为 y1=4/5,y2=3/5,试应用对偶理论求原问题的解。第39页,共105页,编辑于2022年,星期六将将 y1=4/5,y2=3/5的值代入,得知的值代入,得知 为严格不等式,于是由互补松驰为严格不等式,于是由互补松驰性,必有性,必有 x2=x3=x4=0 解:写出对偶问题:解:写出对偶问题:Max S=4y1+3y2 y1+2y2 2 y1-y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1,y2 0又因又因 y1,y2 0,故原问题的两个约束条件必为紧约束,即有,故原问题的两个约束条件必为紧约束,即有 x1+3x5=4 2x1+x5=3 解得解得 x1=x5=1
19、即即 X*=(1,0,0,0,1)T,Z*=5第40页,共105页,编辑于2022年,星期六7 7 解的关系解的关系则原问题单纯表的检验数行对应其对偶问题的一个基解。则原问题单纯表的检验数行对应其对偶问题的一个基解。Ys1 是对应原问题是对应原问题中基变量中基变量XB的剩余变量,的剩余变量,Ys2 是对应原问题中基变量是对应原问题中基变量XN 的剩余变量的剩余变量设原问题:设原问题:Max z=CXAX+Xs=bX,Xs0其对偶问题:其对偶问题:Min w=Yb YA-Ys=CY,Ys0XBXNXs0CN1-CBB-1N1-CBB-1Ys1-Ys2-Y第41页,共105页,编辑于2022年,星
20、期六B B-1-1在单纯表中的位置在单纯表中的位置可将可将(3.4),(3.5)式式 Max z=CBXB+CNXN (3.4)BXB+NXN=b (3.5)改写为改写为 -z+CB XB+CN1XN1+0Xs=0 BXB+NXN+IXs=b最后得最后得B-1即为初始基变量在最终单纯形表中的列向量组成。即为初始基变量在最终单纯形表中的列向量组成。第42页,共105页,编辑于2022年,星期六B-1初始基变量B-1为初始基变量在最终单纯形表中的列向量组成。第43页,共105页,编辑于2022年,星期六3.4 3.4 影子价格影子价格前面讲到,在单纯法的每一步迭代中,目标函数取值前面讲到,在单纯法
21、的每一步迭代中,目标函数取值 z z=C CB BB B-1-1b b 和检验数和检验数 C CN N-C-CB BB B-1-1N N中都有乘子中都有乘子 Y Y=C CB BB B-1-1那么那么Y Y 的经济意义是什么呢?的经济意义是什么呢?设设B B 是是max max z z=CX CX|AXAXb b,X X00的最优基,则的最优基,则 z*z*=C CB BB B-1-1b=Y*bb=Y*b两边对两边对b b求偏导有求偏导有 z*/z*/b b=C CB BB B-1-1=Y*=Y*从对偶问题来看,变量从对偶问题来看,变量 y yi i*的经济意义是在其它条件不变的的经济意义是在
22、其它条件不变的情况下,单位资源变化所引起的目标函数的最优值的变化。情况下,单位资源变化所引起的目标函数的最优值的变化。这种资源的单位改变量引起目标函数的价值改变量,称为该这种资源的单位改变量引起目标函数的价值改变量,称为该资源的影子价格。资源的影子价格。第44页,共105页,编辑于2022年,星期六影子价格的特征影子价格的特征影子价格的大小客观地反映了资源在系统内的稀缺程度。影子价格的大小客观地反映了资源在系统内的稀缺程度。根据互补松驰定理的条件,如果某一资源在系统内供大于求,其影根据互补松驰定理的条件,如果某一资源在系统内供大于求,其影子价格就为零。子价格就为零。即增加该资源的供应不会引起系
23、统目标的任何变化。即增加该资源的供应不会引起系统目标的任何变化。如果某一资源是稀缺资源(即相应约束条件的剩余变量为零)如果某一资源是稀缺资源(即相应约束条件的剩余变量为零),则影子价格必然大于零。,则影子价格必然大于零。影子价格越高,资源在系统中越稀缺。影子价格越高,资源在系统中越稀缺。第45页,共105页,编辑于2022年,星期六影子价格的特征影子价格的特征在完全市场经济条件下,当某种资源的市场价格低于影子价在完全市场经济条件下,当某种资源的市场价格低于影子价格时,企业应买进该资源用于扩大再生产;而当某种资源的格时,企业应买进该资源用于扩大再生产;而当某种资源的市场价格高于影子价格时,企业应
24、卖掉已有资源。市场价格高于影子价格时,企业应卖掉已有资源。影子价格是一种边际价值,与经济学所说的边际成本的概念影子价格是一种边际价值,与经济学所说的边际成本的概念相似,因而在经济管理中有重要的应用价值。相似,因而在经济管理中有重要的应用价值。影子价格是对系统资源的一种最优估价,只有当系统达到最影子价格是对系统资源的一种最优估价,只有当系统达到最优时,才能赋予该资源的这种价值,因此影子价格也称为最优时,才能赋予该资源的这种价值,因此影子价格也称为最优价格。优价格。影子价格的取值与系统状态有关。系统内部资源数量、技术影子价格的取值与系统状态有关。系统内部资源数量、技术系数和价格的任何变化,都会引起
25、影子价格的变化,影子价系数和价格的任何变化,都会引起影子价格的变化,影子价格是一种动态价格。格是一种动态价格。第46页,共105页,编辑于2022年,星期六事事实实上上,如如例例中中互互为为对对偶偶LPLP问问题题分分别别描描述述生生产产计计划划问问题题和和资资源源的定价问题,其数学模型分别是:的定价问题,其数学模型分别是:原问题原问题对偶问题对偶问题第47页,共105页,编辑于2022年,星期六 cj 4 3 0 0CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 Z36 0 0 -1/5 -6/5用单纯形法求得其最优表为:用单纯形法求得
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 对偶 灵敏度 分析 PPT 讲稿
限制150内