第二章第二章 线性性规划的划的对偶偶实际第一第一节 对偶偶问题的提出的提出资源利用源利用问题:原原问题： 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时，该经理以理以为这两种方案具有一两种方案具有一样的的结果，都是最果，都是最优方案。方案。推行到普通情况，可得：推行到普通情况，可得：原原问题： 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 ,y2 , , ym 0 以上以上为规范范对应关系。关系。见表表2-1)代数方式：代数方式：矩矩阵方式：方式： 原原问题 对偶偶问题第二第二节 原原问题与与对偶偶问题的普通的普通对应关系关系例例1、例、例2.结论：LP对偶偶问题的的对偶偶问题就是原就是原问题。例例3. 写出以下写出以下LP的的对偶偶问题 原原问题： min z=7x1+ 4x2 -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 原原问题与与对偶偶问题的普通的普通对应关系关系见表表2-2。作作业：P78 2.1(b)(c) 2.2 2.4第三第三节 对偶偶问题的根本性的根本性质 原原问题 对偶偶问题定理定理1.弱弱对偶性定理偶性定理 假假设X，Y分分别为LP原原问题及其及其对偶偶问题的可行解，那么恒有：的可行解，那么恒有： CXYb证明：明：对AX b，两端同，两端同时左乘可行解左乘可行解Y,得：得： YAX Yb ； 对YA C, 两端同两端同时右乘可行解右乘可行解X,得：得： YAX CX,从而得：从而得： CXYb 证毕。定理定理2.最最优性定理性定理假假设X，Y分分别为LP原原问题及其及其对偶偶问题的可行解，的可行解，且有：且有： CX=Yb那么那么X，Y分分别为LP原原问题及其及其对偶偶问题的最的最优解。解。 充要条件充要条件证明：充分性明：充分性设X* 为LP原原问题的最的最优解，解，设Y* 为LP对偶偶问题的最的最优解，由弱解，由弱对偶性定理知：偶性定理知： 又知又知 故又有：故又有：因此因此X ，Y分分别为LP原原问题及其及其对偶偶问题的最的最优解。解。必要性：必要性：CBB-1b定理定理3.无界性无界性 假假设原原问题或或对偶偶问题有无界解，有无界解，那么其那么其对偶偶问题或原或原问题无可行解。假无可行解。假设原原问题或或对偶偶问题无可行解，那么其无可行解，那么其对偶偶问题或原或原问题或是无可行解或是无界解。或是无可行解或是无界解。 原原问题 对偶偶问题 最最优解解 最最优解解 无界解无界解 无可行解无可行解 无可行解无可行解 无界解无界解定理定理4. 对偶定理偶定理 假假设原原问题有最有最优解，那么其解，那么其对偶偶问题也也一定有最一定有最优解，且它解，且它们的最的最优目的函数目的函数值相等。相等。证明：明：设X*是是LP的最的最优解，它所解，它所对应的基的基为B，那么，那么检验数必数必满足：足： = CCBB-1A0令令Y=CBB-1 (单纯形因子形因子) ,那么有：那么有：YA C，因此，因此，Y是是对偶偶问题的可行解。的可行解。 又知又知LP的最的最优目的函数目的函数值为： z*= CX*= CBB-1b =Yb=w 由最由最优性定理定理性定理定理2可知，可知， Y=CBB-1是是对偶偶问题的最的最优解。解。定理定理5. (互互补松弛定理松弛定理 原原问题及其及其对偶偶问题的可行解是最的可行解是最优解的解的充要条件是：充要条件是：证明：明： 必由必由化成化成规范方式：范方式：因此可得：因此可得：假假设 和和 分分别是原是原问题和和对偶偶问题的可的可行解，且行解，且 那么必有那么必有: z = w 由最由最优性定理可知性定理可知 和和 分分别为原原问题和和对偶偶问题的最的最优解。解。 充由于充由于 和和 分分别为原原问题和和对偶偶问题的最的最优解，故：解，故：从而：从而：又：又：故必有：故必有：定理定理6. (解的解的对应关系关系) 在同一步迭代中同一个在同一步迭代中同一个单纯形表中，形表中，LP原原问题的的检验数数对应于于对偶偶问题的一个解，且目的函数的一个解，且目的函数值相等相等z=w)。其其对应关系关系为： 原原问题 对偶偶问题 决策决策变量量X 松弛松弛变量量YS 松弛松弛变量量XS 决策决策变量量Y 基基变量量XB 非基非基变量量YN 非基非基变量量XN 基基变量量YB证明: (1)由得：或写成：原原问题的的检验数数为： ( X , XS )=( CCBB-1A ， CBB-1 ) ( -YS , -Y )(2)由LP模型的矩阵表达式：写出其对偶问题： XB, XN, XS =( 0， N ， S ) =( 0， CNCBB-1N， CBB-1 ) =( -YS1, -YS2, -Y )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 结论： LP原原问题的的检验数的相反数是其数的相反数是其对偶偶问题的一个解。的一个解。 在最在最优条件下，条件下， = (CCBB-1A) 0其相反数那么其相反数那么为对偶偶问题的一个可行解，的一个可行解，且且z = w 。此。此时， Y=CBB-1 是是对偶偶问题的最的最优解。解。补充例充例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 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 例例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+15y3 s.t 2y1+ 4y2 +0y3-y4 = 2 x10 2y1+ 0y2 +5y3 -y5= 3 x20 y1, y2 , y3 , y4 , y50 对偶偶问题： 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。补充例充例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根据互补松弛定理，在最优情况下将上述结果，代入原问题的约束方程，得二元线性方程组解得所以原问题的最优解为 ，相应的最大值Z=28。原原问题与与对偶偶问题解的解的对应关系：关系：第四第四节 影子价影子价钱 LP模型模型计算算结果的果的经济解解释 在最在最优条件下，原条件下，原问题和和对偶偶问题的目的目的函数分的函数分别是：是： max z=c1x1 +c2x2 + cnxn =min w=b1y1 +b2y2 + bmym对xj、bi求偏求偏导数得：数得：例例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初始表和最初始表和最终表表见下：下：cj 2 3 0 0 0CBXBb x1 x2 x3 x4 x5000x3x4x5121615 2 2 1 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=15X =(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 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影子价影子价钱：某稀缺：某稀缺资源每添加一个源每添加一个单位位时给目的函数目的函数带来的来的变化量，它反映了化量，它反映了资源的稀源的稀缺程度，也反映了部分或个体的缺程度，也反映了部分或个体的经济活活动对整体整体经济效果的影响。效果的影响。几点几点阐明：明：1.阐明明资源的稀缺程度互源的稀缺程度互补松弛定理；松弛定理；2.影子价影子价钱与消与消费价价钱是两个不同的概念；是两个不同的概念；3.影子价影子价钱是一个是一个动态的、部分或微的、部分或微观的的经济尺度系尺度系统观念；念；4.边沿价沿价钱；5.影子价影子价钱确确实定方法。定方法。影子价钱的作用：影子价钱的作用：1.1.辅助决策辅助决策2.2.专业化协作专业化协作3.3.使资源得到合理利用。使资源得到合理利用。作作业：P79 2.6a) 第五第五节 对偶偶单纯形法形法 对偶偶单纯形法就是将形法就是将单纯形法用于形法用于对偶偶问题。 对偶偶单纯形法的根本思想：在形法的根本思想：在坚持持对偶偶问题为可行解的根底上可行解的根底上这时原原问题普普通通为非可行解，非可行解，经过迭代，减少目的函迭代，减少目的函数，当原数，当原问题也到达可行解也到达可行解时，即得到目，即得到目的函数最的函数最优值。 可用表可用表2-5阐明。明。例例5.用用对偶偶单纯形法求解以下形法求解以下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 解：将模型化解：将模型化为规范方式范方式 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 列表求解：列表求解：原原问题最最优解：解： 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作作业：P79 2.8 2.9 第六第六节 灵敏度分析灵敏度分析灵敏度分析：系灵敏度分析：系统或事物由于或事物由于环境条件境条件发生生变化而化而显示出来的敏感程度的分析。示出来的敏感程度的分析。 在前面的在前面的讨论中，都假中，都假设了模型中的参数了模型中的参数aij、bi、cj是常数，但是是常数，但是实践上由于践上由于这些数字些数字是一些估是一些估计或或预测的数字，往往随外界情况的的数字，往往随外界情况的变化而化而变化。因此，就要思索如下的化。因此，就要思索如下的问题：1. 当参数当参数aij、bi、cj在什么范围内变化时，在什么范围内变化时，才不致影响原问题的最优解和最优值？才不致影响原问题的最优解和最优值？2. 当参数当参数aij、bi、cj的变化超出了最优值要的变化超出了最优值要求的范围时，新的最优解和最优值是什么？求的范围时，新的最优解和最优值是什么？ 这就是灵敏度分析和参数线性规划所要这就是灵敏度分析和参数线性规划所要处理的问题。处理的问题。 从数学上来看，灵敏度分析和参数从数学上来看，灵敏度分析和参数线性性规划就划就是研是研讨LP问题最最优解的解的稳定性。定性。 由矩由矩阵关系式可知，当模型或初始表中的关系式可知，当模型或初始表中的参数参数发生生变化化时，不用从，不用从头计算，只需将算，只需将变化后的化后的参数利用最参数利用最终表中的表中的B-1直接反映到最直接反映到最终表中，然后表中，然后看最看最终表的最表的最优性能否遭到影响，假性能否遭到影响，假设最最优性遭到性遭到影响，那么影响，那么继续迭代，求新的最迭代，求新的最优解和最解和最优值即可。即可。灵敏度分析的步灵敏度分析的步骤: (P65)1. 将参数的改将参数的改动经过矩矩阵计算反映到最算反映到最终表中表中见矩矩阵关系式；关系式；2. 检查原原问题能否可行解；能否可行解；3. 检查对偶偶问题能否可行解；能否可行解；4. 按以下原那么得出按以下原那么得出结论或决或决议继续计算的步算的步骤。Cj CB CN 0CBXBb XB XN 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 . 6-1 分析分析cj变化化时，对最最优值的影响的影响 由矩由矩阵关系式可知，关系式可知，cj的的变化化仅仅影响到影响到检验数数 =(0， N ， S ) =(0， CNCBB-1N， CBB-1 ) 1.当当cj是非基是非基变量系数量系数时，cj的的变化只影响非化只影响非基基变量量xj的的检验数；数；2.当当cj是基是基变量系数量系数时， cj的的变化就会影响一化就会影响一切非基切非基变量的量的检验数。数。下面分下面分别讨论。1.1.设cjcj是非基是非基变量量xjxj的目的函数系数的目的函数系数 当当cjcj， =cj + =cj + 是是变化量化量时，要，要保保证在最在最终表中表中jj，00，应有：有： j j， cj cj，- CBB-1- CBB-10 0 cj cj，CBB-1CBB-1或：或： j j， cj + - CBB-1 cj + - CBB-1 j + 0 j + 0 即即 j j 注：注：j 0j 0用单纯形法求解以下用单纯形法求解以下LP问题的结果见下页问题的结果见下页 以上例中的以上例中的c3为例。由于例。由于c3是非基是非基变量量x3的价的价值系数，因此系数，因此c3的的变化只影响到化只影响到检验数数3，所以，所以c3的的变化，只需能化，只需能坚持持30，那，那么最么最优解不解不变。如今将。如今将c3作作为参数，参数，讨论c3在什么范在什么范围内内变化，才干化，才干坚持持30 。由上表的最由上表的最终表知：表知： 这阐明，只需产品这阐明，只需产品A3的单位销售价不的单位销售价不大于大于50元，最优解不变，即还是按原最优方元，最优解不变，即还是按原最优方案安排消费。案安排消费。2.设cr是基是基变量量xr的目的函数系数的目的函数系数 此此时， cr CB，所以，所以 cr的的变化就会影响一化就会影响一切非基切非基变量的量的检验数。数。 当当cr， =cr + 是是变化量化量时，要保，要保证在在最最终表中表中j，0，应有：有： j，cj - CB，B-1cj - CB +0，0， ， ，0B-1cj - CBB-1 arj，j arj，0 j=1,2,n) 或或 arj， j (arj，是最，是最终表中基表中基变量量xr行非零的行非零的约束系数束系数即即例例6. 知知LP问题 max z=(2+1) x1 +(3 +2) x2 s.t 2x1+2x212 4x1 16 5x215 x10 x20 试分分别分析分析1，2在什么范在什么范围内内变化化时，问题的最的最优解不解不变。解：解：1=2=0时的最的最终表表为：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/51. 当当2=0时，将，将1的的变化直接反映到最化直接反映到最终表中表中(表表2-9)。为使表中的解仍为最优解，应有为使表中的解仍为最优解，应有例：假例：假设c1=4，求新的最，求新的最优解，最解，最优值。解：将解：将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新的最新的最优解解为 X=(4，2，0，0，5)T，最最优值为 max z= 44+ 32 =226-2 资源数量资源数量bi变化的影响变化的影响 由矩阵关系式由矩阵关系式b，=B-1b和和z = CB B-1b 可可知，知，bi的的变化仅仅影响到最终表中常数项列的的变化仅仅影响到最终表中常数项列数字和目的函数值数字和目的函数值z的变化，此时，原问题检验的变化，此时，原问题检验数不受影响即对偶问题坚持可行，只需检数不受影响即对偶问题坚持可行，只需检查原问题能否可行即可。查原问题能否可行即可。例例7. 知知LP问题 max z=2x1 + 3 x2 s.t 2x1+2x212+1 4x1 16+2 5x215+3 x10 x20 分分别分析分析1，2 ,3在什么范在什么范围内内变化化时，问题的最的最优解不解不变。解：先分析解：先分析1的的变化。化。当当2 =3=0时的最的最终表表为：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 0cj 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/5cj 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要坚持上述基仍为最优基，应有：要坚持上述基仍为最优基，应有： 3+(1/2)10， 4-210解得：-612，或： 6 b114 同理可推得：-42 ，或： 12b2 -5315，或： 10b330 例：例：设b1=20，求新的最，求新的最优解，最解，最优值。解：将解：将b1的的变化直接反映化直接反映应到最到最终表中表中(1=8)。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/5203x1x3x2 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新的最新的最优解解为 X=(4，3，6，0，0)T，最最优值为 max z= 24+ 33 =176-3 添加一个添加一个变量的分析量的分析 添加一个添加一个变量相当于添加一种新的量相当于添加一种新的产品，品，能否消能否消费这种种产品关品关键是看它的是看它的检验数能否大数能否大于零。因此，分析步于零。因此，分析步骤是：是：1. 计算新增算新增变量量xj的的检验数数 j cj - CBB-12. 假假设j0 ，那么原最，那么原最优解不解不变；假；假设j 0，那么，那么转3;3. 计算算Pj，= B-1,再按再按单纯形法形法继续迭代。迭代。 例例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 ，故将有关参数反映到最，故将有关参数反映到最终单纯形表中，用形表中，用单纯形法形法继续计算。算。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新的最新的最优解解为X=(3，2，0，0，0，1)T,最最优值为max z=23+32+41=166-4 添加一个约束条件的分析添加一个约束条件的分析 添加一个约束条件，相当于增添了一道工添加一个约束条件，相当于增添了一道工序或资源限制。序或资源限制。分析步骤：分析步骤：1. 将原来问题的最优解代入这个新增的约束条将原来问题的最优解代入这个新增的约束条件之中。假设满足，那么阐明新约束条件不构件之中。假设满足，那么阐明新约束条件不构成限制，否那么转下一步；成限制，否那么转下一步；2. 将新增约束条件直接反映到最终表中，再进将新增约束条件直接反映到最终表中，再进展分析。展分析。例例9. 在第一章例在第一章例2中，增添一个中，增添一个约束条件束条件 3x1+2x214试分析最分析最优解的解的变化。化。解：解：1. 将原将原问题的最的最优解代入新解代入新约束得：束得： 33+23=15 14不不满足。足。 将新增将新增约束加上松弛束加上松弛变量量x6后写成后写成 ： 3x1+2x2+x6=14 直接反映到最直接反映到最终表中，并将基矩表中，并将基矩阵化化为单位位矩矩阵。这时，原，原问题成成为非可行解，故用非可行解，故用对偶偶单纯形法形法继续迭代。迭代。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 0cj 2 3 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/36-5 约束系数束系数aij变化的影响化的影响补 假假设xj在最在最终表中表中为非基非基变量，那么量，那么aij的的变化将使最化将使最终表中表中xj的的检验数数j发生生变化，化，假假设j0,那么用那么用单纯形法形法继续计算。算。 假假设xj在最在最终表中表中为基基变量，那么量，那么aij的的变化将使最化将使最终表中的表中的B-1发生生变化，因此有化，因此有能能够出出现原原问题和和对偶偶问题均均为非可行解的非可行解的情况，此情况，此时，须引入人工引入人工变量，将原量，将原问题转化化为可行解，再用可行解，再用单纯形法形法继续计算。算。Cj CB CN 0CBXBb XB XN 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 . 例例. 知知LP问题 max z=2x1+x2 s.t. 5x215 6x1+2x224 x1+ x25 x10 x20 最最终表表为：最最优解解为X=7/2，3/2，15/2，0，0T ,最最优值为max z=2(7/2)+1(3/2)=17/2=8.5假假设c2=3，P2 =8，4，1T,试分析最分析最优解解的的变化。化。解：解：2 = c2 - CBB-12 =30，1/4，1/28，4，1T =33/2=3/2 0 将有关参数反映到最将有关参数反映到最终单纯形表中。形表中。 对表中的第一个表中的第一个约束，可写成：束，可写成： x3+ 4x4 24x5 =9两端同乘两端同乘1，再加上人工，再加上人工变量量x6得：得： x3 4x4 24x5 x6 9用上式交用上式交换表中的第一个表中的第一个约束，得表束，得表2-19，因因5 0 ，故用，故用单纯形法形法继续迭代。迭代。新的最新的最优解解为X=11/4，15/8，0，0，3/8，0T，最最优值为max=2(11/4)+3(15/8)=89/8P80 2.10(d)第七第七节 参数参数线性性规划划灵敏度分析：研灵敏度分析：研讨使使问题的最的最优解或最解或最优基基坚持不持不变时的参数的参数值变化范化范围。参数参数线性性规划：研划：研讨线性性规划中的参数划中的参数aij，cj，bi超出灵敏度分析的范超出灵敏度分析的范围而延而延续变化化时，最最优解的解的变化情况。化情况。参数参数线性性规划要求：划要求： 当当问题中有多个参数中有多个参数变化化时，应使目的函数使目的函数z()是是的的线性函数。例如：性函数。例如：1当有多个当有多个bi值变动时，可将常数，可将常数项写写为bi=bi+i，式中，式中i可以是恣意的可以是恣意的实数；数；2当有多个当有多个cj值变动时，可将目的函数系数写，可将目的函数系数写为cj=cj+j，式中，式中j可以是恣意的可以是恣意的实数。数。求解参数求解参数线性性规划的步划的步骤：1.令令=0，求解原来，求解原来问题的最的最终单纯形表；形表；2.将参数的将参数的变化反映到最化反映到最终表中去；表中去；3.让逐逐渐添加或减少，察看原添加或减少，察看原问题和和对偶偶问题解的解的变化，看哪一个首先出化，看哪一个首先出现非可行解，非可行解，用用单纯形法或形法或对偶偶单纯形法形法继续迭代，确定迭代，确定的范的范围。例例10. 求解以下参数求解以下参数线性性规划划问题 max z()=(2+2) x1 +(3 +) x2 s.t 2x1+2x212 4x1 16 5x215 x10 x20解：解：=0时的最的最终表表为：将参数的将参数的变化反映到最化反映到最终表中表表中表2-16cj 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/5cj2+2 3+ 0 0 0CBXB b x1 x2 x3 x4 x52+203+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。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) 000x3x4x5 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。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() 为纵坐坐标，可画出，可画出z()随随变化的情况化的情况见图2-2。例例11. 求解以下参数求解以下参数线性性规划划问题 max z=2x1 + 3x2 s.t 2x1+2x212 4x1 16 5x215 + x10 x20解：解：=0时的最的最终表表为：用公式用公式b= B-1b将参数的将参数的变化反映到最化反映到最终表中表中表表2-19cj 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由表可知，当由表可知，当-515-515时为最最优基，先基，先讨论-5-5时的情况，此的情况，此时，基，基变量量x4x4 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-15-(1/5) 0 0 -1 0 -1/5cj 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时，此，此题无可行解。无可行解。 下面分析下面分析1515时的情形，此的情形，此时，基，基变量量x1x1 0 0，用，用对偶偶单纯形法迭代得表形法迭代得表2-212-21。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。例例13：知见下表，试决议：知见下表，试决议：原稿纸原稿纸（捆）（捆）日记本日记本（打）（打）练习本练习本（箱）（箱）资源限制资源限制白坯纸白坯纸（kg)30000（kg)工人工人(工日）工日） 100（工日）（工日）单位单位利润利润 2（元（元/捆）捆） 3（元（元/打）打） 1（元（元/箱）箱）1盈利最大的消费方案；盈利最大的消费方案；2假设白坯纸的供应量不变，人工不够假设白坯纸的供应量不变，人工不够时可招暂时工，工资为时可招暂时工，工资为40元元/人天，问人天，问能否招工？假设招工的话，最多招多少？能否招工？假设招工的话，最多招多少？解：解：设消消费原稿原稿纸x1捆，日捆，日记本本x2打，打，练习本本x3箱；箱；表示招工人数，那么表示招工人数，那么该问题的数学的数学模型模型为：令令 =0 =0，用，用单纯形法求得原形法求得原问题的最的最优消消费方案方案见表表2-282-28： 由于人工的影子价由于人工的影子价钱y2=5040，故招工是合，故招工是合算的。当算的。当 0时，将，将变化后的常数化后的常数项反映到最反映到最终表表中并中并继续计算，算，结果果见表表2-29。 由此可以看出，由此可以看出，该厂招工的数量最多厂招工的数量最多为200人，人，工厂利工厂利润额z()与招工数量与招工数量之之间的函数关系的函数关系见图2-4。