线性规划模型案例 —数学建模与系统仿真 主讲:王晓峰 E-mail:xfwang8280126.com
线 性 规 划 模 型 案 例 ——数学建模与系统仿真 主讲：王晓峰 E-mail:xfwang828@126.com
教学规圳模剋案例 1奶制品的生产与销售 2自来水输送与货机装运 3汽车生产与原油采购 4接力队选拔和选课策略
数学规划模型案例 1 奶制品的生产与销售 2 自来水输送与货机装运 3 汽车生产与原油采购 4 接力队选拔和选课策略
数学规划模型 实际问题中min(或max)z=f(x)2x=(x2…,xn) 的优化模型 st.g(x)≤0,i=1,2, x决策变量x)}目标函数90-约束条件 决策变量个数n和 数 多元函数约束条件个数m较大线性规划 条件极值 最优解在可行域规非线性规划 划整数规划 的边界上取得 重点在模型的建立和结果的分析
数学规划模型 实际问题中 的优化模型 T min( max) ( ), ( , , ) 1 s.t. ( ) 0, 1,2, , n i z f x x x x g x i m = = = 或 x~决策变量 f(x)~目标函数 gi (x)0~约束条件 多元函数 条件极值 决策变量个数n和 约束条件个数m较大 最优解在可行域 的边界上取得 数 学 规 划 线性规划 非线性规划 整数规划 重点在模型的建立和结果的分析
例1加工奶制品的生产计划 问「1桶 12h 3kgA1获利24元/kg 题牛奶或 kGa 2 获利16元/ 8h 每天:50桶牛奶时间480h至多加工100kgA1 制订生产计划,使每天获利最大 35元可买到1桶牛奶,买吗?若买,每天最多买多少? 可聘用临时工人,付出的工资最多是每小时几元? A1的获利增加到30元/kg,应否改变生产计划? c
例1 加工奶制品的生产计划 1桶 牛奶 3kgA1 12h 8h 4kgA2 或 获利24元/kg 获利16元/kg 50桶牛奶 时间480h 至多加工100kgA1 制订生产计划，使每天获利最大 • 35元可买到1桶牛奶，买吗？若买，每天最多买多少? • 可聘用临时工人，付出的工资最多是每小时几元? • A1的获利增加到 30元/kg，应否改变生产计划？ 每天： 问 题
基本1桶 kga 12h 获利24元/kg 模型牛奶或 kga 获利16元/kg 8h 2 每天50桶牛奶时间480h至多加工100kgA1 决策变量x1桶牛奶生产A1x2桶牛奶生产A2 目标函数获利24×3x1获利16×4x2 每天获利mxz=72x1+64x2 线性 原料供应 x,+x2<50 规划 约束条件劳动时间 12x1+8x,≤480 模型 加工能力 3x,≤100 LP 非负约束 x12x2≥0
1桶 牛奶 3kgA1 12h 8h 4kgA2 或 获利24元/kg 获利16元/kg x1桶牛奶生产A1 x2桶牛奶生产A2 获利 24×3x1 获利 16×4 x2 原料供应 x1 + x2 50 劳动时间 12x1 +8x2 480 加工能力 3x1 100 决策变量 目标函数 max 72 1 64 2 每天获利 z = x + x 约束条件 非负约束 x1 , x2 0 线性 规划 模型 (LP) 时间480h 至多加工100kgA1 每天 50桶牛奶 基本 模型
模型求解 软件实现 LINGO model: Global optimal solution found max=72*x1+64*x2; Objective value 3360.000 Imilk xl+ x2<50; Total solver iterations: 2 time Variable value Reduced Cost 12*x1+8*x2<480 X120.00000 0.000000 cpc]3*x1<100: X230.00000 0.000000 end Row Slack or Surplus Dual Price 3360.000 1.000000 MLLK0.000000 48.00000 TIME0.000000 2.000000 CPCT40.00000 0.000000 20桶牛奶生产A1,30桶生产A2,利润3360元 c
模型求解 软件实现 LINGO model: max = 72*x1+64*x2; [milk] x1 + x2<50; [time] 12*x1+8*x2<480; [cpct] 3*x1<100; end Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 20桶牛奶生产A1 , 30桶生产A2，利润3360元
结果解释 model: Global optimal solution found max=72*x1+64x2; Obiective value: 3360.000 miIk」x1+x2<50; Total solver iterations: 2 time Ⅴ ariableⅤalue Reduced cost 12*x1+8*x2<480 X120.00000 0.000000 cpct3*x1<100; X2 30.00000 0.000000 end Row Slack or Surplus dual Price 13360.000 1000000 原料无剩余←MILK0.0000 48.00000 种时间无剩余←TME 0.000000 2.000000 资加工能力剩余40←CPCT 40.00000 0.000000 源 “资源”剩余为零的约束为紧约束(有效约束)
结果解释 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 model: max = 72*x1+64*x2; [milk] x1 + x2<50; [time] 12*x1+8*x2<480; [cpct] 3*x1<100; end 三 种 资 源 “资源” 剩余为零的约束为紧约束（有效约束） 原料无剩余 时间无剩余 加工能力剩余40
Global optimal solution found 结果解释 Objective value: 3360.000 Total solver iterations: 2最优解下“资源”增加 Variable value Reduced cost1单位时“效益”的增 X120.00000 0.000000 量 X230.00000 0.000000 Row Slack or Surplus Dual Price 影子价格 13360.000 1.000000 MILK0048.00原料增加1单位,利润增长48 TIME0.0002.00000时间增加1单位,利润增长2 CPCT40.000000加能力增长不影响利润 35元可买到1桶牛奶,要买吗?35<48,应该买! 聘用临时工人付出的工资最多每小时几元?2元!
Global optimal solution found. 结果解释 Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 最优解下“资源”增加 1单位时“效益”的增 量 影子价格 • 35元可买到1桶牛奶，要买吗? 35 <48, 应该买！ • 聘用临时工人付出的工资最多每小时几元? 2元！ 原料增加1单位, 利润增长48 时间增加1单位, 利润增长2 加工能力增长不影响利润
敏感性分析(“ LINGORanges”) 最优解不变时目标函 Ranges in which the basis is unchanged: 数系数允许变化范围 Objective Coefficient Ranges(约束条件不变) Current Allowable Allowable Variable Coefficient Increase Decrease X172.0000024.000008.000000 x1系数范围(64,96) X264.000900001.00002系数范围(48,72) Righthand side ranges Row Current Allowable Allowable RHS Increase Decrease MLLK50.0000010.000006666667 x1系数由24×3=72 TIVE480.000053.3333380.00000 增加为30×3=90, CPCT 100.0000 INFINITY 40.00000 在允许范围内 A获利增加到30元/kg,应否改变生产计划?不变
Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000 最优解不变时目标函 数系数允许变化范围 敏感性分析 (“LINGO|Ranges” ) x1系数范围(64,96) x2系数范围(48,72) • A1获利增加到 30元/kg，应否改变生产计划? x1系数由24 3=72 增加为303=90， 在允许范围内 不变！ (约束条件不变)
结果解释影子价格有意义时约束右端的允许变化范围 Ranges in which the basis is unchanged (目标函数不变) Obiective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X172.0000024.000008.000000 X2 64.00000800000016.00000 Righthand side ranges Row Current Allowable Allowable RHS Increase Decrease MLLK50.0000010.000006.666667 原料最多增加10 TIME480.00053338000时间最多增加53 CPCT 100.0000 INFINITY 40.00000 充分条件! 35元可买到1桶牛奶每天最多买多少?最多买10桶! c
结果解释 Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000 影子价格有意义时约束右端的允许变化范围 原料最多增加10 时间最多增加53 • 35元可买到1桶牛奶, 每天最多买多少? 最多买10桶! (目标函数不变) 充分条件 !