第三章线性规划的对偶理论与灵敏度分析精选文档.ppt

《第三章线性规划的对偶理论与灵敏度分析精选文档.ppt》由会员分享，可在线阅读，更多相关《第三章线性规划的对偶理论与灵敏度分析精选文档.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章线性规划的对偶理论与灵敏度分析1本讲稿第一页，共三十九页3.1 线性规划的对偶问题一、引例一、引例例例3 31 1生产计划问题（资源利用问题）生产计划问题（资源利用问题）胜利家具厂生产桌子和椅子两种家具。桌胜利家具厂生产桌子和椅子两种家具。桌子售价子售价5050元元/个，椅子销售价格个，椅子销售价格30/30/个，生产桌个，生产桌子和椅子要求需要木工和油漆工两种工种。生子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工产一个桌子需要木工4 4小时，油漆工小时，油漆工2 2小时。生小时。生产一个椅子需要木工产一个椅子需要木工3 3小时，油漆工小时，油漆工1 1小时。该小时。该厂每个

2、月可用木工工时为厂每个月可用木工工时为120120小时，油漆工工时小时，油漆工工时为为5050小时。问该厂如何组织生产才能使每月的小时。问该厂如何组织生产才能使每月的销售收入最大？销售收入最大？本讲稿第二页，共三十九页数学模型数学模型 max g=50 xmax g=50 x1 1+30 x+30 x2 2 s.t.4x s.t.4x1 1+3x+3x2 2 120 (3.1)120 (3.1)2x 2x1 1+x+x2 2 50 50 x x1 1,x,x2 2 0 0本讲稿第三页，共三十九页 如果我们换一个角度，考虑另外一如果我们换一个角度，考虑另外一种经营问题。种经营问题。假如有一个企业

3、家有一批假如有一个企业家有一批等待加工的订单，有意利用该家具厂的等待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。因木工和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工此，他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研时的价格。可以构造一个数学模型来研究如何既使家具厂觉得有利可图肯把资究如何既使家具厂觉得有利可图肯把资源出租给他，又使自己付的租金最少？源出租给他，又使自己付的租金最少？本讲稿第四页，共三十九页 假设假设 y y1 1,y,y2 2 分别表示每个木工和分别表示每个木工和油漆工工时的租金，则所付租金最小油漆工工时的租金，则所付租金最

4、小的目标函数可表示为：的目标函数可表示为：min s=120 ymin s=120 y1 1+50 y+50 y2 2目标函数中的系数目标函数中的系数 120 120，50 50 分别表示分别表示可供出租的木工和油漆工工时数。可供出租的木工和油漆工工时数。本讲稿第五页，共三十九页 该企业家所付的租金不能太低，该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图而否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的低于家具厂利用这些资源所能得到的利益：利益：4 y4 y1 1+2y+2y2 2 50 50 3 y

5、3 y1 1+y+y2 2 30 30 y y1 1,y,y2 2 0 0本讲稿第六页，共三十九页 得到另外一个数学模型：得到另外一个数学模型：min s=120 y min s=120 y1 1+50 y+50 y2 2 s.t.4 y s.t.4 y1 1+2y+2y2 2 50 (3.2)50 (3.2)3 y 3 y1 1+y+y2 2 30 30 y y1 1,y,y2 2 0 0本讲稿第七页，共三十九页 模型模型(3.1)(3.1)和模型和模型(3.2)(3.2)既有区别又有既有区别又有联系。联系在于它们都是关于家具厂的联系。联系在于它们都是关于家具厂的模型并且使用相同的数据，区别

6、在于模模型并且使用相同的数据，区别在于模型反映的实质内容是不同的。模型型反映的实质内容是不同的。模型(3.1)(3.1)是站在家具厂经营者立场追求销售收是站在家具厂经营者立场追求销售收入最大，模型入最大，模型(3.2)(3.2)则则是站在家具厂对是站在家具厂对手的立场追求所付的租金最少。手的立场追求所付的租金最少。本讲稿第八页，共三十九页 如果模型如果模型(3.1)(3.1)称为原问题，称为原问题，则模型则模型(3.2)(3.2)称为对偶问题。称为对偶问题。任何线性规划问题都有对偶问题，任何线性规划问题都有对偶问题，而且都有相应的意义。而且都有相应的意义。本讲稿第九页，共三十九页例例3.2 3

