数量模型与算法基础：影子价格和对偶问题

影子价格和对偶问题1对偶问题:原问题线性规划有一个有趣的特性,就是任何一个目标求极大，约束为<=的问题都有一个与其匹配的目标求极小，约束为>=的线性规划问题.

例；原问题为

Maxz=8*x1+10*x2+2*x3

s.t.2*x1+1*x2+3*x3<=70

4*x1+2*x2+2*x3<=80

3*x1+1*x3<=15

2*x1+2*x2

<=50

x1,x2,x3>=0对偶问题则原问题的对偶问题为

Minw=70*y1+80*y2+15*y3+50*y4y*b

s.t2*y1+4*y2+3*y3+2*y4>=8A’*y>=c

1*y1+1*y2+1*y4>=10

3*y1+2*y2+1*y3>=2

y1,y2,y3,y3>=0可以看出：1、若一个模型为目标求极大，约束为小于等于的不等式,则它的对偶模型为目标求极小，约束为极大的不等式

即“MAX,〈=”与“MIN,〉=”相对应

2、从约束条件系数矩阵来看,一个模型中为A另一个为A的转置,一个模型是m个约束n个变量则他的对偶模型为n个约束m个变量

3、从数据b，c的位置看，两个规划模型中b和c的位置对换

即8、10、2与70、80、15、50对换

4、两个规划模型中变量非负.§1对偶问题的提出

原问题与对偶问题的关系原问题目标函数max目标函数minm个≤≥=n个≥≤=n个≥0≤0无符号限制m个≥0≤0无符号限制目标函数的系数约束条件右端常数系数矩阵A约束条件右端常数目标函数的系数系数矩阵AT约束条件约束条件变量变量对偶问题e.g.1

写出(P)问题的(D)问题maxz=2x1+3x2-5x3+x4s.t.4x1+x2-3x3+2x4≥53x1-2x2+7x4≤4-2x1+3x2+4x3+x4=6

x1≤

0,x2,x3≥0,x4无符号限制minw=5y1+4y2+6y3s.t.4y1+3y2-2y3≤

2y1-2y2+3y3≥

3-3y1+4y3≥-52y1+7y2+y3=1

y1≤

0,y2≥0,y3无符号限制Matlab解对偶问题c=[-2;-3];b=[24;10];A=[36;21];lb=[0;0];ub=[];[xz]=linprog(c,A,b,[],[],lb,ub);xz=-z%duality,shadowprices%c2=[24;10];c2=b;%b2=[-2;-3];b2=c;%A2=[-3-2;-6-1];A2=-A';lb2=[0;0];ub2=[];[y,w]=linprog(c2,A2,b2,[],[],lb2,ub2);ywx=42z=14===y=0.444440.33333w=14对称型对偶线性规划对称对偶线性规划具有对称形式的线性规划的特点是：①全部约束条件均为不等式，对极大化问题为≤，对极小化问题为≥。②全部变量均为非负。列出对称对偶线性规划的步骤是：①规定非负的对偶变量，变量数等于原始问题的约束方程数。②把原始问题的目标函数系数作为对偶问题约束不等式的右端常数。③把原始问题约束不等式的右端常数作为对偶问题的目标函数系数。④把原始问题的系数矩阵转置后作为对偶问题的系数矩阵。⑤把原始问题约束条件中的不等号反向作为对偶问题约束条件的不等号。⑥将原始问题目标函数取极大化改成对偶问题目标函数取极小化。非对称型对偶线性规划非对称对偶线性规划有时线性规划并不以对称方式出现，如约束条件并不都是同向不等式，变量可以是非正的或没有符号约束。列写非对称对偶线性规划可参照原始-对偶表（见表）按下列步骤进行：①规定对偶变量，变量个数等于原始问题约束不等式数。②把原始问题的目标函数系数作为对偶问题约束不等式的右端常数。b2=c③把原始问题约束不等式的右端常数作为对偶问题的目标函数系数。c2=b④把原始问题的系数矩阵转置后作为对偶问题的系数矩阵。A2=A’⑤根据原始问题的约束不等式情况，确定对偶变量的符号约束。⑥根据原始问题决策变量的符号约束，确定对偶问题约束不等式的符号方向。影子价格影子价格：用线性规则方法计算出来的反映资源最优使用效果的价格。(不一定等于资源的市场价格）当资源增加一个单位时，目标函数最大值的增量与资源的增量的比值，就是目标函数对约束条件（即资源）的一阶偏导数。用线性规划解决如何在限资源b下使总产出为最大z*=cx*时，其对偶解就是求出相应的资源使用极小值w*=y*b，y*值作为对资源的经济评价，表现为影子价格。这种影子价格反映生产设备、自然资源、劳动力的最优使用效果。资源的合理利用问题：资源单位消费产品资源限制单位利润还有现金，如何投资决策依据：比较第i种资源增加一个单位，其余资源不增加时利润的增加值1、问题的提出边际价格2、影子价格的定义资源单位消费产品甲乙资源限制钢材52170煤炭23100设备台时15150单位利润（万元）1018最优解X*=(50/7，200/7)最优值Z*=4100/7Y*=(0，32/7,6/7)对偶问题的最优解对偶问题最优解Y*=(0，32/7,6/7)钢材煤炭设备台时即再增加1吨钢材，利润不会增加即再增加1吨煤炭，利润增加32/7万元即再增加1个台时，利润增加6/7万元原问题最优解X*=(50/7，200/7)对偶问题最优解Y*=(0，3/7,6/7)钢材煤炭设备台时把X*代入：现有资源中的煤炭和设备台时已经全部用完而没有剩余，因此若增加这两种资源，必然会工厂带来新的效益。现有资源中的钢材有剩余，因此若增加这种资源，只能造成积压，不会给工厂增加效益。*影子价格的大小客观地反映了资源在系统内部的稀缺程度例：已知某家具公司生产书桌、餐桌、椅子三种产品。生产这些家具需要木材和和两种熟练工人：漆工和木工。各种家具的资源需求如下表，且公司确信书桌和椅子的需求是无限的，但餐桌最多能卖出5个，问如何安排生产，能使总收入最大？书桌餐桌椅子资源数木材8英寸木板6英寸木板1英寸木板48英寸木板漆工4小时2小时1。5小时20小时木工2小时1。5小时0。5小时8小时售价60元30元20元解：设X1，X2，X3表示书桌、餐桌、椅子的生产数量，Z表示总收入木工约束漆工约束木材约束餐桌约束木工约束漆工约束木材约束餐桌约束解对偶问题Matlab程序见下页clearallpkgloadoptim;c=[603020];c=-c';A=[861421.521.50.5010]b=[482085]lb=[000]’[xz]=linprog(c,A,b,[],[],lb,[]);xz=-z%解对偶问题c2=bb2=-(-c)A2=-A'lb=[0000][yw]=linprog(c2,A2,b2,[],[],lb,[]);yw，即增加1英寸的木材，总收入不增加，即增加1小时的漆工，总收入增加10元，即增加1小时的木工，总收入增加10元，即增加1个餐桌的需求，总收入不增加投资策略：哪种资源的影子价格大就投资那项？

