《运筹学线性规划的对偶理论新a管理资料课件》由会员分享，可在线阅读，更多相关《运筹学线性规划的对偶理论新a管理资料课件（111页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章 线性规划的对偶理论线性规划的对偶理论第一节第一节 对偶问题的提出对偶问题的提出运筹学线性规划的对偶理论(新)a管理资料课件资源利用问题资源利用问题:原问题：原问题： max z=2x1+3x2 s.t 2x1+2x212 y1 0 4x1 16 y2 0 5x215 y3 0 x10 x20对偶问题：对偶问题： min w=12y1+16 y2 +15y3 s.t 2y1+ 4y2 +0y3 2 2y1+ 0y2 +5y3 3 y1, y2 , y3 0 显然，只有当显然，只有当max z= min w时，该经理认时，该经理认为这两种方案具有相同的结果，都是最优方案。为这两种方案
2、具有相同的结果，都是最优方案。运筹学线性规划的对偶理论(新)a管理资料课件推广到一般情况，可得：推广到一般情况，可得：原问题：原问题： max z=c1x1 +c2x2 + cnxn s.t a11x1+ a12x2 + a1nxn b1 a21x1+ a22x2 + a2nxn b2 am1x1+ am2x2 + amnxnbm x1 ,x2 , , xn 0 对偶问题：对偶问题： min w=b1y1 +b2y2 + bmym s.t a11y1+ a21y2 + am1ym c1 a12y1+ a22y2 + am2ym c2 . a1ny1+ a2ny2 + amnym cn y1 ,
3、y2 , , ym 0 以上为标准对应关系。（见表以上为标准对应关系。（见表2-1)运筹学线性规划的对偶理论(新)a管理资料课件运筹学线性规划的对偶理论(新)a管理资料课件代数形式：代数形式：运筹学线性规划的对偶理论(新)a管理资料课件矩阵形式：矩阵形式： 原问题原问题 对偶问题对偶问题运筹学线性规划的对偶理论(新)a管理资料课件第二节第二节 原问题与对偶问题的一般对应关系原问题与对偶问题的一般对应关系例例1、例、例2.结论：结论：LP对偶问题的对偶问题就是原问题。对偶问题的对偶问题就是原问题。例例3. 写出下列写出下列LP的对偶问题的对偶问题 原问题：原问题： min z=7x1+ 4x2
4、-3x3 s.t - 4x1+ 2 x2 - 6x3 24 y1 0 -3x1+ x2 +2x3 15 y2 0 5x2 +3x3 = 30 y3 无约束无约束 2x1- 2x2 +4x3 -1 y4 0 x1 0 , x2取值无约束，取值无约束，x30 对偶问题：对偶问题： max z=24y1+ 15y2 +30y3 - 10y4 s.t - 4y1- 3y2 + 0y3 + 2y4 7 2y1+ y2 + 5y3 2y4 = 4 - 6y1+ 2y2 + 3y3 + 4y4 -3 y1 0 , y20, y3无约束无约束,y40 运筹学线性规划的对偶理论(新)a管理资料课件原问题与对偶问
5、题的一般对应关系见表原问题与对偶问题的一般对应关系见表2-2。运筹学线性规划的对偶理论(新)a管理资料课件作业：作业：P78 2.1(b)(c) 2.2 2.4第三节第三节 对偶问题的基本性质对偶问题的基本性质 原问题原问题 对偶问题对偶问题运筹学线性规划的对偶理论(新)a管理资料课件定理定理1.（弱对偶性定理）（弱对偶性定理） 若若X，Y分别为分别为LP原问题及其对偶问题的原问题及其对偶问题的可行解，则恒有：可行解，则恒有： CXYb证明：对证明：对AX b，两端同时左乘可行解，两端同时左乘可行解Y,得：得： YAX Yb ； 对对YA C, 两端同时右乘可行解两端同时右乘可行解X,得：得：
6、 YAX CX,从而得：从而得： CXYb 证毕。证毕。运筹学线性规划的对偶理论(新)a管理资料课件定理定理2.（最优性定理）（最优性定理）若若X，Y分别为分别为LP原问题及其对偶问题的可行解，原问题及其对偶问题的可行解，且有：且有： CX=Yb则则X，Y分别为分别为LP原问题及其对偶问题的最优解。原问题及其对偶问题的最优解。 （充要条件）（充要条件）证明证明：（充分性）：（充分性）设设X* 为为LP原问题的最优解，设原问题的最优解，设Y* 为为LP对偶问题的最优解，由弱对偶性定理知：对偶问题的最优解，由弱对偶性定理知： 又已知又已知 故又有：故又有：因此因此X ，Y分别为分别为LP原问题及其
7、对偶问题的最优解。原问题及其对偶问题的最优解。（必要性：（必要性：CBB-1b）运筹学线性规划的对偶理论(新)a管理资料课件定理定理3.（无界性）无界性） 如果原问题（或对偶问题）有无界解，如果原问题（或对偶问题）有无界解，则其对偶问题（或原问题）无可行解。如果原则其对偶问题（或原问题）无可行解。如果原问题（或对偶问题）无可行解，则其对偶问题问题（或对偶问题）无可行解，则其对偶问题（或原问题）或是无可行解或是无界解。（或原问题）或是无可行解或是无界解。 原问题原问题 对偶问题对偶问题 最优解最优解 最优解最优解 无界解无界解 无可行解无可行解 无可行解无可行解 无界解无界解运筹学线性规划的对偶
8、理论(新)a管理资料课件定理定理4. （对偶定理）（对偶定理） 若原问题有最优解，则其对偶问题也一定若原问题有最优解，则其对偶问题也一定有最优解，且它们的最优目标函数值相等。有最优解，且它们的最优目标函数值相等。证明：设证明：设X*是是LP的最优解，它所对应的基为的最优解，它所对应的基为B，则检验数必满足：，则检验数必满足： = CCBB-1A0令令Y=CBB-1 (单纯形因子单纯形因子) ,则有：则有：YA C，因此，因此，Y是对偶问题的可行解。是对偶问题的可行解。 又知又知LP的最优的最优目标函数值为：目标函数值为： z*= CX*= CBB-1b =Yb=w 由最优性定理（定理由最优性定
9、理（定理2）可知，）可知， Y=CBB-1是对偶是对偶问题的最优解。问题的最优解。运筹学线性规划的对偶理论(新)a管理资料课件定理定理5. (互补松弛定理）互补松弛定理） 原问题及其对偶问题的可行解是最优解的原问题及其对偶问题的可行解是最优解的充要条件是：充要条件是：证明证明： （必）（必）由由化成标准形式：化成标准形式：因此可得：因此可得：运筹学线性规划的对偶理论(新)a管理资料课件若若 和和 分别是原问题和对偶问题的可行分别是原问题和对偶问题的可行解，且解，且 则必有则必有: z = w 由最优性定理可知由最优性定理可知 和和 分别为原问分别为原问题和对偶问题的最优解。题和对偶问题的最优解
10、。 （充）因为（充）因为 和和 分别为原问题和对分别为原问题和对偶问题的最优解，故：偶问题的最优解，故：从而：从而：又：又：故必有：故必有：运筹学线性规划的对偶理论(新)a管理资料课件定理定理6. (解的对应关系解的对应关系) 在同一步迭代中（同一在同一步迭代中（同一个单纯形表中），个单纯形表中），LP原问题的检验数对应于对偶原问题的检验数对应于对偶问题的一个解，且目标函数值相等（问题的一个解，且目标函数值相等（z=w)。其对应关系为：其对应关系为： 原问题原问题 对偶问题对偶问题 决策变量决策变量X 松弛变量松弛变量YS 松弛变量松弛变量XS 决策变量决策变量Y 基变量基变量XB 非基变量非
11、基变量YN 非基变量非基变量XN 基变量基变量YB运筹学线性规划的对偶理论(新)a管理资料课件证明: (1)由得：或写成：运筹学线性规划的对偶理论(新)a管理资料课件原问题的检验数为：原问题的检验数为： ( X , XS )=( CCBB-1A ， CBB-1 ) ( -YS , -Y )运筹学线性规划的对偶理论(新)a管理资料课件(2)由LP模型的矩阵表达式：写出其对偶问题：运筹学线性规划的对偶理论(新)a管理资料课件 （XB, XN, XS ）=( 0， N ， S ) =( 0， CNCBB-1N， CBB-1 ) =( -YS1, -YS2, -Y )运筹学线性规划的对偶理论(新)a管
12、理资料课件Cj CB CN 0CBXBb XB XN XSCBXBB-1b I B-1N B-1 j=cj-zj 0 CN - CBB-1N - CBB-1Cj CB CN 0CBXBb XB XN XS 0XSb B N I j=cj-zj CB CN 0 运筹学线性规划的对偶理论(新)a管理资料课件结论：结论： LP原问题的检验数的相反数是其对原问题的检验数的相反数是其对偶问题的一个解。偶问题的一个解。 在最优条件下，在最优条件下， = (CCBB-1A) 0其相反数则为对偶问题的一个可行解，其相反数则为对偶问题的一个可行解，且且z = w 。此时，。此时， Y=CBB-1 是对偶问题是对
13、偶问题的最优解。的最优解。运筹学线性规划的对偶理论(新)a管理资料课件补充例补充例4.已知已知LP问题问题 max z=6x1+ 14x2 +13x3 (1/2)x1+ 2x2 + x324 y1 x1+ 2x2 +4x360 y2 x1 ， x2 ，x30最终表为：最终表为： （ x4 ，x5 为松弛变量）为松弛变量）原问题的解为：原问题的解为： X=(36，0，6，0，0)T对偶问题的解为：对偶问题的解为： Y=（11，1/2，0，9，0）最优值为：最优值为： max z= 636+136 =294 min w=2411+60(1/2)=294Cj 6 14 13 0 0CBXBb x1
14、x2 x3 x4 x5 613x1x336 6 1 6 0 4 -1 0 -1 1 -1 1/2= cj-zj 0 -9 0 -11 -1/2 运筹学线性规划的对偶理论(新)a管理资料课件例例3. 对本章的两个互为对偶的对本章的两个互为对偶的LP数学模型，将数学模型，将其分别化为标准形式：其分别化为标准形式： (注：注：= zj-cj ) 原问题：原问题： max z=2x1+3x2 s.t 2x1+2x2+x3 =12 y1 0 4x1 +x4 =16 y2 0 5x2 +x5=15 y3 0 x1, x2, x3, x4, x50对偶问题：对偶问题： min w=12y1+16 y2+15
15、y3 s.t 2y1+ 4y2 +0y3-y4 = 2 x10 2y1+ 0y2 +5y3 -y5= 3 x20 y1, y2 , y3 , y4 , y50 运筹学线性规划的对偶理论(新)a管理资料课件对偶问题：对偶问题： max w=-12y1-16 y2-15y3 s.t -2y1- 4y2- 0y3+y4 =-2 x10 -2y1- 0y2- 5y3 +y5=-3 x20 y1, y2 , y3 , y4 , y50 两个问题的最终单纯形表及变量对应关系分两个问题的最终单纯形表及变量对应关系分别见表别见表2-3和和2-4。运筹学线性规划的对偶理论(新)a管理资料课件运筹学线性规划的对偶
16、理论(新)a管理资料课件运筹学线性规划的对偶理论(新)a管理资料课件补充例补充例5. 已知已知LP原问题为原问题为 max z=1x1+ 2x2 + 3x2 +4x2 1x1+ 2x2 + 2x3 +3x420 y1 2x1+ 1x2 + 3x3 +2x420 y2 xj0 (j=1,2,3,4) 若其对偶问题的最优解为若其对偶问题的最优解为Y=（1.2，0.2），求），求原问题的最优解和最优值。原问题的最优解和最优值。解：解：1.写出对偶问题。写出对偶问题。2.结合松紧定理计算。结合松紧定理计算。3.max z=min w=201.2+200.2=28运筹学线性规划的对偶理论(新)a管理资料
17、课件运筹学线性规划的对偶理论(新)a管理资料课件运筹学线性规划的对偶理论(新)a管理资料课件根据互补松弛定理，在最优情况下将上述结果，代入原问题的约束方程，得二元线性方程组解得所以原问题的最优解为 ，相应的最大值Z=28。运筹学线性规划的对偶理论(新)a管理资料课件原问题与对偶问题解的对应关系：原问题与对偶问题解的对应关系：运筹学线性规划的对偶理论(新)a管理资料课件第四节第四节 影子价格影子价格 （LP模型计算结果的经济解释）模型计算结果的经济解释） 在最优条件下，原问题和对偶问题的目在最优条件下，原问题和对偶问题的目标函数分别是：标函数分别是： max z=c1x1 +c2x2 + cnx
18、n =min w=b1y1 +b2y2 + bmym对对xj、bi求偏导数得：求偏导数得：运筹学线性规划的对偶理论(新)a管理资料课件例例3. 对以下（第一章例对以下（第一章例2）的）的LP数学模型标准形数学模型标准形式：式： max z=2x1+3x2 s.t 2x1+2x2+x3 =12 y1 0 4x1 +x4 =16 y2 0 5x2 +x5=15 y3 0 x1, x2, x3, x4, x50初始表和最终表见下：初始表和最终表见下：运筹学线性规划的对偶理论(新)a管理资料课件cj 2 3 0 0 0CBXBb x1 x2 x3 x4 x5000x3x4x5121615 2 2 1
19、0 0 4 0 0 1 0 0 (5) 0 0 112/215/5*cj-zj0 2 3 0 0 0203x1x4x2 3 4 3 1 0 1/2 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5cj-zj -15 0 0 -1 0 -1/5最优解最优解 X =(3，3，0，4)T。最优值。最优值 max z=15运筹学线性规划的对偶理论(新)a管理资料课件X =(3，3，0，4，0)T。 最优值最优值 z=15b1 =13时，时，X1=(7/2，3，0，2，0)T z1=16 z1-z=16-15=1 (= y1)b2 =17时，时，X1=(3，3，0，5，0)T z1=15
20、z1-z=15-15=0 (= y2)b3=16时，时， X1=(14/5，16/5，0，34/5，0)T z1=76/5 z1-z=76/5-75/5=1/5 (= y3) （见图（见图2-1）运筹学线性规划的对偶理论(新)a管理资料课件运筹学线性规划的对偶理论(新)a管理资料课件影子价格：某稀缺资源每增加一个单位时给影子价格：某稀缺资源每增加一个单位时给目标函数带来的变化量，它反映了资源的稀目标函数带来的变化量，它反映了资源的稀缺程度，也反映了局部或个体的经济活动对缺程度，也反映了局部或个体的经济活动对整体经济效果的影响。整体经济效果的影响。几点说明：几点说明：1.说明资源的稀缺程度（互补
21、松弛定理）；说明资源的稀缺程度（互补松弛定理）；2.影子价格与生产价格是两个不同的概念；影子价格与生产价格是两个不同的概念；3.影子价格是一个动态的、局部（或微观）影子价格是一个动态的、局部（或微观）的经济尺度（系统观点）；的经济尺度（系统观点）；4.边际价格；边际价格；5.影子价格的确定方法。影子价格的确定方法。运筹学线性规划的对偶理论(新)a管理资料课件影子价格的作用：影子价格的作用：1.1.辅助决策辅助决策2.2.专业化协作专业化协作3.3.使资源得到合理利用。使资源得到合理利用。运筹学线性规划的对偶理论(新)a管理资料课件作业：作业：P79 2.6（a) 第五节第五节 对偶单纯形法对偶
22、单纯形法 对偶单纯形法就是将单纯形法用于对对偶单纯形法就是将单纯形法用于对偶问题。偶问题。 对偶单纯形法的基本思想：在保持对对偶单纯形法的基本思想：在保持对偶问题为可行解的基础上（这时原问题一偶问题为可行解的基础上（这时原问题一般为非可行解），通过迭代，减少目标函般为非可行解），通过迭代，减少目标函数，当原问题也达到可行解时，即得到目数，当原问题也达到可行解时，即得到目标函数最优值。标函数最优值。 可用表可用表2-5说明。说明。运筹学线性规划的对偶理论(新)a管理资料课件运筹学线性规划的对偶理论(新)a管理资料课件运筹学线性规划的对偶理论(新)a管理资料课件例例5.用对偶单纯形法求解下列用对偶
23、单纯形法求解下列LP问题：问题： min w=12y1+16 y2+15y3 s.t 2y1+ 4y2 +0y3-y4 = 2 x10 2y1+ 0y2 +5y3 -y5= 3 x20 y1, y2 , y3 , y4 , y50 运筹学线性规划的对偶理论(新)a管理资料课件解：将模型化为标准形式解：将模型化为标准形式 max w=-12y1-16 y2-15y3 s.t -2y1- 4y2- 0y3+y4 =-2 x10 -2y1- 0y2- 5y3 +y5=-3 x20 y1, y2 , y3 , y4 , y50 列表求解：列表求解：运筹学线性规划的对偶理论(新)a管理资料课件运筹学线性
24、规划的对偶理论(新)a管理资料课件原问题最优解：原问题最优解： Y=(1，0，1/5，0，0)对偶问题最优解：对偶问题最优解： X=(3，3，0，4，0)T 最优值：最优值： min w= - max(w) = -(-12)1+(-15)1/5=15或或max z= -(-2)3+(-3)3=15运筹学线性规划的对偶理论(新)a管理资料课件（作业：（作业：P79 2.8 2.9 ）第六节第六节 灵敏度分析灵敏度分析灵敏度分析：系统或事物由于环境条件发生变灵敏度分析：系统或事物由于环境条件发生变化而显示出来的敏感程度的分析。化而显示出来的敏感程度的分析。 在前面的讨论中，都假设了模型中的参数在前
25、面的讨论中，都假设了模型中的参数aij、bi、cj是常数，但是实际上由于这些数字是常数，但是实际上由于这些数字是一些估计或预测的数字，往往随外界情况的是一些估计或预测的数字，往往随外界情况的变化而变化。因此，就要考虑如下的问题：变化而变化。因此，就要考虑如下的问题：运筹学线性规划的对偶理论(新)a管理资料课件1. 当参数当参数aij、bi、cj在什么范围内变化时，在什么范围内变化时，才不致影响原问题的最优解和最优值？才不致影响原问题的最优解和最优值？2. 当参数当参数aij、bi、cj的变化超出了最优值要的变化超出了最优值要求的范围时，新的最优解和最优值是什么？求的范围时，新的最优解和最优值是
26、什么？ 这就是灵敏度分析和参数线性规划所要这就是灵敏度分析和参数线性规划所要解决的问题。解决的问题。运筹学线性规划的对偶理论(新)a管理资料课件 从数学上来看，灵敏度分析和参数线性规从数学上来看，灵敏度分析和参数线性规划就是研究划就是研究LP问题最优解的稳定性。问题最优解的稳定性。 由矩阵关系式可知，当模型（或初始表）由矩阵关系式可知，当模型（或初始表）中的参数发生变化时，不必从头计算，只需中的参数发生变化时，不必从头计算，只需将变化后的参数利用最终表中的将变化后的参数利用最终表中的B-1直接反映直接反映到最终表中，然后看最终表的最优性是否受到最终表中，然后看最终表的最优性是否受到影响，若最优
27、性受到影响，则继续迭代，到影响，若最优性受到影响，则继续迭代，求新的最优解和最优值即可。求新的最优解和最优值即可。运筹学线性规划的对偶理论(新)a管理资料课件灵敏度分析的步骤灵敏度分析的步骤: (P65)1. 将参数的改变通过矩阵计算反映到最终表中将参数的改变通过矩阵计算反映到最终表中（见矩阵关系式）；（见矩阵关系式）；2. 检查原问题是否可行解；检查原问题是否可行解；3. 检查对偶问题是否可行解；检查对偶问题是否可行解；4. 按以下原则得出结论或决定继续计算的步骤。按以下原则得出结论或决定继续计算的步骤。运筹学线性规划的对偶理论(新)a管理资料课件Cj CB CN 0CBXBb XB XN
28、XS 0XSb B N I j=cj-zj CB CN 0Cj CB CN 0CBXBb XB XN XSCBXBB-1b I B-1N B-1 j=cj-zj 0 CN - CBB-1N - CBB-1 . 运筹学线性规划的对偶理论(新)a管理资料课件6-1 分析分析cj变化时，对最优值的影响变化时，对最优值的影响 由矩阵关系式可知，由矩阵关系式可知，cj的变化仅仅影响到的变化仅仅影响到检验数检验数 =(0， N ， S ) =(0， CNCBB-1N， CBB-1 ) 1.当当cj是非基变量系数时，是非基变量系数时，cj的变化只影响非的变化只影响非基变量基变量xj的检验数；的检验数；2.当
29、当cj是基变量系数时，是基变量系数时， cj的变化就会影响所的变化就会影响所有非基变量的检验数。有非基变量的检验数。下面分别讨论。下面分别讨论。运筹学线性规划的对偶理论(新)a管理资料课件1.1.设设c cj j是非基变量是非基变量x xj j的目标函数系数的目标函数系数 当当c cj j， =c =cj j + +（ 是变化量）时，要是变化量）时，要保证在最终表中保证在最终表中j j，00，应有：，应有： j j， c cj j，- C- CB BB B-1-100 c cj j，CCB BB B-1-1或：或： j j， c cj j + - C + - CB BB B-1-1 j j +
30、 0 + 0 即即 j j （注：（注：j j 0 0）运筹学线性规划的对偶理论(新)a管理资料课件用单纯形法求解下列用单纯形法求解下列LP问题的结果见下页问题的结果见下页运筹学线性规划的对偶理论(新)a管理资料课件运筹学线性规划的对偶理论(新)a管理资料课件 以上例中的以上例中的c3为例。由于为例。由于c3是非基变量是非基变量x3的价值系数，因此的价值系数，因此c3的变化只影响到检验数的变化只影响到检验数3，所以，所以c3的变化，只要能保持的变化，只要能保持30，则最优解，则最优解不变。现在将不变。现在将c3作为参数，讨论作为参数，讨论c3在什么范围在什么范围内变化，才能保持内变化，才能保持
31、30 。由上表的最终表知：由上表的最终表知：运筹学线性规划的对偶理论(新)a管理资料课件 这说明，只要产品这说明，只要产品A3的单位销售价不的单位销售价不大于大于50元，最优解不变，即还是按原最优计元，最优解不变，即还是按原最优计划安排生产。划安排生产。运筹学线性规划的对偶理论(新)a管理资料课件2.设设cr是基变量是基变量xr的目标函数系数的目标函数系数 此时，此时， cr CB，所以，所以 cr的变化就会影响所有的变化就会影响所有非基变量的检验数。非基变量的检验数。 当当cr， =cr +（ 是变化量）时，要保证在最是变化量）时，要保证在最终表中终表中j，0，应有：，应有： j，cj -
32、CB，B-1cj - （CB +（0，0， ， ，0）B-1cj - CBB-1 arj，j arj，0 （j=1,2,n) 或或 arj， j (arj，是最终表中基变量是最终表中基变量xr行非零的约束系数）行非零的约束系数）运筹学线性规划的对偶理论(新)a管理资料课件即即运筹学线性规划的对偶理论(新)a管理资料课件例例6. 已知已知LP问题问题 max z=(2+1) x1 +(3 +2) x2 s.t 2x1+2x212 4x1 16 5x215 x10 x20 试试分别分别分析分析1，2在什么范围内变化时，在什么范围内变化时，问题的最优解不变。问题的最优解不变。解：解：1=2=0时的最
33、终表为：时的最终表为：运筹学线性规划的对偶理论(新)a管理资料课件cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5203x1x4x2 3 4 3 1 0 1/2 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5cj-zj -15 0 0 -1 0 -1/5运筹学线性规划的对偶理论(新)a管理资料课件1. 当当2=0时，时，将将1的变化直接反映到最终表中的变化直接反映到最终表中(表表2-9)。运筹学线性规划的对偶理论(新)a管理资料课件为使表中的解仍为最优解，应有为使表中的解仍为最优解，应有运筹学线性规划的对偶理论(新)a管理资料课件例：若例：若c1=4，求新的最
34、优解，最优值。，求新的最优解，最优值。解：将解：将c1的变化直接反映到最终表中。的变化直接反映到最终表中。cj 4 3 0 0 0CBXBb x1 x2 x3 x4 x5403x1x4x2 3 4 3 1 0 1/2 0 -1/5 0 0 -2 1 (4/5) 0 1 0 0 1/54/(4/5)3/(1/5)cj-zj -21 0 0 -2 0 1/5403x1x5x2 4 5 2 1 0 0 1/4 0 0 0 -5/2 5/4 1 0 1 1/2 -1/4 0cj-zj -22 0 0 -3/2 -1/4 0运筹学线性规划的对偶理论(新)a管理资料课件新的最优解为新的最优解为 X=(4，
35、2，0，0，5)T，最优值为最优值为 max z= 44+ 32 =22运筹学线性规划的对偶理论(新)a管理资料课件6-2 资源数量资源数量bi变化的影响变化的影响 由矩阵关系式由矩阵关系式b，=B-1b和和z = CB B-1b 可可知，知，bi的的变化仅仅影响到最终表中常数项列的的变化仅仅影响到最终表中常数项列数字和目标函数值数字和目标函数值z的变化，此时，原问题检验的变化，此时，原问题检验数不受影响（即对偶问题保持可行），只需检数不受影响（即对偶问题保持可行），只需检查原问题是否可行即可。查原问题是否可行即可。运筹学线性规划的对偶理论(新)a管理资料课件例例7. 已知已知LP问题问题 m
36、ax z=2x1 + 3 x2 s.t 2x1+2x212+1 4x1 16+2 5x215+3 x10 x20 分别分别分析分析1，2 ,3在什么范围内变化在什么范围内变化时，问题的最优解不变。时，问题的最优解不变。解：先分析解：先分析1的变化。的变化。当当2 =3=0时的最终表为：时的最终表为：运筹学线性规划的对偶理论(新)a管理资料课件cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5000x3x4x5121615 2 2 1 0 0 4 0 0 1 0 0 5 0 0 1cj-zj 0 2 3 0 0 0运筹学线性规划的对偶理论(新)a管理资料课件cj 2 3 0 0
37、0CBXB b x1 x2 x3 x4 x5203x1x4x2 3 4 3 1 0 1/2 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5cj-zj -15 0 0 -1 0 -1/5运筹学线性规划的对偶理论(新)a管理资料课件cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5203x1x4x23+(1/2)1 4-21 3 1 0 1/2 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5cj-zj-15-1 0 0 -1 0 -1/5要保持上述基仍为最优基，应有：要保持上述基仍为最优基，应有：运筹学线性规划的对偶理论(新)a管理资料课件 3+(1
38、/2)10， 4-210解得：解得：-612，或：，或： 6 b114 同理可推得：同理可推得：-42 ，或：，或： 12b2 -5315，或：，或： 10b330 例：设例：设b1=20，求新的最优解，最优值。求新的最优解，最优值。解：将解：将b1的变化直接反映应到最终表中的变化直接反映应到最终表中(1=8)。运筹学线性规划的对偶理论(新)a管理资料课件cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5203x1x4x2 7-12 3 1 0 1/2 0 -1/5 0 0 (-2) 1 4/5 0 1 0 0 1/5cj-zj-23 0 0 -1 0 -1/5203x1x3x
39、2 4 6 3 1 0 0 1/4 0 0 0 1 -1/2 -2/5 0 1 0 0 1/5cj-zj -17 0 0 0 -1/2 -3/5运筹学线性规划的对偶理论(新)a管理资料课件新的最优解为新的最优解为 X=(4，3，6，0，0)T，最优值为最优值为 max z= 24+ 33 =17运筹学线性规划的对偶理论(新)a管理资料课件6-3 增加一个变量的分析增加一个变量的分析 增加一个变量相当于增加一种新的产品，增加一个变量相当于增加一种新的产品，是否生产这种产品关键是看它的检验数是否大是否生产这种产品关键是看它的检验数是否大于零。因此，分析步骤是：于零。因此，分析步骤是：1. 计算新增
40、变量计算新增变量xj的检验数的检验数 j cj - CBB-12. 若若j0 ，则原最优解不变；若，则原最优解不变；若j 0，则转，则转3;3. 计算计算Pj，= B-1,再按单纯形法继续迭代。再按单纯形法继续迭代。 运筹学线性规划的对偶理论(新)a管理资料课件例例8. 在第一章例在第一章例2中，增加一个变量中，增加一个变量x6，且，且c6=4， P6 =(2，4，5)T,试分析最优解的变化。试分析最优解的变化。解：解： 6=c6 - CBB-16 =4-(1，0，1/5)(2，4，5)T =4 - 3=1 因检验数因检验数6 0 ，故将有关参数反映到最，故将有关参数反映到最终单纯形表中，用单
41、纯形法继续计算。终单纯形表中，用单纯形法继续计算。运筹学线性规划的对偶理论(新)a管理资料课件cj 2 3 0 0 0 4CBXB b x1 x2 x3 x4 x5 x6203x1x4x2 3 4 3 1 0 1/2 0 -1/5 0 0 0 -2 1 4/5 (4) 0 1 0 0 1/5 14/4*3/1cj-zj-15 0 0 -1 0 -1/5 1243x1x6x2 3 1 2 1 0 1/2 0 -1/5 0 0 0 -1/2 1/4 1/5 1 0 1 1/2 -1/4 0 0cj-zj -16 0 0 -1/2 -1/4 -2/5 0运筹学线性规划的对偶理论(新)a管理资料课件新
42、的最优解为新的最优解为X=(3，2，0，0，0，1)T,最优值为最优值为max z=23+32+41=16运筹学线性规划的对偶理论(新)a管理资料课件6-4 增加一个约束条件的分析增加一个约束条件的分析 增加一个约束条件，相当于增添了一道工增加一个约束条件，相当于增添了一道工序或资源限制。序或资源限制。分析步骤：分析步骤：1. 将原来问题的最优解代入这个新增的约束条将原来问题的最优解代入这个新增的约束条件之中。若满足，则说明新约束条件不形成限件之中。若满足，则说明新约束条件不形成限制，否则转下一步；制，否则转下一步；2. 将新增约束条件直接反映到最终表中，再进将新增约束条件直接反映到最终表中，
43、再进行分析。行分析。运筹学线性规划的对偶理论(新)a管理资料课件例例9. 在第一章例在第一章例2中，增添一个约束条件中，增添一个约束条件 3x1+2x214试分析最优解的变化。试分析最优解的变化。解：解：1. 将原问题的最优解代入新约束得：将原问题的最优解代入新约束得： 33+23=15 14不满足。不满足。 将新增约束加上松弛变量将新增约束加上松弛变量x6后写成后写成 ： 3x1+2x2+x6=14 直接反映到最终表中，并将基矩阵化为单位直接反映到最终表中，并将基矩阵化为单位矩阵。这时，原问题成为非可行解，故用对偶单矩阵。这时，原问题成为非可行解，故用对偶单纯形法继续迭代。纯形法继续迭代。运
44、筹学线性规划的对偶理论(新)a管理资料课件cj 2 3 0 0 0 0CBXB b x1 x2 x3 x4 x5 x62030x1x4x2x6 3 4 314 1 0 1/2 0 -1/5 0 0 0 -2 1 4/5 0 0 1 0 0 1/5 0 3 2 0 0 0 1cj-zj-15 0 0 -1 0 -1/5 02030x1x4x2x6 3 4 3 -1 1 0 1/2 0 -1/5 0 0 0 -2 1 4/5 0 0 1 0 0 1/5 0 0 0 (-3/2) 0 1/5 1cj-zj-15 0 0 -1 0 -1/5 0运筹学线性规划的对偶理论(新)a管理资料课件cj 2 3
45、0 0 0 4CBXB b x1 x2 x3 x4 x5 x62030x1x4x2x3 8/316/3 3 2/3 1 0 0 0 -2/15 1/3 0 0 0 1 8/15 -4/3 0 1 0 0 1/5 0 0 0 1 0 -2/15 -2/3cj-zj-43/3 0 0 0 0 -1/3 -2/3新的最优解为新的最优解为X=(8/3，3，2/3，16/3，0，0)T,最优值为最优值为max z=2(8/3)+33=43/3运筹学线性规划的对偶理论(新)a管理资料课件6-5 约束系数约束系数aij变化的影响（补）变化的影响（补） 假如假如xj在最终表中为非基变量，则在最终表中为非基变量
46、，则aij的变的变化将使最终表中化将使最终表中xj的检验数的检验数j发生变化，若发生变化，若j0,则用单纯形法继续计算。则用单纯形法继续计算。 假如假如xj在最终表中为基变量，则在最终表中为基变量，则aij的变化的变化将使最终表中的将使最终表中的B-1发生变化，因此有可能出发生变化，因此有可能出现原问题和对偶问题均为非可行解的情况，现原问题和对偶问题均为非可行解的情况，此时，须引入人工变量，将原问题转化为可此时，须引入人工变量，将原问题转化为可行解，再用单纯形法继续计算。行解，再用单纯形法继续计算。运筹学线性规划的对偶理论(新)a管理资料课件Cj CB CN 0CBXBb XB XN XS 0
47、XSb B N I j=cj-zj CB CN 0Cj CB CN 0CBXBb XB XN XSCBXBB-1b I B-1N B-1 j=cj-zj 0 CN - CBB-1N - CBB-1 . 运筹学线性规划的对偶理论(新)a管理资料课件例例. 已知已知LP问题问题 max z=2x1+x2 s.t. 5x215 6x1+2x224 x1+ x25 x10 x20 最终表为：最终表为：运筹学线性规划的对偶理论(新)a管理资料课件最优解为最优解为X=（7/2，3/2，15/2，0，0）T ,最优值为最优值为max z=2(7/2)+1(3/2)=17/2=8.5运筹学线性规划的对偶理论(
48、新)a管理资料课件若若c2=3，P2 =（8，4，1）T,试分析最优解的试分析最优解的变化。变化。解：解：2 = c2 - CBB-12 =3（0，1/4，1/2）（8，4，1）T =3（3/2）=3/2 0 将有关参数反映到最终单纯形表中。将有关参数反映到最终单纯形表中。运筹学线性规划的对偶理论(新)a管理资料课件运筹学线性规划的对偶理论(新)a管理资料课件 对表中的第一个约束，可写成：对表中的第一个约束，可写成： x3+ 4x4 24x5 =9两端同乘（两端同乘（1），再加上人工变量），再加上人工变量x6得：得： x3 4x4 24x5 x6 9用上式替换表中的第一个约束，得表用上式替换表
49、中的第一个约束，得表2-19，因因5 0 ，故用单纯形法继续迭代。，故用单纯形法继续迭代。运筹学线性规划的对偶理论(新)a管理资料课件新的最优解为新的最优解为X=（11/4，15/8，0，0，3/8，0）T，最优值为最优值为max=2(11/4)+3(15/8)=89/8运筹学线性规划的对偶理论(新)a管理资料课件P80 2.10(d)第七节第七节 参数线性规划参数线性规划灵敏度分析：研究使问题的最优解或最优基灵敏度分析：研究使问题的最优解或最优基保持不变时的参数值变化范围。保持不变时的参数值变化范围。参数线性规划：研究线性规划中的参数参数线性规划：研究线性规划中的参数aij，cj，bi超出灵
50、敏度分析的范围而连续变化时，最超出灵敏度分析的范围而连续变化时，最优解的变化情况。优解的变化情况。运筹学线性规划的对偶理论(新)a管理资料课件参数线性规划要求：参数线性规划要求： 当问题中有多个参数变化时，应使目标函数当问题中有多个参数变化时，应使目标函数z()是是的线性函数。例如：的线性函数。例如：（1）当有多个）当有多个bi值变动时，可将常数项写为值变动时，可将常数项写为bi=bi+i，式中，式中i可以是任意的实数；可以是任意的实数；（2）当有多个）当有多个cj值变动时，可将目标函数系数写值变动时，可将目标函数系数写为为cj=cj+j，式中，式中j可以是任意的实数。可以是任意的实数。运筹学
51、线性规划的对偶理论(新)a管理资料课件求解参数线性规划的步骤：求解参数线性规划的步骤：1.令令=0，求解原来问题的最终单纯形表；，求解原来问题的最终单纯形表；2.将参数的变化反映到最终表中去；将参数的变化反映到最终表中去；3.让让逐步增加（或减少），观察逐步增加（或减少），观察原问题和对原问题和对偶问题解偶问题解的变化，看的变化，看哪一个首先出现非可行解哪一个首先出现非可行解，用用单纯形法或对偶单纯形法单纯形法或对偶单纯形法继续迭代，确定继续迭代，确定的范围。的范围。运筹学线性规划的对偶理论(新)a管理资料课件例例10. 求解以下参数线性规划问题求解以下参数线性规划问题 max z()=(2+
52、2) x1 +(3 +) x2 s.t 2x1+2x212 4x1 16 5x215 x10 x20解：解：=0时的最终表为：时的最终表为：运筹学线性规划的对偶理论(新)a管理资料课件将参数的变化反映到最终表中（表将参数的变化反映到最终表中（表2-16）cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5203x1x4x2 3 4 3 1 0 1/2 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5cj-zj -15 0 0 -1 0 -1/5运筹学线性规划的对偶理论(新)a管理资料课件cj2+2 3+ 0 0 0CBXB b x1 x2 x3 x4 x52+203
53、+x1x4x2 3 4 3 1 0 (1/5) 0 -1/5 0 0 -2 1 4/5 (-11） 0 1 0 0 1/5cj-zj -15-9 0 0 -1- 0 -1/5+(1/5) 当当-1时，可将时，可将x3作为换入变量进行单纯形迭作为换入变量进行单纯形迭代，得表代，得表2-17。运筹学线性规划的对偶理论(新)a管理资料课件cj2+2 3+ 0 0 0CBXB b x1 x2 x3 x4 x5003+x3x4x2 616 3 2 0 1 0 -2/5 4 0 0 1 0 (-3-1） 0 1 0 0 (1/5)cj-zj -9-32+2 0 0 0 -3/5-(1/5) 000x3x4
54、x5 12 16 15 2 2 1 0 0 4 0 0 1 0 (-3） 0 5 0 0 1cj-zj 02+2 3+ 0 0 0当当1时，可将时，可将x5作为换入变量进行单纯形迭作为换入变量进行单纯形迭代，得表代，得表2-18。运筹学线性规划的对偶理论(新)a管理资料课件cj2+2 3+ 0 0 0CBXB b x1 x2 x3 x4 x52+203+x1x5x2 4 5 2 1 0 0 1/4 0 0 0 -5/2 5/4 1(1) 0 1 1/2 -1/4 0cj-zj-14-10 0 0 -3/2-(1/2)1/4-(1/4) 0 以以为横坐标，在为横坐标，在z() 为纵坐标，可画出为
55、纵坐标，可画出z()随随变化的情况见图变化的情况见图2-2。运筹学线性规划的对偶理论(新)a管理资料课件运筹学线性规划的对偶理论(新)a管理资料课件例例11. 求解以下参数线性规划问题求解以下参数线性规划问题 max z=2x1 + 3x2 s.t 2x1+2x212 4x1 16 5x215 + x10 x20解：解：=0时的最终表为：时的最终表为：运筹学线性规划的对偶理论(新)a管理资料课件用公式用公式b= B-1b将参数的变化反映到最终表中将参数的变化反映到最终表中（表（表2-19）cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5203x1x4x2 3 4 3 1 0
56、1/2 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5cj-zj -15 0 0 -1 0 -1/5运筹学线性规划的对偶理论(新)a管理资料课件由表可知，当由表可知，当-515-515时为最优基，先讨论时为最优基，先讨论-5-5时的情况，此时，基变量时的情况，此时，基变量x x4 4 0 0，用对偶单纯形，用对偶单纯形法迭代得表法迭代得表2-202-20。cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5203x1x4x23-(1/5) 4+(4/5) 3+(1/5) 1 0 1/2 0 -1/5 0 0 (-2) 1 4/5 0 1 0 0 1/5cj-zj-
57、15-(1/5) 0 0 -1 0 -1/5运筹学线性规划的对偶理论(新)a管理资料课件cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5203x1x3x2 4-2-(2/5) 3+(1/5) 1 0 0 1/4 0 0 0 1 -1/2 -2/5 0 1 0 0 1/5cj-zj-17-(3/5) 0 0 0 -1/2 -3/5由表可知，当由表可知，当-15-5-15-5时为最优基，当时为最优基，当-15-15时，本题无可行解。时，本题无可行解。 下面分析下面分析15时的情形，时的情形，此时，基变量此时，基变量x x1 1 0 0，用对偶单纯形法迭代得表，用对偶单纯形法迭代得
58、表2-212-21。运筹学线性规划的对偶理论(新)a管理资料课件cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5003x5x4x2-15+ 16 6 -5 0 -5/2 0 1 4 0 0 1 0 1 1 1/2 0 0cj-zj -18 -1 0 -3/2 0 0 以以为横坐标，在为横坐标，在z() 为纵坐标，可画出为纵坐标，可画出z()随随变化的情况见图变化的情况见图2-3。运筹学线性规划的对偶理论(新)a管理资料课件运筹学线性规划的对偶理论(新)a管理资料课件例例13：已知见下表，试决定：已知见下表，试决定：原稿纸原稿纸（捆）（捆）日记本日记本（打）（打）练习本练习本（
59、箱）（箱）资源限制资源限制白坯纸白坯纸（kg)30000（kg)工人工人(工日）工日） 100（工日）（工日）单位单位利润利润 2（元（元/捆）捆） 3（元（元/打）打） 1（元（元/箱）箱）运筹学线性规划的对偶理论(新)a管理资料课件（1）盈利最大的生产方案；）盈利最大的生产方案；（2）若白坯纸的供应量不变，人工不够时）若白坯纸的供应量不变，人工不够时可招临时工，工资为可招临时工，工资为40元元/（人天），问是（人天），问是否招工？若招工的话，最多招多少？否招工？若招工的话，最多招多少？运筹学线性规划的对偶理论(新)a管理资料课件解：解：设生产设生产原稿纸原稿纸x x1 1捆，捆，日记本日记
60、本x x2 2打，打，练习本练习本x x3 3箱；箱；表示招工人数，则该问题的数学模型表示招工人数，则该问题的数学模型为：为：令令 =0 =0，用单纯形法求得原问题的最优生产方案，用单纯形法求得原问题的最优生产方案见表见表2-282-28：运筹学线性规划的对偶理论(新)a管理资料课件 由于人工的影子价格由于人工的影子价格y2=5040，故招工，故招工是合算的。当是合算的。当 0 0时，将变化后的常数项反时，将变化后的常数项反映到最终表中并继续计算，结果见表映到最终表中并继续计算，结果见表2-29。运筹学线性规划的对偶理论(新)a管理资料课件 由此可以看出，该厂招工的数量最多为由此可以看出，该厂招工的数量最多为200人，工厂利润额人，工厂利润额z()与招工数量与招工数量之间的函之间的函数关系见图数关系见图2-4。运筹学线性规划的对偶理论(新)a管理资料课件运筹学线性规划的对偶理论(新)a管理资料课件运筹学线性规划的对偶理论(新)a管理资料课件