7、.2 营养配餐问题营养配餐问题 假定一个成年人每天需要从食物中获得假定一个成年人每天需要从食物中获得30003000千卡的热量、千卡的热量、5555克蛋白质和克蛋白质和800800毫克的毫克的钙。如果市场上只有四种食品可供选择，它钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？下使购买食品的费用最小？本讲稿第十页，共三十九页各种食物的营养成分表本讲稿第十一页，共三十九页解：解：设设x xj j为第为第j j种食品每天的购入量，则配

8、餐问种食品每天的购入量，则配餐问题的线性规划模型为：题的线性规划模型为：min S=14xmin S=14x1 1+6x+6x2 2+3x+3x3 3+2x+2x4 4 s.t.1000 xs.t.1000 x1 1+800 x+800 x2 2+900 x+900 x3 3+200 x+200 x4 4 3000 3000 50 x 50 x1 1+60 x+60 x2 2+20 x+20 x3 3+10 x+10 x4 4 55 55 400 x 400 x1 1+200 x+200 x2 2+300 x+300 x3 3+500 x+500 x4 4 800 800 x x1 1，x x

9、2 2，x x3 3，x x4 4 0 0 (3.3)(3.3)本讲稿第十二页，共三十九页该问题的对偶问题：该问题的对偶问题：max g=3000 ymax g=3000 y1 1+55y+55y2 2+800y+800y3 3s.t.1000 ys.t.1000 y1 1+50y+50y2 2+400y+400y3 3 14 14 800 y 800 y1 1+60y+60y2 2+200y+200y3 3 6 6 900 y 900 y1 1+20y+20y2 2+300y+300y3 3 3 3 200 y 200 y1 1+10y+10y2 2+500y+500y3 3 2 2 y y

10、1 1，y y2 2，y y3 3 0 0 (3.4)(3.4)本讲稿第十三页，共三十九页该问题的对偶问题该问题的对偶问题(3.4)(3.4)经济意义可解释为：经济意义可解释为：市场上有一厂商生产三种可代替食品中的市场上有一厂商生产三种可代替食品中的热量、蛋白质和钙的营养素，该厂商希望热量、蛋白质和钙的营养素，该厂商希望它的产品既有市场竞争力，又能带来最大它的产品既有市场竞争力，又能带来最大利润，因此需要构造一个模型来研究定价利润，因此需要构造一个模型来研究定价问题。以上模型的变量为各营养素单位营问题。以上模型的变量为各营养素单位营养量的价格，目标函数反映厂商利润最大养量的价格，目标函数反映厂

11、商利润最大的目标，约束条件反映市场的竞争条件，的目标，约束条件反映市场的竞争条件，即：用于购买与某种食品营养价值相同的即：用于购买与某种食品营养价值相同的营养素的价格应小于该食品的市场价格。营养素的价格应小于该食品的市场价格。本讲稿第十四页，共三十九页二、对偶规则原问题一般模型：对偶问题一般模型：maxZ=CX min=Yb AX b YA C X 0 Y 0本讲稿第十五页，共三十九页对偶规则v原问题有m个约束条件，对偶问题有m个变量v原问题有n个变量，对偶问题有n个约束条件v原问题的价值系数对应对偶问题的右端项v原问题的右端项对应对偶问题的价值系数v原问题的技术系数矩阵转置后为对偶问题系数矩

12、阵v原问题的约束条件与对偶问题方向相反v原问题与对偶问题优化方向相反本讲稿第十六页，共三十九页 原问题 对偶问题目标函数 max min 目标函数约束条件 m个 =变量 n个 无约束价值系数约束条件的右端项变量符号 n个 无约束约束条件 m个 =约束条件的右端项价值系数.本讲稿第十七页，共三十九页v例3.3 写出下列线性规划问题的对偶问题minZ=3x1+2x2-6x3+x5 2x1+x2-4x3+x4+3x5 7 x1+2x3-x4 4 -x1+3x2 -x4+x5 =-2 x1，x2，x3 0;x4 0;x5无限制本讲稿第十八页，共三十九页vmax=7y1+4y2-2y3 2y1+y2-y

