数据挖掘-对偶理论与灵敏度分析

运筹学

OPERATIONAL

RESEARCH燕山大学经济管理学院运筹学课程教学课题组编制2第二章线性规划的对偶理论与灵敏度分析3第一节LP的对偶理论一、对偶问题的提出Ⅰ

Ⅱ每天可用能力

设备A0515

设备B6224

调试工序

115

利润

21①两种家电各生产多少,可获最大利润?4解:设两种家电产量分别为变量x1

，x2

5x2

156x1+2x2

24

x1+x2

5

x1，x2

0

maxZ=2x1+x25②另一家公司至少应付出多少代价才能使美佳公司愿意出让自己的资源而不组织两种产品的生产？解：设

y1,

y2,

y3分别为A,B设备和调试工序工时出让的单价。minW=15y1+24y2+5y36y2+y325y1+2y2+y31y1…y3

06二、对偶问题与原问题的关系1.“对称型”(P)MaxZ=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXnb1a21X1+a22X2+…+a2nXnb2………am1X1+am2X2+…+amnXnbmXj0(j=1,…,n)7MinW=b1Y1+b2Y2+…+bnYna11Y1+a21Y2+…+am1Ymc1a12Y1+a22Y2+…+am2Ymc2………a1nY1+a2nY2+…+amnYmcnYi0(i=1,…,m)(D)8例1：写出下面问题的对偶规划maxZ=5X1+6X23X1-2X2

74X1+X2

9X1,X2

0minW=7y1+9y23y1+4y25

-2y1+y2

6y1,y2

09例1：写出下面问题的对偶规划maxZ=5X1+6X23X1-2X2=74X1+X2

9X1,X2

02.“非对称型”(P)10对偶问题minW=7y1+9y23y1+4y25

-2y1+y2

6y1自由

,y2

011例2：写对偶规划minZ=4X1+2X2-3X3-X1+2X2

62X1+3X3

9X1+5X2-2X3=

4X2,X3012maxW=6y1+9y2+4y3-y1+2y2+y3=

42y1+5y323y2-2y3

-3y10,y20,y3自由13minZ=4X1+2X2-3X3X1-2X2

-

62X1+3X3

9X1+5X2-2X3=

4X2,X30或将原问题变形为14观察结论:①一对对偶问题都有最优解，且目标函数值相等。②最优表中有两个问题的最优解。15第二节对偶问题的基本性质一、单纯形法计算的矩阵描述maxZ=CX

AX≤bX0(P)maxZ=CX

AX+IXS=bX,XS016（初始单纯形表）非基变量基变量XBXNXS0XSbBNIσCBCN017（迭代中的单纯形表）基变量非基变量XBXNXS0XBB-1bIB-1NB-1σ0CN-CBB-1N-CBB-118二、对偶问题的基本性质1.对称性：对偶问题的对偶问题是原问题2.定理1(弱对偶定理)若,分别是原问题和对偶问题的可行解，则存在推论：1.原问题任一可行解的目标函数值是其对偶问题目标函数值的下界，反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。19

推论：2.若原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之，对偶问题有无界解，原问题无可行解。（但逆向不成立）推论：3.若原问题有可行解，对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解，而原问题无可行解，则对偶问题的目标函数值无界。203.定理2yX,分别为(P),(D)的可行解，且XyC=b,则它们是(P),(D)

的最优解。4.定理3（对偶定理）若原问题有最优解，对偶问题也有最优解，且目标函数值相等。或若原问题与对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。5.互补松弛性：，分别是原问题和对偶问题的可行解，则当且仅当为最优解。21例：min=2x1+3x2+5x3+2x4+3x5其对偶解

y1﹡=4/5y2﹡=3/5Z﹡=5用对偶理论求(P)的最优解x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53

xi0(i=1…5)(P)在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，该约束条件取严格等式。反之，若约束条件取严格不等式，则其所对应的对偶变量一定为0。22

第四节对偶单纯形法minZ=2X1+3X2+4X3X1+2X2+X3

32X1-X2+3X34X1,X2,X3023初始单纯形表为CBXBbx1x2x3x4x5-2-3-4000x4-3-1-2-1100x5-4-21-301σ-2-3-40024思路：(max型)单纯形法：找基B，满足B-1b0，即先找到基可行解，当

C

-CBB-1A不全0，（即检验数）。迭代保持B-1b0，使C

-CBB-1A0，即CBB-1AC，（保持原问题的为基可行解，寻找对偶问题的可行解）25一、对偶单纯形法的基本思路：找基B，满足C

-CBB-1A0（检验数），即找到对偶问题的可行解。如果B-1b不全0，即原问题的基解为非可行解，则迭代保持C

-CBB-1A0，使B-1b0。即保持对偶问题的解为可行解，使原问题的基解逐渐转换为基可行解。26二、对偶单纯形法基本步骤max型(min型)(1)

作初始表，要求全部σj

0(0)(2)

判定：B-1b全0，停。否则，取max{B-1b}=(B-1b)l

B-1b<0令第

l行的Xjl为换出变量.27(3)确定换入变量①若Xil行的alj全0，停，原问题无可行解。②若Xil行的alj有alj<0,则求σjσkθ=min{}=aljalkalj<0

Xk为换入变量σkalk(4)

