9299.net
大学生考试网 让学习变简单
赞助商链接
当前位置:首页 >> 数学 >>

教案2

教案2


1.3 线性规划问题的标准形式
? 为了求解LP问题,必须统一其模型,本课程 选用标准型式为 (1) 目标函数为求最大
对于目标函数是求最小怎么办? min Z=1000 x1+800 x2 令:z’= -z, 则minz=maxz’ maxZ’= -1000 x1-800 x2

1

(2)约束条件均用线性等式方程来表示, 且右边常数项均非负。
实际情形约束条件显然不可能都是等式关系。 当表达式中含“≤”时 可在约束条件左边加上一个非负的变量——松弛变量,使原来的“≥”变为“= ”; max z = 2x1 + 3x2 s.t. x1 + 2 x2 ? 8 4 x1 ? 16 4 x2 ? 12 x1,x2 ?0 max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 =8 4 x1 + x4 =16 4 x2 +x5 =12 x1,x2,x3,x4,x5 ?0

2

当表达式中含“≥”时, 可以在约束条件左边减去一个非负变量——剩余变量, 使原来的“≥”变为“=”。 目标:min f =1000 x1+800 x2 约束条件: x1 ≥1 0.8 x1+ x2 ≥1.6 x1 ≤2 x2 ≤1.4 x1、x2 ≥0

maxz'=–minz=-1000 x1-800 x2+0·3+0·4+0·5+0·6 x x x x s.t. x1 -x3 =1 0.8 x1+ x2 -x4 =1.6 x1 + x5 = 2 x2 +x6=1.4 x1、x2、x3、x4、x5、x6≥0

3

(3)所有变量要求非负
现实中,有些变量可能从物理意义或经济意义上讲没有非负要求 min z =x1-x2+4 x3 s.t. 3 x2-4 x3 ≥-9 -x1 + x2 ≥6 5 x2+2 x3 ≤16 x1 ≤ 0 ,x2 ≥0, x3无符号限制

解:令x1’=-x1,x1’≥0, x3 = x3’-x3’’, x3’、x3’’ ≥0 将第一个约束条件两端乘“-1”并加入松弛变量x4, 第二个约束减剩余变量x5,第三个约束加入松弛变量x6,代入整理后得:
maxz ’=x1’+x2-4 x3’+4 x3’’ s.t. -3 x2+4 x3’-4 x3’’+x4 =9 x1’ + x2 - x5 = 6 5 x2+2 x3’-2 x3’’ +x6 = 16 x1’, x2, x3’、 x3’’,x4,x5,x6≥0

4

练习:
max z =2x1+x2+3x3 +x4 s.t. x1+x2+x3 +x4 ≤ 7 2x1-3x2+x3 =-8 -x1-2x2+2x4 ≥ 1 x1 , x3 ≥ 0, x2 ≤ 0, x4无符号限制

min z =2x1-x2+2x3 s.t. -x1+x2+x3 =4 - x 1 + x2 - x 3 ≤ 6 x1 ≤0 ,x2 ≥3, x3无符号限制 再思考:如果x有区间限制怎么办?
5

经过上述过程,可得到线性规划问题数学模型的标准形式为:

max z =c1x1 + c2x2 +·+ cnxn · · s.t. a11x1 + a12x2 +·+ a1nxn = b1 · · a21x1 + a22x2 +·+ a2nxn = b2 · · · · · · · · am1x1 + am2x2 +·+ amnxn = bm · · x1,x2,·,xn ? 0 · · 其中bi ? 0,(i =1,2,·,m) · ·
一般m< n;m,n > 0。

(1.1)

(1.2) (1.3)

6

标准型的简写形式: max z =c1x1 + c2x2 +·+ cnxn · · s.t. a11x1 + a12x2 +·+ a1nxn = b1 · · a21x1 + a22x2 +·+ a2nxn = b2 · · · · · · · · am1x1 + am2x2 +·+ amnxn = bm · · x1,x2,·,xn ? 0 · · 用求和符号表示 n
max z ?

(1.1)

(1.2)
(1.3)

?
n

c jx j

j?1

?

