对偶变量表示i种资源每增加单位对目标函数的贡献对偶变量.ppt

Ø 对偶变量表示第 i 种资源每增加一单位对目标函数 的贡献Ø 对偶变量已被赋予各种名称，如影子价格、边际投 入、边际效益等Ø 对偶变量在实用中远比最优解重要和有趣原因在 于绝大多数公司都希望改善他们的现状，LP问题的最 优解（z*和x*）只能告诉他们在目前情况下如何最好 地分配他们的资源，而对偶变量为公司提供了增加利 润和挖潜革新的信息（当人们知道如何解释它们的含 义时）对于线性规划的最大值问题，都相应存在着一个特定的包含同样数据的最小值问题： 一个方面是在一定的资源条件下，如何最合理地规划使用这种资源，使得完成的任务量最大； 另一个方面是根据已确定的任务如何规划使用资源，使得消耗的资源为最少 这样的问题可以看作是从两个不同角度对同一个问题所进行的分析与研究，是根据同样的条件与数据 所构成的两个问题；它们之间的关系是相对的，通常 称一个问题是另一个问题的对偶问题某工厂在计划期内要安排生产甲、乙两种产品 已知制造甲产品需要A型配件5个、B型配件3个；制 造乙产品需要A型配件2个、B型配件4个 而在计划期内该工厂只能提供A型配件180个，B 型配件135个又知道该工厂每生产一件甲产品可获 利润20元，一件乙产品可获利润15元。

问在计划期内甲、乙产品应该各安排生产多少 件，才能使总利润最大? 【例 原问题】设x1、x2分别表示生产甲、乙产品的件数，Z表示 总利润，则原问题模型如下： 最优解的目标函数值为787.5现在换个角度考虑，假如有人想购买该工厂的这180个单位A型配件和135个单位B型配件，那么工厂对每个单位A型配件和B型配件定价最少应为多少呢？显然，从购买者的角度来看价格是越低越好，而从工厂的角度来看售出的收益不应低于它自己生产甲、乙两种产品时的收益，否则工厂宁愿自己生产也不愿售出（从而对于工厂来说，其定价至少应使卖出原料所得收益不少于生产所得利润） 可得如下模型： 【对偶问题】最优解的目标函数值为787.5对比原问题结果，我们发现： 两个模型的最优解对应的目标值是一样的！ 思考：是什么原因使得最优解目标值相同？这是因为，对于第二个模型来说如果定价低了，则厂家宁愿自己生产；如果定价高了，则买方就会从别的渠道购买，所以售出所得刚好就是自己生产能得到的利润（注意需要前提：假设信息是完全公开的！） 通过该模型我们还可以看到：当资源价格非零时，如果厂家的资源每增加一个单位，获利可增加 （ 例如每增加一个单位A型配件，可多卖2.5）——通过对偶变量就能发现潜在利润（原问题中的对偶变量相 当于对偶问题中的变量x、y） ！ 对给定LP问题，可利用下表直接写出对偶：例例 一个中间商由采购员、推销员和检验员结合而成。

它的任务是作为农民的中间人，贮存收获的农作物 （如烟草、玉米和花生），为农民推销这些农作物 从总销售额中提取一定百分比作为他们的收入x1=贮存烟草的吨数x2=贮存玉米的吨数x3=贮存花生的吨数一位经济管理学院的毕业生，他学过线性规划他为这个中间商的经营建立了一个数学模型基本 上是如下形式：一个实际例子其中，方程（1）是利润关系式方程（2）反映库房 空间（10,000）方程（3）反映有限加工处理时间（ 600人工时），方程（4）到方程（6）反映每种作物 的产量预测显然，该问题中的系数全是估计值，但 我们把它处理成确定性问题我们可以通过lindo软件计算出它的结果，得到： 目标值（利润）z = 2000.385元x1=130x2= 11.538462 x3= 70.384613y1=0.023077（增加单位库房空间的获利）y2=2.807692（增加单位人工时获利）y3=0.653846（增加单位玉米获利）y4=0（增加单位烟草获利）y5=0（增加单位花生获利）分析：虽然上述解出的规划是在假定利润极大的条件 下达到的，但观察对偶变量的情况，发现利润进一步 增加是可能的 首先看到y4= y5= 0，意味着烟草和花生的任何增 加将不再引起利润的增加，能够增加总利润的是(a) 库房空间 (b) 劳力 (c) 玉米。

为了得到额外的玉米，我们必须从外区调运进来； 为了增加库房空间，可以租用或扩建； 为了得到额外劳力，可以加班或雇用临时工我们还可以用对偶变量来确定应该付给额外库房 空间、劳力或玉米的价格，这种价格应该小于相应的对 偶变量的值 例如付给额外劳动力的工资应低于2.81元/小时； 除非库房空间租用价格小于0.023元/m2，否则我们不考 虑它；最后，对购买额外玉米来说，至少要保证每吨有 0.65元利润。