第3章 LP的对偶问题与灵敏度分析,§1 原问题与对偶问题 §2 对偶问题基本性质 §3 对偶单纯形法 §4 灵敏度分析,§1 原问题与对偶问题,大自然中任何事物之间的关系均可以用阴阳八卦的思想来理解，有着生生相克的特性一件事物有正面，还有反面；有积极作用，还有消极作用对偶问题正是如此！,阴阳机器厂在计划期内生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需设备A、B、C台时如下：,该工厂每生产一单位产品Ⅰ可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应该怎样安排生产，才能获利最多？,设产品Ⅰ的计划产量为x1，产品Ⅱ的计划产量为x2， 则有线性规划问题LP1：,目标函数： 约束条件：,现假定有另一八卦机器厂，该厂的规模较小一些，想租用阴阳厂的设备进行生产那么阴阳厂的领导应该给自己的设备制定一个怎样的出租价格呢？,设出租设备A、B、C的价格分别定为 y1、y2、 y3该问题可从两个角度进行分析： 对于阴阳厂，总租金应当不低于原利润： 生产产品Ⅰ所需设备台时不应当低于原利润： 生产产品Ⅱ所需设备台时不应当低于原利润： 对于八卦厂，希望支付的总租金最少，即：,因此可以建立另一线性规划问题LP2：,目标函数： 约束条件：,在这种情况下，我们称LP1、LP2互为对偶问题，即一个为原问题，另一个则为对偶问题。
原问题 对偶问题,,用矩阵形式，可表达为：,原问题 对偶问题,,在上例中，原问题与对偶问题的矩阵形式可以写作：,原问题 对偶问题,,二者之间的关系：,原问题中求目标函数极大化问题，对偶问题中求目标函数极小化问题 原问题中约束条件的个数等于对偶问题中变量的个数 原问题约束条件中符号为 号，对偶问题中约束条件符号为 号 原问题目标函数的系数是其对偶问题约束条件的右端项可用如下表格来表示：,,例1：写出下述线性规划问题的对偶问题,解：第一步：将5x1-3x2+x3 =200转换成： 5x1-3x2+x3≥200 和 5x1-3x2+x3≤200, 然后将所有的约束条件写成≤（≥亦可），有,第二步：令与上式中四个约束条件对应的对偶变量分别为y1,y2,y3’,y3’’(因为它俩来自于同一个约束条件），则有对偶问题：,第三步：再令y3=y3’-y3’’，则有最终的对偶问题：,例2：写出下述LP的对偶问题：,按照上述三个步骤，求得其对偶问题为：,原问题与对偶问题互化关系表：,,,,,§2 对偶问题的基本性质,化标准形：,,设有LP问题：,,不违背一般，设B是一个可行基，与B相应，做矩阵分块如下：,一、单纯形法的矩阵描述,,式（1），（2）可表示为：,,即：,,式（5）两端左乘B-1得：,由式（6）得：,带入式（4）得： 由式（8）得单纯形法的最优性条件为：,,,二、单纯形表的矩阵结构,由（7），（8）可构造单纯形表：,三、对偶规划与原规划最优解的关系,当原问题得到最优解时，必有：,,,令： ，上式等价为：,,可知这是对偶规划的一个可行解,,且此时： ，可见对偶规划与原规划最优解的目标函数值相等，不是偶然的。
四、由原规划最终单纯形表确定对偶规划最优解,考察单纯形表结构，可在原规划得到最优解时，同时直接得到对偶规划最优解，这已经是明确的问题 并且由： 还可发现对偶问题的最优解y= 实际是原问题松弛变量的检验数的相反数举例,MAX 50x1+100x2+0s1+0s2+0s3. S.T. x1 + x2+ s1+ 0s2+ 0s3=300, 2x1 + x2+ 0s1+ s2+ 0s3=400, 0x1 + x2+ 0s1+ 0s2+ s3=250, x1,x2,s1,s2,s3≥0,Lindo求解对偶问题,min 300y1+400y2+250y3 st y1+y2=50 y1+y2+y3=100 end,五、对偶问题基本性质,§3 对偶单纯形法,单纯形法是在保持原问题的所有约束条件的常数大于等于零的情况下，通过迭代，使得所有的检验数都小于等于零，最后求得最优解 对偶单纯形法则是在保持原问题的所有检验数都小于等于零的情况下，通过迭代，使得所有约束条件的常数都大于等于零，最后求得最优解 优点： 初始解可以是非可行解； 对于一些大于等于号约束条件可以不添加人工变量，只需把两边同乘以-1，化成小于等于约束。
缺点： 不是所有初始解其检验数都小于等于零在单纯形法中，原问题的最优解满足：,对偶单纯形法计算步骤如下：,例1 已知线性规划问题 试分析λ1和λ2分别在什么范围内变化时，问题的最优解不变§4 灵敏度分析,,一、目标函数中系数Cj的灵敏度分析,分析：此例中目标函数的系数cj的变化仅仅影响到检验数σj的变化，所以将Cj的变化直接反映到最终单纯形表中解：当λ1=λ2=0时，上述LP问题的最终单纯形表如上表所示 （i）对基变量x1的目标函数系数进行灵敏度分析：将λ1的变化反映到最终单纯形表中：,表中的解仍为最优解的条件是：-1-1/2λ1≤0 -1/5+1/5λ1≤0 故有-2≤λ1≤1时，该LP问题的最优解不变ii）类似的可以得到，其他条件不变的情况下，λ2≥-1时，该LP问题的最优解不变2/5+1/5（3+ λ2 ）,,,二、约束条件右端常数项bi的灵敏度分析,例2 LP问题,分别分析右端常数项在什么范围内变化时，最优基不变分析：原问题的最终单纯形表如下为，,右端常数项的灵敏度分析： （i）,使问题最优基不变的条件是,,,（ii）类似的，使问题最优基不变的第二个约束条件右端常数项的变化范围是： λ2≥-50 (iii）同样，-50≤λ3≤50 即200≤250+λ3≤300时，对偶价格不变，原问题的最优基不会发生变化。
三、增加一个量的灵敏度分析,实际中，增加一个变量的计算步骤如下： （1）计算 ; （2）计算 ； （3）若 ，只需将 和 的值直接反映到最终单纯形表中，原最优解不变； 若 ，则按单纯形法继续迭代计算例3 在例1中，若增加一个变量x6，有c6=4，P6=(2,4,5)T，试分析问题的最优解的变化 解：,,,代入最后一张单纯形表中，有,16,例5：某工厂计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原料的消耗，以及资源的限制，如下表所示：,该工厂每生产一单位产品Ⅰ可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少个Ⅰ产品和 Ⅱ产品才能使工厂获利最多？,补充（约束方程系数矩阵A灵敏度分析）,该问题的数学模型为：,OBF: MAX 50x1+100x2. S.T. x1+x2 300, 2x1+x2 400, x2 250 xj 0,其最终单纯形表如下：,现假设该厂除了生产Ⅰ、Ⅱ产品外，现试制成一种新产品Ⅲ，已知生产产品Ⅲ，每件需要设备2台时，并消耗A原料0.5公斤，B原料1.5公斤，获利150元，问该厂是否应该生产该产品和生产多少？,解：显然x3是非基变量。
主要来计算x3的检验数经过初等行变换，x3所在列的系数变成：,新单纯形表如下：,假设上例题中产品Ⅲ的工艺结构有了改进，这时生产1件产品Ⅲ需要设备1.5台时，并消耗A原料2公斤，B原料1公斤，获利160元，问该厂的原生产计划是否需要修改？,解：x3所在列的系数变成：,新单纯形表如下：,,,,,2、在初始单纯形表上的变量xk的系数列pk改变为pk’，经过迭代后，在最终单纯形表上xk是基变量这时一般需要重新进行计算1、在初始单纯形表上的变量xk的系数列pk改变为pk’，经过迭代后，在最终单纯形表上xk是非基变量四、增加一个约束条件的分析,增加一个约束条件以后，必须验证该约束条件是否对最优解起作用，方法是将原问题的最优解变量的取值代入新增的约束条件中，如满足，说明新增加的约束条件未起作用；否则，须将新增约束条件直接反映到最终单纯形表中进行迭代运算 例4 在例1中，增加一个约束条件3x1+2x2≤14，分析最优解的变化 解：因有3×3+2×3=1514，说明增加的约束条件有限制作用，将其添加到松弛变量后的方程3x1+2x2+x6=14反映到单纯形表中，并继续进行行初等变换，将P1，P4，P2，P6化成单位向量，并用对偶单纯形法迭代，结果如下：,,1/5,。