文档详情

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

发布:2016-10-22约1万字共15页下载文档
文本预览下载声明
第三章 对偶线性规划问题 §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
显示全部
相似文档