模型与软件3_数学规划软件.ppt

优化模型与软件工具数学规划软件;线性规划;求解线性规划模型的历史; 80年代：计算机硬件、软件技术进步加快，求解模型的规模又上升一个数量级 内点法问世，新软件出现，如CPLEX，OSL等； 出现较完整的模型构造求解系统：GAMS，AMPL等 90年代：信息技术时代，运筹学与信息技术的融合 出现了基于WINDOWS平台的应用系统 IT与OR的集成，出现集信息采集、存储、分析、优化于一体的综合决策支持系统； 可求解有上千万变量的超大型数学模型； 典型应用：金融、航空、通讯、能源、军事等领域;线性规划软件的进步（一）;线性规划软件的进步（二）;求解线性规划综合速度的提高;线性规划软件的进步;单纯形方法的计算效率;求解线性规划的多项式方法;单纯形方法与内点法的竞赛;整数规划;整数规划;即便求解很小的整数规划也会很困难，求解时间可能以指数增长。如果用穷举法求???，需要的时间如下： n 解的数量 求解时间 10 1.02?103 1.02?10-3 秒 20 1.05?106 1.05 秒 30 1.07?109 18 分钟 40 1.10?1012 13 天 50 1.73?1015 36 年 100 1.27?1030 4 亿亿 年;整数规划求解史：1950－1998;分支定界法;整数规划－NP难题;线性规划求解速度也可能是瓶颈;整数规划求解方法进展;预处理;节点选择方法;割平面法;整数规划求解方法进展;一个求解实例;其它方法带来的改善;求解技术改进带来的好处;运筹模型技术的应用前景;学习动物精神;学习动物精神;谢谢大家！