40 第六章 单纯形法的灵敏度分析与对偶 • §1 单纯形表的灵敏度分析 • §2 线性规划的对偶问题 • §3 对偶规划的基本性质 • §4 对偶单纯形法 §1 单纯形表的灵敏度分析 一、目标函数中变量Ck系数灵敏度分析 1. 在最终的单纯形表里,X k是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系,所以当Ck变成Ck+ΔCk时,在最终单纯形表中其系数的增广矩阵不变,又因为Xk是非基变量,所以基变量的目标函数的系数不变,即CB不变,可知Zk也不变,只是Ck变成了Ck+ΔCk。这时δK= Ck-Zk就变成了Ck+ΔCk- Zk=δK +ΔCk。要使原来的最优解仍为最优解,只要δK+ ΔCk≤0即可,也就是Ck的增量ΔCk≤—δK。 2. 在最终的单纯形表中, X k是基变量 当Ck变成Ck+ ΔCk时,最终单纯形表中约束方程的增广矩阵不变,但是基变量的目标函数的系数CB变了,则ZJ(J=1,2,…,N)一般也变了,不妨设CB=(CB1, CB2…, Ck,…,CBm),当CB变成=(CB1, CB2…,Ck+ ΔCk,…,CBm),则: ZJ=(CB1, CB2…, Ck,…,CBm)(a’1j , a’2j ,…, a’Kj ,…, a’mj) Z’J=(CB1, CB2…, Ck+ΔCk,…,CBm)(a’1j , a’2j ,…, a’Kj ,…, a’mj) T = ZJ + ΔCk a’Kj 根据上式可知 检验数δJ (J=1,2,… ..,M)变成了δ’J,有δ’ J=CJ-Z’J=δJ+ΔCK a’Kj 。要使最优解不变,只要当J≠K时,δ’J <=0 0a'a'δMinΔC0a'a'δMaxΔCa'δΔCa'0a'δΔCa'0a'0δ'1a'0δX,a'ΔCZΔCC'ZΔCCδ'kj;0a'δ,a'δΔC,0a';0a'δ,a'δΔC,0a'δa'ΔC0,a'ΔCδkjkjjkkjkjjkkjjkkjkjjkkjkkkkkkKkkkkkkkkkkkjjkjjkkjkjjkjjkkjjkjkkjkj的变化范围为,所以可知满足的,所有小于,满足的以外的所有大于于除了要使得最优解不变,对。,可知,知是基变量,因为时,当这里时当这里时当 41 例: 目标函数:Max Z=50X1+100X2 约束条件:X1+X2≤300 2X1+X2≤400 X2≤250 X1,X2≥0 最优单纯形表如下 表6—1 我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。 这里δ3= -50,所以当c3的增量Δc3≤50,最优解不变。 再对基变量x1的目标函数的系数c1进行灵敏度分析。 在a11¡ ,a12¡ ,a13¡ ,a14¡ ,a15¡ 中 ,除 了 知 道 a11¡ 和 a13¡ 大 于 0, a15¡...