13、3 3 y1 +3y3 2 -4y1+2y2 -6 y1 -y2 -y3 0 3y1 +y3=1 y1 0，y2 0y3 无约束本讲稿第十九页，共三十九页例例3.43.4：写出下列线性规划写出下列线性规划问题的对偶问题问题的对偶问题max S=10 xmax S=10 x1 1+x+x2 2 +2x+2x3 3s.t.Xs.t.X1 1+x+x2 2+2x+2x3 3 10 10 4x 4x1 1+2x+2x2 2 -x-x3 3 20 20 x x1 1，x x2 2，x x3 3 0 0本讲稿第二十页，共三十九页三、对偶问题的基本性质v对称性：对偶问题的对偶问题是原问题v弱对偶性：极大化原

14、问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值 v无界性：原问题无界，对偶问题无可行解本讲稿第二十一页，共三十九页 对偶定理：对偶定理：若一个问题有若一个问题有最优解，则另一问题也有最最优解，则另一问题也有最优解，且目标函数值相等。优解，且目标函数值相等。推理推理:对偶问题的最优解为对偶问题的最优解为原问题最优表中原问题最优表中,相应的松相应的松驰变量检验数的相反数。驰变量检验数的相反数。本讲稿第二十二页，共三十九页原问题与对偶问题解的对应关系原问题与对偶问题解的对应关系本讲稿第二十三页，共三十九页3.2 3.2 对偶单纯形法对偶单纯形法原始单纯形法的基本思路：原始单纯形

15、法的基本思路：在换基迭代在换基迭代过程中，始终保持过程中，始终保持基变量值非负基变量值非负，逐步，逐步使使检验数变成非正检验数变成非正，最后求得最优解或，最后求得最优解或判断无最优解。判断无最优解。对偶单纯形法的基本思路：对偶单纯形法的基本思路：在换基迭代在换基迭代过程中，始终保持过程中，始终保持检验数非正检验数非正，逐步使逐步使基变量值变成非负，基变量值变成非负，最后求得最优解或最后求得最优解或判断无最优解。判断无最优解。本讲稿第二十四页，共三十九页例例2-92-9：用对偶单纯形法解下列线性规划用对偶单纯形法解下列线性规划问题问题 min Z=2xmin Z=2x1 1+3x+3x2 2+4

16、x+4x3 3s.t.xs.t.x1 1+2x+2x2 2 +x+x3 3 3 3 2x 2x1 1-x-x2 2+3x+3x3 3 4 4 x x1 1，x x2 2，x x3 3 0 0本讲稿第二十五页，共三十九页3.3 3.3 对偶解的经济解释对偶解的经济解释 如果把线性规划的约束看成广义资如果把线性规划的约束看成广义资源约束，右边项则代表某种资源的可用源约束，右边项则代表某种资源的可用量。对偶解的经济含义是资源的单位改量。对偶解的经济含义是资源的单位改变量引起目标函数值的改变量。通常称变量引起目标函数值的改变量。通常称为影子价格。影子价格表明对偶解是对为影子价格。影子价格表明对偶解是对

17、系统内部资源的客观估计，又表明它是系统内部资源的客观估计，又表明它是一种虚拟的价格而不是真实价格。一种虚拟的价格而不是真实价格。本讲稿第二十六页，共三十九页影子价格的特征：影子价格的特征：影子价格是对系统资源的最优估计，影子价格是对系统资源的最优估计，只有系统达到最优状态时才可能赋只有系统达到最优状态时才可能赋与资源这种价值。因此，也称为与资源这种价值。因此，也称为最最优价格优价格。影子价格的取值与系统的价值取向影子价格的取值与系统的价值取向有关，并受系统状态变化的影响。有关，并受系统状态变化的影响。系统内部资源数量和价格的变化，系统内部资源数量和价格的变化，它是它是一种动态的价格体系一种动态

18、的价格体系。本讲稿第二十七页，共三十九页影子价格的大小客观反映了资源在系统影子价格的大小客观反映了资源在系统内的稀缺程度。内的稀缺程度。如果某资源在系统内如果某资源在系统内供供大于求，大于求，尽管它有市场价格，但它的影尽管它有市场价格，但它的影子价格等于零。增加这种资源的供应不子价格等于零。增加这种资源的供应不会引起系统目标的任何变化。如果某资会引起系统目标的任何变化。如果某资源是源是稀缺资源稀缺资源，其影子价格必然大于零。，其影子价格必然大于零。影子价格越高，这种资源在系统中越稀影子价格越高，这种资源在系统中越稀缺。缺。本讲稿第二十八页，共三十九页影子价格是一种影子价格是一种边际价值边际价值

