当前位置:首页 >> 其它课程 >> 运筹学教学课件 第二章 对偶理论与灵敏度分析

运筹学教学课件 第二章 对偶理论与灵敏度分析


第二章 对偶理论与灵敏度分析
? ? ?

?
?

?
?

§1 单纯形法的矩阵描述 §2 改进单纯形法 §3 对偶问题的提出 §4 线性规划的对偶理论 §5 对偶问题的经济解释——影子价格 §6 对偶单纯形法 §7 灵敏度分析

本章重点与难点
一、重点

? 1、对偶问题 能写出任意一个线性规 划的对偶问题 2、对偶问题的性质及其应 用 ? 对称性、 ? 弱对偶性、 ? 无界性、
? ? ?

?

从最优单纯形表中获得 最优基矩阵的逆矩阵* 从最优单纯形表中获得 对偶问题的最优解*

?

3、对偶单纯形法
? ? ?

思想 步骤 计算
什么是灵敏度分析 资源数量变化的分析 价值系数变化的分析 技术系数变化变化的分 析

?

4、灵敏度分析
? ? ? ?

? ?

可行解释最优解时的性 质 对偶定理、 互补松弛性

本章难点
二、难点 ? 1、对偶问题 能写出任意一个线性规 划的对偶问题 2、对偶问题的性质及其应 用 ? 对称性、 ? 弱对偶性、 ? 无界性、
? ? ? ?

从最优单纯形表中获得 最优基矩阵的逆矩阵 从最优单纯形表中获得 对偶问题的最优解 思想 步骤 计算 什么是灵敏度分析 资源数量变化的分析 价值系数变化的分析 技术系数变化变化的分 析

?

?

3、对偶单纯形法
? ? ?

?

4、灵敏度分析
? ? ? ?

?
?

可行解释最优解时的性 质 对偶定理、 互补松弛性

§1 单纯形法的矩阵描述
?
? ?

设线性规划问题

?

Max z=CX AX≤b X≥0

?
? ? ?

给这个线性规划问题的约束条件加入松弛 变量Xs=( xn+1,xn+2,…,xn+m)T得到标准型:
Max z=CX+0Xs AX+IXs=b X,Xs≥0 (2.1) (2.2) (2.3)

?

设B是一个可行基,即基矩阵。若将系数 矩阵(A,I)分为(B,N)两块,这里N是非基 变量的系数矩阵。对应于B的基变量,用 向量XB=(xB1,xB2,…,xBm)T表示,则

? XB ? X ?? ?X ? ? ? ? N?
? ? ?

同时C=(CB,CN)于是 ? XB ? (B,N) ? ? =b ? ?
?XN ?

?

(CB,CN)

? XB ? ? ? =CBXB+CNXN ?X ? ? N?

? ? ?

?
?

?
? ? ? ?

将(2.1),(2.2),(2.3)改写为 Max z=CBXB+CNXN (2.4) BXB+NXN=b (2.5) XB,XN≥0 将(2.5)移项后得到 BXB =b-NXN (2.6) 对(2.6)左乘B-1后得 XB = B-1b- B-1NXN (2.7) 将(2.7)代入(2.4)得 z=CB B-1b+(CN- CBB-1N)XN (2.8)

?

令非基变量XN=0,得到一个基可行解
? B ?1 b ? ? ?? ?0 ? ? ?

X (1)
?
?

目标函数值 z= CB B-1b

例 单纯形法的矩阵描述
? ?

?
? ?

Max z=2x1+3x2 x1+2x2≤8 4x1 ≤16 4x2 ≤12 X1,x2≥0 对于可行基 ?1 0 B= ? 4 0 ? ?0 1 ?

解 (1)化为标准形 Max z=2x1+3x2+0x3+0x3+0x3 x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1,x2 ,x3,x4 x5≥0

?

?

2? ? N= 0? 4? ?

?1 0? ? ? ?0 1? ?0 0? ? ?

?

?
?

对应的基变量为XB=(x1,x5,x2)T, 非基变量 XN=(x3,x4)T. X=(x1,x5,x2 , x3,x4)T=(XB T ,XN T) T ,CB=(2,0,3),CN=(0,0), C=(2,0,3, 0,0)=(CB ,CN)

用矩阵形式表示为
?

?

? XB ? Max z=(CB,CN) ? ? ?X ? ? N? ? XB ? (B,N) ? ?=b或BXB+NXN=b ?X ? ? N?

?

xB,xN≥0 这里b=(8,16,12),

1/ 4 0? ? 0 ? ? -1= ? 2 1/ 2 0? ? B ? ?1 / 2 ? 1 / 8 1 ? ? ?

? ?

BXB =b-NXN 对上式左乘B-1后得

?

? 4? ? ? XB = B-1b- B-1NXN= ? 4 ?? 2? ? ?

? ?

代入目标函数得 z=CB B-1b+(CN- CBB-1N)XN=14-3/2x3-1/8x4

? 0 1/ 4 ? ? ? ? x3 ? ? ? 2 1/ 2 ? ? x ? ? ? ?1 / 2 ? 1 / 8 ? ? 4 ? ? ?

从(2.7),(2.8)可以看出
(1) 目标函数中非基变量的系数CN- CBB-1N就 是第一章的检验数。因为XB在(2.8)中的系 数是0,即 ? CB-CBB-1B=0 ? 又因CN中对应于Xs的系数为0,在(2.8)式 中Xs的系数实质上是0-CBB-1,因此所有检验数 都可用C-CBB-1A与-CBB-1表示。

( 2) 用矩阵描述时θ规则的表达式是

? ( B ?1b) i ? ( B ?1b) l ? ? ?1 ? ? min? ?1 | ( B Pj ) i ? 0? ? ?1 i ? ( B Pj ) i ? ( B Pj ) l ? ?

(3)单纯形表
? ? ? ?

? ?

