数学建模第一篇第三章解析.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
显示全部