以alk为主元，换基迭代28CBXBbx1x2x3x4x5-2-3-4000x4-3-1-2-1100x5-4-21-301σ-2-3-400θ1-4/3--29CBXBbx1x2x3x4x5-2-3-4000x4-10-5/21/21-1/2-2x121-1/23/20-1/2σ0-4-10-1θ-8/5--230CBXBbx1x2x3x4x5-2-3-400-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5σ00-9/5-8/5-1/531练习1：maxZ=-X1-4X2-3X4X1+2X2-X3+X4

3-2X1-X2+4X3+X42X1…X4

032最优解：X=(7,0,4,0)TZ=-7-1-40-300CBXBbX1X2X3X4X5X60X5-3(-1)-21-1100

X6-221-4-1010σ

-1-40-300-1

X1312-11-100

X6-80-3(-2)-321

-

3σ

0-2-1-2-10-1

X1717/205/2-2-1/20

X3403/213/2-1-1/2

-7

σ0-1/20-1/2-2-1/233maxZ=-X1-X22X1-X2

2-X1+1/2X21X1,X2

0练习2：34第五节灵敏度分析CBB-1bC

-CBB-1AB-1bB-1A原始数据A，b，CA=(P1P2…

Pn)aij,bj,cj一、灵敏度分析的概念对系统或事物（线性规划问题）因周围条件的变化（如aij,bj,cj

的变化）显示出来的敏感程度的分析。35(1)参数A，b，C在什么范围内变动，对当前方案无影响？(2)参数A，b，C中的一个(几个)变动，对当前方案影响？(3)如果最优方案改变，如何用简便方法求新方案？二、灵敏度分析所解决的问题36原问题对偶问题结论或继续计算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表重新计算37一、分析cj的变化cj的变化首先影响检验数①XB=B-1b

②σA=

C

-CBB-1A=C

-Y

A

σN=

CN-CBB-1N=CN-Y

Nσj=

Cj-CBB-1Pj=Cj-Y

Pj

38maxZ=2X1+X25X2+X3=156X1+2X2+X4=24X1+X2+X5=5Xj0设备A设备B调试工序39CBXBbx1x2x3x4x5θ210000x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2σ000-1/4-1/21.若家电1的利润降至1.5元/件，而家电2的利润增至2元/件时，美佳公司最优生产计划有何变化？402.若家电1的利润不变，则家电2的利润在什么范围内变化时则该公司的最优生产计划将不发生变化。CBXBbx1x2x3x4x5θ21+λ0000x315/20015/4-15/22x17/21001/4-1/21+λx23/2010-1/43/2σ000-1/4+1/4λ-1/2-3/2λ41-1/4+1/4λ≤0-1/2-3/2λ≤0-1/3≤λ≤12/3≤c2≤242二、分析

bi的变化bi的变化首先影响XB=B-1b

①XB=B-1b

②σA=

C

-CBB-1A=C

-Y

A

σN=

CN-CBB-1N=CN-Y

Nσj=

Cj-CBB-1Pj=Cj-Y

Pj

433.若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化。∵XB=B-1b，b

b’=b+△b

∴

XB=B-1b’=B-1(b+△b)=B-1b+B-1△bB-1△b=5/4–15/201001/4-1/28=20-1/43/20-244CBXBbx1x2x3x4x5θ210000x335/20015/4-15/22x111/21001/4-1/21x2-1/2010-1/43/2σ000-1/4-1/245CBXBbx1x2x3x4x5θ210000x335/20015/4-15/22x111/21001/4-1/21x2-1/2010-1/43/2σ000-1/4-1/20x315051002x15110010x420-401-6σ0-100-2464.若设备A和B每天能力不变，而调试工序在什么范围内变化，问题的最优基不变。B-1△b=5/4–15/20

-15/2λ01/4-1/20=-1/2λ0-1/43/2λ3/2λ47CBXBbx1x2x3x4x5θ210000x315/2-15/2λ0015/4-15/22x17/2-1/2λ1001/4-1/21x23/2+3/2λ010-1/43/2σ000-1/4-1/21≤λ≤14≤b3≤648三、增加一个决策变量xj的分析

5.公司计划推出新产品3，生产一件所需设备A,B及调试工序的时间分别为3小时、4小时、2小时，预期盈利3元/件，试分析该种产品是否值得投产，如投产，对该公司的最优生产计划有何影响。49σ6=

C6-CBB-1P6=C6-Y

P63=3-(0,1/4,1/2)4=12P6

=B-1P6=~5/4-15/23-701/4-1/24=00-1/43/22250CBXBbx1x2x3x4x5x62100030x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/22σ000-1/4-1/2151CBXBbx1x2x3x4x5x62100030x315/20014/5-15/2-72x17/21001/4-1/201x23/2010-1/43/22σ000-1/4-1/210x351/407/213/8-9/402x17/21001/4-1/203x63/401/40-1/83/41σ0-1/20-1/8-5/4052四、分析

aij的变化①XB=B-1b②σj=

Cj-CBB-1Pj=Cj-Y

Pj

③Pj

=B-1Pj

~53CBXBbx1x2x3x4x5x2’2100030x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2σ000-1/4-1/254σ2’

=

C2’

-CBB-1P2’=C2’

-Y

P2’8=3-(0,1/4,1/2)4=3/21P2

=B-1P2’=~5/4-15/2811/201/4-1/24=1/20-1/43/211/255CBXBb