a ij x j ? b i

i ? 1,2,..., m

j?1

xj ? 0

j ? 1 , 2 ,..., n

7

用矩阵描述为:
max z =CX AX = b X ?0
a11 … a12 … a1n a21 … a22 … a2n … … A= am1 … am2 …amn

= (P1,P2,·,Pn); 0 = · ·

0 0 … 0

称 A 为约束条件的m × n 阶系数矩阵,一般A的秩为m。
8

用向量表示:
max z ? CX
n

?

Pj x j ? b j ? 1 ,? , n

j?1

xj ? 0

其 中 : C ? ( c 1 , c 2 ,? , c n )

X=

x1 x2 … xn

Pj =

a1j a2j … amj

b=

b1 b2 … bm

向 量 Pj 对 应 的 决 策 变 量 为 xj 。
9

Max z=(c1 , c2, …,cn ) a11 a21 … am1

x1 x2
?

=Σ cjxj =CX
Σ aijxj =bi

a12 … a1n x1 a22 … a2n x2 ? = ? … … am2 … amn xn b
m

xn b1 b2

i=1,…,m AX = b
X ≥0 xj≥0 j=1,…,n
10

x1 (p1,p2, …,pn) x2 = b ?

Σ Pjxj=b

xn

1.4 线性规划问题的解的概念
max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 =8 4 x1 + x4 =16 4 x2 +x5 =12 x1,x2,x3,x4,x5 ?0

11

? 基 A中的m × m 阶非奇异矩阵B ; (意味着A的秩为m,|B | ≠ 0,B 的各列线性无关) · 基向量 B中的列向量; · 基变量 B中的列向量对应的变量; · 非基变量 非B中的列向量对应的变量; 例如,若A的前m列线性无关,则
a11 … a12 … a1m a21 … a22 … a2m … … am1 … am2 …amm

B =
是个基。

=( P1,P2,…,Pm )

P1,P2,…,Pm是基向量; x1,x2,…,xm 是基变量; xm+1,…,xn 是非基变量; m 若Am×n,m<n,则至多有 C n 个基,每个基有m个基变 量,n- m 个非基变量。 12

· 基解 对应每一个基B,令所有非基变量为零,由 (1.5) 约 束方程组求得的解X ;
约束方程组(1.5)中,有m 个方程n 个变量,m<n,有无穷 多解,若前 m 个系数向量线性无关,令xm+1=…=xn =0,则可求 出XB =( x1,x2,…,xm)T,则X=( x1,x2,…,xm,0,…,0)T 就是一个基解。 至多有 C n 个基解,基解的非零分量至多m个,非零分量个 数小于m 的基解为退化解。
m

? 基可行解

满足非负条件(1.6)的基解;
m

同样至多有 C n 个基可行解,基可行解至多有m个正分量。 · 可行基 对应于基可行解的基; · 基最优解 使目标函数达到最大值的基可行解。
13

上述解的概念中基解和基可行解最为重要,各种解的 关系粗略地可用下图表示:
非可行解

可行解 最优解 基 可 行 解

基解

14

§2 线性规划问题的几何意义
本节重点:
凸组合的概念 凸集的概念 线性规划基本定理
15

x2

如例1,max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 =8 4 x1 + x4 =16 4 x2 +x5 =12 x1,x2,x3,x4,x5 ?0

A Q4 3 Q3 ? Q2(4,2)

Q1
O

4

x1

16

§2 线性规划问题的几何意义
本节重点:
凸组合的概念 凸集的概念 线性规划基本定理
17

2.1 基本概念
? 凸组合 设 X 1 ,? , X
K i ?1
K n ? E ,若存在 ? 1 ,? ,? k ,0 ?

?i

?1

,且 ? ? i ? 1 ,使
X ? ?1X
1

1

?? ??kX
K

k

则称X 为 X ,? , X

的凸组合。

二维空间
两点连线上的任何一点都是这两点的凸组合
X ? ?X ? ( 1 ? ? )X
1 2

(0 ?? ? 1)

X1

2

X

1

2 X18

?凸集

