- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
a11 a A 21 a m1
a12 a1n a 22 a 2 n a m 2 a mn
为系数矩阵
11
Operations 2、标准型的化法 (1)min→max ∵ min z = cx = -max(-z) ∴ max(-z) = -min z = -cx 令z’ = -z 则max z’ = -cx
X i X
i 1
2.2 基本定理 1、定理1 若线性规划存在可行域，则: 可行域 D = {X|AX = b,X ≥ 0}为凸集。
18
Operations
Research
证明： 设 X(1)=(x1(1),x2(1),· · · ,xn(1))T ∈ D； X(2)=(x1(2),x2(2),· · · ,xn(2))T ∈ D； (X(1) ≠ X(2)) 有 AX(1) = b， AX(2) = b 令 X = α X(1) + (1 - α )X(2) (0<α <1) 则 AX = α AX(1) + (1 - α )AX(2) = α b + (1 - α )b = b ∵ α >0 1–α >0 ∴ X ≥ 0， 即D为凸集 2、定理2 线性规划的基可行解对应于可行域的顶 点。 3、定理3 若线性规划有解，则一定存在基可行解 为最优解。
2
Operations
Research
说明： (1)决策变量：x1，x2，· · · ，x n
。
一组决策变量表示为问题的一个方案； (2)目标函数：max(min)z z为决策变量的线性函数; (3)约束条件 一组线性不等式。 cj为价值系数, bi为资源， aij为技术系数(i=1,…,m;j=1,…,n)
基可行解
O(0,0)
Research
Q5(4,3) Q2(4,2)
Q3(2,3)
Q1(4,0)
非可行解
可行解
基解
16
Operations
Research
§2 线性规划问题的几何意义 2.1 基本概念 1、凸集：设K为En(n维欧式空间)的一点集，X(1)∈K，X(2)∈K 。 若α X(1)+(1-α )X(2)∈K，则称K为凸集。（0<α <1）
取x3、x4为基变量,令非基变量x1= x2=0 ∴ 初始基可行解：X(0) = (0 0 3 4)T
20
Operations 2、观察法 [eg.9]max z = x1 + 3x2 + 2x3 + x4 x1 + 2x2 + 3x3 =3 3x2 + x3 + x4 = 4 x1,x2,x3,x4 ≥ 0
.
3
Operations
Research
1.2 图解法 [eg.3]用图解法求eg.1。 max z = 2x1 + 3x2 1x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x 1，x 2 ≥ 0
解： (1)建立x1 - x2坐标； (2)约束条件的几何表示；
x2
① ② ③
可行域
Q3 Q2
X(1) X(1)
X(2)
X(2)
凸集
X(1)
X(1) X(2) X(2)
非凸集
17
Operations
Research
2、顶点：X∈K，X(1)∈K，X(2)∈K (任意两点)。若X不能用 α X(1)+(1-α )X(2)表示，则称X为K的一个顶点。(0<α <1) 注：顶点所对应的解是基可行解。 3、凸组合：设X(i)∈En，若存在0<μ i<1，i = 1,2,· · · ,k， k 1 i i 1 k 使 ,则称X为X(i)(i=1,2,· · · ,k)的凸组合。 (i )
Operations
Research
[eg.2]污水处理问题 环保要求河水含污低于2‰，河水可自身净化20%。 问：化工厂1、2每天各处理多少污水，使总费用最少？
化工厂1 500万m3 2 万m 3 1000元/万m3 化工厂2
分析： 1.4万m3 化工厂1处理污水x1万m3, 800元/万m3 3 3 200 万 m 化工厂2处理污水x2万m 。 min z = 1000x1 + 800x2 (2 - x1)/500 ≤ 2/1000 [(1 - 0.2)(2 - x1) + 1.4 - x2]/(500 + 200) ≤ 2/1000 x1 ≤ 2 x2 ≤ 1.4 x1，x2 ≥ 0 这里min z:表示求z的最小值。
其中 : X ( x1 x2 xn ) T C (c1 c2 cn ) p j (a1 j a 2 j a mj ) : x j的系数列向量
T
b (b1 b2 bm )
T
10
Operations
Research
用矩阵描述为： max z = CX AX = b X ≥ 0 其中: X = (x1,x2,· · · ,xn)T C = (c1,c2,· · · ,cn) b = (b1,b2,· · · ,bm)T
13
Operations
Research
1.4 线性规划解的概念 设线性规划为 max z = CX ① AX = b ② X≥0 ③ A为m × n矩阵, n > m, Rank A = m (A为行满秩矩阵） 1、可行解：满足条件②、③的X； 2、最优解：满足条件①的可行解； 3、基：取B为A中的m × m子矩阵，Rank B = m，则称B为线性 规划问题的一个基。 取B = (p1,p2,· · · ,pm) pj = (a1j,a2j,· · · ,amj)T 则称x1,x2,· · · ,xm为基变量，其它为非基变量。
14
Operations 4、基解：取B = (p1,p2,· · · ,pm) a11,· · · ,a1m x1 a1m+1,· · · ,a1n xm+1 b1 ┆ ┆ ┆ + ┆ ┆ ┆ =┆ am1,· · · ,amm xm amm+1,· · · ,amn xn bm ↑ ↑ ↑ ↑ 基 基变量 非基 非基变量 令 xm+1 = · · ·= xn = 0 (非基变量为0) 则 BXB = b ( 0) ( 0) (0) T ∴ X B B 1b ( x1 , x2 ,, xm )
*
∴由此求得最优解：x1* = 4 x2* = 2 最大值：max z = z* = 2x1* + 3x2*= 14(元)
5
Operations
Research
讨论： (1)唯一最优解
max z = z*时，解唯一，如上例。
x2
(2)无穷多最优解 [eg.4] 对eg.1，若目标函数 z = 2x1 + 4x2，此时表示 目标函数的直线与表示 条件①的直线平行， 最优点在线段Q3Q2上。 即存在无穷多最优解。
Research
(2)不等式(≤，≥) 对于“≤”情况：在“≤”左边加上一个松弛变量（非负） ，变为等式； 对于“≥”情况：在“≥”左边减去一个剩余变量（非 负），变为等式。 注意：松弛变量、剩余变量在目标函数中的价值系数为 0 。 (3)无约束变量 令xk = xk’ - xk”，xk’,xk” ≥ 0，代入即可。
化标准型
max z = x1 + 3x2 + 0x3 + 0x4 x1 + 2x2 + x3 =3 2x1 + 3x2 + x4 = 4 x1,x2,x3,x4 ≥ 0
1 2 1 0 系数矩阵 A p1 p2 p3 p4 , 则 B p3 p4 2 3 0 1
② ③ ①
Q4
3
(3)目标函数的几何表示； z = 2x1 + 3x2
x2 2 1 x1 z 3 3
o
4 Q1
x1
*
4
Operations 首先取z = 0，然后，使z逐 渐增大，直至找到最优解所对 应的点。
x2
Research
② ③
Q2(4,2)
Q4
Q3
3
①
*
4 Q1
x1
可见，在Q2点z取到最大值。 因此， Q2点所对应的解为最优解。 Q2点坐标为(4，2)。 即: x1* = 4，x2* = 2
Research
基解：X ( x , x ,, x , 0 , ,0)
( 0) 1 ( 0) 2 (0) m m个 n m个
T
基解个数 C
m n
n! m!(n m)!
15
Operations 5、基可行解 Q4(0,3) 满足③式要求的基解。 如右图所示，各边交点O,Q1,Q2,Q3,Q4 均为基可行解；而其延长线的交点Q5为 基解，但不是基可行解。 6、可行基 基可行解对应的B为可行基。
Research
(4)无可行解 x2 [eg.6] max z = 2x1 + 3x2 2 2x1 + 4x2 ≥ 8 1 x1 + x2 ≤ 1 1 x1，x2 ≥ 0 无公共部分，无可行域。 即无可行解。 在实际问题中，可能是关系错。
4
x1
8
Operations
Research
1.3 线性规划的标准型 1、标准型 max z = c1x1 + c2x2 + · · · + cnxn a11x1 + a12x2 + · · · + a1nxn = b1 a21x1 + a22x2 + · · · + a2nxn = b2 ┆ ┆ am1x1 + am2x2 + · · · + amnxn = bm x 1，x 2，· · · ，x n ≥ 0
