《运筹学在数学建模中的应用概要课件》由会员分享，可在线阅读，更多相关《运筹学在数学建模中的应用概要课件（129页珍藏版）》请在金锄头文库上搜索。
1、运筹学 在数学建模中的应用,一、运筹学概况 二、线性规划 三、整数规划与多目标规划 四、图论与网络优化 五、动态规划 六、赛题选讲,运 筹 学 概 况,运筹学的定义 运筹学简史 运筹学的主要内容及应用重点 运筹学应用步骤 运筹学在数学建模竞赛中的地位,运筹学是一种给出问题不坏的答案的艺术，否则的话问题的结果会更坏。,一、运筹学的定义, 运筹学(辞海)：20世纪40年代开始形成的一门学科，主要研究经济活动与军事活动中能用数量来表达的有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，做出综合性合理安排，以达到较经济有效地使用人力物力., 作为一门定量优化决策科学，起源于第二次
2、世界 战，英文原意 OperationResearch；,二、运筹学简史,深水炸弹的释放问题 防空系统的预警问题,运筹学的 一些分支,英美海空军 作战参谋部 组成了运筹 学研究小组,二战中,二战后,军事,工、商业领域,存储论、决策科学 、预测科学等分支, 20世纪50年代中期钱学森和许国志教授引入 “运用学”, 1957年 取 “运筹”二字，将OR正式命名为“运筹学” 开始应用于建筑业和纺织业,史记中“夫运筹帷幄之中，决胜千里之外”,线性规划,数 学 规 划,非线性规划,整数规划,动态规划,多目标规划,组 合 优 化,最优计数问题,网络优化,排序问题,统筹图,随 机 优 化,对策论,排队论,库
3、存论,决策分析,可靠性分析,三、运 筹 学 主 要 内 容,下的最大值或最小值。,将一个优化问题用数学式子来描述，即求函数,在约束条件,和,数学规划问题的一般形式,“受约束于”之意,网络优化 研究解决生产组织、计划管理中诸如最短路径问题、最小连接问题、最小费用流问题、最优分派问题及关键线路图等。特别在计划和安排大型复杂工程时，网络技术是重要的工具。,排队论 是20世纪初由丹麦数学家Erlang应用数学方法在研究电话话务理论过程中而发展起来的一门学科，排队论也称随机服务系统理论，排队论是定量的研究排队问题，寻找系统内在规律，寻找供求关系平衡的最优方案。,如机器等待修理、船舶等待装卸、顾客等待服务
4、等。,对策论 研究具有利害冲突的各方，如何制定对自己有利从而战胜对手的斗争策略,田忌赛马,运筹学的应用重点,1.市场销售 在广告预算和媒体的选择、竞争性定价、新产品开发、销售计划的制定等方面。如美国杜邦公司在五十年代起就非常重视将作业研究用于研究如合做好广告工作、产品定价和新产品的引入。,2. 生产计划 在总体计划方面主要是从总体确定生产、储存和劳动力的配合等计划以适应变动的需求计划，主要用线性规划和仿真方法等。此外，还可用于生产作业计划、日程表的编排等。还有在合理下料、配料问题、物料管理等方面的应用。,3. 库存管理 存货模型将库存理论与计算器的物料管理信息系统相结合，主要应用于多种物料库存
5、量的管理，确定某些设备的能力或容量，如工厂的库存、停车厂的大小、新增发电设备容量大小、计算机的主存储器容量、合理的水库容量等。,4. 运输问题 这里涉及空运、水运、公路运输、铁路运输、捷运、管道运输和厂内运输等。包括班次调度计划及人员服务时间安排等问题。,5.财政和会计 这里涉及预算、贷款、成本分析、定价、投资、证券管理、现金管理等。用得较多的方法是：统计分析、数学规划、决策分析。此外，还有盈亏点分析法、价值分析法等。,6. 人事管理 这里涉及六方面。(1)人员的获得和需求估计；(2)人才的开发，即进行教育和训练；(3)人员的分配，主要是各种指派问题；(4)各类人员的合理利用问题；(5)人才的
6、评价，其中有如何测定一个人对组织、社会的贡献；(6)薪资和津贴的确定等。,7.设备维修、更新和可靠度、项目选择和评价 如电力系统的可靠度分析、核能电厂的可靠度以及风险评估等。,8.工程的最佳化设计 在土木、建筑、水利、信息、电子、电机、光学、机械、环境和化工等领域皆有作业研究的应用。,9.城市管理 包括各种紧急服务救难系统的设计和运用。如消防队救火站、救护车、警车等分布点的设立。美国曾用等候理论方法来确定纽约市紧急电话站的值班人数。加拿大亦曾研究一城市警车的配置和负则范围，事故发生后警车应走的路线等。,分析与表述问题,建立模型,对模型和由模型导出的解进行检验,建立起对解的有效控制,对问题求解,
7、方案实施,不满意,满意,运筹学应用步骤,五、运筹学在数学建模竞赛中的地位,有人统计： 在全国大学生数学建模竞赛题中有40%可以用运筹学中的优化方法解决,1. CUMCM-1995A: 一个飞行管理问题 2. CUMCM-2000B: 钢管订购与运输 3. CUMCM-2003B：露天矿生产的车辆安排 4. CUMCM-2000D: 空洞探测 5. CUMCM-2006 B: 艾滋病疗法的评价及疗效的预测 6. CUMCM-2006 C : 易拉罐形状和尺寸的最优设计 7. CUMCM-2009B：眼科病床的合理安排,线 性 规 划,线性规划实例, 在各类经济活动中，经常遇到这样的问题： 在生产
8、条件不变的情况下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，组织生产过程，使总的经济效益最好。,可以化成或近似地化成“线性规划”（Linear Programming，简记为LP）问题,线性规划研究的实际问题： 生产计划问题、物资运输问题、合理下料问题、库存问题、劳动力问题、最优设计问题等,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天,例: 奶制品生产计划,x1桶牛奶生产A1,x2桶牛
9、奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,一般形式,目标函数 价值向量 价值系数 决策变量,右端向量,系 数 矩 阵,规范形式,标准形式,三种形式的LP问题全都是等价的，即一种形式的LP可以简单的变换为另一种形式的LP，且它们有相同的解 .,对于非标准形式的线性规划，可通过下列办法化成标准形式,若求 ,可化为求,若约束条件中含有不等式 或 则可引进新变量 （称为松弛变量），化为等式约束： 或,总假定 ，否则在等式两边乘以-1即可,若变量 无非负限
10、制，则引入两个非负变量 与 令 ，便可化为标准形式,线性规划模型的解的几种情况,图解法,约束条件,目标函数,在B(20,30)点得到最优解,模型求解,软件实现,LINDO 6.1,max 72x1+64x2 st 2）x1+x250 3）12x1+8x2480 4）3x1100 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
11、.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,DO RANGE (SENSITIVITY) ANALYSIS?,No,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.00000
12、0 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,原料无剩余,时间无剩余,加工能力剩余40,max 72x1+64x2 st 2）x1+x250 3）12x1+8x2480 4）3x1100 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
13、 DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.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 AL
14、LOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 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 R
15、ANGE(SENSITIVITY) ANALYSIS?,Yes,x1系数范围(64,96),x2系数范围(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 CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.33333
