优化问题及其数学模型.ppt

《优化问题及其数学模型.ppt》由会员分享，可在线阅读，更多相关《优化问题及其数学模型.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27第一讲第一讲优化问题及其数学模型优化问题及其数学模型原书相关信息原书相关信息谢金星谢金星,薛毅编著薛毅编著,清华大学出版社清华大学出版社,2005年年7月第月第1版版.http:/ 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27 最优化是工程技术、经济管理、科学研究、社最优化是工程技术、经济管理、科学研究、社最优化是工程技

2、术、经济管理、科学研究、社最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题会生活中经常遇到的问题会生活中经常遇到的问题会生活中经常遇到的问题,如如如如:优化模型和算法的重要意义优化模型和算法的重要意义结构设计结构设计结构设计结构设计资源分配资源分配资源分配资源分配生产计划生产计划生产计划生产计划运输方案运输方案运输方案运输方案解决优化问题的手段解决优化问题的手段解决优化问题的手段解决优化问题的手段 经验积累，主观判断经验积累，主观判断经验积累，主观判断经验积累，主观判断 作试验，比优劣作试验，比优劣作试验，比优劣作试验，比优劣 建立数学模型，求解最优策略建立数学模型，求解最优策略

3、建立数学模型，求解最优策略建立数学模型，求解最优策略最优化最优化最优化最优化:在一定条件下，寻求使目标最大在一定条件下，寻求使目标最大在一定条件下，寻求使目标最大在一定条件下，寻求使目标最大(小小小小)的决策的决策的决策的决策 1.优化模型的基本概念优化模型的基本概念新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27优化问题三要素：优化问题三要素：决策变量决策变量；目标函数目标函数；约束条件约束条件约约束束条条件件决策变量决策变量优化问题的一般形式优化问题的一般形式无约束优化

4、无约束优化(没有约束没有约束)与约束优化与约束优化(有约束有约束)可行解（只满足约束）与最优解可行解（只满足约束）与最优解(取到最优值取到最优值)目标函数目标函数新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27局部最优解与整体最优解局部最优解与整体最优解局部最优解局部最优解(LocalOptimalSolution,如如x1)整体最优解整体最优解(GlobalOptimalSolution,如如x2)x*f(x)x1x2o新余学院新余学院 建模组建模组优优优优 化化化化 建

5、建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27优化模型的优化模型的简单分类简单分类线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性整数规划整数规划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)

6、一般整数规划，一般整数规划，0-1（整数）规划（整数）规划连连续续优优化化离离散散优优化化数学规划数学规划新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27优化模型的简单分类和求解难度优化模型的简单分类和求解难度 优化线性规划非线性规划二次规划连续优化整数规划 问题求解的难度增加新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/272.优化问题的建模实例优化问题

7、的建模实例新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/271桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶时间时间480小时小时 至多加工至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获

8、利增加到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：线性规划模型例线性规划模型例1.1:奶制品生产计划奶制品生产计划 新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/271桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天

