第03章 对偶理论.ppt

对偶理论（Dual Theory） 对偶理论是线性规划中的一种重要理论，它研究的是每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。这些问题除了在数学模型上有着对应关系外，还有密切的相关性质，以致于从一个问题的最优解完全可以得出有关另一个问题的最优解的全部信息。 3.1 线性规划的对偶问题 在线性规划问题中，每一个问题都伴随有另一个问题，称它为对偶线性规划问题。这些问题除了在数学模型上有着对应关系外，还有密切的相关性质，以致于从一个问题的最优解完全可以得出有关另一个问题的最优解的全部信息。 例如，某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表： 产品资源 A B C 资源限量Ⅰ 9 8 6500 Ⅱ 5 4 7450 Ⅲ 8 3 2300 Ⅳ 7 6 4550 单件产品利润100 80 70 设x1，x2，x3分别为产品A，B，C的产量，则线性规划数学模型为： 现在从另一个角度来考虑企业的决策问题。如果企业自己不生产产品，而将现有的资源转让或出租给其他企业，那么资源的转让价格是多少才合理？合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。 这 一决策问题可用下列线性规划数学模型来表示： 设y1，y2，y3，y4分别表示四种资源的单位增值价格（售价＝成本＋增值），总增值最低（买方期望值）可表示为： 从卖方来说，企业生产一件产品A用了四种资源的数量分别是9，5，8，7个单位，利润是100，企业出售这些数量的资源所得的利润不能少于100，即 同理，对产品B和C也有 价格不可能小于零，即有 从而企业的资源价格模型为： 产品资源 A B C 资源限量Ⅰ 9 8 6500 Ⅱ 5 4 7450 Ⅲ 8 3 2300 Ⅳ 7 6 4550 单件产品利润100 80 70 这也是一个线性规划数学模型，称这一线性规划模型是前面生产计划模型的对偶线性规划模型，这一问题称为对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。 上述两个模型是对同一个问题从不同的角度考虑的极值问题，期间有一定的内在联系，比如：约束矩阵互为转置；一个问题的常数项是另一个问题的目标函数系数；一个问题的变量个数等于另一个问题的约束条件个数，并影响其类型等。 我们把这种对应关系称为对称性对偶关系。 3.1.2 对称性对偶关系的一般形式 原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。 对称型对偶的定义： 目标函数求极大值时，所有约束条件为≤号，变量非负； 目标函数求极小值时，所有约束条件为≥号，变量非负。 分别对应 和 习惯上，我们习惯将（3.1）看做对称型对偶的原问题。 3.1.2 对称性对偶关系的一般形式 这样，用矩阵形式表示的原问题和对偶问题为： 其中，Y = (y1，y2，…，yn)，其他同前。 （3.1）和（3.3）是互为对偶的，任何一个看做原问题，另一个就是其对偶问题。 对于非对称型对偶的对应关系，我们可以通过先转换为对称型对偶，然后再进行分析，找出其规律。 最终，我们只需根据对应关系，直接写出对偶问题。 3.1 线性规划的对偶问题【例3-2】 写出下列线性规划的对偶问题。 【解】 这两个问题都是对称型对偶的形式，其对偶分别为 和， 这两个问题的对偶关系非常重要，它们之间存在着一定的对称关系，可以通过对称型对偶的定义来了解。 对偶理论在实际应用中具有非常重要的意义，它可以帮助我们更好地理解线性规划问题，并且可以提高解决问题的效率。 对偶理论是线性规划中的一种重要理论，它研究的是每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。这些问题除了在数学模型上有着对应关系外，还有密切的相关性质，以致于从一个问题的最优解完全可以得出有关另一个问题的最优解的全部信息。