线性规划的对偶理论课件

*

线性规划的对偶理论*1.对偶问题的提出1.从数学角度提出对偶问题(1)正规化的线性规划数学模型(2)检验数与最优条件(3)对偶模型2.从经济学角度提出对偶问题(1)例1(2)例1的数学模型

(3)例1的对偶模型*正规化的线性规划数学模型Maxz=CXAX+EXs=bX,Xs

0*检验数与最优条件*对偶模型*例1*例1的数学模型Maxz=8x1+7x2x1+2x2

1004x1+3x2

2005x1+6x2

300x1，

x2

0*例1的对偶模型Minz=100x1+200x2+300x3x1+4x2+5x3

82x1+3x2+6x3

7x1，

x2

0*2.对偶关系*3.对偶性质1.对称性:对偶问题的对偶是原问题；2.弱对偶性:CX

Yb,X和Y是可行解；3.无界性:原问题无界,对偶问题无可行解；4.最优性:CX=

Yb,X和Y是最优解；5.对偶性:原问题与对偶问题同时具有最优解且最优值相等；6.互补松弛性；7.对应性。*互补松弛性对于线性规划的最优解，若某一约束条件的对偶变量值大于零，则该约束条件取严格等式；反之，若约束条件取严格不等式，则其对应的对偶变量一定为零。*对应性1.原问题：Maxz=CXAX+EXs=b，X，Xs

0

2.对偶问题：

Minz=YbYA-EYs=C，Y，Ys

0

3.对应关系4.例2

*4.对偶单纯形法1.对偶单纯形法的内涵2.对偶单纯形法的优点和应用的前提条件3.对偶单纯形法的计算步骤

4.例3（例3-5）*对偶单纯形法的内涵对偶单纯形法：在对偶可行基的基础上进行的单纯形法即为对偶单纯形法。单纯形法是在原问题可行的基础上，通过迭代使对偶问题达到可行，从而得到最优解。根据对偶问题的对称性，可这样考虑，若原问题不可行而对偶问题可行，那么在保持对偶问题可行的基础上，逐步迭代使原问题达到可行，也可得到最优解。*对偶单纯形法的优点和

应用的前提条件对偶单纯形法的优点是原问题的初始解不要求是可行解，可以从非可行解开始迭代，从而省去了引入人工变量的麻烦。当然对偶单纯形法的应用也是有前提条件的，这一前提条件就是对偶问题的解是基可行解。*对偶单纯形法的计算步骤1.根据对偶基可行解列初始单纯形表；2.最优性检验：若原问题也为基可行解，则已得到最优解，过程结束；否则，进入第3步。3.选择出基变量：Min{bi

|

bi0}4.选择入基变量：Min{

j

/aij

|

aij

0}若所有的aij均大于零，则无可行解。5.迭代运算，重复1~4步。*例2Maxz=2x1+x23x1+4x2+x3=186x1+2x2+x4

=24

x1+x2+x5

=6

x1~4

0

Minw=18y1+24y2+6y33y1+6y2+y3-y4=24y1+2y2+y3-y5=1y1~5

0

*例2的求解结果*例3（第35页例3-5）Minw=x1+4x2+3x4

x1+2x2-x3+x43-2x1-x2+4x3+x42

x1~40

转换成标准形式：Minw=x1+4x2+3x4

x1+2x2-x3+x4-x5=3-2x1-x2+4x3+x4-x6=2

x1~60

*例3的求解过程

*例3的求解过程

*例3的求解过程*5.线性规划的灵敏度分析1.灵敏度分析的内涵2.灵敏度分析的处理方法3.资源系数变化的灵敏度分析4.价值系数变化的灵敏度分析

5.技术系数变化的灵敏度分析6.增加新变量的灵敏度分析7.增加新约束的灵敏度分析*灵敏度分析的内涵灵敏度分析是对系统因环境变化显示出来的敏感程度的分析。在线性规划中讨论灵敏度分析，目的是描述一种能确定模型结构中元素变化对问题最优解影响的分析方法。灵敏度分析主要回答两方面问题：因素有一定量变化时，最优解有什么变化；因素在什么范围内变化时，最优解保持不变。*灵敏度分析的处理方法*资源系数变化的灵敏度分析1.基本原理

(B|E)

(E|B-1)A

B-1A，XB=B-1(b+b)

j保持不变，

XB

非负最优基不变。2.第37页例3-6

Maxz=5x1+12x2+4x3+0x4-Mx5x1+2x2+x3+x4

=52x1-x2+3x3+x5=2

x1，x2，x3，x4

，x50

*例3-6的求解

*例3-6的求解

*例3-6的求解

*例3-6的求解*价值系数变化的灵敏度分析1.原理：cj

的变化只会影响

j2.第38页例3-7

Maxz=2x1+3x2+x3x1+x2+x3+x4

=3x1+4x2+7x3+x5=9

x1，x2，x3，x4

，x50

*第38页例3-7的求解

*第38页例3-7的求解

*第38页例3-7的求解

*第39页例3-8的求解

*第39页例3-8的求解

*第39页例3-8的求解*技术系数变化的灵敏度分析1.原理：同bi的变化，B-1pj

反映进最终单纯形表。2.Xj

为非基变量3.Xj

为基变量4.练习第41页例3-115.练习第41页例3-12*Xj

为非基变量（例3-7）*

Xj

为基变量（例3-7）

*

Xj

为基变量（例3-7）*第41页例3-11

Maxz=5x1+12x2+4x3x1+2x2+x3+x4

=52x1-x2+3x3+x5=2

x1，x2，x3，x4

，x50

*第41页例3-11

*第41页例3-11*第41页例3-12

Maxz=2x1+3x2+x3x1+x2+x3+x4

=3x1+4x2+7x3+x5=9

x1，x2，x3，x4

，x50

*第41页例3-12

*第41页例3-12

*第41页例3-12*增加新变量的灵敏度分析1.步骤：(1)求

新，如果

新0，最优解不变；如果

新0，最优解有变化。(2)B-1p新

反映进最终单纯形表，并用单纯形法求解。2.例题：第42页例3-13*第42页例3-13

*第42页例3-13*增加新约束的灵敏度分析1.步骤：(1)检验原最优解是否满足新增加的约束条件，如果满足，最优解不变；如果不满足，最优解变化；(2)将新约束反映进最终单纯形表；

(3)基变量系数向量单位化；(4)用单纯形法、对偶单纯形法或引入人工变量求解。2.例题：第43页例3-14*第43页例3-14

Maxz=2x1+3x