9、获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l5约约束束条条件件目标目标函数函数 Z=0Z=2400Z=3600z=c(常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解LPLP的通常解法是单纯形法的通常解法是单纯形法(G.B.Dantz

10、ig,1947)(G.B.Dantzig,1947)新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27线性规划模型的解的几种情况线性规划模型的解的几种情况 线性规划问题线性规划问题有可行解有可行解(Feasible)无无可可行行解解（Infeasible）有有最最优优解解（Optimal）无无最最优优解解(Unbounded)新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2

11、022/10/27假设假设A产销平衡产销平衡假设假设Bp随随x(两种牌号两种牌号)增加而减小，呈线性关系增加而减小，呈线性关系某厂生产两个牌号的同一种产品，如何确定产量使利润最大某厂生产两个牌号的同一种产品，如何确定产量使利润最大二次规划模型例：产销计划问题二次规划模型例：产销计划问题新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27假设假设C假设假设D两产品的产量之和不可能超过两产品的产量之和不可能超过100件件假设假设E甲产量不可能超过乙的产量的甲产量不可能超过乙的产量的

12、2倍倍假设假设F求甲、乙产量，使总利润最大？求甲、乙产量，使总利润最大？新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27目标目标利润最大利润最大=（100-x1 x2-2）x1+（x1-2x2-3）x2=98 x1+277 x2x12 x1 x22x22约束约束x1+x2100 x12 x2x1,x20二次规划模型二次规划模型(QP)若还要求产量为整数，则是整数二次规划模型若还要求产量为整数，则是整数二次规划模型(IQP)新余学院新余学院 建模组建模组优优优优 化化化化 建

13、建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27非线性规划模型例：选址问题非线性规划模型例：选址问题某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai,bi)(单位：公里单位：公里),水泥日用量水泥日用量di(单位：吨）单位：吨）假设：假设：料场料场和工地之间和工地之间有直线道路有直线道路新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27用例中数据计算，最优解为总吨公里数为总吨公里数为总吨

14、公里数为总吨公里数为线性规划模型线性规划模型（LP）决策变量：决策变量：ci j(料场料场j到到工地工地i的的运量）运量）12维维新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27选址问题：选址问题：NLPNLP2）改建两个新料场，需要确定新料场位置）改建两个新料场，需要确定新料场位置(xj,yj)和和运量运量cij，在其它条件不变下使总吨公里数最小。，在其它条件不变下使总吨公里数最小。决策变量：决策变量：ci j，(xj,yj)16维维非线性规划模型非线性规划模型(NLP)

15、新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27整数规划整数规划 -例例1.4:1.4:聘用方案聘用方案决策变量决策变量：周一至周日每天：周一至周日每天(新新)聘用人数聘用人数x1,x2,x7目标函数目标函数：7天天(新新)聘用人数之和聘用人数之和约束条件约束条件：周一至周日每天需要人数：周一至周日每天需要人数新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/

16、27连续工作连续工作5天天周一工作的应是周一工作的应是(上上)周四至周一聘用的周四至周一聘用的设系统已进入稳态（不是开始的几周）设系统已进入稳态（不是开始的几周）聘用方案聘用方案整数规划整数规划模型模型(IP)(IP)新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27丁的蛙泳成绩退步到丁的蛙泳成绩退步到115”2；戊的自由泳成绩进；戊的自由泳成绩进步到步到57”5,组成接力队的方案是否应该调整组成接力队的方案是否应该调整？如何选拔队员组成如何选拔队员组成4 4 100100米

17、混合泳接力队米混合泳接力队?0-1规划规划混合泳接力队的选拔混合泳接力队的选拔甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”4例：例：5名候选人的名候选人的百米成绩百米成绩穷举法穷举法：组成接力队的方案共有组成接力队的方案共有5!=120种种。新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27

18、目标目标函数函数若选择队员若选择队员i参加泳姿参加泳姿j 的比赛，记的比赛，记xij=1,否则记否则记xij=0 0-1规划模型规划模型 cij(秒秒)队员队员i 第第j 种泳姿的百米成绩种泳姿的百米成绩约束约束条件条件每人最多入选泳姿之一每人最多入选泳姿之一ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有每种泳姿有且只有1 1人人 0-1规划规划:整数规划的特例整数规划的特例新余学院新余学院 建模组建模组优优优优 化化化化 建建建

19、建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27整数规划问题整数规划问题一般形式一般形式整数线性规划整数线性规划(ILP)目标和约束均为线性函数目标和约束均为线性函数整数非线性规划整数非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数整数规划问题的分类整数规划问题的分类纯纯(全全)整数规划整数规划(PIP)决策变量均为整数决策变量均为整数混合整数规划混合整数规划(MIP)决策变量有整数，也有实数决策变量有整数，也有实数0-1规划规划决策变量只取决策变量只取0或或1新余学院新余学院 建模组建模组优优优优 化化

20、化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题整数规划问题对应的松弛问题整数规划问题对应的松弛问题松弛问题松弛整数规划问题最优解最优解整数非整数整数舍入非最优解新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27x1x20Po69Zmax56去掉整数限制后，可行域为点（0,0),(6,0),(0,5),P(2.25,3

21、.75)围成的4边形从LP最优解经过简单的“移动”不一定能得到IP最优解例例新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27无无约约束束优优化化更多的优化问题更多的优化问题线线性性规规划划非非线线性性规规划划网网络络优优化化组组合合优优化化整整数数规规划划不不确确定定规规划划多多目目标标规规划划目目标标规规划划动动态态规规划划连续优化连续优化离散优化离散优化从其他角度分类从其他角度分类应用广泛：应用广泛：生产和运作管理、经济与金融、图论和网生产和运作管理、经济与金融、图论和

22、网络优化、目标规划问题、对策论、排队论、存储论，络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等以及更加综合、更加复杂的决策问题等实际问题规模往往较大，用软件求解比较方便实际问题规模往往较大，用软件求解比较方便新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27建模时需要注意的几个基本问题建模时需要注意的几个基本问题1、尽量使用实数优化，减少整数约束和整数变量尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数尽量使

23、用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最如：尽量少使用绝对值、符号函数、多个变量求最大大/最小值、四舍五入、取整函数等最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量尽量使用线性模型，减少非线性约束和非线性变量的个数的个数（如（如x/y5改为改为x5y）4、合理设定变量上下界，尽可能给出变量初始值合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当模型中使用的参数数量级要适当(如小于如小于103)新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUnivers

24、ityMCM优优 化化 建建 模模2022/10/27课后作业课后作业统计数据统计数据广告媒体效果报纸电台电视每个广告影响的总人数影响的已婚人数影响平均收入以上的人数最低广告数量限制（个）最高广告数量限制（个）每个广告的成本（万元）5000015000200002510031000002000030000301501.51500004000050000205015例例1一家连琐店公司正在计划明年的广告预算，该公司计划用一家连琐店公司正在计划明年的广告预算，该公司计划用1000万元在报纸、广播和电视上做广告。下表是他们做规划用的统计数万元在报纸、广播和电视上做广告。下表是他们做规划用的统计数据：

25、据：新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27该公司的目标是使广告影响的人数最多，并且满足下面的条件：该公司的目标是使广告影响的人数最多，并且满足下面的条件：1)至少要影响至少要影响500万人口；万人口；2)至少要影响至少要影响100万已结婚的人口；万已结婚的人口；3)至少要影响至少要影响150万收入在平均收入以上的人口；万收入在平均收入以上的人口；4)在每种媒介上所做的广告要在最高和最低限制数之间。在每种媒介上所做的广告要在最高和最低限制数之间。统计数据统计数据广告

