第二章对偶理论11课件.pptVIP

第二章 LP的对偶理论(dual theory); §1 对偶问题的提出 一、对偶问题的提出 在理论上和实践上，对偶理论都是LP中一个十分重要和有趣的概念。支持对偶理论的基本思想是，每一个LP问题都存在一个与其对偶的问题，原问题与对偶问题对一个实际问题从不同角度提出来，并进行描述，组成一对互为对偶的LP问题。在求出一个问题解的时候，也同时可以得到另一个问题的解。下面通过一个例子看一下对偶问题的经济意义。; 例：美佳公司计划制造甲乙两种产品。已知各制造一件产品时分别占用设备A,B的台时，每天可用于这两种产品的能力，各售出一件时的获利能力如下表。问该公司应制造两种产品各多少件，获取的利润最大？ ; MAX Z= 2X1+X2  满足条件：  X1+5X2 ?17  6X1+2X2 ? 24  X1≥0, X2≥0; 现从另一个角度提出问题：假定东方公司想把美佳公司 （的资源)收买过来，它至少应付出多大代价（底线）， 才能使美佳公司愿意放弃生产活动，出让自己的资源？ 显然，该企业愿意出让的条件是，出让的价格不应低 于同等数量资源由自己组织生产活动时获取的利润。 分析：设y1 , y2 分别表示单位时间（h）设备A 、设备B 的出让代价，则从东方公司来看，希望用最小的代价把全 部资源收买过来， 故有： min w=17 y1 +24 y2 因生产一件甲产品需两种设备分别为1、6小时，盈利2 元，生产一件乙产品需两种设备分别为5、1小时，盈利1 元。 从美佳公司来看，出让资源获得的利润应不少于自己组 织生产获得的利润。因此有： y1 + 6y2 ? 2 5 y1 +2 y2 ? 1 ; 要使收买成功，双方的要求都必须满足，于是得到出让资源问题的线性规划数学模型： min w=17 y1 +24 y2  y1 + 6y2 ? 2 5 y1 +2 y2 ? 1 y1 ? 0, y2 ? 0;原问题： LP1: maxZ=2X1+X2 X1 +5X2 ? 17 6X1+2X2 ? 24 X1 ? 0, X2 ? 0;1）目标函数的目标互为相反(max,min)； 2）目标函数的系数是另一个约束条件右端的向量； 3）约束系数矩阵是另一个的约束系数矩 阵的转置； 4）约束方程的个数与另一个的变量的个数相等； 5）约束条件在一个问题中为“≤ ”，在另一个问题中为 “?”。;二、对偶问题的一般提法（对称形式下对偶问题的一般提法） 看书P41 原问题：m种资源bi(i=1…m)生产n种产品xj(j=1…n)，获利分别为cj (j=1…n)元，aij为工艺系数，则原问题为 Maxz=∑cjxj ∑aijxj≤bi(i=1…m) xj≥0 (j=1…n) 对偶问题：设将上述资源出售定价为yi（i=1…m），使获得收益不低于原企业生产产品出售获得的收益，则应满足 Minw=∑biyi ∑aijyi ≥ cj (j=1…n) yi≥0 (i=1…m) ;三、LP的对偶问题也可以从数学的角度引出来 （了解） 检验数为?B=CB-CBB-1B (1) ?N=CN-CBB-1N (2) -Y= -CBB-1 (1) (2)合到一起，检验数一般形式为 ：?=C-CBB-1A 令Y= CBB-1 ，称为单纯形乘子 当所有?j ? 0时， YA ? C Y ? 0 又Z=CX=CBb’ = CBB-1b=Yb= W,所以： min w=Yb st. YA ? C Y ? 0;;一、对偶关系（对称形式） ; ;;例：给出下列线性规划的对偶问题： MAX Z=X1+ 2 X2 + X3 X1+ X2 – X3 ?2 y1 X1 – X2 + X3 =1 y2 st. 2X1+ X2 + X3 ? 2 y3