为了便于在表中找出B-1 所在的位置,将 (2.4),(2.5)改写为 -z+CBXB+CN1XN1+0Xs=0 BXB+NXN1+IXs=b 当确定XB为基变量时,经过基变换后可得 到XB 与z得表达式(2.7),(2.8)并将他 们改写为 XB+B-1N1XN1+B-1Xs=B-1b -z+(CN-CBB-1N1)XN1- CBB-1Xs=- CBB-1b

上述两式用矩阵表示为
?? z ? ? ? -1 ? ?? X B ? ? B ?1b B ? ? ? ??? -1 ?? - CBB ? X N1 - C B B-1b ? ? ? ? ? ?X ? ? s ?

-1 ?0 I B N1 ? ? 1 0 C - C B-1 N N B 1 ?

用表格表示为表2-1
基变量 XB B CB
?左乘以

非基变量 XN1 Xs N1 CN1 I 0

RHS b 0
?约束条件

B-1
?目标函数

用表格表示为表2-1
基变量 XB I CB
?乘以-

非基变量 XN1 Xs B-1N1 CN1 B-1 0

RHS B-1b 0

去目标函数中的畸变两

CB加到目标函数中消

用表格表示为表2-1
基变量 XB
I 0

?最优解

非基变量 XN1 Xs
B-1N1 CN-CBB-1N1 B-1 - CBB-1

RHS
B-1b - CBB-1b
?目标函数-z

?检验数

?对偶问题

的最优解

的值

cj CB

xB X1 X2 x3

b

3 x1

5 4 0 x2 x3 x4 0 5 4 4 1/3 -2/3 12/3 -5/3

0 x5 0 1 0 0

0 x6 0 0 1 0

8/3 2/3 1 14/3 -4/3 0 20/3 5/3 0 -1/3 0

Cj-zj X2 X3 x1

0 0 1

1 0 0

0 15/41 8/41 -10/41 1 -6/41 5/41 4/41 0 -2/41 -12/41 15/41

Cj-zj

§3对偶问题的提出
?

第一章的例1讨论了利用有限的资源如 何安排生产才能获得最大的利润的问 题。现在从另一角度来讨论这个问题。 假设该工厂的决策者决定这些资源不 用来生产而是考虑将其出租或出售。 这时决策者就要考虑给每种资源如何 定价的问题。

?

?

?
? ?

设用y1,y3,y3分别表示出租单位设备台时的租金和 出让单位原材料A,B得附加值。于是 y1+4y2≥2 2y1+4y3≥3 则所有资源出租和出让,其所得收入为 ω=8y1+16y2+12y3

?
? ?

?
? ?

则得到下面的线性规划问题 minω=8y1+16y2+12y3 y1+4y2≥2 2y1+4y3≥3 y1,y2,y3≥0 称这个线性规划问题为原问题的对偶问题。

下面在从另一角度来讨论。
从§1得到检验数的另一表达式是 ? CN-CBB-1N与- CBB-1 ? 由第一章知,当检验数 ? CN-CBB-1N≤0 ? CBB-1≤0 ? 则线性规划问题已得到最优解。可见(2.9), (2.10)是作为得到最优解的条件。

?

?

? ?

1.(2.9),(2.10)中都有乘子CBB-1 ,称为单 纯形乘子并用符号Y=CBB-1表示。由于(2.10)的 条件,可得Y≥0 2.对应基变量XB 的检验数是0。它是CB-CBB-1B=0. 包括基变量在内的所有检验数可用C-CBB-1A≤0表 示。即C-CBB-1A=C-YA≤0,移项得到YA≥C 3.由条件(2.10)得到-Y=- CBB-1 即Yb= CBB-1b=z因Y的上界为无限大,所以只存 在最小值。

? ? ? ?

?

4.在这里可以得到另一个线性规划问题 Min ω=Yb YA≥C Y≥0 称它为原线性规划问题{Max z=CX|AX≤b,X≥0} 的对偶规划问题。

?

从这两个规划问题的表达式可看出:根据原线 性规划问题的系数矩阵A,C,b就可以写出它的对 偶问题。如第一章的例1,原问题的系数矩阵是;
?1 2? ? ? A ? ?4 0? ? 0 4? ? ?

?

C ? (2,3);

?8 ? ? ? b ? ?16 ? ?12 ? ? ?

那麽它的对偶问题是
?

Min ω=Y(8,16,12)T
?1 2? ? ? Y ? 4 0 ?≥(2,3)或 ATY ≥ ? 0 4? ? ?

?

? 2? ? ? ? 3? ? ?

? ? ? ? ? ?

?

Y≥0 这里Y=( y1,y2,y3) 即 minω=8y1+16y2+12y3 y1+4y2≥2 2y1+4y3≥3 y1,y2,y3≥0

对偶问题的提出_另一个例子
实例:某家电厂家利用现有资源生产两种 产品, 有关数据如下表:
产品Ⅰ 设备A 设备B 调试工序 利润(元) 0 6 1 2 产品Ⅱ 5 2 1 1 D 15时 24时 5时



Ⅰ产量––––– Ⅱ产量–––––

x2

x1
1 2

如何安排生产, 使获利最多?

max z ? 2 x ? x s.t. 5 x ? 15
2

6 x ? 2 x ? 24 x ?x ?5 x,x ? 0
1 2 1 2 1 2

厂 家

设:设备A —— 设备B ––––

调试工序 ––––

y1元/时 y 2元/时 y 3元/时
付出的代价最小, 且对方能接受。
出让代价应不低于 用同等数量的资源 自己生产的利润。

收 购

?

厂家能接受的条件:
出让代价应不低于 2 6 y2 ? y3 ? 用同等数量的资源 5 y1 ? 2 y2 ? y3 ? 1 自己生产的利润。
单位产品Ⅰ出租 收入不低于2元 单位产品Ⅱ出租 收入不低于1元

?

收购方的意愿: min w ? 15 y1 ? 24 y2 ? 5 y3
Ⅰ 设备A 设备B 调试工序 利润(元) 0 6 1 2 Ⅱ 5 2 1 1 D 15时 24时 5时

原 问 题

