运筹学-第二章线性规划的对偶理论与灵敏度分析_胡运权

第二章 线性规划的对偶理论与灵敏度分析

例一美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设 备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、 各售出一件时的获利情况如下表所示。问该公司应制造Ⅰ、Ⅱ两种家电备多少 件.使获取的利润为最大。

设：

x1—— A产品的生产量 max z= 2 x1 + x2 5x2 ≤ 15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1,x2 ≥ 0

x2—— B产品的生产量

利润 约束 条件 st .

一、标准化 利润 max z= 2 x1 + x2 + 0x3 + 0x4 + 0x5 5x2 + x3 = 15 约束 6x1 + 2x2 + x4 = 24 st . 条件 x1 + x 2 + x5 = 5 x1,x2 ,x3 ,x4 ,x5 ≥ 0 二、写出初始单纯形表(必定存在有单位矩阵)C CCB 0 0 0 2 0 1 XB b b

22

11

00xx4 3 11 00 00 00

00xx5 4 0 5/4 1 1/4 0 -1/4

00x5 0 -15/2 0-1/2 1 3/2 θ

xx1 x2x2 x3 1 00 61 10 20 50 20 11 10

15 xx3 15/2 3 24 xx4 7/2 1 5 xx5 3/2 2 σ σ

0 -1/4 0 -1/2

三、最优解检验(唯一解、无限多解、无界解和无解)X =(7/2,3/2,15/2,0,0)*

Z = 17/2

*

四、分析 把解X=(7/2,3/2)代入原问题(因为x3、 x4、 x5为附加变量) 5×3÷2=15/2 5x2 ≤ < 15 A有空闲 = ≤ 24 B设备已经饱和 6x1 + 24 2 2x x1 + 5 2 x 5 调试工序也已经满负荷 = ≤ x1,x2 ≥ 0

约束 条件

一个问题？市场上设备A、设备B和调试工序每小时值多少钱？ 在什么价位时，才能使美佳公司愿意出让自己的资源？

例一

设：

y1 — 设备A值的价值 y2 — 设备B值的价值 y3 — 调试工序值的价值min z= 15 y1 + 24y2 + 5y3

分

总价值

6y2 + y3 ≥析

2

st .

5y1 + 2y2 + y3 y1 , y 2 , y3

≥ 1 ≥ 0

问题求解min z= 15 y1 + 24y2 + 5y3 6y2 + y3 ≥ 2 max z'= -15 y1 - 24y2 - 5y3 6y2 + y3 – y4 = 2

st .

5y1 + 2y2 + y3 y1 , y 2 , y3C CB -M YB y6 b 2 -15 y1 0

≥ 1 ≥-24 y2 6

st .

5y1 + 2y2 + y3

– y5 =

1

0-5 y3 1 0 y4 -1 0 y5 0 -M y6 1

y1, y 2, y3, y 4, y5

≥ 0

-M y7 0 θ

-M

y7σ

1

5

2

1

0-M

-1-M

00

10

M-15 8M-24 2M-5

问题求解min z= 15 y1 + 24y2 + 5y3 6y2 + y3 ≥ 2 max z'= -15 y1 - 24y2 - 5y3 6y2 + y3 – y4 = 2

st .

5y1 + 2y2 + y3 y1 , y 2 , y3C CB -24 YB y2 b 1/4 -15 y1 -5/4

≥ 1 ≥-24 y2 1

st .

5y1 + 2y2 + y3

– y5 =

1

0-5 y3 0 0 y4 -1/4

y1, y 2, y3, y 4, y5

≥ 0

0 y5 1/4 θ

-5

y3σ

1/2

15/2-15/2

00

10

1/2-7/2

-3/2-3/2

Y=(0, ¼, ½ , 0, 0)

z'=-17/2

z = 17/2

问题分析问题：T T min z=Z= ω=C 24y2 + 5y3 15y1 + X=Y b

原问题：

Z/ b=(YTb) 'max Tz= 2 x1 + x2 =Y 利润5x2 ≤ 15 6x1 + 2x2 ≤ 24 约束 条件 st . x1 + x2 ≤ 5 x1,x2 ≥ 0问题 的解X =(7/2,3/2,15/2,0,0) Z = 17/2* *

6y 估价——影子价格 2 + y3 ≥ 2 (即增加单位资源所 + y st . 5y1 + 2y2 ≥ 1 3 得到的贡献) y1 , y 2 , y3 ≥ 0 问题 Y=(0, ¼, ½ , 0, 0 ) 的解Z = 17/2 两个问题的最优解的值一致 最大值

问题可行解的目标值必定不大于最*

结 论

小值问题可行解的目标值 一个问题的剩余变量(松弛变量) 不为0 (即有资源剩余),则对应问题的解为0 一个决策变量不为0,则对应的问题的约束 条件的剩余变量(松弛变量) 为0(即资源彻 底用完)