K ? E ,若任意两点 X ? K ,X ? K 的凸组合属
n 1 2

于 K, 即
X ? ?X ? ( 1 ? ? )X ? K
1 2

(0 ?? ? 1)

则称 K 为凸集。

(a)

(b)

(c)

(d)

(e)

上 图 中 (a )、 (b ) 是 凸 集 , (c ) 、 (d ) 不 是 凸 集 , 任 何 两 个 凸 集 的 交 集 是 凸 集 , 如 图 (e)。 从 直 观 上 说 , 凸 集 没 有凹入部分,其内部没有空洞。
19

?

顶点(极点)
设 K 是 凸 集 , X? K, 若 X 不 能 用 K 的 其 它 两 点 的 凸 组 X ?
1

合 表 示 , 即 不 存 在

K, X ?
2

K (X ? X ) , 能 使
1 2

X ? ?X
顶点。

1

? (1 ? ? )X

2

(0? ? ? 1) , 则 称 X 为 K 的 一 个

(a)

(b)

(c)

(d)

(e)

图中红粗线和红点是顶点。
20

2 .2 基 本 定 理
定理 1 若线性规划问题存在可行解,则所有可行解的集合 — — 可 行 域 D = {X | A X = b , X ? 0 }是 凸 集 。 证明: 设 X ? D , X ? D , 则 A X =b, A X =b, X ?0, X ?0
1 2 1 2 1 2

故 A X = A [? X = ? AX
1
1

1

? ( 1 ? ? )X ]
2 2

? ( 1 ? ? ) AX
2

? b (0 ?? ? 1)

X ? ?X ? ( 1 ? ? )X
所 以 X?D , D 为 凸 集 。

? 0

21

引理 1

线 性 规 划 问 题 的 可 行 解 X = ( x 1 ,x 2 , · ,x n ) ··

T

为基可行解的充分必要条件是 X 的正分量所对应的系 数列向量是线性无关的。
证明: 必要性:由基可行解的定义可知, 为基可行解 ? 其 X 正分量的系数列向量线性无关。 充 分 性 : 设 可 行 解 X = ( x 1 , x 2 , ? , x s, 0 , ? , 0 )
T

的 系 数 列 向 量 P 1, ? , P s 线 性 无 关 , 则 必 有 s ? m , 当 s = m 时 , P 1, ? , P s 构 成 的 行 列 式 不 为 0 , X 为 基 可 行 解 ; 当 s < m 时,总可从其余的系数列向量中取出 m – s 个与 P 1, ? , P s 构 成 最 大 线 性 无 关 向 量 组 , 行 列 式 之 值 不 为 0 , 对 应 的 解 恰 为 X, 由 定 义 它 是 基 可 行 解 。
22

定理 2

线 性规划问题的基可行解 X 对 应 于可行域 D 的 顶 点 。