max z ? 2 x1 ? x 2 s.t. 5 x 2 ? 15 6 x1 ? 2 x 2 ? 24 x1 ? x 2 ? 5 x1, x 2 ? 0
min w ? 15 y1 ? 24 y2 ? 5 y3 s.t 6y ? y ? 2 对
2 3

厂 家

一对对偶问题

5y ? 2y ? y ? 1
1 2 3

收 购

y ,y ,y ?0
1 2 3

厂 家

偶 问 题

原问题
? ? ? ? ? ? ? ? ? ? ?

对偶问题

max s.t.

z ? CX AX ? b X?0

?min w ? Yb ? ? ? s.t. YA ? C ? Y?0 ?
2个约束 3个变量

一 般 规 律

3个约束 2个变量

C ? (c1 , c2 )
? x1 ? X ?? ? ? x2 ?

Y ? (y1,y 2 ,y 3 )
? b1 ? b ? ? b2 ? ? b3 ? ? ?

A ? (aij )

特点:

? min 2.限定向量b ? 价值向量C
1. max (资源向量)

其它形式 的对偶

?

3.一个约束 ? 一个变量。
4. max

? z 的LP约束“? ” min z LP是“? ”的约束。



5.变量都是非负限制。

二、原问题与对偶问题的数学模 型
?

1.对称形式的对偶

当原问题对偶问题只含有不等式约束 时,称为对称形式的对偶。
情形一: 原问题
? ? ? ? ? ? ? ? ? ? ?

对偶问题

max s.t.

z ? CX AX ? b X?0

?min w ? Yb ? ? ? s.t. YA ? C ? Y?0 ?

情形二:

原问题

对偶问题

?max z ? CX ?min w ? Yb ? ? ?s.t AX ? b ? ?s.t YA ? C ? ? X?0 Y?0 ? ?
证明 化为标准对称型 ? CX ?max z ?

? ?s.t ? AX ? ? b ? X?0 ? b ?min w ? ?Y ? ? ? ?s.t ? Y ? ? C A ? Y? ? 0 ?

(Y ? ?Y ?)

?

2、 非对称形式的对偶
若原问题的约束条件是等式,则
原问题 对偶问题

?max z ? CX ?min w ? Yb ? ? ? AX ? b ? ? YA ? C ? Y无约束 ? X ?0 ? ?

推导:
原问题

?max z ? CX ? AX ? b ?? AX ? b ? X ?0 ?

?max z ? CX ?? A ? ? b ? ?? X ? ?? A? ?? b ? ? ? ? ? ? ? X ?0

根据对称形式的对偶模型,可直接 写出上述问题的对偶问题:

?b? ? min w ? (Y ,Y ) ? ?-b? ? ?
1 2

? A ??C (Y 1,Y 2 ) ? ?? A? ? ? Y 1 ? 0 ,Y 2 ? 0

?min w ? (Y 1 ? Y 2 ) ? b ? ? ?(Y 1 ? Y 2 ) ? A ? C ? Y 1 ? 0, Y 2 ? 0 ?


Y ? Y 1 ? Y 2 ,得对偶问题为:
?max w ? Yb ? ? ? YA ? C ? Y无约束 ?
证毕。

三、原问题与对偶问题的对应关 系
原问题(或对偶问题) 对偶问题(或原问题)

目标函数 min w 目标函数 max z n个变量 n个约束 变量 ? 0 约束 ? max z 变量 ? 0 约束 ? 自由变量 约束 ? m个约束 m个变量 min z 约束 ? 变量 ? 0 变量 ? 0 约束 ? 自由变量 约束 ? 目标函数的价值向量 约束条件的限定向量 约束条件的限定向量 目标函数的价值向量

?

例:

max z ? 5 x1 ? 3x 2 ? 2 x 3 ? 4 x 4 ? 5 x1 ? x 2 ? x 3 ? 8 x 4 ? 8 ? s.t ?2 x1 ? 4 x 2 ? 3x 3 ? 2 x 4 ? 10 ? x1,x 2 ? 0 x 3 ,x 4无约束 ?

对偶问题为

min w ? 8 y1 ? 10 y2
? 5 y1 ? 2 y 2 ? 0 ? y1 ? 4 y 2 ? 3 ? s.t.? y1 ? 3 y 2 ? 2 ?8 y1 ? 2 y 2 ? 4 ? y1 ? 0, y2无约束 ?

§4 线性规划的对偶理论

4.1 原问题和对偶问题的关系

表2-2
x y y1 Y2 … ym 对偶关系 Max z a11 a12 … a1n a21 a22 … a2n …………… am1am2… amn ≥≥…≥ c1 c2 …cn ≤ ≤ … ≤ b1 B2


x1 x2 c xn

原关系

minω

bm Max minω

z=

表2-4 线性规划的对偶关系
原问题(或对偶问题) 目标函数max z n个 变 ≥0 量 ≤0 无约束 约 m个 束 ≤ 条 ≥ 件 = 约束条件右端项 目标函数变量的系数 对偶问题(或原问题) 目标函数min w n个 约 ≥ 束 ≤ 条 = 件 n个 ≥0 变 ≤0 量 无约束 目标函数变量的系数 约束条件右端项

例1 试求下述线性规划问题的对 偶问题
? ? ? ?

?

min z=2x1+3x2-5x3+x4 x1+x2-3x3+x4≥5 2x1 +2x3-x4≤4 x2+x3+x4=6 x1≤0,x2,x3≥0;x4无约束


?

?

?
? ? ? ?

设对应于三个约束条件的对偶变量分别为 y1,y2,y3;由于目标函数是求极小值,由上表知 其对偶问题为 max z’=5y1+4y2+6y3 y1+2y2 ≥2 y1 +y3≤3 -3y1+2y2+y3≤-5 y1-y2+y3=1 y1≥0,y2≤0,y3无约束

4.2 对偶问题的基本性质
? ?

? ?

?

