运筹学课件 第二章-对偶问题.ppt

2.3 对偶对偶问题与灵敏度分析问题与灵敏度分析 2.3.1 线性规划的对偶问题 2.3.2 灵敏度分析回顾煤电油例：某厂生产两种产品回顾煤电油例：某厂生产两种产品:产品甲，产产品甲，产品乙。需要三种资源：煤，电，油。品乙。需要三种资源：煤，电，油。甲 乙 资源限量 煤(t)9 4 360 电（kw/h)4 5 200 油（t）3 10 300单位价格（万元）7 122.3.1 线性规划的对偶问题线性规划的对偶问题一、一、LP的对偶问题及其模型的对偶问题及其模型1.对偶问题对偶问题 问如何决定生产方案，使总收入最大？问如何决定生产方案，使总收入最大？生产模型(P)现有另一厂商，提出购买全部资源煤、电、油。现有另一厂商，提出购买全部资源煤、电、油。设煤、电、油的购买单价分别为设煤、电、油的购买单价分别为y1,y2,y3，总花费为，总花费为w w。购买模型(D)称(D)为(P)的对偶问题，(P)为(D)的原问题。2.对偶模型的一般式对偶模型的一般式原问题（P)max z=CXs.t.AXbX 0对偶问题(D)min w=Ybs.t.YACY 0maxbACCATbminmnmn原问题（原问题（P）对偶问题（对偶问题（D）目标max型目标min型有n个变量（非负）有n个约束（大于等于）有m个约束（小于等于）有m个变量（非负）价格系数资源向量资源向量价格系数技术系数矩阵技术系数矩阵的转置第i个约束为等式第i个变量为自由变量第j个变量为自由变量第j个约束为等式对偶问题模型的特点：对偶问题模型的特点：例1：写出下列LP问题的对偶问题写出上述对偶问题的对偶问题结论：对偶问题的对偶问题为原问题。若原问题第若原问题第i个约束为个约束为“=”，则对偶问题，则对偶问题yi为自为自由变量。同理，若原问题由变量。同理，若原问题xj为自由变量，则对偶问为自由变量，则对偶问题第题第j个约束为个约束为“=”式。式。令x2=-x2，则上式化为：若原问题若原问题xj0，则对则对偶偶问题问题第第j个个约约束束反号（与反号（与规规定形式比）。同理，若原定形式比）。同理，若原问题问题第第i个个约约束反号（与束反号（与规规定形式比），定形式比），则对则对偶偶问题问题yi0。max z=CXs.t.AXbX 0min w=Ybs.t.YA C Y 0小结：写一个线性规划问题的对偶问题小结：写一个线性规划问题的对偶问题max z=CXs.t.AXbX 0min w=Ybs.t.YA C Y 0max z=CXs.t.AX=bX 0min w=ybs.t.YA C Y:自由变量约束条件的类型与非负条件对偶约束条件的类型与非负条件对偶非标准的约束条件类型对应非正常的非负条件非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的对偶变换是一一对应的例例2 写出下面线性规划的对偶规划：写出下面线性规划的对偶规划：二、对偶问题的基本性质二、对偶问题的基本性质对偶的对偶就是原始问题，互为对偶min z=-CXs.t.-AX -bX 0Max-w=-Ybs.t.-YA -CY 0min w=Ybs.t.YA CY 0max z=CXs.t.AX b X 0对偶的定义对偶的定义1、对称性、对称性设X、Y分别是(P)问题和(D)问题的任一可行解，则 CX Yb注：此性质只适用于(P)max型与(D)min型。2、弱对偶性、弱对偶性3、无界性、无界性若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。证：用反证法证：用反证法若（D）有可行解，则由弱对偶性，有Z(x)w(y)即(P)的目标函数值有上界这与(P)有无界解相矛盾，所以命题成立。注：性质注：性质3的逆命题不成立。的逆命题不成立。事实上，原问题（对偶问题）无可行解，则对偶问题（原问题）有无界解或无可行解。4.最优性图示为：5.强对偶性 设 如果(P)问题有最优解，则(D)问题也有最优解，且最优值相等。证：对(P)增加松弛变量XS，化为标准型：设其最优基解为B，则单纯形终表为：Cj C 0CB XB B-1b X XS B-1A B-1 I Z*=CBB-1b C-CBB-1A 0-CBB-1I若(P)有最优解，则检验数：x=C-CBB-1A 0 s=0-CBB-1I=-CBB-10小结：（P）无界解无可行解最优解无界解无可行解最优解（D）三、对偶变量的经济含义三、对偶变量的经济含义影子价格影子价格1、影子价格的定义：式中：bi第i种资源的拥有量，yi对第i种资源的估价。定义：(D)问题的最优解y*=CBB-1为(P)问题资源的 影子价格。于是CBB-1:(1)作为(D)问题的最优解y*买主最低的价格买主最低的价格(2)作为(P)问题的影子价格卖主内部掌握卖主内部掌握 的价格的价格例5.煤、电、油例的最终表：X*=(20,24,84,0,0)T，z*=428=w*，Y*=(0,1.36,0.52)=CBB-1资源煤的影子价格为0资源电的影子价格为1.36资源油的影子价格为0.52影子价格越高，说明这种资源对生产越重要。2.3.2 灵敏度分析灵敏度分析一、定义：灵敏度分析讨论建模时的系数及有关变量变化时对解的影响。反映在两个方面二、目的：（1）参数在何范围内变化最优解（基）不变。（2）参数变化，最优解有何变化。1.资源向量b的变化分析问题：br在何范围时可使原问题最优基不变。2.价格系数C变化的分析方法：问题：cj在什么范围内变化，最优解不变。结果：（1）若Cj的变化使检验数仍全部0，则原问题最优解不变。（2）若Cj的变化使检验数中含有0的量，则应用单纯形法迭代至最优。3.追加新变量的分析。问题：新加入的变量是否应进基（如新产品是否应投产）方法：只需计算新变量Xn+1的检验数 n+1=Cn+1-CBB-1Pn+10则投产0则不投产若n+10，则用单纯形法迭代至最优。例：回顾煤电油例的终表。（1）请指出电的影子价格是多少？并给出使最优基仍适用的电的变化范围？（2）若有人愿以每度1元的价格向该厂供应25度电，是否值得接受？（3）甲产品的价格在何范围内变化时，原最优解不变？（4）若现又考虑一新产品丙，资源单耗为10、2、5，售价为6.5，是否应投产？解：（1）电的影子价格为1.36即电的增量在-50,26.92内变动时，可使原最优基B不变。（2）因为25 26.92，所以原有影子价格仍适用，而1.36 1，故值得接受。（3）（4）第章线性规划第章线性规划（Linear Programming）第章线性规划第章线性规划2.1 线性规划的模型与图解法线性规划的模型与图解法2.2 单纯形法单纯形法2.3 对偶问题与灵敏度分析对偶问题与灵敏度分析2.4 运输问题运输问题2.1 线性规划的模型与图解法线性规划的模型与图解法2.1.1 问题的引入问题的引入（）生产安排问题（）生产安排问题l 如何合理使用有限的人力、物力和资金，如何合理使用有限的人力、物力和资金，使得收到最好的经济效益。使得收到最好的经济效益。例例1 1：某工厂可生产甲、乙两种产品，需消耗煤、：某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产方案。试拟订使总收入最大的生产方案。资源单耗产品资源单耗产品 资源资源甲甲 乙乙资源限量资源限量煤煤电电油油9 44 5 3 10360200300单位产品价格单位产品价格 7 12 甲甲 乙乙 资源限量资源限量 煤煤(t)9 4 360 电（电（kwh)4 5 200 油（油（t）3 10 300 单价（万元）单价（万元）7 12解：设甲乙产品产量分别为解：设甲乙产品产量分别为x x1 1和和x x2 2 kgkg，决策变量决策变量总收入为总收入为z z万元。万元。则则 max z=7xmax z=7x1 1+12x+12x2 2 目标函数目标函数 9x 9x1 1+4x+4x2 2 360 360 4x 4x1 1+5x+5x2 2 200 200 3x 3x1 1+10 x+10 x2 2 300 300 x x1 1，x x2 200s.t.约束条件约束条件（）配料问题（）配料问题l 如何合理地搭配（混合）材料，以最如何合理地搭配（混合）材料，以最经济的方式，达到配比要求。经济的方式，达到配比要求。例例例例2 2 2 2：（营养配餐问题）：（营养配餐问题）：（营养配餐问题）：（营养配餐问题）假定一个成年人每天假定一个成年人每天假定一个成年人每天假定一个成年人每天需要从食物中获得需要从食物中获得需要从食物中获得需要从食物中获得3000300030003000千卡的热量、千卡的热量、千卡的热量、千卡的热量、55555555克蛋白克蛋白克蛋白克蛋白质和质和质和质和800800800800毫克的钙。如果市场上只有四种食品毫克的钙。如果市场上只有四种食品毫克的钙。如果市场上只有四种食品毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分可供选择，它们每千克所含的热量和营养成分可供选择，它们每千克所含的热量和营养成分可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营和市场价格见下表。问如何选择才能在满足营和市场价格见下表。问如何选择才能在满足营和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？养的前提下使购买食品的费用最小？养的前提下使购买食品的费用最小？养的前提下使购买食品的费用最小？解解：设设x xj j(j=1,2,3,4)(j=1,2,3,4)为为第第j j种种食食品品每每天天的的购购入入量量，z z为为每每天天购购买买食食品品的的总总费费用用，则则配餐问题的线性规划模型为：配餐问题的线性规划模型为：min z=14xmin z=14x1 1+6x+6x2 2+3x+3x3 3+2x+2x4 4 1000 x 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,x2 2,x,x3 3,x,x4 4 0 0（3 3）下料问题）下料问题l 如何截取原材料，在达到截取要求的如何截取原材料，在达到截取要求的情况下，使废料最少。情况下，使废料最少。例例3 3：料长：料长7.47.4米，截成米，截成2.92.9、2.12.1、1.51.5米各米各200200根根,方案如下表。如何截取余料最少？方案如下表。如何截取余料最少？方案方案料型料型 1 2 3 4 5 2.9米米 2.1米米 1.5米米 1 2 0 1 0 0 0 2 2 1 3 1 2 0 3 合计合计 残料残料 7.4 7.3 7.2 7.1 6.6 0 0.1 0.2 0.3 0.8解解：设设x xj j(j=1,2,3,4,5)(j=1,2,3,4,5)为为采采用用第第j j种种方方案案截截取取的的原原料料根根数数，z z为为截截取取后后的的余余料料总总米米数数，则下料问题的线性规划模型为：则下料问题的线性规划模型为：min z=0 xmin z=0 x1 1+0.1x+0.1x2 2+0.2x+0.2x3 3+0.3x+0.3x4 4+0.8x+0.8x5 5 x x1 1+2x+2x2 2 +x+x4 4 200200 2x 2x3 3+2x+2x4 4+x+x5 5 200 200 3x 3x1 1+x+x2 2+2x+2x3 3 +3x+3x5 5 200200 x xj j 0(j=1,2,3,4,5)0(j=1,2,3,4,5)2.1.2 线性规划的模型线性规划的模型 一、一、LP模型的三要素模型的三要素 规划问题的数学模型包含三个组成要素：规划问题的数学模型包含三个组成要素：（1）决策变量）决策变量：指决策者为实现规划目标采指决策者为实现规划目标采取的方案措施，是问题中要确定的未知量。取的方案措施，是问题中要确定的未知量。（2）目标函数：）目标函数：指问题要达到的目的要求，指问题要达到的目的要求，表示为决策变量的函数。表示为决策变量的函数。（3）约束条件：）约束条件：指决策变量取值时受到的各指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等种可用资源的限制，表示为含决策变量的等式或不等式。式或不等式。二、二、LP模型的一般式模型的一般式一般地，线性规划模型：一般地，线性规划模型：1、决策变量：、决策变量：x x1 1,x,xn n2 2、目、目标标函数：函数：3 3、约约束条件：束条件：简记为：简记为：例如：练习练习1 1：某畜牧厂每日要为牲畜购买饲料以使其获取某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场上可选择的饲料有四种养分。市场上可选择的饲料有M、N两种。两种。有关数据如下：有关数据如下：试决定买试决定买M与与N二种饲料各多少公斤而使支出的总费用二种饲料各多少公斤而使支出的总费用为最少？为最少？410售价 0.4 0.6 2.0 1.7牲畜每日需要量 0 0.1 0.2 0.1N 0.1 0 0.1 0.2 M每公斤含营养成分 A B C D饲料2.1.3 线性规划模型的图解法线性规划模型的图解法（适用于（适用于2个个变量的一般型）变量的一般型）一、线性规划问题的解的概念一、线性规划问题的解的概念 设线性规划问题的一般型为设线性规划问题的一般型为（1）可行解：满足全部约束条件的决策变量）可行解：满足全部约束条件的决策变量X为可行解；为可行解；全部可行解的集合全部可行解的集合R称为可行解域。称为可行解域。（2）最优解：使目标函数为最大（或最小）的可行解）最优解：使目标函数为最大（或最小）的可行解X*。二、线性规划的图解法二、线性规划的图解法l 图解法步骤：图解法步骤：1、根据约束条件画出可行解域；、根据约束条件画出可行解域；（1）先作非负约束）先作非负约束（2）再作资源限制约束）再作资源限制约束（3）各约束的公共部分即该）各约束的公共部分即该LP的约束的图形（可行域）的约束的图形（可行域）2、画出目标函数的等值线；、画出目标函数的等值线；（1）任给）任给z两个不同的值，作相应两条直线两个不同的值，作相应两条直线（2）将目标直线向增大的方向移，直至可行域的边界，）将目标直线向增大的方向移，直至可行域的边界，交点交点X*即最优解。即最优解。3、求出最优解。、求出最优解。由交点二直线联立求解出最优解由交点二直线联立求解出最优解X*的值。的值。x1x209040405030100Dl1l2l3例例1 用图解法求解下列线性规划问题。用图解法求解下列线性规划问题。可行域可行域目标函数等值线目标函数等值线X*有唯一最优解（顶点有唯一最优解（顶点D）解直线解直线l2,l3组成的线性方组成的线性方程组得：程组得：X*=(20,24)T最优生产方案最优生产方案Z*=720+1224=428最大收入最大收入（2）在模型（）在模型（1）中，目）中，目标标函数改函数改为为 max z=3x1+10 x2，其它不，其它不变变。09040405030100Dl1l2l3AX1易知，目易知，目标标函数等函数等值值线线与直与直线线l l3 3平行。平行。X2故故线线段段ADAD上的点均上的点均为为最最优优解。解。有无有无穷穷多最多最优优解解x1x204可行域无界，在可行域上没可行域无界，在可行域上没有使目标函数值为有限的最有使目标函数值为有限的最优解。优解。无有限最优解（无界解）无有限最优解（无界解）1x2012x1-1不存在所有约束条件的不存在所有约束条件的公共范围公共范围无可行解无可行解小结：1、线性规划问题2、两个重要结论、两个重要结论1）线性规划的可行域是凸多面体。）线性规划的可行域是凸多面体。2）线性规划的最优解在可行域的角点（顶点）上。）线性规划的最优解在可行域的角点（顶点）上。凸多面体凸多面体凹多面体角点（顶点）思考题：约束条件不等式的几何意义是什么？思考题：约束条件不等式的几何意义是什么？怎样做图？怎样做图？2.4.1 运输问题的一般模型运输问题的一般模型一、一般提法一、一般提法1、产销平衡问题、产销平衡问题 A1（a1）A2（a2）产地：产地：.Am（am）B1（b1）B2（b2）销地：销地：.Bn（bn）2.4 运输问题2.4.1 运输问题的一般模型2.4.2 表上作业法2.4.3 产销不平衡问题 已知从已知从Ai到到Bj的单位运价为的单位运价为cij,且且问题：如何制定最合理的物资调运方案，问题：如何制定最合理的物资调运方案，使总运费最低？使总运费最低？2、产销不平衡问题、产销不平衡问题（化为产销平衡问题来 解决）供不应求：供大于求：例：某食品公司下设3个加工厂和4个门市部，各加工厂每天的产量和各门市部每天的销量及运价如表：门市部加工厂B1B2B3B4产量A13113107A219284A3741059销量365620A2A3B2A1B3B4B1运输问题网络图a2=4a3=9b1=3b2=6b3=5b4=6a1=7供应量供应地运价需求量需求地311310192874105二、模型设从设从Ai 到Bj的运量是xij(i=1,2,3;j=1,2,3,4),z为总费用。min z=3x11+11x12+3x13+10 x14 +x21+9x22+2x23+8x24 +7x31+4x32+10 x33+5x34 x11+x12+x13+x14=7 x21+x22+x23+x24=4 x31+x32+x33+x34=9 x11+x21+x31=3 x12+x22+x32=6 x13+x23+x33=5 x14+x24+x34=6 xij0 (i=1,2,3;j=1,2,3,4)运输问题的一般模型运输问题的一般模型有有m m个产地生产某种物资，有个产地生产某种物资，有n n个地区需要个地区需要该类物资。该类物资。令令a a1 1,a a2 2,a am m表示各产地产量，表示各产地产量，b b1 1,b b2 2,b bn n表示各销地的销量，表示各销地的销量，a ai i=b bj j 称为产销平衡。称为产销平衡。设设x xijij表示产地表示产地 i i 运往销地运往销地 j j 的物资量，的物资量，c cijij表示对应的单位运费，则我们有运输问表示对应的单位运费，则我们有运输问题的数学模型如下：题的数学模型如下：u运输问题有运输问题有m n个决策变量，个决策变量，m+n个约束个约束条件。由于有产销平衡条件，只有条件。由于有产销平衡条件，只有m+n1个个约束相互独立，因此，运输问题的基变量只约束相互独立，因此，运输问题的基变量只有有m+n1 个个.模型特点：（1）有有限最优解）有有限最优解（2）系数矩阵中每列只有两个）系数矩阵中每列只有两个1，其余全，其余全 为为0。（3）基变量的个数）基变量的个数=m+n-1运输问题的表格表示2.4.2 表上作业法表上作业法运输问题的求解步骤运输问题的求解步骤确定初始可行方案（最小元素法）确定初始可行方案（最小元素法）最优性检验（闭回路法）最优性检验（闭回路法）调整新方案调整新方案方法：最先满足最小的运费安排调运。方法：最先满足最小的运费安排调运。总是从运价表中找最小元，优先满足供应，填上总是从运价表中找最小元，优先满足供应，填上相应运量后划去一线（最后划两线）。相应运量后划去一线（最后划两线）。一、确定初始可行方案-最小元素法314336初始解：初始解：x13=4，x14=3，x21=3，x23=1，x32=6，x34=3，其余，其余xij=0相应的运费为：相应的运费为：Z0=34+103+13+21+46+53=86v方法评价：优点：较简便易行，方法评价：优点：较简便易行，有目标观念。有目标观念。缺点：只从单一格出发，缺点：只从单一格出发，无全局观念。无全局观念。u注：注：（1）有数字格表示基变量，）有数字格表示基变量，其个数为其个数为m+n-1，空格表示非基变量。，空格表示非基变量。（2）每填上一个数后，则只能划去一行（或）每填上一个数后，则只能划去一行（或一列）。一列）。（3）若中间过程填上一个数后，同时划去一）若中间过程填上一个数后，同时划去一行和一列，有数字格的个数将少行和一列，有数字格的个数将少1个，这时，个，这时，要在所划去的该行（或该列）上任意一格填要在所划去的该行（或该列）上任意一格填一个一个0，此格当有数格对待。，此格当有数格对待。二、最优性检验二、最优性检验-（计算空格检验数）（计算空格检验数）要求：除此空格外，其余顶点均为有要求：除此空格外，其余顶点均为有数格。数格。方法：方法：找出每个空格的闭回路。找出每个空格的闭回路。闭回路：由水平或垂直线组成的闭合闭回路：由水平或垂直线组成的闭合图形。图形。314336（2）计算每个空格的检验数。）计算每个空格的检验数。等于其闭回路上由此空格起奇数顶点运价与偶数等于其闭回路上由此空格起奇数顶点运价与偶数顶点运价的负值之和。顶点运价的负值之和。31433611=3-3+2-1=112=11-10+5-4=222=9-2+3-10+5-4=124=8-10+3-2=-131=7-5+10-3+2-1=1033=10-3+10-5=12（3）若所有）若所有ij0，则当前方案是最优方，则当前方案是最优方案，否则转第三步调整新方案。案，否则转第三步调整新方案。注：运输问题检验数的经济意义：注：运输问题检验数的经济意义：当该空格增运当该空格增运1单位时引起的总运单位时引起的总运费的增量。费的增量。本例中由于本例中由于24=-1销销1、模型、模型2、方法、方法增加一个虚设的销地，其销量为增加一个虚设的销地，其销量为ai-bj。例：求解下面的运输问题。例：求解下面的运输问题。虚拟一个销地8145411=2-4+3-1=023=6-5+4-3=224=0-0+4-3=1所有所有ij0,得到最优解。得到最优解。最优解：最优解：x12*=1，x13*=4，x14*=5，x21*=8，x22*=4，其，其余余xij*=0最少运费为：最少运费为：Z*=41+54+18+34+0=44二、产二、产销销1、模型、模型2、方法、方法增加一个虚设的产地，其产量为增加一个虚设的产地，其产量为bj-ai。