对偶问题与灵敏度分析.doc

第三章 线性规划的对偶理论与灵敏度分析3.1对偶问题的一般概念1.对偶问题的提出对偶理论是线性规划的内容之一。任何一个线性规划都有一个伴生的线性规划，称之为原规划的对偶规划问题。下面通过实例引出对偶问题，然后给出对偶线性规划的定义。对偶问题的经济意义：第一章例1提出的线性规划问题为：某工厂生产、两种型号的计算机，每生产一台型和型计算机所需的原料、工时和提供的利润以及资源的限制量如下表：资料 产品总量原料23100工时42120利润64试确定获利最大的生产方案。该问题的线性规划数学模型为：假如现在工厂自己不生产、，而将可利用的资源都出让给其他企业，试确定这些资源的最低可接受价格。最低可接受价格是指按这种价格转让资源比自己生产、合算的价格。设y1，y2为这两种资源的价格，为了使工厂出让资源合算，显然应该使出让原来生产一台的资源所得收入不低于自己生产一台产品的利润，即 ，对于产品类似，即。显然在满足这两个约束的条件下，价格越高，该工厂越合算，但价格太高，接受方面又不会愿意购买。因此，我们需要确定的价格是使工厂合算的最低价格，故应建立目标函数： 。综上所述，出让资源问题的数学模型如下： 工厂决策者所面临的两个问题的数学模型都是线性规划，它们在结构上具有某种对称性，称后一个线性规划为原规划的对偶问题。定义 称线性规划 为原线性规划的对偶 是一个行向量，它的每一个分量 称为对偶变量。例：写出下列线性规划问题的对偶问题： 解： 则 下面考虑标准形式的线性规划问题的对偶问题： 现将问题改写成等价形式 设对偶变量向量为，其中u，v均为m维行向量，因此写出它的对偶问题 令 ，则上式又可写成 其中的分量 无符号限制。即标准形式的线性规划问题的对偶问题和标准型线性规划问题的不同之处在于对偶变量 无符号限制，所以称为一对非对称的对偶问题。混合形式的对偶问题转化原问题（或对偶问题）对偶问题（或原问题）目标函数目标函数价值系数 C资源系数资源系数 b价值系数行约束的个数 m对偶变量的个数为m第i个行约束为“”第i个变量为“ ”第i个行约束为“=”第i个变量无限制原变量的个数为n行约束的个数为n第j个变量为“ ”第j行约束为“ ”第k个变量无限制第k行约束为“=”例：写出下列线性规划问题的对偶问题 解：设对应于3个约束条件的对偶变量分别为 ， 3.2 对偶问题的基本性质Th 1 （对称性定理）对偶问题（D）的对偶是原问题（L） 证： 原规划为 对偶规划为 得 得Th2 (弱对偶问题) 若和 分别是原问题和对偶问题的可行解，则 证:因为,所以，即 又因为 所以。推论1 若 和 分别是原问题和对偶问题的可行解，则 是原问题的最小值的一个下界，是对偶问题的最大值的一个上界。推论2 若原（对偶）问题可行，但目标函数无解，则对偶（原）问题不可行。推论3 若原（对偶）问题可行，而对偶（原）问题不可行，则原（对偶）问题的目标函数无界。Th3 （最优性）若 和 分别为互为对偶线性规划问题和原线性规划问题的可行解,，则，分别是原问题和对偶问题的最优解。Th4 （主对偶定理）若互为对偶的线性规划问题都有可行解，则他们都有最优解，且最优值相等。Th5 （对偶定理）若互为对偶的线性规划问题中的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。 证：设，是原问题的最优基的最优解，记则有 即 （证明Y为原问题的可行解）；再有,可得 即 (证明最优性) 知 是原问题的最优解。 可知：对偶最优解实际是原问题松弛变量检验数的相反数。 原问题最优解求得最优解的同时其对偶问题的最优解也应运而生。3.3 对偶问题的经济解释影子价格 在单纯性算法中，设,是最优解 ：最优基取则是对偶最优解。下面讨论的经济含义。设有单位增量，其它参数不b变，则： 即.所以表示在原问题已取得最优解的情况下，第种资源改变一个单位时总收益的变化值，也可以说是对第种资源的一种价格估计。这种价格估计并不是第种资源的实际价值或成本，而是由该企业在制产品的收益来估计所用资源的单位价值，称为影子价格。与具体企业有关，同一资源，产品不同，影子价格不同，企业不同，影子价格不同。利用工艺条件来估计的资源的单位价值，影子是潜在的，不是实际价格，跟在企业后面的价格估计。由于影子价格是指资源增加时对最优效益的贡献，所以，也称它为资源的机会成本或边际产品，它表示资源在最优产品组合时，具有的“潜在价值”或“贡献”。资源的影子价格是与具体的企业及产品有关的，同一种资源，在不同企业，或生产不同产品时对应的影子价格并不相同。从对偶问题引出的实例中，可以看出，影子价格也是企业出让资源的最低价格，企业按这种价格出让资源与利用这种资源自己生产所获得的收益是相等的。影子价格是经济学中的重要概念，将一个企业拥有的资源的影子价格与市场价格比较，可以决定是购入还是出让该种资源。当某种资源的市场价格低于影子价格时，企业应该买进资源，用于扩大生产；而当市场价格高于影子价格时，则企业的决策者应该将已有资源卖掉。这样获利会更多。在考虑一个地区或一个国家某种资源 地儿进出口决策中，资源的影子价格是影响决策的一个重要因素。 利用单纯形表表示求解线性规划，在求得最优解的同时，很容易得到问题的各种资源的影子价格。某种资源的影子价格，就是该资源对应的约束条件所加松弛变量在最优表中的检验数的相反数。3.4对偶单纯形法 在单纯形法中，原问题的最优解满足：（1）是基本解（2） 可行（）（3）检验数，即对偶解可行。单纯形算法是从满足（1）、（2）的一个基可行解出发，转换到另一个基可行解，一直迭代到（3）得到满足的，即对偶可行解为止。而对偶单纯形法则是从满足（1）、（3）的一个对偶可行解出发，以基变量值是否全非负为检验数，连续迭代到（2）得到满足，即原问题的基可行解为止。两种算法结果是一样的，区别是对偶单纯形法的初始解不一定可行，只要求所有检验数都非正，在保证所得解始终是对偶可行解的前提下，连续迭代到原问题的基解可行，从而取得问题的最优解。对偶单纯形法的计算步骤如下：（1）确定原问题的初始解B，使所有检验数，即是对偶可行解，建立初始单纯形表。（2）检验基变量的取值，若则已得到最优解，计算停，否则求确定单纯形表第L行对应的基变量为旋出变量。（3） 若所有,则原问题无可行解，计算停；否则，计算 确定对应的为旋出变量。（4）以为主元作（L，K）旋出变换，得新的单纯形表，转（2）。例：利用对偶单纯形法求解下述问题 解：令-12-8-16-12000-2-2-1-40100-3-2-20-401-12-8-16-12000-2-2-1-4010-123/41/21/2010-1/4-6-2-1600-3-822140-10-12-1/4-1/20-211/2-1/4-20-80-2-3-8101-441-1-121/2104-2-11/2000-4-4-2最优解， ， 多重最优解，不唯一最优解。总结：本例如果用单纯形法计算，确定初始基可行解时需要引入两个人工变量，计算量要多于对偶单纯形法。一般情况下，如果问题能够用对偶单纯形法计算，计算量会少于单纯形法。但是，对偶单纯形法并不是一种普遍算法，它有一定的局限性，不是任何线性规划问题都能用对偶单纯形法计算的。当线性规划具备以下条件时，可以用对偶单纯形法求解：（1）问题标准化后，价值系数全为负。（2）所有约束全是不等式。3.5 灵敏度分析在线性规划问题中，目标函数，约束条件的系数以及资源的限制量等都当作确定的常数，并在这些系数值的基础上求得最优解。但是实际上，这些系数或资源限制并不是一成不变的，它们是一些估计或预测的数字，比如价值系数随市场的变化而变化，约束系数随着工艺的变化或消耗定额的变化而变化，计划期的资源限制量也是经常变化的。这些系数变化，最优解会受到什么影响，最优解对哪些参数的变动最敏感？分析线性规划模型的某些系数的变动对最优解的影响，被称作灵敏度分析。灵敏度分析主要解决两个问题：1、 这些系数在什么范围内变化时，原先求出的最优解或最优基不变，即最优解相对参数的稳定性。2、 如果系数的变化引起了最优解的变化，如何用最简便的方法求出新的最优解。1、 目标函数中系数C的分析分别就非基变量和基变量的价值系数两种情况来讨论（1） 设非基变量的价值系数，有增量，其它参数不变，求的范围使原最优解不变。由于是非基变量的价值系数，因此它的改变仅仅影响检验数的变化，而对其它检验数没有影响。由于知，当时，原最优解不变。（2） 设基变量的价值系数有增量，其它参数不变，求的范围使最优解不变。由于是基变量的价值系数，因此它的变化将影响所有非基变量检验数的变化。由新的非基变量检验数：可知：当时最优解不变。已知一个例子的最优解以及最优值如下：640001002310012042016400420011/2-1/462010-1/43/800-1/2-5/4（1） 求使原最优解不变的的变化范围。（2） 若变为12，求新的最优解。解：（1）即是基变量价值系数，用非基变量的检验数与单纯形表第一行相应元素相比得： （2）即 将代入原最优表。重新计算检验数，原最优解不再是最优解，用单纯形法继续计算，结果如下：12400420011/2-1/4122010-1/43/800-1/2-5/4040021-1/2123011/201/40-20-3新的最优解：最优值2、 资源系数的分析设有增量，其它系数不变，则的变化将影响其变量所取的值，但对检验数没有影响，记新的基变量为，则，这里是原最优基逆阵的第列，如果变化后仍有，则原最优基不变。由此可知，当满足时，原最优基不变，当时， 大于取大；当时，小于取小。结果说明，的变化范围是由原基变量的相反数与的第列元素的比值所确定。如果不在上述范围变动，则变化后的基变量所取值可定会出现负变量，但由于不影响检验数的变化，因此可以用取代原最优解，以该解为初始解，用对偶单纯形法继续求解。已知线性规划问题的初始解及最优解，见下表：（1） 求得范围，使原最优基不变。（2） 若变为200.试求新的最优解。640001002310012042016400420011/2-1/462010-1/43/800-1/2-5/4解：（1）， 用基变量的负值与的第一行相应的元素去比，原最优基不变。（2）不是可行解，须用替代原最优表中的值，并采用对偶单纯形法求解。6400470011/2-1/46-510-1/43/800-1/2-5/44602101/2020-401-3/2-200-2最优解最优值3、 系数矩阵的分析分四种情况讨论：（1） 增加一个新变量的分析设是新增加的变量，其对应的系数列向量，价值系数为，试讨论原最优解有无改变，及如何尽快地求出新的最优解。如果原问题增加一个新变量，则系数矩阵增加一列，新增加的列在以为基的单纯形表中应为，所以可先计算及，若，则原最优解不变。反之可将增添列原最优表的后面，用单纯形法继续迭代。例：设在已求解得原线性规划问题中考虑生产型计算机，已知生产每台型计算机所需原料4个单位，工时3个单位，可获利8个单位。试问该厂是否应该生产型计算机，如果生产，应该生产多少。解： 设产生型计算机台，由原最优基的可得：得因为，所以安排生产型计算机有利，将增添到原最优表的后面，并用单纯形法继续计算，结果如下：64008420011/2-1/45/462010-1/43/81/800-1/2-5/49/481604/52/5-1/516181-1/10-3/102/500-9/8-7/5-4/50最优解最优基（2） 增加一个约束条件的分析设是新增加的约束条件，试分析原问题的最优解有无变化。将原最优解代入新约束中，如果满足新的约束条件，则原最优解不变，反之，则需要进一步求出新的最优解。考虑到单纯形算法中，每步迭代得到的单纯形表对应的约束方程组等价，因此，可以将新的约束方程增添到原最优表的下面，变化后的单纯形表增加一行和一列，新约束对应的基变量，在单纯形表中，由于增加了新的约束，原基变量对应的列向量可能不再是单位列变量，所以需要用初等行变换将表中基变量对应的列向量变为单位列向量。变换后，原最优表的检验数不变，但基变量的值一般要变。若，则获得最优解；反之，若，则用对偶单纯性形法继续求解。例：设在原线性规划问题中增加一道工序，需要在另一台设备上进行。已知、型产品在该设备上加工工时分别为2、3个单位，计划期内该设备总台时为90单位，试分析原最优解有无变化，如果有变化，求出新的最优解。、解：新工序的对应的约束条件为，将原问题最优解代入该约束条件左端，显然不满足约束条件，因此原最优解不再是最优解。将增添到原最优表的下面，用初等行变换及对偶单纯形法计算，结果如下：64000420011/2-1/4062010-1/43/800902300100-1/2-5/40415010-1/41/2622. 51003/8-1/40100010-1000-5/4-1/2最优解最优值3改变某非基变量的系数列向量的分析设非基变量的系数列向量变为，试分析原最优解有何变化。该变化只影响最优单纯形表的第列及检验数。因此，可以先计算，若，则以代替原最优表中的第列，用单纯形法继续计算。、4、 改变某基变量的系数列向量的分析设基变量的系数列向量变为，试分析原最优解有何变化。显然，的变化将导致的变化，似乎只能重新计算变化后的模型。但是，经过认真分析，还是可以利用原最优解计算新最优解的。我们可以将看作新增加的变量，用替代原最优解的第列（单位列向量），然后再