1、对称性 对偶问题的对偶是原问题。 2、弱对偶性 若X*是原问题的可行解,Y*是对偶 问题的可行解。则存在 CX*≤Y*b 3、无界性 若原问题(对偶问题)为无界解,则其 对偶问题(原问题)无可行解。 ? 4、可行解是最优解时的性质 设 X 是原问题的可 ? ? ? 行解,Y 是对偶问题的可行解,当C X = Y b时, ? ? 和 X 是最优解。 Y

5、对偶定理 若原问题有最优解, 那么对偶问题也有最优解且两个线 性规划的最优值相同。 ? ? ? 6、互补松驰性 若 X , Y分别是对 偶问题和原问题的可行解。那么 ? ? ? 为 Y Xs=0和Ys X =0,当且仅当 X Y , ? 最优解。
?
? X

7、原问题与对偶问题的解
? 从最优单纯形表中获得最优基矩阵

的逆矩阵*
? 从最优单纯形表中获得对偶问题的

最优解*

用表格表示为表2-1
基变量 XB B CB
?左乘以

非基变量 XN1 Xs N1 CN1 I 0

RHS b 0
?约束条件

B-1
?目标函数

用表格表示为表2-1
基变量 XB I CB
?乘以-

非基变量 XN1 Xs B-1N1 CN1 B-1 0

RHS B-1b 0

去目标函数中的畸变两

CB加到目标函数中消

用表格表示为表2-1
基变量 XB
I 0

?最优解

非基变量 XN1 Xs
B-1N1 CN-CBB-1N1 B-1 - CBB-1

RHS
B-1b - CBB-1b
?目标函数-z

?检验数

?对偶问题

的最优解

的值

表1-3
cj 2 3 0 0 0 θ

cB xB 0 x3 0 x4 0 x5
-z

B 8 16 12
0

x1 1 4 0
2

x2 2 0 4
3

x3 1 0 0
0

x4 0 1 0
0

x5 0 0 1
0

4 3

表1.4
cj cB xB 0 x3 0 x4 0 x2
-z

2 B 2 16 3
9

3 x2 0 0 1
0

0 x3 1 0 0
0

0 x4 0 1 0
0

0 x5 -1/2 0 1/4
-3/4

θ 2 4 -

x1 1 4 0
2

表1-5
cj b cB xB 2 x1 0 x4 3 x2 -z 2 8 3 2 x1 1 0 0 3 x2 0 0 1 0 0 x3 1 -4 0 -2 0 x4 0 1 0 0 0 x5 θ

-1/2 2 4 1/4 12 1/4

-13 0

表 1-6
cj cB xB b 2 x1 3 x2 0 x3 0 x4 0 x5 θ

2 x1 0 x5 3 x2
-z

4 4 2
-14

1 0 0
0

0 0 1
0

0 -2 1/2
-1.5

1/4 0 1/2 1
-1/8 0 -1/8 0

从表1-6看出检验数都小于或等于零,于 是对应的基可行解X=(4,2,0,0,4)为最优 解, ? 对偶问题的最优解为y1=1.5,y2=1/8 ? 最优值z=14. ? 非基变量的检验数都是正,因此有唯 一最优解。

? ? ? ?

7、设原问题是 max z=CX;AX+Xs=b,X,Xs≥0 它的对偶问题是 min ω=Yb;YA-Ys=C;Y,Ys≥0 则原问题单纯形表的检验数行对应其对偶问题的一 个基解,其对应关系如下表: XB 0 -Ys1 XN CN-CBB-1N –-Ys2 XS -CBB-1 -Y

?

其中Ys1对应于原问题中基变量XB的剩余变量,Ys2对 应于原问题中非基变量XN的剩余变量。

例4 对偶问题无解性的应用
已知线性规划问题 max z=x1+x2 -x1+x2+x3≤2 -2x1+x2-x3≤1 x1,x2,x3≥0 试用对偶理论证明该线性规划问题无最优解。

? ? ? ? ?


?

?

?
? ? ? ?

首先看到该问题存在可行解X=(0,0,0);而对 偶问题为 min ω=2y1+y2 -y1-2y2≥1 y1+y2≥1 y1-y2≥0 y1,y2≥0 由于该问题无可行解,故原问题无最优解。

例5 互补松弛性的应用
? ?

?
? ?

已知线性规划问题 min ω=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x5≥4 2x1-x2+3x3+x4+x5≥3 x1,x2,x3,x4,x5≥0 对偶问题的最优解为y1*=4/5, y2*=3/5;z=5.用对偶理论求出原问题的最 优解。


? ? ? ? ? ?

?
?

先写出它的对偶问题 max z=4y1+3y2 y1+2y2≤2 (1) y1-y2≤3 (2) 2y1+3y2≤5 (3) y1+y2≤2 (4) 3y1+y2≤3 (5) y1,y2≥0 (6)

将y1*,y2*的值代入约束条件,得(2), (3),(4)为严格不等式;由互补松 弛性得x2*=x3*=x4*=0,因y1,y2≥0;原问题的 两个约束条件应取等式,即 ? 3x1*+x5*=4 ? 2x1*+x5*=3 ? 求解得x1*=1,x2*=1,故原问题的最优解为 ? X*=(1,0,0,0,1); ω*=5.
?

§6 对偶单纯形法

最优单纯形表的性质
1.
2. 3. 4.

右端系数全部非负; 检验数行全部非正; 右端系数为原问题的基可行解; 检验数行为对偶问题的基可行解。

单纯形法的原理
?

单纯形法是从原问题的初始基可行解出发(右 端系数大于等于零,检验数可能有正的),在保持 原问题的基可行解的前提下,逐渐迭代到使检 验数全部小于或等于零为止.

?

在b列中得到的是原问题的(最优)基可行解. 在检验数行得到的是对偶问题的(最优)基可行 解.

?

对偶单纯形法的原理
? 根据对偶问题的对称性,若保持对偶问题的 解是基可行解,即检验数cj-CBB-1Pj≤0 ? 原问题在非可行解的基础上,通过逐步迭代

