广西大学MBA 管理运筹学 第六章 单纯形法的灵敏度分析与对偶

广西大学 MBA 课件 管理运筹学

第六章 单纯形法的灵敏 度分析与对偶

§6.1、单纯形表的灵敏度分析 §6.3、对偶单纯形法 这一章里只讲§6.2、线性规划的 对偶问题。

§6.2、线性规划的对偶问题

广西大学 MBA 课件 管理运筹学

§1.单纯形表的灵敏度分析 一、目标函数中变量系数Ck 灵敏度分析 1.在最终的单纯形表里，xk 是非基变量。 在这种情况下，由于约束方程系数增广矩阵在迭代 中只是其本身的行的初等变换与 Ck 没有任何关系，所 以当Ck 变成Ck+△Ck 时，在最终单纯形表中其系数的增 广矩阵不变，又因为xk 是非基变量，所以基变量的目标 函数的系数不变，即CB不变，可知Z K也不变，只是Ck 变成了Ck+△Ck 。这时σK=CK –Zk 就变成了Ck+△Ck – Zk=σK+ Ck 。要使得原来的最优解仍为最优解，只要 σK+ Ck ≤0即可，也就是Ck的增量 CK≤-σK 即可。

广西大学 MBA 课件 管理运筹学

2.在最终的单纯形表中，XK是基变量。 当CK变成Ck+△Ck时，同上一样，可知在最终的单纯形表中的 约束方程的增广矩阵不变，但是基变量在目标函数中的系数CB 变了，则Zj (j=1,2,…,n)一般也变了，不妨设CB=(CB1,CB2,…, CK, …,CBm) , 当CB 变成 (CB1,CB2,…,( CK+ Ck) , …,CBm) , 则：

′ j , a2 j ,..., akj ,..., amj )T 变成了: ′ ′ z j = (cB1, cB 2 ,..., cK ,..., cBm )(a1 ′ ′ ′ ′ ′ z′j = (cB1, cB 2 ,..., (cK + ck ),..., cBm )(a1 j , a2 j ,..., akj ,..., amj )T ′ ′ ′ ′ = cB1a1 j + cB 2a2 j + ... + (cK + ck )akj + ... + cBm amj ′ ′ ′ ′ ′ = cB1a1 j + cB 2a2 j + ... + cK akj + ... + cBm amj + ck akj ′ = z j + ck akj . ′ ′ 这样检验数σ ′j = c j z′j = c j z j + ck akj = (c j z j ) + ck akj ′ = σ j + ck akj

广西大学 MBA 课件 管理运筹学

要使最优解不变, 只要当j ≠ k时,σ ′j ≤ 0, 也就是 : ′ ′ σ ′j + ck akj ≤ 0, ck akj ≤ σ ′j , σ j σ j 当a′kj > 0, ck ≤ , 这里 ≥ 0; a′kj a′kj σ j σ j 当a′kj < 0, ck ≥ , 这里 ≤ 0; a′kj a ′kj ′ ′ 而当j = k时,σ k = ck + ck zk = ck + ck zk ck a′ , KK ′ ′ 因为xk 是基变量, 知σ k = 0, akk = 1, 故知σ k = 0. 这也就是说，要使最优解不变，对于除了akk′ 外的所 有的大于零的akj′,Ck的增量△Ck 都要小于等于 –σj / akj′ , 对于所有小于零的akj′ , Ck都要大于等于–σj / akj′ 。我 们用数学式表示使得最优解不变， C 的变化范围为： σ j σ j ′ ′ max akj < 0 ≤ ck ≤ min akj > 0 akj akj ′ ′

广西大学 MBA 课件 管理运筹学

以第2章例1为例在最终的单纯形表上对b 进行灵敏度分析。 以第2章例1为例在最终的单纯形表上对bj进行灵敏度分析。 max Z=50X1+100X2, X1+X2≤300, 2X1+X2≤400, X2≤250, X1≥0, X2≥0. 此题在第五章里，已得到最终

单纯形表为： 目标函数： 约束条件：

迭代 次数

基变 量 CB x1 S2 x2 zj σj=cj-zj 50 0 100

x1 50 1 0 0 50 0

x2 100 0 0 1

s1 0 1 -2 0

s2 0 0 1 0 0 0

s3 0 -1 1 1 50 -50 b 50 50 250Z= 27500

2

100 50 0 -50

广西大学 MBA 课件 管理运筹学

先对非基变量s 的目标函数的系数C 先对非基变量 1的目标函数的系数 3进行灵敏度 分析。这里σ 分析。这里 3=-50,所以当 3 的增量 3≤-(-50)即 ，所以当C 的增量 C 即 C3≤50时，最优解不变，也就是说 1的目标函数的系数 时 最优解不变，也就是说S C′3=C3+△C3≤0+50=50时，最优解不变。 △ 时 最优解不变。 再对基变量x 的目标函数的系数C 进行灵敏度分析。 再对基变量 1的目标函数的系数 1进行灵敏度分析。′ ′ ′ ′ ′ ′ ′ ′ 在a11, a12 , a13, a14 , a15中, 知道除了a11外有a13 > 0, a15 < 0, σ j σ 3 50 ′ 可知, = = 50, 有 min a1 j > 0 = min{50} = 50, a13 1 a1 j ′ σ j σ5 50 ′ 同样有: max a1 j < 0 = max = max( ) = 50, 1 a1 j a15 ′ ′ 这样可知当 50 ≤ C1 ≤ 50时, 也就是x1的目标函数c1有 : ′ ′ 50 50 ≤ c1 = c1 + c1 ≤ 50 + 50,即0 ≤ c1 ≤ 100的最优解不变 .

也可以按以下方法来计算出使最优解不变的C′1的变化范围。

广西大学 MBA 课件 管理运筹学

在最终的单纯形表中， 代替原来的C 计算得表如下： 在最终的单纯形表中，用C′1代替原来的 1=50计算得表如下： 计算得表如下 迭代 次数 基变 量 CB x1 S2 x2 zj σj=cj-zj C′1 0 100 x1 x2 C′1 100 1 0 0 C′1 0 0 0 1 s1 0 1 -2 0 0 0 s2 0 0 1 0 s3 0 -1 1 1 -C′1+100 C′1- 100 b 50 50 250

2

100 C′1 0 - C′1

从σ3≤0,得到-C′1≤0,即C′1≥0,并且从σ5≤0, 得到C′1-100≤0,C′1≤100。 从上两式可知：当0≤C′1≤100 时最优解不变，如果采取了不 属于这范围的C′1,必存在某个检验数σj>0,我们可以继续用 单纯形表进行迭代，以求出新的最优解。

广西大学 MBA 课件 管理运筹学

用最终单纯形表对Cj 进行灵敏度分析，求得使最 优解保持不变的C1, C3变化范围与我们在第三章里用计算 机求解所得的结果是一样，其实管理运筹学软件就是按 这种方法进行编程，对Cj 进行灵敏度分析的。二、约束方程右边常数灵敏度分析 我们在第三章对线性规划问题的计算机求解中，也曾经对 约束方程右边常数bj 进行了灵敏度分析，根据计算机输出的 表格，可知道，约束方程右边常数在什么范围内变化时，其 对偶价格不 …… 此处隐藏：4722字，全部文档内容请下载后查看。喜欢就下载吧 ……