《whut运筹学-7矩阵表示对偶问题理论影子价格.ppt》由会员分享，可在线阅读，更多相关《whut运筹学-7矩阵表示对偶问题理论影子价格.ppt（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 对偶理论与灵敏度分析对偶理论与灵敏度分析 (Dual Theories and Sensitivity Analysis)单纯形法的矩阵描述单纯形法的矩阵描述 线性规划的对偶问题线性规划的对偶问题 对偶问题的基本性质对偶问题的基本性质 对偶问题的经济解释对偶问题的经济解释 -影子价格影子价格 对偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析例例 单纯形法的矩阵描述单纯形法的矩阵描述 (Matrices Description)XB x1 x2 x3 x4 x5 bx1 1 0 0 1/4 0 4x5 0 0 -2 0.5 1 4x2 0 1 0.5 -1/8 0 2-z 0 0 -3/2 -1
2、/8 0 -14CB=2 0 3 CN=0 0 单纯形法的矩阵描述单纯形法的矩阵描述BCBXBCNXNNb 单纯形法的矩阵描述单纯形法的矩阵描述 单纯形法的矩阵描述单纯形法的矩阵描述B-1 NB-1 b 单纯形法的矩阵描述单纯形法的矩阵描述考虑线性规划问题的标准型考虑线性规划问题的标准型 A Cm n,R(A)=m.可行基可行基相应于非基变量的系数矩阵相应于非基变量的系数矩阵令令 A=(B N)X=(XB XN)TC=(CB CN)单纯形法的矩阵描述单纯形法的矩阵描述 矩阵形式的单纯形表矩阵形式的单纯形表 XB XB XN b XB I B-1N B-1b -z 0 CN-CB B-1N -C
3、B B-1b单纯形表中变量单纯形表中变量 xj 的系数列向量的系数列向量：B-1aj 单纯形表中约束方程的右端项单纯形表中约束方程的右端项：B-1b 单纯形表中目标函数值单纯形表中目标函数值：CBB-1b单纯形表中变量单纯形表中变量 xj 的检验数的检验数：Cj-CBB-1aj 单纯形法的矩阵描述单纯形法的矩阵描述 单纯形法的矩阵描述单纯形法的矩阵描述继续讨论上例继续讨论上例XB x1 x2 x3 x4 x5 bx1 1 0 0 1/4 0 4x5 0 0 -2 0.5 1 4x2 0 1 0.5 -1/8 0 2-z 0 0 -3/2 -1/8 0 -14CB=2 0 3 CBB-1=1.5
4、 1/8 0 单纯形法的矩阵描述单纯形法的矩阵描述例例 用单纯形法求解下述线性规划问题用单纯形法求解下述线性规划问题.解解:把原问题化为标准型把原问题化为标准型 单纯形法的矩阵描述单纯形法的矩阵描述用单纯形法求解如下用单纯形法求解如下:迭代迭代XB x1 x2 x3 x4 x5 b R x3 1 2 1 0 0 8 4x4 4 0 0 1 0 16 -x5 0 4 0 0 1 12 3-z 2 3 0 0 0 0XB x1 x2 x3 x4 x5 b R x3 1 0 1 0 -0.5 2 2x4 4 0 0 1 0 16 4x2 0 1 0 0 1/4 3 -z 2 0 0 0 -3/4 -
5、9 单纯形法的矩阵描述单纯形法的矩阵描述 迭代迭代 迭代迭代 X*=(4,2)T z*=14 XB x1 x2 x3 x4 x5 b Rx1 1 0 1 0 -0.5 2 -x4 0 0 -4 1 2 8 4 x2 0 1 0 0 1/4 3 12-z 0 0 -2 0 1/4 -13XB x1 x2 x3 x4 x5 b R x1 1 0 0 1/4 0 4x5 0 0 -2 0.5 1 4x2 0 1 0.5 -1/8 0 2-z 0 0 -3/2 -1/8 0 -14 单纯形法的矩阵描述单纯形法的矩阵描述线性规划问题的对偶问题线性规划问题的对偶问题 (Dual Problems)1.对偶
6、问题的提出对偶问题的提出 (Dual Problem)例例1 1 某工厂用两台机器生产三种产品某工厂用两台机器生产三种产品,有关数据如下表有关数据如下表:如何组织生产，使总利润最大？如何组织生产，使总利润最大？甲甲(m)(m)乙乙(m)(m)丙丙(m)(m)限制条件限制条件机器机器 I 1 1 1 135机器机器 II 1 4 7 405利润利润 2 3 11/3 x1,x2,x3 -分别生产甲、分别生产甲、乙、丙产品的数量乙、丙产品的数量例例2 2 若另一工厂想要租赁这两台机器用于生产产品，那么该若另一工厂想要租赁这两台机器用于生产产品，那么该 工厂应该如何确定合理的租金呢？工厂应该如何确定
7、合理的租金呢？线性规划问题的对偶问题线性规划问题的对偶问题 y1,y2 -机机器器I与与机机器器II 的每台时的租金的每台时的租金例例1 1与例与例2 2是一个问题的两个方面是一个问题的两个方面两个线性规划模型是一对对偶问题两个线性规划模型是一对对偶问题线性规划问题的对偶问题线性规划问题的对偶问题2.原问题与对偶问题的关系原问题与对偶问题的关系 对称性关系对称性关系 例例 3 3 求下列问题的对偶问题求下列问题的对偶问题 对称性形式的对偶关系对称性形式的对偶关系线性规划问题的对偶问题线性规划问题的对偶问题非对称性关系非对称性关系 练习：练习：线性规划问题的对偶问题线性规划问题的对偶问题 原原(
8、对偶对偶)问题问题目标函数目标函数 max z=CX 0n 个变量个变量 0 自由变量自由变量 m 个约束个约束 AX b =对偶对偶(原原)问题问题目标函数目标函数 min w=YTb n 个约束个约束 ATY CT =0m 个变量个变量 0 自由变量自由变量原问题与对偶问题对偶关系对照表原问题与对偶问题对偶关系对照表线性规划问题的对偶问题线性规划问题的对偶问题例例 4 4 求下列问题的对偶问题求下列问题的对偶问题线性规划问题的对偶问题线性规划问题的对偶问题例例 5 5 求下列问题的对偶问题求下列问题的对偶问题线性规划问题的对偶问题线性规划问题的对偶问题考虑对称性关系的对偶：考虑对称性关系的
9、对偶：对称性对称性对偶问题的基本性质对偶问题的基本性质(Basic Properties)对偶问题的对偶是原问题。对偶问题的对偶是原问题。弱对偶性弱对偶性若原若原(对偶对偶)问题有无界解，则对偶问题有无界解，则对偶(原原)问题无可行解问题无可行解.无界性无界性对偶问题的基本性质对偶问题的基本性质原原对偶对偶原原对偶对偶不可行不可行不可行不可行无界无界不可行不可行可行解是最优解时的性质可行解是最优解时的性质对偶定理对偶定理若原问题有最优解，相应的最优基为若原问题有最优解，相应的最优基为 B,则对偶问题也有最优解，且最则对偶问题也有最优解，且最优解为优解为(CBB-1)T；并且目标函数值相等，均为
10、；并且目标函数值相等，均为 CBB-1b.对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质变量对应关系变量对应关系设原问题是设原问题是它的对偶问题是它的对偶问题是则原问题单纯性表的检验数行对应其对偶问题的一个基解：则原问题单纯性表的检验数行对应其对偶问题的一个基解：原问题原问题 XBXNXS检验数 0CN-CBB-1N-CBB-1对偶问题 YTS1 -YTS2-YT例例 已知用单纯形法求解下述线性规划问题所得最终表如下，试确已知用单纯形法求解下述线性规划问题所得最终表如下，试确 定该问题的对偶问题的最优解定该问题的对偶问题的最优解.对偶问题的基本性质对偶问题的基本性质解
11、解:由已知得由已知得 CB=(2 0 3),因此，由对偶定理可得所求问题的对偶问题的最优解为：因此，由对偶定理可得所求问题的对偶问题的最优解为：XB x1 x2 x3 x4 x5 b R x1 1 0 0 1/4 0 4x5 0 0 -2 0.5 1 4x2 0 1 0.5 -1/8 0 2-z 0 0 -3/2 -1/8 0 -14其中其中 x3,x4,x5 为为 松弛变量。松弛变量。(Y*)Tb=?对偶问题的基本性质对偶问题的基本性质互补松弛性互补松弛性令令 原问题的可行解，原问题的可行解，是对偶问题的可行解，则它们分别是原问题是对偶问题的可行解，则它们分别是原问题与对偶问题的最优解的充要
12、条件是与对偶问题的最优解的充要条件是:例例 6 已知线性规划问题已知线性规划问题且其最优解为且其最优解为x*1=2,x*2=0,x*3=8.试用对偶问题的性质求其对试用对偶问题的性质求其对偶问题的最优解。偶问题的最优解。对偶问题的基本性质对偶问题的基本性质解解:此线性规划问题的对偶问题是：此线性规划问题的对偶问题是：将将 x*x*1 1=2,=2,x*x*2 2=0,=0,x*x*3 3=8=8 代入原线性规划问题的约束条件中，可知第一个约束代入原线性规划问题的约束条件中，可知第一个约束条件为严格不等式，则由互补松弛性得条件为严格不等式，则由互补松弛性得 y*y*1 1=0.=0.对偶问题的基
13、本性质对偶问题的基本性质 又因又因 x*x*1 1 x*x*3 300，所以对偶问题的第一个约束条件以及第三个约束条件所以对偶问题的第一个约束条件以及第三个约束条件 均应取等式，即均应取等式，即 8 8y*y*1 1+4+4 y*y*2 2+2+2y*y*3 3=60=60，y*y*1 1+1.5+1.5y*y*2 2+0.5+0.5y*y*3 3=20.=20.解之得解之得 y*y*2 2=10,=10,y*y*3 3=10.=10.因此，对偶问题的最优解为因此，对偶问题的最优解为 y*1=0,y*2=10,y*3=10.线性规划对偶问题的经济解释线性规划对偶问题的经济解释-影子价格影子价格
14、(Shadow Prices)设设 与与 分别是原问分别是原问题与对偶问题的最优解，则由对偶问题的基本性质有题与对偶问题的最优解，则由对偶问题的基本性质有由此，由此，变量变量 的的经济意义经济意义是：是：在其他条件不变的情况下，在其他条件不变的情况下，第第 i种资源的单位改变量所引起的目标函数值的增加量种资源的单位改变量所引起的目标函数值的增加量。1 1 影子价格的解释影子价格的解释 变量变量 的值代表对第的值代表对第 i 种资源的估价。这种估价不是资种资源的估价。这种估价不是资 源源 i 的市场价格，而是具体工厂根据资源在生产中做出的贡的市场价格，而是具体工厂根据资源在生产中做出的贡 献而作
15、的估价，称它为献而作的估价，称它为 “影子价格影子价格 ”。影子价格是对偶解的一个十分形象的名称，它既表明了对偶影子价格是对偶解的一个十分形象的名称，它既表明了对偶 解是对系统内部资源的一种客观估价，又表明它是一种虚解是对系统内部资源的一种客观估价，又表明它是一种虚 拟的价格，而不是真实的价格。拟的价格，而不是真实的价格。线性规划对偶问题的经济解释线性规划对偶问题的经济解释-影子价格影子价格例例 某工厂用三台机器生产两种产品某工厂用三台机器生产两种产品,有关数据如下表有关数据如下表:如何组织生产，使总利润最大？如何组织生产，使总利润最大？甲甲(m)(m)乙乙(m)(m)可供资源可供资源(台时台
16、时)机器机器 I 1 2 8 机器机器 II 4 0 16 机器机器 III 0 4 12 利润利润 2 3 x1,x2 -分别生产甲、分别生产甲、乙产品的数量乙产品的数量 X*=(4,2)T z*=14 线性规划对偶问题的经济解释线性规划对偶问题的经济解释-影子价格影子价格问题：若另一工厂想要租赁这三台机器用于生产产品，那么该问题：若另一工厂想要租赁这三台机器用于生产产品，那么该 工厂应该如何确定合理的租金呢？工厂应该如何确定合理的租金呢？y1,y2,y2 -机机器器I、机机器器II与与机机器器III 的每台时的租金的每台时的租金线性规划对偶问题的经济解释线性规划对偶问题的经济解释-影子价格
17、影子价格2 2 影子价格的作用影子价格的作用 影子价格的大小反映了资源在系统内的稀缺程度影子价格的大小反映了资源在系统内的稀缺程度根据互补松弛性，某种资源的影子价格为根据互补松弛性，某种资源的影子价格为 0 时，该种资源未充分利时，该种资源未充分利用，仍有剩余；某种资源的影子价格不为用，仍有剩余；某种资源的影子价格不为 0 时，该种资源在生产中时，该种资源在生产中已消耗完毕，目前比较稀缺，此时如果管理者增加该资源的供应已消耗完毕，目前比较稀缺，此时如果管理者增加该资源的供应量，则总收益就会增加。量，则总收益就会增加。线性规划对偶问题的经济解释线性规划对偶问题的经济解释-影子价格影子价格 影子价格对市场有调节作用影子价格对市场有调节作用在完全市场经济的条件下，当某种资源的市场价小于或等于影子在完全市场经济的条件下，当某种资源的市场价小于或等于影子价格时，则企业应买进该资源以扩大再生产；反之，则应将已有价格时，则企业应买进该资源以扩大再生产；反之，则应将已有资源卖掉。所以资源卖掉。所以“影子价格影子价格”能为企业或部门提供今后能为企业或部门提供今后“活动活动”的一的一种经济信息。种经济信息。线性规划对偶问题的经济解释线性规划对偶问题的经济解释-影子价格影子价格