19、，它与经，它与经济学中边际成本的概念相同。济学中边际成本的概念相同。因而因而在经济管理中有十分重要的价值。在经济管理中有十分重要的价值。企业管理者可以根据资源在企业内企业管理者可以根据资源在企业内部影子价格的部影子价格的 大小决定企业的大小决定企业的经营经营策略策略。本讲稿第二十九页，共三十九页一般来讲，我们按以下原则考虑企业的经营策一般来讲，我们按以下原则考虑企业的经营策略：略：如果某资源的影子价格高于市场价格，表明如果某资源的影子价格高于市场价格，表明该资源在系统内有获利能力，应买入该资源。该资源在系统内有获利能力，应买入该资源。如果某资源的影子价格低于市场价格，表明该如果某资源的影子价格

20、低于市场价格，表明该资源在系统内无获利能力，应卖出该资源。资源在系统内无获利能力，应卖出该资源。如果某资源的影子价格等于市场价格，表明该如果某资源的影子价格等于市场价格，表明该资源在系统内处于平衡状态，既不用买入，也不资源在系统内处于平衡状态，既不用买入，也不必卖出该资源。必卖出该资源。本讲稿第三十页，共三十九页3.4 3.4 灵敏度分析灵敏度分析 在以前讨论线性规划问题时，假定在以前讨论线性规划问题时，假定aij,bi,cj都是常数，但实际上这些系数往往都是常数，但实际上这些系数往往是估计值和预测值是估计值和预测值 aij,bi,cj变化时，最优解将如何变化的分变化时，最优解将如何变化的分析

21、，就叫灵敏度分析。析，就叫灵敏度分析。本讲稿第三十一页，共三十九页 灵敏度分析讨论两个问题：灵敏度分析讨论两个问题：1、研究系数在什么范围内变化最优解仍为最、研究系数在什么范围内变化最优解仍为最优解。优解。2、若原最优解不再是最优解，如何用最简便、若原最优解不再是最优解，如何用最简便的方法找到新的最优解。的方法找到新的最优解。本讲稿第三十二页，共三十九页v假定线性规划问题 maxZ=CX s.t.AX=b X0的最优表为：cjcB 基基 b x1 x2 xnB-1A jC-CB B-1A本讲稿第三十三页，共三十九页v不难看出，表中各块与参数不难看出，表中各块与参数（aij,bi,cj）的关的关

22、系为：系为：vB-1A与bi,cj无关无关，与与aij有关；有关；vvXB=B-1b与cj无关无关，与与bi,aij有关有关;vj=C-CB B-1A与bi无关无关，与与cj,aij有关；有关；vZ=CB B-1b与bi,cj,aij均有关；均有关；本讲稿第三十四页，共三十九页v由此可知，当某些参数变化时，并不一定要重新计算整个单纯形表，而可以从原最优单纯形表出发，作适当修改后再求新的最优解本讲稿第三十五页，共三十九页v灵敏度分析的步骤为：考察上述修改考察上述修改是否使是否使最优解有所变化最优解有所变化验明解的可行性验明解的可行性验明解的最优性验明解的最优性把修改后的表把修改后的表作为初始单纯

23、形表，作为初始单纯形表，重新迭代求优重新迭代求优修改原最优修改原最优单纯形表单纯形表本讲稿第三十六页，共三十九页v一、cj变化的情况变化的情况vv当只有当只有cj发生变化时，显然原最优解的可行发生变化时，显然原最优解的可行性不变，只需检查其最优性，若仍有全部性不变，只需检查其最优性，若仍有全部j0,则原则原最优解仍是最优解；否则在最优解仍是最优解；否则在原来的原来的最优单纯形表的基础上换基迭代，以求出新最优单纯形表的基础上换基迭代，以求出新的最优解。的最优解。本讲稿第三十七页，共三十九页v例：美佳公司计划制造，两种产品。已知各制造一件时分别占用的设备A、B的台时，调试工序及每天可用于这两种家电的能力，各售出一件时的获利情况如表1：项目 每天可用能力设备A（小时）设备B（小时）调试工序（小时）0 5 6 2 1 115245利润（元）2 1表1本讲稿第三十八页，共三十九页v问（1）该公司应制造两种家电各多少件，使获取的利润最大？v（2）若家电的利润降至1.5元/件，而家电的利润增至2元/件，美佳公司的最优生产计划有何变化？v（3）若家电的利润不变，则家电的利润在什么范围内变化时，美佳公司的最优生产计划不发生变化？本讲稿第三十九页，共三十九页