数学建模第一篇第三章解析.doc

第三章 对偶线性规划问题 §1-3-1对偶线性规划问题 例1 某工厂生产甲、乙、丙三种产品，使用两种主要原料A和B，已知生产每单位产品需要原料数、现有原料树以及每单位产品价格如表1-3-1。问：应如何安排生产，可使总产值最大？ 表1-3-1 生产计划问题的数据 产品 原料 甲 乙 丙 现有原料 原料A 4 3 6 120公斤 原料B 2 4 5 100公斤 单位价格（元） 4 5 3 解：设分别表示甲、乙、丙三种产品的产量，则可建立线性规划数学模型： （1.3.1） 现工厂的决策者决定除了生产甲、乙、丙三种产品以外，如果合适的话，可以考虑将这两种原料出售，那么对于购买者来说，尽可能以较低的价格购买，又使得工厂接受，这时A、B的价格应分别是多少？ 设原料A、B的价格分别为，则合理的定价应满足线性规划问题： （1.3.2） 我们称线性规划问题（1.3.2）为线性规划问题（1.3.1）的对偶线性规划问题。 一般地，给定线性规划问题： （LP） 即（LP） 与线性规划问题 （DLP） 即（DLP） 其中，，， ，。 称这两个线性规划问题为互为对偶的线性规划问题，其中一个称为原问题，另一个称为它的对偶问题。 我们引进表达这一对互为对偶的线性规划问题的对偶表，表1-3-2。 表1-3-2 对偶表 … 约束条件 minW … ≤ … ≤ … … … … … … … … ≤ 约束条件 ≥ ≥ … ≥ maxS … 定理1.3.1 若线性规划问题（LP）中第k个约束条件是等式，那么它的对偶线性规划问题（DLP）中的第k个变量无非负限制。反之亦然。 线性规划问题与其对偶问题的对偶关系如表1-3-3所示。 表1-3-3 线性规划问题与其对偶问题之间的关系 原问题（或对偶线性规划问题） 对偶线性规划问题（或原问题） 1 求目标函数的最大值 求目标函数的最小值 2 有个不等式 有个非负变量 3 有个非负变量 有个不等式 4 目标函数的系数 约束条件右端常数 5 约束条件右端常数 目标函数的系数 6 第k个约束条件是等式 第k个变量没有非负限制 7 第个变量没有非负限制 第个约束条件是等式 例2 写出下述线性规划问题的对偶线性规划问题 解：首先将线性规划问题写成标准形式： 则其对偶线性规划问题为： §1-3-2 对偶变量的经济意义——影子价格 例1中原问题所述的是如何利用有限资源安排生产方案，以获得最大产值的线性规划问题，而它的对偶线性规划问题却是用来描述如何在相同资源的条件下，正确估价资源的使用价值以达到支付最少费用的问题。这是从两个不同的角度来讨论有限资源的最优配置问题。 对于两种资源A、B来说，市场上有它们的价格，但不是它们的使用价值。它们的使用价值要通过生产各种产品等经济活动来实现。在工厂现有资源的条件下，安排最优生产计划使总产值达到最大。若在其他条件不变动条件下，增加某种资源1单位，这时最优生产计划随之改变，最终可使总产值增加。这个增加值就反映了这种资源的边际价值，也称为影子价格（Shadow Price）或对偶价格（Dual Price）。 这种影子价格不同于市场价格，它主要反映了在这个经济系统中该种资源的稀缺程度。若在最优计划的条件下，某种资源过剩，则增加投入也不会使总产值增加，这时该种资源的影子价格为0；若某种资源稀缺，成为扩大生产规模的制约因素，则增加该种资源的投入，就会使总产值增加，该种资源的影子价格就大于0。可见，一种资源的影子价格应与所处的经济系统有关。如例1中原问题（1.3.1）： 则其对偶线性规划问题（1.3.2）为： 这两个线性规划问题都存在最优解和，且使得。 对偶线性规划问题的最优解：。这说明对偶线性规划问题的最优解是对应资源的边际价格——影子价格（Shadow Price）。 对于对偶线性规划问题（1.3.2）的最优解为，，。，两种资源的影子价格。用LINGO10.0求解两个互为对偶的线性规划问题的结果如下: Max=4*x1+5*x2+3*x3; 4*x1+3*x2+6*x3120; 2*x1+4*x2+5*x3100; 输出结果： Objective value: 152.0000 Total solver iterations: 2 Variable Value Reduced Cost X1 18.00000 0.000000 X2 16.00000