第三章 线性规划的对偶理论及灵敏度分析.doc

第三章 线性规划的对偶理论及灵敏度分析主要内容：1、对偶问题及其性质； 2、对偶单纯形法； 3、灵敏度分析。重点与难点：对偶问题与原问题的对应关系，对偶问题的基本性质，对偶单纯形法的求解步骤，灵敏度分析的方法。要 求：理解线性规划对偶问题的性质，熟练掌握对偶单纯形法的求解步骤和灵敏度分析的方法和技巧，能够用这些数学方法解决实际问题。1 对偶问题的对称形式一、对偶问题引例，某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备台时及A、B两种原材料的消耗，该工厂每生产一件产品甲可获利2元，每生产一件产品乙可获利3元，问应如何安排计划才能使该工厂获利最多？甲乙设备原材料A原材料B1402048台时16kg12kg解：设、分别为甲、乙两种产品的产量则目标函数 约束条件 (1) 假设该工厂决定不再生产甲、乙产品，而将其出租或出售。这时要考虑每种资源的定价问题，设分别为出租单位设备台时的租金和出让单位原材料A、B的附加额。 作一比较：若用一个单位台时和4个单位原材料A生产一件产品甲，可获利2元，那么生产每件产品甲的设备台时和原材料出租和出让的收入应不低于生产一件甲产品的利润。即： 同理，将生产每件乙产品的设备台时和原材料出租和出让的收入应不低于生产一件乙产品的利润。即： 将工厂所有设备台时和资源都出租和出让，其收入为 对工厂来说，越大越好；但对接受者来说，支付的愈少愈好，所以工厂只能在满足所有产品的利润前提下，使其总收入尽可能小，才能实现其愿望。为此，得到如下模型：(2)我们就称(2)为模型(1)的对偶问题。一般地，设原问题为 则其对偶问题为： 矩阵形式：原问题 对偶问题 二、原问题与对偶问题的关系原问题（或对偶问题）对偶问题（或原问题）目标函数max z目标函数min变量n个00无约束n个=约束条件约束条件m个=m个00无约束变量约束条件右端项目标函数变量的系数目标函数变量的系数约束条件的右端项例1 求下列问题的对偶问题解：2 对偶问题的基本性质一、对称性：对偶问题的对偶是原问题。证：设原问题为 则其对偶问题为： 对上式两边取负号，得 上式的对偶问题为 （两边同取负号）二、弱对偶性：若是原问题的可行解，是对偶问题的可行解，则存在。证：是原问题的可行解有 已知是对偶问题的可行解，用左乘上式得 同理，用右乘之得,故三、无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。 注意：此性质不可逆。四、可行解是最优解时的性质最优性：设是原问题的可行解，是对偶问题的可行解，当时，、是最优解。五、对偶定理（强对偶性）：若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。反之，若其一无最优解，则另一也无最优解。六、互补松弛性：若、分别是原问题和对偶问题的可行解，那么和，当且仅当、为最优解。证：设原问题和对偶问题的标准型是 将分别代入原问题和对偶问题目标函数得，若；则由性质4知，、为最优解。又如果、为原问题和对偶问题的最优解，由性质4有即必有例2 已知线性规划问题试用对偶理论证明上述线性规划问题无最优解。证：原问题存在可行解，如上述问题的对偶问题为由第一个约束条件知，对偶问题无可行解，所以，由对偶定理知，原问题无最优解。七、对偶问题的经济解释-影子价格 由对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等，即有求z对b的偏导数得： 即 其经济学意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。 的值代表对第i种资源的估价，这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。影子价格随具体情况而异，在完全市场经济条件下，当某种资源的市场价格低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价格高于企业影子价格时，则企业应把已有的资源卖掉。可见，影子价格对市场有调节作用。3 对偶单纯形法一、基本思路 对偶单纯形法是运用对偶原理求解原问题的一种方法，而不是求解对偶问题的单纯形法。 首先讨论这样一个问题：设原问题：则其对偶问题：化为标准型： 设B是原问题的一个可行基，于是A=(B|N)，原问题可改写为：相应地对偶问题可以表示为min这里-对应原问题中基变量的剩余变量-对应原问题中非变量的剩余变量当求得原问题的一个基解，其相应的检验数为与。现分析这些检验数与对偶问题的解之间的关系：令代入(1)、(2)得由此可得出：原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如下：0说明：在单纯形表中若在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解，当在检验数行得到对偶问题的解也是基可行解时，根据性质知，已知到最优解，即原问题与对偶问题是最优解。根据对偶问题的对称性，可这样考虑：若保持对偶问题的解是基可行解，即，而原问题在非可行解的基础上，逐步迭代达到基可行解，这样也得到了最优解。方法是：设原问题 设B是一个基，令，它对应的变量为 当非基变量都为零时，可以得到，若在中至少有一个负分量，设，并且在单纯形表的检验数行中的检验数都为负值，即对偶问题保持可行解，它的各分量是：1.对应基变量的检验数是2.对应非基变量的检验数是： 每次迭代是将基变量中的负分量取出，去替换非基变量中的，经基变换，所有检验数仍保持负值，原问题逐步由非可行解向可行解靠近，当原问题得到可行解时，便得到了最优解。二计算步骤(1)列出初始单纯形表，若所有，则停止计算，已得到最优解。若b中含有负元素，则需继续计算。(2)确定换出变量，基变量为换出变量。(3)确定换入变量 检查行的系数，若所有0，则无可行解，停止计算。若存在0，说明生产丙产品是有利的。（2）计算丙产品在最终表中对应的列向量并将（1）、（2）的计算结果填入最终表：230005b24101/41/403/20400-221/21232011/2-1/801/4-1.5-1/81.2521103/2-1/8-3/405200-11/41/2131.5013/4-3/16-1/80-1/4-7/16-5/8由于b列的数字无变化，原问题的解是可行解，但，说明目标函数值还可改善。（3）将作为换入变量，作为换出变量，进行运算求最优解（见上表）。这时最优解；总利润为16.5元，比原计划增加了2.5元。例7、 分析原计划生产产品的工艺结构发生变化。在引例中，若原计划生产甲产品的工艺结构有了必改进，这时有关它的技术系数向量，每件利润4元，试分析对原最优计划有什么影响？解：设改进后的甲产品产量为，那么对应的列向量为检验数将上述结果填入最终表的列向量位置得：43000b445/4001/40041/20-21/21323/811/2-1/803/8-3/2-1/843.21000.2002.400-20.4130.8010.5-0.20-1.5-0.2从表中可看出，原问题和对偶问题的解都是可行解，所以表中的结果已是最优解，即应生产甲产品3.2单位，生产乙产品0.8单位,可获利15.2元。注：若原问题和对偶问题均为非可行解时，需要引进人工变量后重新求解。例8、 增减约束条件的分析。已知下列线性规划问题其最终单纯形表： 98501900b19224/3012/3-10/3501-1/2-1/310-1/64/3-4-2/3-13/310/3如果在上述问题中增加约束条件试分析对原最优解有何影响？解：将原最优解代入新增约束条件检验：须将该约束条件引入单纯形最优表继续迭代。加入松弛变量，新增约束条件变为与原约束方程联立，消去得用对