第二章对偶理论ppt课件.ppt

《第二章对偶理论ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章LP的对偶理论(dualtheory)§1对偶问题的提出§2原问题与对偶问题§3对偶问题的基本性质§4对偶问题的经济意义——影子价格§5对偶单纯形法§6灵敏度分析§7参数线性规划1§1对偶问题的提出一、对偶问题的提出在理论上和实践上，对偶理论都是LP中一个十分重要和有趣的概念。支持对偶理论的基本思想是，每一个LP问题都存在一个与其对偶的问题，原问题与对偶问题对一个实际问题从不同角度提出来，并进行描述，组成一对互为对偶的LP问题。在求出一个问题解的时候，也同时可以得到另一个问题的解。下面通过一个例子看一下对偶问题的经济意义。2美佳公司

2、计划制造甲乙两种产品。已知各制造一件产品时分别占用设备A,B的台时，每天可用于这两种产品的能力，各售出一件时的获利能力如下表。问该公司应制造两种产品各多少件，获取的利润最大？项目甲乙每天可用能力设备A1517设备B6224利润213MAXZ=2X1+X2满足条件：X1+5X2176X1+2X224X1≥0,X2≥0列出线性规划模型为：4现从另一个角度提出问题：假定东方公司想把美佳公司（的资源)收买过来，它至少应付出多大代价（底线），才能使美佳公司愿意放弃生产活动，出让自己的资源？显然，该企业愿意出让的条件是，出让的价格不应低于同

3、等数量资源由自己组织生产活动时获取的利润。分析：设y1,y2分别表示单位时间（h）设备A、设备B的出让代价，则从东方公司来看，希望用最小的代价把全部资源收买过来，故有：minw=17y1+24y2因生产一件甲产品需两种设备分别为1、6小时，盈利2元，生产一件乙产品需两种设备分别为5、1小时，盈利1元。从美佳公司来看，出让资源获得的利润应不少于自己组织生产获得的利润。因此有：y1+6y225y1+2y215要使收买成功，双方的要求都必须满足，于是得到出让资源问题的线性规划数学模型：minw=17y1+24y2y1+6y225y1+

4、2y21y10,y20于是我们得到两个线性规划：6原问题：LP1:maxZ=2X1+X2X1+5X2176X1+2X224X10,X20对偶问题：LP2：minw=17y1+24y2y1+6y225y1+2y21y10,y20我们把LP2称为LP1的对偶问题；若把LP2看成原问题，则LP1就是LP2的对偶问题。比较两者，看有什么规律？71）目标函数的目标互为相反(max,min)；2）目标函数的系数是另一个约束条件右端的向量；3）约束系数矩阵是另一个的约束系数矩阵的转置；4）约束方程的个数与另一个的变量的个数相等；

5、5）约束条件在一个问题中为“≤”，在另一个问题中为“”。8二、对偶问题的一般提法（对称形式下对偶问题的一般提法）看书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)9三、LP的对偶问题也可以从数学的角度引

6、出来（了解）检验数为B=CB-CBB-1B(1)N=CN-CBB-1N(2)-Y=CBB-1(1)(2)合到一起，检验数一般形式为：=C-CBB-1A令Y=CBB-1，称为单纯形乘子当所有j0时，YACY0又Z=CX=CBb’=CBB-1b=Yb=W,所以：minw=Ybst.YACY010从例子看到，原问题为求max，对偶问题为求min，因为：（1）对偶问题的可行解（Y=CBB-1）满足原问题的最优化条件（0）；（2）因此对原问题来说，只有最优解（X＊=B-1b）才是其对偶问题的可行解。（3）也即原问题的最优解目标

7、函数值是它的对偶问题可行解目标函数值最小的一个。(注意对偶问题求min)(Z＊=CX=CBb／=CBB-1b=Yb=W)（4）由此可知，原问题目标函数的最大值对应于对偶问题的目标函数的最小值。CX＊Yb（具体见第三节基本性质）11一、对偶关系（对称形式）§2原问题与对偶问题原问题对偶问题maxz=CXminw=Ybst.AXbst.YACX0Y0看书上表2.1，验证对应关系对称性：LP的原问题与对偶问题之间存在对称关系，即LP对偶问题的对偶是原问题结论：LP对偶问题与原问题互为对偶。看例2，通过例子得出结论第一步，化为对称形式下

8、的原问题形式；第二步，根据对应关系写出其对偶问题；第三步，做一变换，得到原问题。12二、非对称形式原问题与对偶问题之间的关系看例3，是一个最小化问题第一步，化为对称形式下的对偶问题形式（min