26、媒体效果报纸电台电视每个广告影响的总人数影响的已婚人数影响平均收入以上的人数最低广告数量限制（个）最高广告数量限制（个）每个广告的成本（万元）5000015000200002510031000002000030000301501.51500004000050000205015新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27例例2有两个煤厂有两个煤厂A,B，每月分别进煤不小于，每月分别进煤不小于60t，100t，它们负担供，它们负担供应三个居民区用煤任务，这三个居民区每月需用

27、煤分别是应三个居民区用煤任务，这三个居民区每月需用煤分别是45t,75t和和40t，A厂到这三个居民区单位运费分别是厂到这三个居民区单位运费分别是10千元千元/吨吨,5千元千元/吨，吨，6千千元元/吨，吨，B厂到这三个居民区单位运费分别是厂到这三个居民区单位运费分别是4千元千元/吨吨,8千元千元/吨吨,15千千元元/吨吨,问这两个煤厂如何分配供煤，才使总运费最少？请写出相应的问这两个煤厂如何分配供煤，才使总运费最少？请写出相应的数学模型。数学模型。例例3用长度为用长度为500cm的条材，截成长度分别为的条材，截成长度分别为98cm和和78cm二种毛坯，二种毛坯，要求共截出长要求共截出长98cm

28、的毛坯的毛坯10000根，根，78cm的的20000根，问怎样截法，根，问怎样截法，才使所用的原料最小？写出相应的数学模型。才使所用的原料最小？写出相应的数学模型。新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27例例4某房地产开发商准备在两片开发区上分别圈出一块长方形土地，某房地产开发商准备在两片开发区上分别圈出一块长方形土地，并砌围墙将这两块土地分别围起来，每块土地的面积不得小于并砌围墙将这两块土地分别围起来，每块土地的面积不得小于1000平米，围墙的高度不能低于平米，围

29、墙的高度不能低于2米。能够用于砌墙的每块砖是一样的，米。能够用于砌墙的每块砖是一样的，每块砖的高度为每块砖的高度为10cm，长度为，长度为30cm，宽度为，宽度为15cm（假设砖的宽度（假设砖的宽度就是围墙的宽度）。该开发商希望用就是围墙的宽度）。该开发商希望用10万块砖，使圈出的两块土地万块砖，使圈出的两块土地的面积之和最大，问应如何圈地？的面积之和最大，问应如何圈地？新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/27例例5某厂生产三种产品某厂生产三种产品I，II，III。

30、每种产品要经过两道工序加工。每种产品要经过两道工序加工。设该厂有两种规格的设备能完成工序，它们以表示；有三种规格的设该厂有两种规格的设备能完成工序，它们以表示；有三种规格的设备能完成工序，它们以表示。产品设备能完成工序，它们以表示。产品I可在任何一种规格设备上加工。可在任何一种规格设备上加工。产品产品II可在任何规格的设备上加工，但完成工序时，只能在设备上可在任何规格的设备上加工，但完成工序时，只能在设备上加工；产品加工；产品III只能在与设备上加工。已知在各种机床设备的单件工只能在与设备上加工。已知在各种机床设备的单件工时，原材料费，产品销售价格，各种设备有效台时以及满负荷操作时，原材料费，

31、产品销售价格，各种设备有效台时以及满负荷操作时机床设备的费用如下表，要求安排最优的生产计划，使该厂利润时机床设备的费用如下表，要求安排最优的生产计划，使该厂利润最大。最大。设备产 品设备有效台时满负荷时的设备费用(元)IIIIII57647 10 9 81211600010000400070004000300321250783200原料费(元/件)单 价(元/件)0.251.250.352.000.502.80新余学院新余学院 建模组建模组优优优优 化化化化 建建建建 模模模模上一页上一页下一页下一页XinyuUniversityMCM优优 化化 建建 模模2022/10/272022/10/27