达到基可行解,这样也得到了最优解,其优 点是原问题的初始解不一定要是基可行解, 可从非基可行解开始迭代.

对偶单纯形法的基本思路
单纯形法的基本思路:
原问题基可行解 最优解判断

~ ?1 b ?B b?0
对偶问题 最优解判断

? j ? cj ? zj ? 0
对偶问题的可行解

对偶单纯形法 基本思路

对偶单纯形法原理:
?

? ? ?

?
?

?

设原问题为 max z=CX AX=b X≥0 又设B是一个基。不失一般性,令B= (P1,P2,…,Pm),它对应的基变量为 XB=(x1,x2,…,xm) 当非基变量都为0时,可以得到基变量XB=B-1b. 若B-1b中至少有一个负分量,设(B-1b)I<0,并 且在单纯形表的检验数行中的检验数都为非正, 即对偶问题保持基可行解。

对偶单纯形法:
? ? ? ? ?

1、 对应基变量x1,x2,…,xm的检验数是 σi=ci-zi=ci- CBB-1Pi=0,i=1,2,…,m 2、 对应非基变量xm+1,…,xn的检验数是 σj=cj-zj=cj- CBB-1Pj≤0,j=m+1,…,n 每次迭代是将基变量中的负分量xl取出,去替换 非基变量中的xk,经基变换,所有检验数仍保持 非正,从原问题来看,经过每次迭代,原问题 由非可行解往可行解靠近,当原问题得到可行 解时,便得到了最优解。

对偶单纯形法的计算步骤:
1.

2.

3.

根据线性规划问题,列出初始单纯形表。 检查b列的数字,若都为非负,检验数都 为非正,则得到了最优解。停止计算。 若检查b列的数字时,至少还有一个负分 量,检验数保持非正,那么进行下面的 计算。 换基

?

?
?

(1) 确定换出变量 ? min? B ?1b ?i | ?B ?1b ?i 按 i

? 0 ? B ?1b

? ?

?

l

即右端负系数最小者对应的基变量xl为换出变量。

? ?

?
?

(2) 确定换出变量 在单纯形表中检查xl所在行的各系数,若alj≥0,则 无可行解。停止计算。 若存在alj<0(j=1,2,…,n),计算最小比θ.
?c j ? z j ? ck ? z k ? ? ? ? min? | alj ? 0? ? j ? alk ? ? alj ?

?

按θ规则所对应的列的非基变量xk为换入变量, 这样才能保持得到的对偶问题解仍然为可行解。

4 、旋转 ? 以alk为主元素,按原单纯形法在表中 进行迭代运算,得到新的计算表。重 复(1)-(4)的步骤。 ? 注意:对偶单纯形法中旋转与检验数 的计算和单纯形法完全相同.

下面来举例说明具体的算法。

例6 用对偶单纯形法求解 ? min ω=2x1+3x2+4x3 ? x1+2x2+x3≥3 (y1) ? 2x1-x2+3x3≥4 (y2 ) ? x1,x2,x3≥0
?


现将问题化为下面的形式,以便得到 对偶问题的初始可行基 ? max z=-2x1-3x2-4x3 ? -x1-2x2-x3+x4=-3 (y1) ? -2x1+x2-3x3+x5=-4 (y2) ? x1,x2,x3,x4,x5≥0
?

建立该问题的初始单纯形表2-6如下
cj cB xB

b

-2 x1

-3 x2

-4 x3

0 x4

0 x5

0 x4 0 x5

-3 -4

-1 [-2]

-2 1

-1 -3

1 0

0 1

cj-zj

-2

-3

-4

0

0

对偶单纯形表的特点
1. 2. 3.

4.

对偶单纯形表的格式与单纯形表相同; 对偶单纯形表对应于原问题的一个基解; 检验数行全部小于或等于零(极大化问题); 右端系数可以有负数.

表2-7
cj b cB xB 0 x4 -2 x1 cj-zj θ -1 2 0 -2 x1 0 1 -3 x2 [-5/2] -1/2 -4 (-4)/(-5/2) -4 x3 1/2 3/2 -1 0 x4 1 0 0 -1/2 -1/2 -1 (-1)/(-1/2) 0 x5

表2-8
cj b cB xB
-3 x2 -2 x1 cj-zj 2/5 11/5 0

-2 x1
0 1 0

-3 x2
1 0

-4 x3
-1/5 7/5 -3/5

0 x4

0 x5

-2/5 1/5 -1/5 -2/5 -8/5 -1/5

最优解
? 最优解为X*=(11/5,2/5,0,0,0)
? 最优值z*=28/5

? 由最优单纯形表知
? 对偶问题的最优解为

y*=(y1*,y2*)=(8/5,1/5) 最优值 w*=28/5

从以上求解过程可以看到,对偶单纯形 法有以下优点:
?

?

?

(1) 初始解可以是非可行解,当检验数都为负数 (非正)时,就可以进行基的变换,这时不需要加入 人工变量,因此可以简化计算。 (2) 当变量多余约束条件,对这样的线性规划问 题,用对偶单纯形法可以减少计算的工作量。因 此对变量较少而约束条件很多的线性规划问题, 可以先将它变为对偶问题,然后用对偶单纯形法 求解。 (3)在灵敏度分析中,有时需要用对偶单纯形法, 可使问题的处理简化。对偶单纯形法的局限性主 要是对大多数线性规划问题,很难找到一个(对偶) 初始可行基,因而这方法很少单独使用。

§7 灵敏度分析

灵敏度分析的问题
1 什么叫灵敏度分析? ? 所谓灵敏度分析是分析最优方案如何随有关参数的 变化而变化. 2 灵敏度分析的类型; ? 最优解不变时一个或几个参数的变化范围; ? 当一个或几个参数变化后,最优解如何变化. 3 线性规划的灵敏度分析的类型: ? 价值系数的变化 ? 右端资源系数的变化 ? 约束条件的技术系数的变化 ? 增加或减少一种产品 ? 增加或减少一种资源

