线性规划的对偶和灵敏分析.pptx

《线性规划的对偶和灵敏分析.pptx》由会员分享，可在线阅读，更多相关《线性规划的对偶和灵敏分析.pptx（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1线性规划的对偶和灵敏分析线性规划的对偶和灵敏分析当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值相等，即有 Zmax=CX*=2x*1+3x*2 =Wmin=y*b=8y*1+16y*2+12y*3=14 其中X*是原问题的最优解，y*是对偶问题最优解。第1页/共28页通过上面的例子可以看出：yi*的值表示对第i种资源的估价，它是针对具体问题而存在的一种资源的特殊价格，称为“影子价格影子价格”。cj23000CBXBbx1x2x3x4x52x141001/40-0 x5400-21/21-3x22011/2-1/80-cj-zj00-3/2-1/80第2页/共28页即有

2、 X*=(x1,x2)=(4,2)，Y*=(y1,y2,y3)=(3/2,1/8,0)若原材料供应量能增加一个单位，即右端常数向量b=(b1,b2,b3)T=(8,16,12)T中的b1从8个单位增加到9个单位，则目标函数值的变化量为（9y*1+16y*2+12y*3)-(8y*1+16y*2+12y*3)=y*1=3/2 第3页/共28页说明目标函数值的增加一个单位，是因为放宽一个约束条件所产生的附加贡献。就是说，影子价格确定了为得到一个附加单位的约束因素所应花费的成本上限。所所以以，yi*的的经经济济意意义义是是在在其其他他条条件件不不变变的的情情况况下下，单单位位资资源源变变化化所所引引

3、起起的的目目标标函函数数最最优优值的变化。值的变化。第4页/共28页0123456789x1 54321x2（8，0）C=6（0，4）C=0Q2（4，2）Q2（4,2.5）Z=2*4+3*2=14Z=2*4+3*2.5=15.5Q2”（4.25,1.875）Z=2*4.25+3*1.875=14.125Q2(1.5，3.25)Z=2*1.5+3*3.25=12.75第5页/共28页u影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用

4、于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。u影子价格表明资源增加对总效益产生的影响 如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。第6页/共28页3.4 对偶单纯形法对偶单纯形法 一、什么是对偶单纯形法？一、什么是对偶单纯形法？对对偶偶单单纯纯形形法法是是应应用用对对偶偶原原理理求求解解原原始始线线性性规规划划的的一一种种方方法法在在原原始始问问题题的的单纯形表格上进行单纯形表格上进行对偶处理对偶处理。注意：注意：不是解对偶问题的单纯形法！不是解对偶问题的单纯形法！第7页/共28页

5、二、对偶单纯形法的基本思想二、对偶单纯形法的基本思想 1、对对“单单纯纯形形法法”求求解解过过程程认认识识的的提提升升 从更高的层次理解单纯形法从更高的层次理解单纯形法 初始可行基初始可行基（对应一个初始基可行解）（对应一个初始基可行解）迭迭代代另另一一个个可可行行基基（对对应应另另一一个个基基可行解），直至可行解），直至所有检验数所有检验数0为止为止。第8页/共28页 所有检验数所有检验数0意味着什么？意味着什么？第9页/共28页以以上上分分析析过过程程说说明明原原问问题题的的最最优优基基也也是是对对偶偶问问题题的的可可行行基基。换换言言之之，当当原原问问题题的的基基B既既是是原原问问题题的

6、的可可行行基基又又是是对对偶偶问问题题的的可可行行基基时时，B成成为原问题的最优基。为原问题的最优基。定定理理2-5 基基B是是线线性性规规划划的的最最优优基基的的充充要要条条件件是，是，B是是可行基可行基，同时也是，同时也是对偶可行基对偶可行基。第10页/共28页单单纯纯形形法法的的求求解解过过程程就就是是：在在保保持持原原始始可可行行的的前前提提下下(b列列保保持持0)，通通过过逐逐步步迭迭代代实实现现对偶可行对偶可行(检验数行检验数行0)。2、对偶单纯形法思想：对偶单纯形法思想：换换个个角角度度考考虑虑LP求求解解过过程程：保保持持对对偶偶可可行行的的前前提提下下（检检验验数数行行保保持

7、持0），通通过过逐逐步步迭迭代代实现原始可行实现原始可行（b列列0）。）。第11页/共28页原始单纯形法原始单纯形法对偶单纯形法对偶单纯形法前提条件前提条件所有所有0所有所有0最优性检验最优性检验所有所有0？所有所有0？换入、出基换入、出基变量的确定变量的确定先确定换入基变量先确定换入基变量后确定换出基变量后确定换出基变量先确定换出基变量先确定换出基变量后确定换入基变量后确定换入基变量原始基本解原始基本解的进化的进化可行可行最优最优（对偶问题的解从（对偶问题的解从不可行到可行）不可行到可行）非可行非可行可行（最优）可行（最优）（原问题的解从不可行（原问题的解从不可行到可行）到可行）对偶单纯形法

