优化模型讲座2011.ppt
《优化模型讲座2011.ppt》由会员分享,可在线阅读,更多相关《优化模型讲座2011.ppt(49页珍藏版)》请在三一文库上搜索。
1、数学建模讲座,仇秋生 数理信息工程学院 2011、8,内容安排 1、最优化问题简介 2、LINGO软件简介 3、线性规划模型 4、非线性规划模型 5、0-1规划模型 6、投资的收益与风险 7、露天矿生产的车辆安排,1、最优化问题简介,所谓最优化问题就是在许多可行的方案中找到最好的方案。例如:在工程设计中,如何选择设计参数,使得设计方案既满足设计要求,又能降低成本。,优化模型一般包括以下三个要素: (1)决策变量。它通常是该问题要求解的那些未知量。一般用n维向量 表示。 (2)目标函数。通常是该问题要优化(最大或最小)的那个目标的数学表达式,是决策变量的函数。 (3) 约束条件。即决策变量允许取
2、值的范围,常用一组关于决策变量的等式 和不等式 来界定,分别称为等式约束和不等式约束。,一般模型为:,例1:汽车生产计划,汽车厂生产三种类型的汽车,已知各类型每辆车对 钢材、劳动时间的需求,利润及工厂每月的现有量。 若生产某类汽车,则至少生产80辆,求生产计划,使工厂的利润最大,小型 中型 大型 现有量 钢材(吨) 1.5 3 5 600 劳动时间(小时) 280 250 400 60000 利润(万元) 2 3 4,例2 加工奶制品的生产计划,问题:一奶制品加工厂生产A1, A2两种奶制品,1桶牛奶可以在设备甲上用12小时加工成3公斤A1, 或在设备乙上用8小时加工成4公斤A2。生产的产品全
3、部售出,且每公斤A1获利24元,每公斤A2获利16元。现在加工厂每天能得到50桶牛奶供应,每天正式工人总的劳动时间为480小时,且设备甲每天至多能加工100公斤A1。试为工厂制定一个生产计划,使每天获利最大。并进一步讨论以下问题:,(1)35元可买到1桶牛奶,买吗?若买,每天最多买多少? (2)可聘用临时工人,付出的工资最多是每小时几元? (3)A1的获利增加到 30元/公斤,应否改变生产计划?,例2 加工奶制品的生产计划,50桶牛奶,总时间480小时,甲至多加工100公斤A1,制订生产计划,使每天获利最大,35元可买到1桶牛奶,买吗?若买,每天最多买多少?,可聘用临时工人,付出的工资最多是每
4、小时几元?,A1的获利增加到 30元/公斤,应否改变生产计划?,每天:,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,最优化问题分类,(1)线性规划(LP): 所有函数都是决策变量的线性函数。,(2)非线性规划(NLP): 目标函数和约束条件中至少有一个函数是非线性函数。,(3) 二次规划(QP): 目标函数是决策变量的二次函数,而所有约束都是决策变量的线性函数。,3、线性规划模型,重点是:模型建立、模型的化简、结果分析。
5、 求解主要利用LINGO软件。,(4)整数规划(IP): 决策变量仅取整数值。,2、LINGO软件简介,模型求解,软件实现,Model: Max= 72*x1+64*x2; x1+x250; 12*x1+8*x2480; 3*x1100; end,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000
6、2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,20桶牛奶生产A1, 30桶生产A2,利润3360元。,结果解释,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATI
7、ONS= 2,原料无剩余,时间无剩余,加工能力剩余40,Model: Max= 72*x1+64*x2; x1+x250; 12*x1+8*x2480; 3*x1100; end,三种资源,“资源” 剩余为零的约束为紧约束(有效约束),结果解释,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2
8、.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,最优解下“资源”增加1单位时“效益”的增量,原料增加1单位, 利润增长48,时间增加1单位, 利润增长2,加工能力增长不影响利润,影子价格,35元可买到1桶牛奶,要买吗?,35 48, 应该买!,聘用临时工人付出的工资最多每小时几元?,2元!,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.0
9、00000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,最优解不变时目标函数系数允许变化范围,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x1系数范围(64,96),x2
10、系数范围(48,72),A1获利增加到 30元/千克,应否改变生产计划,x1系数由24 3=72增加为303=90,在允许范围内,不变!,(约束条件不变),结果解释,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURR
11、ENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶,每天最多买多少?,最多买10桶!,(目标函数不变),问题:某公司用两种原油(A和B)混合加工两种汽油(甲和乙)。甲、乙两种汽油含原油A的最低比例分别为50%和60%,每吨售价分别为4800元和5600元。该公司现有原油
12、A和B的库存量分别为500吨和1000吨。市场上可买到不超过1500吨的原油A: 购买量不超过500吨时的单价为10000元/吨。购买量超过500吨但不超过1000吨时,超过500吨的部分8000元/吨; 购买量超过1000吨时,超过1000吨的部分6000元/吨。该公司应如何安排原油采购与加工?,例3 原油采购与加工,应如何安排原油的采购和加工 ?,原油采购与加工,市场上可买到不超过1500吨的原油A: 购买量不超过500吨时的单价为10000元/吨; 购买量超过500吨但不超过1000吨时,超过500吨的 部分8000元/吨; 购买量超过1000吨时,超过1000吨的部分6000元/吨。,
13、决策变量,目标函数,问题分析,利润:销售汽油的收入 - 购买原油A的支出 难点:原油A的购价与购买量的关系较复杂,原油A的购买量,原油A, B生产汽油甲,乙的数量,c(x) 购买原油A的支出,利润(千元),c(x)如何表述?,原油供应,约束条件,x 500吨单价为10千元/吨; 500吨 x 1000吨,超过500吨的8千元/吨; 1000吨 x 1500吨,超过1000吨的6千元/吨。,目标函数,目标函数中c(x)不是线性函数,是非线性规划; 对于用分段函数定义的c(x),一般的非线性规划软件也难以输入和求解; 想办法将模型化简,用现成的软件求解。,汽油含原油A的比例限制,约束条件,x1 ,
14、 x2 , x3 以价格10, 8, 6(千元/吨)采购A的吨数,目标函数,只有当以10千元/吨的价格购买x1=500(吨)时,才能以8千元/吨的价格购买x2,方法1,非线性规划模型,可以用LINGO求解,模型求解,x= x1+x2+x3, c(x) = 10x1+8x2+6x3,500吨 x 1000吨,超过500吨的8千元/吨,x= x1+x2+x3, c(x) = 10x1+8x2+6x3,方法1:LINGO求解,Model: Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8*x2 - 6*x3; x11+x12 0; 2*x1
15、2 - 3*x22 0; x=x1+x2+x3; (x1 - 500) * x2=0; (x2 - 500) * x3=0; x1 0; x11 0; x12 0; x21 0; x22 0; x1 0; x2 0; x3 0; end,Objective value: 4800.000 Variable Value Reduced Cost X11 500.0000 0.0000000E+00 X21 500.0000 0.0000000E+00 X12 0.0000000E+00 0.0000000E+00 X22 0.0000000E+00 0.0000000E+00 X1 0.1021
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 模型 讲座 2011
链接地址:https://www.31doc.com/p-2654864.html