当线性规划问题的系数发生变化时,最优解 一般要发生变化,主要有以下几种情况:
原问题
可行解 可行解 非可行解 非可行解

对偶问题 结论或继续计算的步骤
可行解 非可行解 可行解 非可行解 表中的解仍然为最优解 用单纯形法继续迭代求最优解 用对偶单纯形法迭代求最优解

引进人工变量,编制新的单纯形表, 求最优解

7.1 资源数量变化的分析
?

? ?

资源数量变化是指第r种资源系数br发生变 化,即br’=br+Δbr.并假设问题的其它系数 都不变。如果B是原问题的最优基,这样 使原问题的右端的基变量变为 XB’=B-1(b+Δb) 这里Δb=(0,…,Δbr,0,…,0)T.只要 XB’ ≥0,最终表的检验数不变,则最优基 不变,但最优解的值发生了变化,所以XB’ 为新的最优解。

设B为最优基,记

? a11 a12 ? a1r ? a1m ? ?a a ? a ? a ? 22 2r 2m ? ?1 ? 21 B ? ?? ? ? ? ? ? ? ?am1 am 2 ? amr ? amm ?

B ?b

?1

? a11 ?a 21 ?1 B ?b ? ? ?? ? am1 ?

a12 ? a1r ? a1m ? ? a22 ? a2r ? a2m ? ? ? ?? ? am 2 ? amr ? amm ?

?0 ? ? ? ?? ? ? ?b ? r ? ? ?? ? ? ? ?0 ?

新的最优解的值可允许变化的范围用以 下方法确定(参数的变化范围)。 设B是最优基,新的右端项为 B-1(b+Δb)= B-1b+ B-1Δb
?

= B-1b+ B-1

?0 ? ? ? ?? ? ? ?b , B-1 ? ? r? ?? ? ? ? ?0 ?

? ? ? ? a1r ? 0 ? ? a1r ?br ? ? ? ? ? ? ? ?? ?? ? ?? ? ?b ? ? ? a ?b ? ? ?b ? a r ? ir ? r ? ? ir r ? ? ?? ?? ? ?? ? ? ? ? ? ? 0 ? ? a mr ?br ? ? a mr ? ? ?

? ? ? ? ? ? ? ? ? ?

这时在最终表中求得的b列的所有元素 , bi ? air ?br ? 0, i ? 1,2,?, m 由此得 air ?br ? ?bi , i ? 1,2,?, m 当 a ? 0时,?b ? ?b / a ;
ir r i ir

air ? 0时,?br ? ?bi / air ; 于是得到

max {?bi / air | air ? 0} ? ?br ? min{?bi / air | air ? 0}
i i

例如求第一章例1中第二个约束条件b2的变化范围Δb2 时,可计算
?

B-1b+ B-1

? 0 ? ? 4 ? ? 0.25 ? ? 0? ? ? ? ? ? ? ? ? ? ?b2 ? ? ? 4 ? ? ? 0.5 ??b2 ? ? 0 ? ? 0 ? ? 2 ? ? ? 0.125? ? 0? ? ? ? ? ? ? ? ?

?

可得

?b2 ? ?4 / 0.25 ? ?16, ,
?b2 ? ?4 / 0.5 ? ?8
?b2 ? 2 / 0.125 ? 16.所以?b2

的变化范围是[-8,16];显然b2的变换范围是[8,32]。

例1
?

?

?

从表1-5得知第一章例1中,每设备台时的影子价 格为1.5元,若该厂又从别处抽出4台时用于生产, 求这时该厂生产产品的最优方案。 解 先计算B-1Δb 0.25 0 ?? 4 ? ? 0 ? ? 0 ? ?? ? ? ? 0.5 1 ?? 0 ? ? ? ? 8 ? B-1Δb= ? ? 2 ? 0.5 ? 0.125 0 ?? 0 ? ? 2 ? ? ?? ? ? ? 将上述结果反映到最终表中得

?

表2-10。
cj cB xB
2 x1 0 x5 3 x2 cj-zj

b

2 x1
1 0 0 0

3 x2
0 0 1 0

0 x3

0 x4

0 x5
0 1 0 0

4+0 4-8 2+2

0 0.25 -2 0.5 0.5 - 0.125 -1.5 -0.125

由于b列中有负数,故用对偶单纯形法求新的最 优解。计算结果如下表 ? 表2-11
cj cB xB 2 x1 0 x3 3 x2 cj-zj b 4 2 3 0 2 x1 1 0 0 3 x2 0 0 1 0 0 0 x3 0 1 0 0 x4 0.25 -0.25 0 -0.5 0 x5 0 -0.5 0.25 -0.75

最优解
? 即该厂最优生产方案应改为Ⅰ4件、

Ⅱ3件,获利 ? z*=17元 ? 从表中看出x3=2,即设备有两小时未 被利用。

最优基不变时,资源b1变化的范围
?

?

B-1(b+Δb) 0.25 0 ?? 8 ? ?b1 ? ? 4 ? 0 ? ? ? ? ?? ? 0.5 1 ??16 = ?? 2 ? ? ? 4 ? 2?b1 ? ? ? 2 ? 0.5?b ? ? 0.5 ? 0.125 0 ??12 1? ? ?? ? ?

4 ? 2?b1 ? 0 和2 ? 0.5?b1 ? 0
?

即 ? 4 ? ?b1 ? 2 最优基不变

7.2 目标函数中价值系数cj的变化分析
?

可以分别就cj时对应的非基变量和基 变量两种情况来讨论。

(1) 若cj是非基变量xj的系数
? ? ? ? ? ?

这时单纯形表中xj所对应的检验数是 σj =cj- CBB-1Pj 或σj= 当cj增加Δcj时,要保证最终表中这个检验数 仍然小于或等于零,即 σj’=cj+Δcj- CBB-1Pj≤0 那么cj+Δcj≤Ypj=CBPj’,即Δcj的值必需小于或 等于YPj-cj= CBPj’ –cj=-σj,才可以满足原最优 解条件,这可以确定Δcj的变化范围了。

?