8、第12页/共28页3、计算思路（对于、计算思路（对于MAX问题）问题）：建立初始单纯形表，计算检验数行。建立初始单纯形表，计算检验数行。b列列0已得最优解已得最优解至少一个元素至少一个元素0,转下步转下步检验数全部检验数全部0（非非基基变变量量检检验验数数0）第13页/共28页 基变换：基变换：先先确确定定换换出出变变量量解解答答列列中中的的负负元元素素对对应的基变量应的基变量出基出基，即，即相应的行相应的行为主元行为主元行。第14页/共28页然然后后确确定定换换入入变变量量原原则则是是：在在保保持持对对偶偶可行的前提可行的前提下，下，减少原始问题的不可行性减少原始问题的不可行性。如果如果(最

9、小比值原则最小比值原则),则选则选 为换入变量为换入变量,相相应的列为应的列为主元列主元列 ,主元行和主元列交叉处主元行和主元列交叉处的元素的元素 为主元素为主元素。若若 ,要计算最小要计算最小比值吗？为什么？比值吗？为什么？第15页/共28页 按按主主元元素素进进行行换换基基迭迭代代（旋旋转转运运算算、枢枢运运算算），将将主主元元素素变变成成1，主主元元列列变变成成单单位位向量向量，得到新的单纯形表。，得到新的单纯形表。循环以上步骤，直至求出最优解。循环以上步骤，直至求出最优解。第16页/共28页例例3.9 用对偶单纯形法求解用对偶单纯形法求解LP：化为标准型化为标准型 将两个等式约束两边分

10、别乘以将两个等式约束两边分别乘以-1，得，得第17页/共28页以此形式进行列表求解，满足对偶单纯形以此形式进行列表求解，满足对偶单纯形法的基本条件，具体如下：法的基本条件，具体如下：第18页/共28页Cj-2-3-5-600CBXBbx1x2x3x4x5x60 x5-2-1-2-3-1100 x6(-3)-21-1301-2-3-5-600（1）5第19页/共28页Cj-2-3-5-600CBXBbx1x2x3x4x5x60 x5(-1/2)0-5/2-5/2-5/21-1/22x13/21-1/2 1/2-3/20-1/20-4-4-90-1(8/5)8/518/52第20页/共28页Cj-

11、2-3-5-600CBXBbx1x2x3x4x5x63x2 1/50111-2/51/52x18/5101-1-1/5-2/5000-5-8/5-1/5因此，最优解为X*=(8/5,1/5,0,0,0,0)T，最优值*=21/5。第21页/共28页练习练习用对偶单纯形法求解用对偶单纯形法求解LP：化为化为标准型标准型 将三个等式约束两边分别乘以将三个等式约束两边分别乘以-1，然后，然后列表求解如下：列表求解如下：第22页/共28页-3/-1 -9/-1 -比 值 -3 -9 0 0 0 0 -Z -1 -1 1 0 0 -1 -4 0 1 0 -1 -7 0 0 1 -2 -3 -3 y3 y

12、4 y5 0 0 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB第23页/共28页 -6/-3 -3/-1 -比 值 0 -6 -3 0 0 6 -Z 1 1 -1 0 0 0 -3 -1 1 0 0 -6 -1 0 1 2 -1 -1 y1 y4 y5 -3 0 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB第24页/共28页 0 0 -1 -2 0 8 -Z 1 0 -4/3 1/3 0 0 1 1/3 -1/3 0 0 0 1 -2 1 5/3 1/3 1 y1 y2 y5 -3 -9 0 -3 -9 0 0 0

13、 y1 y2 y3 y4 y5 cj yj b XB CB最优解是最优解是Y*=Y*=（5/35/3，1/31/3，0 0，0 0，1 1）T T，目标函数最优值为目标函数最优值为WWminmin=-Z=-Zmaxmax=8=8 第25页/共28页（1）初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。（2）当变量多于约束条件时，用对偶单纯形法计算可以减少计算工作量。而对于变量较少，而约束条件很多的线性规划问题，可以首先将它变换成为对偶问题，然后用对偶单纯形法来求解。从以上求解过程中我们可以看到，对偶单纯形法有以下的优点：第26页/共28页 作业题：P97 6.(1),(3)第27页/共28页