第1章 线性规划2-对偶理论

《第1章 线性规划2-对偶理论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1第二章线性规划的对偶理论2.1对偶问题的提出2.2原问题与对偶问题2.3对偶问题的基本性质2.4影子价格2.5对偶单纯形法2.6灵敏度分析DUAL2线性规划对偶理论概述线性规划对偶理论自1947年提出以来，已经有了很大发展，已成为线性规划的必不可少的重要基础理论。对偶理论是线性规划中的一个最重要的最有趣的概念。支持对偶理论的基本思想是，每一个线性规划问题都存在一个与其对偶的问题。在求出一个问题解的时候，也同时给出了另一问题的解。线性规划对偶问题以及对偶理论中对偶定理的运用是线性规划中主要考点。32.1对偶问题的提出42.1对偶问题的提出52.1对偶问题的提出每一个LP问

2、题，都伴随着另一个LP，而且二者有密切关系，互为对偶，另其中一个问题为原问题，另一个问题为对偶问题，只要得到了其中一个问题的解（目标值），也得到另一问题的解，因此通常只求解一个问题就可以了。例1：（美佳公司）美佳公司应如何生产安排，使已有资源利润最大化。某公司至少该出多大代价，使美佳公司愿意放弃自己的资源，产品资源ⅠⅡ资源约束A0515B6224调试工序115单位产品利润21产品资源AB调试工序单位资源利润Ⅰ0612Ⅱ5211资源量1524562.1对偶问题的提出LP1与LP2两个线性规划问题的表现形式和系数之间存在许多对应关系。并且有我们称前者为原问题，后者是前者的对偶

3、问题。72.2原问题与对偶问题一般认为变量均为非负约束的情况下，约束条件在目标函数取Max时均取“≤”号；当目标函数求Min值时均取“≥“号。则称这些线性规划问题具有对称性。maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn≤b1a21x1+a22x2+……+a2nxn≤b2……am1x1+am2x2+……+amnxn≤bmx1,x2,……,xn≥0minw=b1y1+b2y2+……+bmyms.t.a11y1+a21y2+……+am1ym≥c1a12y1+a22y2+……+am2ym≥c2……a1ny1+a2ny2+……+amn

4、ym≥cny1,y2,……,ym≥0MaxZ=CXs.t.AX≤bX≥0Minw=Y’bs.t.A’Y≥C’Y≥08原问题maxz=CXs.t.AX≤bX≥0对偶问题minw=Y’bs.t.A’Y≥C’Y≥0≥maxbCCATb≤minmnmnA9举例：maxZ=3x1+2x2s.t.-x1+2x2≤43x1+2x2≤14x1-x2≤3x1,x2≥0minw=4y1+14y2+y3s.t.-y1+3y2+y3≥32y1+2x2-y3≥2y1,y2,y3≥0y1y2y3第一种资源第二种资源第三种资源第一种产品第二种产品x1x210原始问题为minz=2x1+3x2-x3s.

5、t.x1+2x2+x3≥62x1-3x2+2x3≥9x1,x2,x3≥0根据定义，对偶问题为maxy=6y1+9y2s.t.y1+2y2≤22y1-3y2≤3y1+2y2≤-1y1,y2≥0原始问题是极小化问题原始问题的约束全为≥原始问题有3个变量，2个约束原始问题的变量全部为非负对偶问题是极大化问题对偶问题的约束全为≤对偶问题有2个变量，3个约束原始问题的变量全部为非负11对偶问题的对偶maxz=6x1+9x2s.t.x1+2x2≤22x1-3x2≤3x1+2x2≤-1x1,x2≥0minw=2y1+3y2-y3s.t.y1+2y2+y3≥62y1-3y2+2y3≥9y

6、1,y2,y3≥0对偶问题的对偶就是原始问题。两个问题中的任一个都可以作为原始问题。另一个就是它的对偶问题。根据定义写出对偶问题根据定义写出对偶问题maxu=6w1+9w2s.t.w1+2w2≤22w1-3w2≤3w1+2w2≤-1w1,w2≥012对偶问题的性质总结对偶的对偶就是原始问题maxz=CXs.t.AX≤bX≥0minw=Y’bs.t.ATY≥C’Y≥0对偶的定义maxu=CWs.t.AW≤CW≥013maxZ=x1+4x2+2x3s.t.5x1-x2+2x3≤8x1+3x2-3x3≤5x1,x2,x3≥0minw=8y1+5y2s.t.5y1+y2≥1-y1

7、+3y2≥42y1-3y2≥2y1,y2≥014数学模型Cj21000CBXBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2σj000-1/4-1/2cj-15-24-500-MCBYBby1y2y3y4y5y6θ-My62061-1011/3-15y11/512/51/50-1/505/2σj06M-18M-2-M-30-24y21/3011/6-1/601/62-15y11/5102/151/15-1/5-1/151/2σj001-3-3-M+8-