第三章对偶理论与灵敏度分析课件.ppt

第三章 对偶理论与灵敏度分析,1 单纯形法的矩阵描述2 改进单纯形法3 对偶问题的提出4 线性规划的对偶理论5 对偶问题的经济解释影子价格6 对偶单纯形法7 灵敏度分析,第三章 对偶理论与灵敏度分析1 单纯形法的矩阵描述,1 单纯形法的矩阵描述,设线性规划问题,设B是一个可行基，令（A，I）=（B，N，I），则：,1 单纯形法的矩阵描述设线性规划问题设B是一个可行基，令,1.检验数的矩阵描述：B=CB-CBB-1B=0 N=CN-CBB-1N S=-CBB-1,=min(B-1b)i/(B-1Pk)i|(B-1Pk)i0=(B-1b)l/(B-1Pk)l,3.单纯形表的矩阵描述：,=C-CBB-1A,2.的矩阵描述：,1.检验数的矩阵描述：=min(B-1b)i/(B-,2 改进单纯形法,用改进单纯形法求解线性规划问题的计算步骤：1.确定初始可行基B1。求出B1-1；2.计算非基变量的检验数N。若N 0已求的最优解，停止计算,否则进行下一步；3.确定换入变量 xk；4.计算B1-1b，B1-1 Pk及；若 0那么无最优解，停止计算，否则进行下一步；5.确定换出变量 xl;6.计算B2-1；7.重复27步。,2 改进单纯形法用改进单纯形法求解线性规划问题的计算步骤,例：用改进单纯形法求解,例：用改进单纯形法求解,解：,解：,3 对偶问题的提出,例：,x1,min,x2,x1,x2,y1,y2,y3,3 对偶问题的提出 例：设备128 台,当该问题达到最优时有：,z的上界为无限大，所以只存在最小值。于是得到另一个线性规划问题,对线性规划问题,对偶问题,原问题,当该问题达到最优时有：z的上界为无限大，所以只,4 线性规划的对偶理论,4.1 原问题与对偶问题的关系,4 线性规划的对偶理论 4.1 原问题与对偶,原问题（对偶问题）,对偶问题（原问题）,例：,2,3,-5,1,原问题（对偶问题）对偶问题（原问题）例：23-51,第三章对偶理论与灵敏度分析课件,第三章对偶理论与灵敏度分析课件,4.2 对偶问题的性质1.对称性 对偶问题的对偶是原问题。2.弱对偶性 若X*是原问题的可行解，Y*是对偶问题的可行解,则存在 CX*Y*b证 设原问题及对偶问题为 max z=CX，AXb，X0 min=Yb，YAC Y0 若X*是原问题的可行解，Y*是对偶问题的可行解 AX*b Y*AC Y*AX*Y*b Y*AX*CX*CX*Y*AX*Y*b,CX*,Y*b,4.2 对偶问题的性质CX*Y*b,3.无界性 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。4.可行解是最优解的性质 设X是原问题的可行解，Y是对偶问题的可行解，当CX=Yb时，X，Y是最优解。5.对偶定理 若原问题有最优解，则对偶问题也有最优解，且目标函数相等。6.互补松驰性 若X是原问题的可行解，Y是对偶问题的可行解，那么YXs=0，Ys X=0，当且仅当 X，Y为最优解。,3.无界性 若原问题（对偶问题）为无界解，则其对偶问题（,6.互补松驰性 若X是原问题的可行解，Y是对偶问题的可行解，那么YXs=0，Ys X=0，但且仅当 X，Y为最优解。证：设原问题及对偶问题的标准型是 max z=CX，AX+XS=b，X，XS 0 min=Yb，YAYS=C Y，YS 0 z=(YAYS)X=YAXYSX=Y(AX+XS)=YAX+YXS X是原问题的可行解，Y是对偶问题的可行解 z=YAXYS X=YAX+YXS当YXs=0，Ys X=0时z=，则X，Y是最优解。当 X，Y是最优解时 z=，则YXs=0，Ys X=0,6.互补松驰性 若X是原问题的可行解，Y是对偶问题,例：已知线性规划问题,max,其对偶问题的最优解为,试用对偶理论求原问题的最优解,解：,例：已知线性规划问题max其对偶问题的最优解为试用对偶理论求,7.设原问题及对偶问题的标准型是 max z=CX，AX+XS=b，X，XS 0 min=Yb，YAYS=C Y，YS 0 则原问题单纯形表的检验数行对应其对偶问题的一个基解，对应关系如下表：,证:,CBB-1A(0，CN+CBB-1N)=CBB-1(B，N)(0，CN+CBB-1N)=(CB，CN)=C,7.设原问题及对偶问题的标准型是XBXNX,5 对偶问题的经济解释影子价格,设B是线性规划问题的一可行基，这目标函数为,所以变量yi的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数值的变化。,yi的值代表对第i种资源的估价。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。,5 对偶问题的经济解释影子价格 设B是,Q2(4,2),Q1(4,0),Q3(2,3),Q4(0,3),O,Q4,Q2,Q3,*,*,A增加4，利润增加41/8=1/2,设备增加2，利润增加23/2=3,Q(5,3/2),Q(4,3),Q2(4,2)X2X10 1,6 对偶单纯形法,0,变为0,变为 0,0,单纯形法,对偶单纯形法,6 对偶单纯形法bXBXNXsXBB-1b IB-1,对偶单纯形法的计算步骤：1.确定初始的基，使非基变量的检验数小于等于零。2.若b 0,则已求得最优解，停止计算，否则进行下一步。3.确定换出变量。计算 min(B-1b)i|(B-1b)i0=(B-1b)l则xl为换出变量。4.确定换入变量。若所有aij 0，则无可行解，停止计算；否则计算=minj/alj|alj0=k/alk则xk为换入变量。5.以alk为主元素进行迭代。6.重复25步。,对偶单纯形法的计算步骤：,例：,例：,-2-3-4 0 0,-3-1-2-1 1 0,-4-2 1-3 0 1,-1 0-5/2 1/2 1-1/2,2 1-1/2 3/2 0-1/2,2/5 0 1-1/5-2/5 1/5,11/5 1 0 7/5 1/5-2/5,0-4-1 0-1,0 0-3/5-8/5-1/5,1-3 4/3/0,/8/5-2 0 2,-2-3,7 灵敏度分析,灵敏度分析的内容：1.当决定线性规划问题的参数aij，bi，cj有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化。2.当决定线性规划问题的参数aij，bi，cj在什么范围内变化时，线性规划问题的最优解或最优基不变。,7 灵敏度分析 灵敏度分析的内容：,7.1 资源数量变化的分析 设b变化为b+b，这时最终单纯形表变为,当B-1(b+b)0时，最优基不变;当B-1(b+b)中有负分量时，可利用对偶单纯形法求解。,7.1 资源数量变化的分析XBbXBXNX,例：第一章例1中，若该厂又从别处抽出4台时用于生产，求这时该厂生产的最优方案。,解：计算B-1b,4 1 0 0 1/4 0,2 0 0 1-1/4-1/2,3 0 1 0 0 1/4,-17 0 0 0-1/2-3/4,/3/4-1/4 0,+0-8+2,4-4 4,例：第一章例1中，若该厂又从别处抽出4台时,例：第一章例1中，资源A在什么范围内变化最优基不变。,解：资源A的变化量b满足下式时最优基不变。,例：第一章例1中，资源A在什么范围内变化最优,7.2 目标函数中价值系数cj的变化 1.若cj是非基变量xj 的系数，则当CN变化CN 后，最终单纯形表的检验数行变为:,当CN+CN-CBB-1N 0时，最优解不变；当CN+CN-CBB-1N 中有正分量时，可利用单纯形法求解。,7.2 目标函数中价值系数cj的变化XB,2.若cj是基变量xj 的系数，则当CB变化CB后，最终单纯形表的检验数行变为:,当非基变量检验数0时，最优解不变；当非基变量检验数中有正分量时，可利用单纯形法求解。,CB,2.若cj是基变量xj 的系数，则当CB变,例：第一章例1中，基变量x2在目标函数中的系数c2在什么范围内变化最优解不变。解：基变量x2 在目标函数中的系数c2的变化量c2满足下式时最优解不变。,0 0-3/2-1/8+0 c2/2 c2/8,c2,2+c2,例：第一章例1中，基变量x2在目标函数中的系,例：第一章例1中，出售资源A可获利1/2元，这是最优解发生什么变化。解：当 c4=1/2时，单纯形表为：,+1/2,3/8,16 8-16,2 1 0 2 0-1/2,8 0 0-4 1 2,3 0 1 0 0-1/4,-17 0 0 0 0-3/4,例：第一章例1中，出售资源A可获利1/2元，,7.3 技术系数aij的变化 1.增加一列Pn+1。则最终单纯形表增加一列B-1Pn+1，检验数为n+1=cn+1-CBB-1Pn+1例：第一章例1中，该厂开发一种新产品，已知生产新产品,每件需消耗原材料A，B各为6kg，3kg，使用设备2台时;每件可获利5元。问该厂是否应该生产该产品和生产多少？解：计算,7.3 技术系数aij的变化,5/4,8/3 2 8,1 1 0 3/2-1/8-3/4 0,2 0 0-1 1/4 1/2 1,3/2 0 1 3/4-3/16-1/8 0,-16.5 0 0-1/4-7/16-5/8 0,3/2 2 1/4,4 1 0,2.改变一列Pj。若 Pj变为Pj，则最终单纯形表增加一列B-1Pj，检验数为j=cj-CBB-1Pj，删除一列Pj。例：第一章例1中，该厂生产产品的工艺结构有了改进，已知生产产品,每件需消耗原材料A，B各为5kg，2kg，使用设备2台时;每件可获利4元。试分析对原最优计划有什么影响？解：计算,2.改变一列Pj。若 Pj变为Pj，则最,3/8,16/5 1 0 0 1/5 0,12/5 0 0-2 2/5 1,4/5 0 1 1/2-1/5 0,-15.2 0 0-3/2-1/5 0,5/4 1/2 3/8,4,4 1 0,例：第一章例1中，该厂生产产品的工艺结构有了改进，已知生产产品,每件需消耗原材料A，B各为5kg，2kg，使用设备4台时;每件可获利4元。试分析对原最优计划有什么影响？,解：计算,例：第一章例1中，该厂生产产品的工艺结构,-21/8,16/5 1 0 0 1/5 0,76/5 0 0-2 6/5 1,-12/5 0 1 1/2-2/5 0,-15.2 0 0-3/2 2/5 0,5/4-7/2 11/8,4,0-1-1/2 2/5 0,12/5,0 0 1,-M,0-M-3/2-2/5+0 0 M/2 2M/5,4 1 0,