线性规划的对偶和灵敏分析PPT学习教案

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/80i第2页/共28页即有 X*=

2、(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页 0 1 2 3 4 5 6 7 8 9 x1 5 4 3 2 1x2（8，0）C=6（0，4）C=012121212m ax23x +2x84x16. .4x12 x ,x0Zxxs tQ2（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 对偶单纯形法对偶单纯形法 一、什么是对偶单纯形法？一、什么是对偶单纯形法？ 对偶单纯形法对偶单纯形法是应用是应用对偶原理对偶原理求解原求解原始线性规划的一种方法始线性规划的一种方法在原始问题的在原始问题的单纯形

5、表格上进行单纯形表格上进行对偶处理对偶处理。 注意：注意：不是解对偶问题的单纯形法！不是解对偶问题的单纯形法！第7页/共28页 二、对偶单纯形法的基本思想二、对偶单纯形法的基本思想 1、对、对“单纯形法单纯形法”求解过程认识的提求解过程认识的提升升 从更高的层次理解单纯形法从更高的层次理解单纯形法 初始可行基初始可行基（对应一个初始基可行解）（对应一个初始基可行解） 迭代迭代另一个可行基另一个可行基（对应另一个基（对应另一个基可行解），直至可行解），直至所有检验数所有检验数0为止为止。第8页/共28页 所有检验数所有检验数0意味着什么？意味着什么？ -1BCC B A0()()BN-1BC B

6、CB0CNNB-1-1BBCCC B BB0CN00NYAC第9页/共28页以上分析过程说明以上分析过程说明原问题的最优基也是对偶问原问题的最优基也是对偶问题的可行基题的可行基。换言之，当原问题的基。换言之，当原问题的基B既是原既是原问题的可行基又是对偶问题的可行基时，问题的可行基又是对偶问题的可行基时，B成成为原问题的最优基。为原问题的最优基。定理定理2-5 基基B是线性规划的是线性规划的最优基最优基的充要条件的充要条件是，是，B是是可行基可行基，同时也是，同时也是对偶可行基对偶可行基。第10页/共28页单纯形法的求解过程就是：在保持原始可行单纯形法的求解过程就是：在保持原始可行的前提下的前

7、提下(b列保持列保持0)，通过逐步迭代实现，通过逐步迭代实现对偶可行对偶可行(检验数行检验数行0)。 2、 对偶单纯形法思想：对偶单纯形法思想： 换个角度考虑换个角度考虑LP求解过程求解过程：保持保持对偶可对偶可行行的前提下（的前提下（检验数行保持检验数行保持0） ，通过逐，通过逐步迭代步迭代实现原始可行实现原始可行（b列列0）。）。 第11页/共28页原始单纯形法原始单纯形法对偶单纯形法对偶单纯形法前提条件前提条件所有所有 0所有所有 0最优性检验最优性检验所有所有 0？所有所有 0？换入、出基换入、出基变量的确定变量的确定先确定换入基变量先确定换入基变量后确定换出基变量后确定换出基变量先确

8、定换出基变量先确定换出基变量后确定换入基变量后确定换入基变量原始基本解原始基本解的进化的进化可行可行最优最优（对偶问题的解从（对偶问题的解从不可行到可行）不可行到可行）非可行非可行可行（最优）可行（最优）（原问题的解从不可行（原问题的解从不可行到可行）到可行）ibj对偶单纯形法ibj第12页/共28页3、计算思路（对于、计算思路（对于MAX问题）问题）： 建立初始单纯形表，计算检验数行。建立初始单纯形表，计算检验数行。b列列0已得最优解已得最优解至少一个元素至少一个元素0,转下步转下步检验数全部检验数全部0（ 非 基 变 量 检（ 非 基 变 量 检验数验数0）第13页/共28页 基变换：基变

9、换： 先确定换出变量先确定换出变量解答列中的负元素对解答列中的负元素对应的基变量应的基变量出基出基，即，即出基，则选lliiixbBbBbB,)(0)()(min111相应的行相应的行为主元行为主元行。第14页/共28页然后然后确定换入变量确定换入变量原则原则是：在是：在保持对偶保持对偶可行的前提可行的前提下，下，减少原始问题的不可行性减少原始问题的不可行性。如果如果 0minlkkkljljjjjazcaazc(最小比值原则最小比值原则),则选则选 为换入变量为换入变量 , 相相应的列为应的列为主元列主元列 , 主元行和主元列交叉处主元行和主元列交叉处的元素的元素 为主元素为主元素。kxlk

10、a若若 ,要计算最小要计算最小比值吗？为什么？比值吗？为什么？0lja 第15页/共28页 按主元素进行换基迭代按主元素进行换基迭代（旋转运算、（旋转运算、枢运算）枢运算），将主元素变成将主元素变成1，主元列变成单位，主元列变成单位向量向量，得到新的单纯形表。，得到新的单纯形表。 循环以上步骤，直至求出最优解。循环以上步骤，直至求出最优解。第16页/共28页例例3.9 用对偶单纯形法求解用对偶单纯形法求解LP： 化为标准型化为标准型 将两个等式约束两边分别乘以将两个等式约束两边分别乘以-1，得，得0,332232. .653min4321432143214321xxxxxxxxxxxxtsxx

11、xxw0,332232. .653max65432164321543214321xxxxxxxxxxxxxxxxtsxxxxw第17页/共28页以此形式进行列表求解，满足对偶单纯形以此形式进行列表求解，满足对偶单纯形法的基本条件，具体如下：法的基本条件，具体如下：0,332232. .6532max62164321543214321xxxxxxxxxxxxxtsxxxxw第18页/共28页Cj -2 -3 -5 -6 0 0 CB XBb x1x2x3 x4 x5 x60 x5 -2 -1 -2 -3 -1 1 0 0 x6 (-3) -2 1 -1 3 0 1 -2 -3 -5 -6 0 0

12、 （1） 5j第19页/共28页Cj -2 -3 -5 -6 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 x5 (-1/2) 0 -5/2 -5/2 -5/2 1 -1/2 2 x1 3/2 1 -1/2 1/2 -3/2 0 -1/2 0 -4 -4 -9 0 -1 (8/5) 8/5 18/5 2j第20页/共28页Cj -2 -3 -5 -6 0 0 CB XB b x1 x2 x3 x4 x5 x6 3 x2 1/5 0 1 1 1 -2/5 1/5 2 x1 8/5 1 0 1 -1 -1/5 -2/5 0 0 0 -5 -8/5 -1/5 j因此，最优解为X*=

13、(8/5,1/5,0,0,0,0)T，最优值*=21/5。第21页/共28页练习练习用对偶单纯形法求解用对偶单纯形法求解LP： 0, 037342. .932121212121yyyyyyyyt syyMinW 0,37342. .935152142132121yyyyyyyyyyyt syyMaxZ将三个等式约束两边分别乘以将三个等式约束两边分别乘以-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 y4 y

14、5 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 y1 y2 y3 y4 y5