华东理工大学：《运筹学动态规划》 线性规划讲义

线性 筹 公 5方 规划 学 论,色

Page:1 QSC 华东理工大学 工商经济学院 生产与运作管理

线性规划经典问题 生产计划问题 某工厂拥有A、B、C三种类型的设备,生产甲、乙、丙 丁四种产品。每件产品在生产中需要占用的设备机时数, 每件产品可以获得的利润以及三种设备可利用的时数如 下表所示: 产品产品产品产品 设备能力 每件产品占用的 乙丙丁 (小时) 机时数(小时/件) 设备A 15102410 2000 设备B 5.0 10 8000 设备C 5303.5 1.0 5000 利润(元/件) 5247308.34418

Page:2 QSC 华东理工大学 工商经济学院 生产与运作管理 线性规划经典问题 生产计划问题 某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、 丁四种产品。每件产品在生产中需要占用的设备机时数， 每件产品可以获得的利润以及三种设备可利用的时数如 下表所示： 每件产品占用的 机时数（小时/件） 产品 甲 产品 乙 产品 丙 产品 丁 设备能力 （小时） 设备A 1.5 1.0 2.4 1.0 2000 设备B 1.0 5.0 1.0 3.5 8000 设备C 1.5 3.0 3.5 1.0 5000 利润（元/件） 5.24 7.30 8.34 4.18

maxz=5.24x1+7.30x2+8.34x3+4.18x4 S t 1.5x +1.0x +24x <2000 +5.0 ≤8000 1.0x1 +35X3+1.0x4≤5000 X

Page:3 QSC 华东理工大学 工商经济学院 生产与运作管理 max z= 5.24x1 +7.30x2 +8.34x3 +4.18x4 s.t. 1.5x1 +1.0x2 +2.4x3 +1.0x4 ≤2000 1.0x1 +5.0x2 +1.0x3 +3.5x4 ≤8000 1.0x1 +3.0x2 +3.5x3 +1.0x4 ≤5000 x1 , x2 , x3 , x4 ≥0

线性规划问题的表示一般形式 max(min Z=C1X1+c,X+…CnX nn St.a1X1+a12X2+…a1nXn≤(=.≥)b1 +a2x2+…a2nXn≤(=>)b2 am1x1+am2X2+…amXn≤(=≥)b 13X1¨Xn≥0

Page:4 QSC 华东理工大学 工商经济学院 生产与运作管理 线性规划问题的表示一般形式 max(min) z = c1 x1 + c2 x2 ++c n xn s t a x a x a x b a x a x a x b a x a x a x b n n n m m mn n m . . ( . ) ( . ) ( . ) 11 1 12 2 1n 1 21 1 22 2 2 2 1 1 2 2 + +  =  + +  =  + +  =        x1 , x1  , xn  0

线性规划问题的表示矩阵形式 b 2 mn max(min) Z=CX S.t. AX0

Page:5 QSC 华东理工大学 工商经济学院 生产与运作管理 线性规划问题的表示-矩阵形式             = n c c c C  2 1             = n x x x X  2 1             = bn b b b  2 1             = m m mn n n a a a a a a a a a A        1 2 21 22 2 11 12 1 max (min) z＝CTX s.t. AX≤(＝,≥)b X≥0

线性规划问题的表示-标准形式 max z=CX s.t. AX=b X>0

Page:6 QSC 华东理工大学 工商经济学院 生产与运作管理 线性规划问题的表示-标准形式 max z＝CTX s.t. AX＝b X≥0

线性规划问题的几何特征 max F X1+3x2 s t X1tX ≤6 +2 <8 约束条件(1) 约束条件(2) 1 7-6-5-4-3-2-101z=0345

Page:7 QSC 华东理工大学 工商经济学院 生产与运作管理 线性规划问题的几何特征 max z= x1+3x2 s.t. x1+x2 ≤6 -x1+2x2 ≤8 x1 , x2 ≥0 1 2 3 4 5 6 x z=0 z=3 z=6 z=9 z=12 z=15.3 0 1 3 4 5 6 约束条件（1） 约束条件（2） C - 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 x 2 1

(a)可行域有界 (b)可行域有界 (c)可行域无界 唯一最优解 多个最优解 唯一最优解 (d)可行域无界 (e)可行域无界 (可行域为空集 多个最优解 目标函数无界 F 无可行解

Page:8 QSC 华东理工大学 工商经济学院 生产与运作管理 (d)可行域无界 (e)可行域无界 (f)可行域为空集 多个最优解 目标函数无界 无可行解 (a)可行域有界 (b)可行域有界 (c)可行域无界 唯一最优解 多个最优解 唯一最优解

线性规划解的基本概念 max x1+2x st +x, 2≌0 max F x +2 s t 1+X2+x 3 +x4=1 19 X x4≥0

Page:9 QSC 华东理工大学 工商经济学院 生产与运作管理 线性规划解的基本概念 max z= x1 +2x2 s.t. x1 +x2 ≤3 x2 ≤1 x1 , x2 ≥0 max z= x1 +2x2 s.t. x1 +x2 +x3 =3 x2 +x4 =1 x1 , x2 , x3 , x4 ≥0

基本解 X 基本可行解 (可行域顶点、极点) X2=0 可行域 (可行解全体) B X4=0 X1=0 X=0 A

Page:10 QSC 华东理工大学 工商经济学院 生产与运作管理 O 1 2 3 1 2 3 x x 2 1 A C B D x3 =0 x4 =0 x 2 =0 x1 =0 可行域 (可行解全体) 基本可行解 (可行域顶点、极点) 基本解