? ? j ? c j ? ? aij yi ? c j ? ? ci aij
i ?1 i ?1

m

m

(2)若cr是基变量xr的系数
?
?

因cr∈CB,当cr增加Δcr时,就引起CB的变 化,这时
(CB+ΔCB)B-1A=CB B-1A+(0,…, Δcr,…,0) B-1A

?
?

= CB B-1A+Δcr(a’r1,a’r2,…,a’rn)
可见当cr增加Δcr时,最终表中的检验数是

?

σj’=cj - CBB-1A-Δcjarj’ =σj- Δcjarj’,j=1,2,…,n

若要求原最优解不变,即必需满足σj’ =σj- Δcjarj’ ≤0。于是得到 ? 当arj’<0,Δcr≤σj/a rj’ ? arj’>0,Δcr≥σj/a rj’ j=1,2,…,n ? Δcr可变化的范围是
?

max{?? j / a rj | a rj ? 0} ? ?cr ? min{?? j / a rj | a rj ? 0}
j j

? 例1

试以第一章例1的最终 表1-5为例,设基变量x2的系数c2 变化Δc2,在原最优解不变的条 件下,确定Δc2的变化范围。 ? 解 这时表1-5最终计算表变成为 表2-12:

cj b cB xB 2 x1 0 x5 3 x2 cj-zj 4 4 2 0

2 x1 1 0 0

3+Δc2 x2 0 0 1 Δc2

0 x3 0 4 0.5 -1.5

0 x4

0 x5

0.25 0 0.5 1 -0.125 0 -0.125 0

为了保持原最优解不变,则x2的检 验数应当为零,于是得表2-13a
cj cB xB b 2 x1 3+Δc2 x2 0 x3 0 x4 0 x5

2 x1 0 x5 3+Δc2 x2
cj-zj

4 4 2
0

1 0 0

0 0 1
0

0 -4 0.5

0.25 0.5 -0.125

0 1 0
0

-1.5 Δc2/8 -Δc2/2 -0.125

从上表可见,为使最优解不变有: ? -1.5-Δc2/2≤0和Δc2/8-0.125≤0,由此 可得Δc2≥-1.5/0.5;Δc2≤1。Δc2的变化 范围为:-3≤Δc2≤1。即c2可以在[0,4] 内变化而不影响原最优解。
?

7.3 技术系数aij的变化
?

分两种情况来讨论技术系数aij的变化, 下面用具体的例子来说明:

例9分析在原计划中是否应该安排一种新产品
?

以第一章例1的最终表1-5为例,设该 厂除了生产产品Ⅰ,Ⅱ外,还生产新 产品Ⅲ,已知生产产品Ⅲ,每件需消 耗原材料A,B各为6㎏,3㎏,使用设 备2台时。每件可获利5元,问该厂是 否应生产新产品和生产多少?

解 分析这问题的步骤是:
(1) 设生产产品Ⅲx3’台,其技术向量P3’=(2,6,3)T, 然后计算最终表中对应于x3’的检验数 σ3‘=c3’-CBB-1P3’=5-(1.5,0.125,0)(2,6,3)T=1.25>0 说明安排生产产品Ⅲ是有利可图的。 (2) 计算Ⅲ在最终表中对应x3’的列向量 0.25 0 ?? 2 ? ?1.5 ? ? 0 ? ?? ? ? ? 0 .5 1 ?? 6 ? ? ? 2 ? B-1P3’= ? ? 2 ? 0.5 ? 0.125 0 ?? 3 ? ? 0.25? ? ?? ? ? ? 只需在表1-5中添上一列

并将(1),(2)中的计算结果填入最终计
算表1-5得表2-13b:
cj b cB xB 2 x1 3 x2 0 x3 0 x4 0 x5 5 x3’

2 x1 0 x5 3 x2
cj-zj

4 4 2
0

1 0 0

0 0 1
0

0 -2 0.5
-1.5

0.25 0.5 -0.125
-0.125 0

0 1 0

1.5 [2] 0.25
1.25

由于b列的数字没有发生变化原问题的解是可行解,但 检验数还有正数,说明目标函数值还可以改善,最优值 为16.5。 (3)进行迭代得最优单纯形表2-13c: cj cB xB 2 x1 0 x3’ 3 x2 cj-zj b 2 x1 1 2 1.5 0 1 0 0 3 x2 0 0 1 0 0 x3 1. 5 –1 0.75 -0.25 0 x4 -0.125 0.25 -0.1875 -0.4375 0 x5 5 x3’

-0.75 0 0. 5 1 -0.125 0 -0.625 0

例10
分析原计划生产产品的工艺结构发生变化。 以第一章例1为例。若P1’=(2,5,2)T ,每件利 润为4元,试分析原最优计划有什么影响?
0.25 0 ?? 2 ? ?1.25 ? ? 0 ? ?? ? ? ? B-1P1’= ? ? 2 0.5 1 ?? 5 ? ? ? 0.5 ? ? 0.5 ? 0.125 0 ?? 2 ? ? 0.375? ? ?? ? ? ?

x1’的检验数为 σ1‘=c1’-CBB-1P1’=4-(1.5,0.125,0)(2,5,2)T=0.375

将以上结果填入最终表x1的列向 量位置,得表2-14
cj cB xB 4 x1 0 x5 3 x2 cj-zj b 4 4 2 0 2 x1 1 0 0 4 x1’ 1.25 50.5 0.375 0.375 0 3 x2 0 0 1 0 x3 0 -2 0.5 -1.5 0 x4 0.25 0.5 0.125 -0.125 0 0 x5 0 1 0

经迭代得最优表2-15:
cj cB xB 4 x 1‘ 0 x5 3 x2 cj-zj 4 x1‘ 1 0 0 0 0 3 x2 0 0 1 0 x3 0 -2 0.5 -1.5 0 x4 0.2 0.4 -0.2 -0.2 0 x5 0 1 0 0

b 3.2 2.4 0.8

?

?