投资策略：不增加木板，不在餐桌的销路上投资（如广告等）若市场上1小时的漆工工资<10元，可增加漆工若市场上1小时的木工工资<10元，可增加木工影子价格是一种资源的虚拟价格≠资源的市场价格为什么叫影子价格？3、影子价格在经济管理中的应用

影子价格能指示企业内部挖潜的方向影子价格越大的资源，表明：这种资源对目标增益的影响越大这种资源对该企业越稀缺、贵重管理措施：重视对该种资源的管理通过挖潜革新、降低消耗或及时补充该种资源影子价格为零的资源，表明：这种资源对该企业来说相对富裕管理措施：向别的企业转让或以市场价出售通过对企业内部的改造、挖潜和增加对影子价格大于零的资源的投入，使原有剩余资源得到充分利用

影子价格在企业经营决策中的作用决策者：将本企业资源的影子价格与当时的市场价格进行比较采用的决策：若某种资源的影子价格>市场价格——卖出若某种资源的影子价格<市场价格——买进关于影子价格的说明：3、影子价格是在系统达到最优时对系统资源的一种最优估价。1、影子价格的大小客观地反映了资源在系统内的稀缺程度2、影子价格的取值与系统的状态有关，系统中任一状态的改变都会引起影子价格的变化例：某工厂准备生产A、B、C三种产品，他们都消耗劳动力和材料，有关数据如下：

原料产品ABC拥有量劳动力63545材料34530售价（元）3141、确定获总收入最大的生产计划2、如果劳动力数量不变，材料不足可以从市场购买，每单位0.4元，问该单位要不要购进原材料扩大生产？劳动力约束材料约束最优生产方案：5个A，0个B，3个C材料的影子价格=3/5=0.6买进>0.4二、边际贡献生产策略问题：资源单位消费产品资源限制单位价格问题：市场上正在热卖第j种产品，是否增加该产品的产量为什么别人热卖的产品我不该生产隐含成本第i种产品的价格新产品开发决策分析资源单位消费产品甲乙资源限制钢材52170煤炭23100设备台时15150单位价格（万元）1018x1x2x3x4x5000-32/7-6/7Z-4100/7x3001-23/711/7540/7x11005/7-3/750/7x2010-1/72/7200/7现有两种新产品A和B，他们对资源的消耗额以及可能获得的单位利润如表所示，试决定他们是否值得投产。产品资源单位消费910单位价格（万元）43设备台时12煤炭21钢材BA现有两种新产品A和B，他们对资源的消耗额以及可能获得的单位利润如表所示，试决定他们是否值得投产。产品A的隐含成本=不生产产品B的隐含成本=可以生产产品资源单位消费910单位价格（万元）43设备台时12煤炭21钢材BA复习题什么是原问题的对偶问题？MATLAB如何求原问题的对偶问题？怎样求线性规划生产模型中资源向量的影子价格？求解原问题的对偶问题复习题什么是线性规划生产模型中影子价格当资源增加一个单位时，目标函数最大值的增量线性规划生产模型中影子价格的大小客观地反映了在此系统内部1.资源的稀缺程度

2生产设备、自然资源、劳动力的最优使用效果3.资源对目标增益的影响复习题对线性规划生产模型中影子