证 明 : 反 证 法 ) 不 失 一 般 性 , 设 X = ( x 1, x 2, x s, 0 , ? , 0 ) ( , ①. 证 X 是基可行解 ? X 是可行域的顶点 X 是基可行解,有

?

s

Pj x j ? b
1

(s ? m ) ,
2

P 1, ? , P s 线 性 无 关
1 2

j?1

设 X 不是顶点,则有 X ,X
1

为可行解,X ? X ,
2

X ? ?X ? ( 1 ? ? )X
由 得 故

? 0

( 0 ?? ? 1 )

ax j ? ( 1 ? ? ) x j ? 0
1 2

(j > s)

xj ? xj ? 0
1 2

(j > s)
s 2

?

s

j?1

Pj x j ? b , ? Pj x j ? b
1 j?1 1

二式相减得 由 X ? X
1 2

?

s

Pj ( x j ? x j ) ? 0
2 1 2

j?1

知 ? j ? s 使 x j ? x j , 这 与 P 1, · , P s 线 性 无 关 矛 盾 。 ·· 23

②.证 X 是可行域的顶点?X 是基可行解 (等价于证:X 不是基可行解? X 不是可行域的顶点) 设 X 不是基可行解

?
s

s

Pj x j ? b

(s ? n )

j?1

存 在 不 全 为 0 的 一 组 实 数 ? 1 ,? ,? s , 使

??
j?1

j

Pj ? 0

用 一 正 数 ?乘 以 上 式 与 前 式 相 加 减 可 得 :

?(x
j?1

s

j

? ??

j

)Pj ? b ,

?(x
j?1

s

j

? ??

j

)Pj ? b

即可得
1 2

1 X = ( x 1 ? ?? 1 , x 2 ? ?? 2 ,? , x s ? ?? s ,0 ,? ,0 ) 2 X = ( x 1 ? ?? 1 , x 2 ? ?? 2 ,? , x s ? ?? s ,0 ,? ,0 )

X ? X , 只 要 ?充 分 小 , X 、 X 都 为 可 行 解 ,
1 2

X ?

1 2

X ?
1

1 2

X ,即 X 不是顶点,得证。
24

2

25

定理 3 证明:
0

若可行域有界,线性规划问题的目标函数一定可以在顶点上 设 X ,X
0 1 2

达到最优。 ,·,X ··
k *

是可行域的顶点,若 X 不是顶点,且
0 *

0

目 标 函 数 在 X 处 达 到 最 优 z = C X (标 准 型 是 z = m a x z)。 因 X 不是顶点,所以它可以用 D 的顶点线性表示为
0 X = ? ? i X ,? i ? 0 , ? ? i = 1
i i?1 i ?1 k k

因此
0 C X = C ? ? i X = ? ? i CX
i i ?1 i?1 k k i

在 所 有 的 顶 点 中 必 然 能 找 到 某 一 个 顶 点 X , 使 得 CX 是 所 有 CX 中 最大者。并且将 X 代替上式中的所有 X ,就得到
m i

m

m

i

??
i?1

k

CX i

i

?

??
i?1

k

CX i
0

m

= C X
m

m

由此得到 根据假设 C X
(0 )

C X ? C X
m

是最大值,所以只能有

C X =C X

0

m

即目标函数在顶点 X 处也达到最大值。

26

结论:
线性规划问题的可行域是凸 集(凸多面体),有有限多个 顶点。顶点对应基可行解。当 可行域有界时,必有顶点达到 目标函数最优值。

27

补充

线 性规划基 本定理 : 线 性 规 划问题

若存在可行解则必定存在基可行解;若 存在最优解则必定存在基最优解。(
证略 )

因此,下面求解线性规划问题就是求其基 最优解,当存在无穷多最优解时,若能找出 它的所有基最优解,这些基最优解的任一凸 组合便表示它的一个最优解。
28

练习
X1和X2为某一线性规划问题的最优解,证明 该线性规划问题有无穷多个最优解。

29

如例1,max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 =8 4 x1 + x4 =16 4 x2 +x5 =12 x1,x2,x3,x4,x5 ?0
x2 A Q4 3 Q3 ? Q2(4,2) Q1 O

4

x1
30

选基变量
(x1,x2,x3) (x1,x2,x4)
1 4 0 1 4 0


2 0 4 2 0 4 1 0 0 0 1 0

基解

是否为基可行解 z值
否 —— 13

(4,3,-2,0,0)T
(2,3,0,8,0)T




(x1,x3,x5)
(x1,x3,x4) (x1,x4,x5)

1 4 0
1 4 0 1 4 0

2 0 4

0 0 1

(4,2,0,0,4)T

14
——

1 0 0 1 0 0 0 0 1 0 0 1

|B|=0 无基和基解

(8,0,0,-16,12)T



——
31

选基变量
(x1,x3,x5) (x2,x3,x4)
1 4 0


1 0 0 0 0 1

基解

是否为基可行解 z值
是 8 9

(4,0,4,0,12)T
(0,3,2,16,0)T |B|=0 无基和基解 (0,4,0,16,-4)T

(x2,x3,x5)
(x2,x4,x5) (x3,x4,x5)

2 1 0 0 0 1 4 0 0 2 1 0 0 0 0 4 0 1 2 0 4 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1



——
否 ——

(4,3,-2,0,0)T



0
32


更多搜索:教案2

推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 大学生考试网 9299.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com