上表表明原问题和对偶问题的解都是可行解 所以表中的结果已是最优解。即应当生产 Ⅰ‘3.2单位;生产产品Ⅱ0.8单位。可获利15.2 元。 注意 :若碰到原问题和对偶问题均为非可行 解时,这就需要引进人工变量后重新求解。

例11
?

?

设例10中Ⅰ‘的技术系数向量为P1’=(4,5,2)T,而 每件获利仍然为4元。试问应如何安排最优生产 方案? 解 方法与例10相同,以x1’代替x1,计算 B-1P1’=
0.25 0 ?? 4 ? ?1.25 ? ? 0 ? ?? ? ? ? 0. 5 1 ?? 5 ? ? ? ? 3.5 ? ?? 2 ? 0.5 ? 0.125 0 ?? 2 ? ?1.375? ? ?? ? ? ?

?

? ?

x1’的检验数为 σ1‘=c1’-CBB-1P1’=4-(1.5,0.125,0)(4,5,2)T =-2.625

将以上结果填入最终表x1的列向量位置,得
表2-16
cB xB b x1’ x2 x3 x4 x5

4 x1 0 x5 3 x2 cj-zj

4 4 2

1.25 -3.5 1.357 -2.625

0 0 1 0

0 -2 0.5 -1.5

0.25 0.5 0.125 -0.125 0

0 1 0

将表2-16的x1’替换基变量中的x1,得表217
cB xB b 4 x1‘ 3.2 0 x5 15.3 3 x2 -2.4 x1’ 1 0 0 x2 0 0 1 x3 0 -2 0.5 x4 0.2 1.2 -0.4 x5 0 1 0

cj-zj

0

0

-1.5

0.4

0

由于原问题与对偶问题都是非可行解。 于是引入人工变量x6 因在表2-17中x2 所在行,用方程表示时为 0x1’+x2+0.5x3-0.4x4+0x5=-2.4 引入人工变量x6后,便为 -x2-0.5x3+0.4x4+x6=2.4

将x6作为基变量代替x2,填入表217的表2-18
cB x B b x1’ x2 x3 x4 x5 x6

4 x`1 3.2 0 x5 15.2 -M x6 2.4
cj-zj

1 0 0
0

0 0 -1
3-M

0 -2 -0.5
-0.5M

0.2 1.2 [0.4]
-0.8 0 +0.4M

0 1 0
0

0 0 1

用单纯形法求解得表2-19
cj cB xB 4 x1‘ 0 x5 0 x4 cj-zj 4 x1‘ 3 x2 0 x4 cj-zj b 2 8 6 0 0.667 2.667 12.667 1 0 0 0 4 x1‘ 1 0 0 1 0 1 0 0 3 x2 0.5 3 -2.5 0 x3 0 x4 0 x5 0 1 0 0 -0.33 0.33 0.83 -0.33 -M x6 0.5 -3 2.5 -M+2 0 -1 0 -M+3 1.25 0 0 –0.5 1 –1.25 -1 0 0.33 -0.167 1.667 -0.83 0 0 1 0

?

除以上介绍的几项分析外,还可以作 增减约束条件的分析。


更多相关文档:

运筹学[第二章对偶理论和灵敏度分析]山东大学期末考试知识点复习

运筹学:山东大学期末考试知识点复习运筹学:山东大学期末考试知识点复习隐藏>> 山东大学期末考试知识点复习 第二章对偶理论和灵敏度分析 1.对偶问题间的关系 若某线...

《运筹学》 第三章线性规划对偶理论与灵敏度分析习题及 答案

运筹学》 第三章线性规划对偶理论与灵敏度分析习题及 答案_管理学_高等教育_...第二章 线性规划的对偶... 120页 免费 运筹学课件 第二章线性规... 44页...

对偶理论与灵敏度分析

关键词:对偶理论与灵敏度分析运筹学 1/2 相关文档推荐 灵敏度分析与对偶理论 ...第二章 对偶理论与灵敏度... 32页 1财富值 3最优化教案(对偶理论及灵......

运筹学对偶理论与灵敏度分析作业

运筹学教学课件 第二章 ... 122页 1下载券 运筹学2对偶理论与灵敏度... ...运​筹​学​对​偶​理​论​与​灵​敏​度​分​析...

运筹学实验二灵敏度分析

运筹学教学课件 第二章 ... 122页 1下载券 运筹学2第二章_对偶理论... ...实验报告 实验概述:实验二、灵敏度分析(操作型) 实验概述:实验二、灵敏度分析(...

运筹学课件第二章对偶问题

运筹学课件第二章对偶问题_理学_高等教育_教育专区。运筹学 课件第二章线性规划的对偶理论与灵敏度分析一、学习目的与要求 1、掌握对偶理论及其性质 2、掌握对偶单...

对偶理论与灵敏度分析

搜 试试 帮助 全部 DOC PPT TXT PDF XLS ...第二章对偶理论灵敏度分析 92页 2财富值 2.对偶理论...运筹学 重点 讲解运筹学 重点 讲解隐藏>> §2 对偶...

第三章对偶规划和灵敏度分析

搜 试试 帮助 全部 DOC PPT TXT PDF XLS ...运筹学课程运筹学课程隐藏>> 第三章对偶规划和灵敏...难点:对偶原理,灵敏度分析法。 教学方法:讲授法,...

对偶问题与灵敏度分析

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...《运筹学》 第三章线性规... 8页 4下载券 图与...的对偶理论与灵敏度分析 1.对偶问题的提出 对偶问题...

运筹学

运筹学教案运筹学教案隐藏>> 教案2005~2006 学年第二学期 学院 ( 系、部 )...(教学章、节或主题) :第二章 对偶理论与灵敏度分析 2.1 单纯形法矩阵描述 ...
更多相关标签:
运筹学对偶问题 | 运筹学对偶问题例题 | 运筹学对偶单纯形法 | 运筹学对偶问题视频 | 运筹学对偶 | 运筹学对偶理论 | 运筹学对偶问题案例 | 运筹学灵敏度分析 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com