第二章线性规划的对偶理论与灵敏度分析一、学习目的与要求 1、掌握对偶理论及其性质 2、掌握对偶单纯形法3、熟悉灵敏度分析的概念和内容4、掌握限制常数与价值系数、约束条件系数的变化对原最优解的影响5、掌握增加新变量和增加新的约束条件对原最优解的影响，并求出相应因素的灵敏度范围6、了解参数线性规划的解法 二、课时 6学时第一节 线性规划的对偶问题一、对偶问题的提出定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题，在求出一个问题的解时，也同时给出了另一问题的解。
应用：在某些情况下，解对偶问题比解原问题更加容易；对偶变量有重要的经济解释(影子价格)；作为灵敏度分析的工具；对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解)；避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量)。
例：某家具厂木器车间生产木门与木窗；两种产品。
加工木门收入为56元/扇，加工木窗收入为30元/扇。
生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。
问：(1)该车间应如何安排生产才能使每日收入最大？(2)假若有一个个体经营者，手中有一批木器家具生产订单。
他想利用该木器车间的木工与油漆工来加工完成他的订单。
他就要考虑付给该车间每个工时的价格。
他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。
解(1)：设该车间每日安排生产木门x1扇，木窗x2扇，则数学模型为⎪⎩⎪⎨⎧≥≤+≤++=-0502120343056max 21212121x x x x x x x zX*=(15,20)’ Z*=1440元解(2)：设y 1为付给木工每个工时的价格，y 2为付给油工每个工时的价格⎪⎩⎪⎨⎧≥≥+≥++=-0303562450120min 21212121y y y y y y y wY*=(2,24)’ W*=1440元将上述问题1与问题2称为一对对偶问题，两者之间存在着紧密的联系与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同。
第二章线性规划的对偶理论4-灵敏度分析是指对系统或事物因周围条件变化显示出来的敏感程度的分析。
以前在线性规划问题中，都假定问题中的a ij ，b i ，c j 是已知数。
但实际上这些数往往是一些估计和预测的数据，如c j 随市场条件的改变而改变；a ij 随工艺条件的改变而改变；b i 则是根据资源投入后能产生多大经济效果来决定的一种决策变量。
当这些参数中的一个或几个变化时，问题的最优解会有什么变化，或者这些参数在一个多大的范围内变化时，问题的最优解不变。
这就是灵敏度分析所要研究解决的问题。
第二章对偶理论与灵敏度分析2.4 灵敏度分析C N -C B B -1N -C B B -10c j -z j B -1N B -1I C B X B B -1b X N X s X B非基变量基变量当B 为最优基时，上表检验数行应≤0灵敏度分析的步骤可以归纳如下：1.将参数的改变计算反映到最终单纯形表上来：△b /=B -1△b △P /j =B -1 △P j (c j -z j ) /= c j -∑=*m i iij y a12. 检查原问题是否仍为可行解3. 检查对偶问题是否仍为可行解4. 按下表所列情况得出结论和决定继续计算的步骤原问题对偶问题结论或继续计算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表重新计算一、分析c的变化j的变化二、分析bi的分析三、增加一个变量xj的变化四、分析参数aij五、增加一个约束条件的分析、分析c j 的变化例：在最初讲的第一个例子中，（1）若甲种产品的利润降至1.5元/件，而乙的利润增至2元/件时，该公司的最优生产计划有何变化；解：(1) 将甲、乙的利润变化直接反映到最终单纯形表中得下表c j1.52000C B基b x 1x 2x 3x 4x 50x 315/20015/4-15/21.5x 17/21001/4-1/22x 23/2010-1/43/2c j -z j 0001/8-9/4[ ]例一c j →21000C B基b x 1x 2x 3x 4x 50x 315051000x 424620100x 5511001c j -z j →210000x 315051002x 1412/601/600x 5102/30-1/61c j -z j →01/30-1/300x 315/20015/4-15/22x 17/21001/4-1/21x 23/2010-1/43/2c j -z j →000-1/4-1/2[ ][ ]最优解为X = (2/7, 2/3, 15/2, 0, 0)T ，代入目标函数得z = 8.5。