5*3/2 = 15/2 < 15 6*7/2+2*3/2 = 24 = 24 7/2+3/2 = 5 = 5

对偶规则

——

变量、约束与系数

原问题有m个约束条件，对偶问题有m个变量原问题有n个变量，对偶问题有n个约束条件 原问题的价值系数对应对偶问题的右端项 原问题的右端项对应对偶问题的价值系数 原问题的技术系数矩阵转置后为对偶问题系数矩阵

解的关系max z= 2 x1 + x2 5x2 ≤ 15 问题变量 6x1 + 2x2 ≤ 24 约束 条件 st . x1 + x2 ≤ 5 x1,x2 ≥ 0C CB 0 2 1 XB x3 x1 x2 σ -σ*

利润

min z= 15y1 + 24y2 + 5y3 问题剩余松弛变量 6y2 + y3 ≥ 2 st . 5y1 + 2y2 + y3 ≥ 1 y1 , y 2 , y30 C CB -24 YB y2 b 1/4 -15 y1 -5/4 15/2 σ -15/2 3/2 3/2 -24 y2 1 1/4 0 3/2 0 0 -7/2 7/2 1 1/2 -5 y3 0

≥0 y4 -1/4

00 y5

2 b 15/2 7/2 3/2 x1 0 1 0 0 0

1 x2 0 0 1 0 0

0 x3 1 0 0 0 0

0 x4 5/4 1/4 -1/4 -1/4 1/4

x5 -15/2 -1/2 3/2 -1/2 1/2

-5

y3

1/2

X =(7/2,3/2,

15/2,0,0)

Y=(0, ¼, ½15/20, 0 0 , 0 ) -σ

一、线性规划的对偶问题1、对偶问题定义对 称 形 式max z = CTXst. AX ≤ b X≥ 0 其中： C=(c1,c2, b=(b1,b2, X=(x1,x2, Y=(y1,y2,

min w = YTb T AY ≥ C st. Y≥ 0a11 a12 … … … a1n a2n┇

… … … …

,cn)T ,bm)T ,xn)T ,ym)T

A=

a21 a22┇ ┇

am1 am2 …

amn

利润

max z= 2 x1 + x2 5x2 ≤ 15 约束 6x1 + 2x2 ≤ 24 st . 条件 x1 + x2 ≤ 5 x1,x2 ≥ 0

min z= 15y1 + 24y2 + 5y3 6y2 + y3 ≥ st .

2

5y1 + 2y2 + y3y1 , y 2 , y3

≥ 1 ≥ 0

一、线性规划的对偶问题非对称形式？max z = c1x1 + c2x2 +c3x3 a11x1+a12x2+a13x3 ≤ b1 st. a21x1+a22x2+a23x3 = b2 a31x1+a32x2+a33x3 ≥ b3 st.

min w = b1y1 +a11y1 + a12y1 + a13y1 + y1≥0,

b 2y2 + b3y3

x1 ≥ 0, x2 ≤ 0, x3无约束

a21y2 + a31y3 ≥ c1 a22y2 + a32y3 ≤ c2 a23y2 + a33y3 = c3 y2无约束，y3 ≤0

max z = c1x1 - c2x2' + c3x3' - c3x3" a11x1 - a12x2' + a13x3'- a13x3" ≤ b1 a21x1 - a22x2' + a23x3'- a23x3" ≤ b2 st. -a x + a x ' _ a x '+ a x " ≤-b 21 1 22 2 23 3 23 3 2 -a31x1 + a32x2' - a33x3'+ a33x3" ≤-b3 x1 , x2', x3',x3" ≥0

min w = b1y1 +

b2y2'- b2y2" - b3y3'

a11y1 + a21y2'– a21y2" - a31y3'≥ c1 -a12y1 - a22y2'+ a22y2" - a32y3'≥-c2 st. a13y1 + a23y2'– a23y2"- a33y3'≥ c3 -a13y1 - a23y2'+ a23y2"+ a33y3'≥-c3 y1 , y2', y2" ,y3'≥0

对偶规则—— 变量与约束对应关系原问题(对偶问题)max z=CTX AX (≤ = ≥) b X (≤ = ≥) 0 或无约束 有n个决策变量 xj (j=0、2……n) xj ≥ 0

对偶问题(原问题)min w=YTb T A Y (≤ = ≥) C Y (≤ = ≥) 0 或无约束 有n个约束条件 对应的约束为 ≥

变量

xj ≤ 0 xj 无约束

约束

对应的约束为 ≤ 对应的约束为 =

有m个约束条件 对应的约束为 ≤

约束

对应的约束为 ≥ 对应的约束为 =

有m个决策变量 yj (j=0、 2……m) yj ≥ 0

变量

yj ≤ 0 yj 无约束

max Z 4x 1 3x 2 5x 1 x 2 6 7x …… 此处隐藏：3965字，全部文档内容请下载后查看。喜欢就下载吧 ……