第1讲优化问题及其数学模型

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,新余学院 建模组,优 化 建 模,上一页,下一页,Xinyu University MCM,优 化 建 模,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2024/11/6,第一讲,优化问题及其数学模型,原书相关信息,谢金星,薛毅编著,清华大学出版社,2019,年,7,月第,1,版,.,faculty.math.tsinghua.edu/jxie/lindo,内容提要,1.,优化模型的基本概念,2.,优化问题的建模实例,2024/11/6,最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如,:,优化模型和算法的重要意义,结构设计,资源分配,生产计划,运输方案,解决优化问题的手段,经验积累，主观判断,作试验，比优劣,建立数学模型，求解最优策略,最优化,:,在一定条件下，寻求使目标最大,(,小,),的决策,1.,优化模型的基本概念,2024/11/6,优化问题三要素：,决策变量,；,目标函数,；,约束条件,约束条件,决策变量,优化问题的一般形式,无约束优化,(,没有约束,),与约束优化,(,有约束,),可行解（只满足约束）与最优解,(,取到最优值,),目标函数,2024/11/6,局部最优解与整体最优解,局部最优解,(Local Optimal Solution,如,x,1,),整体最优解,(Global Optimal Solution,如,x,2,),x,*,f,(,x,),x,1,x,2,o,2024/11/6,优化模型的,简单分类,线性规划,(LP),目标和约束均为线性函数,非线性规划,(NLP),目标或约束中存在非线性函数,二次规划,(QP),目标为二次函数、约束为线性,整数规划,(IP),决策变量,(,全部或部分,),为整数,整数,线性,规划,(ILP),，整数,非线性,规划,(INLP),纯整数规划,(PIP),混合整数规划,(MIP),一般整数规划，,0-1,（整数）规划,连续优化,离散优化,数学规划,2024/11/6,优化模型的简单分类和求解难度,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,问题求解的难度增加,2024/11/6,2.,优化问题的建模实例,2024/11/6,1,桶牛奶,3,公斤,A,1,12,小时,8,小时,4,公斤,A,2,或,获利,24,元,/,公斤,获利,16,元,/,公斤,50,桶牛奶,时间,480,小时,至多加工,100,公斤,A,1,制订生产计划，使每天获利最大,35,元可买到,1,桶牛奶，买吗？若买，每天最多买多少,?,可聘用临时工人，付出的工资最多是每小时几元,?,A,1,的获利增加到,30,元,/,公斤，应否改变生产计划？,每天：,线性规划模型例,1.1:,奶制品生产计划,2024/11/6,1,桶牛奶,3,公斤,A,1,12,小时,8,小时,4,公斤,A,2,或,获利,24,元,/,公斤,获利,16,元,/,公斤,x,1,桶牛奶生产,A,1,x,2,桶牛奶生产,A,2,获利,243,x,1,获利,164,x,2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型,(LP),时间,480,小时,至多加工,100,公斤,A,1,50,桶牛奶,每天,2024/11/6,模型求解,图解法,x,1,x,2,0,A,B,C,D,l,1,l,2,l,3,l,4,l,5,约束条件,目标函数,Z,=0,Z,=2400,Z,=3600,z,=,c,(,常数,),等值线,c,在,B,(20,30),点得到最优解,LP,的通常解法是单纯形法,(G.B.Dantzig,1947),2024/11/6,线性规划模型的解的几种情况,线性规划问题,有可行解,(Feasible),无可行解（,Infeasible,）,有最优解（,Optimal,）,无最优解,(Unbounded),2024/11/6,假设,A,产销平衡,假设,B,p,随,x,(,两种牌号)增加而减小，呈线性关系,某厂生产两个牌号的同一种产品，如何确定产量使利润最大,二次规划模型例,1.2,：产销计划问题,2024/11/6,假设,C,假设,D,两产品的产量之和不可能超过,100,件,假设,E,甲产量不可能超过乙的产量的,2,倍,假设,F,求甲、乙产量，使总利润最大？,2024/11/6,目标,利润最大,=,（,100-,x,1,-0.1,x,2,-2,）,x,1,+,（,280-0.2,x,1,-2,x,2,-3,）,x,2,=98,x,1,+277,x,2,x,1,2,0.3,x,1,x,2,2,x,2,2,约束,x,1,+,x,2,100,x,1,2,x,2,x,1,x,2,0,二次规划模型,(QP),若还要求产量为整数，则是整数二次规划模型,(IQP),2024/11/6,非线性规划模型例,1.3,：选址问题,某公司有,6,个建筑工地，位置坐标为,(,a,i,b,i,)(,单位：公里,),水泥日用量,d,i,(,单位：吨）,假设：,料场和工地之间有直线道路,2024/11/6,用例中数据计算，最优解为,总吨公里数为,136.2,线性规划模型（,LP,）,决策变量：,c,i j,(,料场,j,到,工地,i,的运量）,12,维,2024/11/6,选址问题：,NLP,2,）改建两个新料场，需要确定新料场位置,(,x,j,y,j,),和运量,c,ij,，在其它条件不变下使总吨公里数最小。,决策变量：,c,i j,，,(,x,j,y,j,)16,维,非线性规划模型,(NLP),2024/11/6,整数规划,-,例,1.4:,聘用方案,决策变量,：周一至周日每天,(,新,),聘用人数,x,1,x,2,x,7,目标函数,：,7,天,(,新,),聘用人数之和,约束条件,：周一至周日每天需要人数,2024/11/6,连续工作,5,天,周一工作的应是,(,上,),周四至周一聘用的,设系统已进入稳态（不是开始的几周）,聘用方案,整数规划,模型,(IP),2024/11/6,丁的蛙泳成绩退步到,115”2,；戊的自由泳成绩进步到,57”5,组成接力队的方案是否应该调整,？,如何选拔队员组成,4,100,米混合泳接力队,?,0-1,规划 混合泳接力队的选拔,甲,乙,丙,丁,戊,蝶泳,106”8,57”2,118”,110”,107”4,仰泳,115”6,106”,107”8,114”2,111”,蛙泳,127”,106”4,124”6,109”6,123”8,自由泳,58”6,53”,59”4,57”2,102”4,例,1.5,：,5,名候选人的,百米成绩,穷举法,：,组成接力队的方案共有,5!=120,种,。,2024/11/6,目标函数,若选择队员,i,参加泳姿,j,的比赛，记,x,ij,=1,否则记,x,ij,=0,0-1,规划模型,c,ij,(,秒,),队员,i,第,j,种泳姿的百米成绩,约束条件,每人最多入选泳姿之一,c,ij,i,=1,i,=2,i,=3,i,=4,i,=5,j,=1,66.8,57.2,78,70,67.4,j,=2,75.6,66,67.8,74.2,71,j,=3,87,66.4,84.6,69.6,83.8,j,=4,58.6,53,59.4,57.2,62.4,每种泳姿有且只有,1,人,0-1,规划,:,整数规划的特例,2024/11/6,整数规划问题一般形式,整数线性规划,(ILP),目标和约束均为线性函数,整数非线性规划,(NLP),目标或约束中存在非线性函数,整数规划问题的分类,纯,(,全,),整数规划,(PIP),决策变量均为整数,混合整数规划,(MIP),决策变量有整数，也有实数,0-1,规划,决策变量只取,0,或,1,2024/11/6,取消整数规划中决策变量为整数的限制（,松弛,），对应的连续优化问题称为原问题的,松弛问题,整数规划问题对应的松弛问题,松弛问题,松弛,整数规划问题,最优解,最优解,整数,非整数,整数,舍入,非最优解,2024/11/6,x,1,x,2,0,P,o,6,9,Z,max,5,6,去掉整数限制后，可行域为点（,0,0),(6,0),(0,5),P(2.25,3.75),围成的,4,边形,从,LP,最优解经过简单的“移动”不一定能得到,IP,最优解,例,1.6,2024/11/6,无约束优化,更多的优化问题,线性规划,非线性规划,网络优化,组合优化,整数规划,不确定规划,多目标规划,目标规划,动态规划,连续优化,离散优化,从其他角度分类,应用广泛：,生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等,实际问题规模往往较大，用软件求解比较方便,2024/11/6,建模时需要注意的几个基本问题,1,、,尽量使用实数优化，减少整数约束和整数变量,2,、,尽量使用光滑优化，减少非光滑约束的个数,如：尽量少使用绝对值、符号函数、多个变量求最大,/,最小值、四舍五入、取整函数等,3,、,尽量使用线性模型，减少非线性约束和非线性变量的个数 （如,x/y,5,改为,x,5,y,）,4,、,合理设定变量上下界，尽可能给出变量初始值,5,、,模型中使用的参数数量级要适当,(,如小于,10,3,),2024/11/6,课后作业,统计数据,广告媒体,效果,报纸,电台,电视,每个广告影响的总人数,影响的已婚人数,影响平均收入以上的人数,最低广告数量限制（个）,最高广告数量限制（个）,每个广告的成本（万元）,50000,15000,20000,25,100,3,100000,20000,30000,30,150,1.5,150000,40000,50000,20,50,15,例,1,一家连琐店公司正在计划明年的广告预算，该公司计划用,1000,万元在报纸、广播和电视上做广告。下表是他们做规划用的统计数据：,2024/11/6,该公司的目标是使广告影响的人数最多，并且满足下面的条件：,至少要影响,500,万人口；,至少要影响,100,万已结婚的人口；,至少要影响,150,万收入在平均收入以上的人口；,在每种媒介上所做的广告要在最高和最低限制数之间。,统计数据,广告媒体,效果,报纸,电台,电视,每个广告影响的总人数,影响的已婚人数,影响平均收入以上的人数,最低广告数量限制（个）,最高广告数量限制（个）,每个广告的成本（万元）,50000,15000,20000,25,100,3,100000,20000,30000,30,150,1.5,150000,40000,50000,20,50,15,2024/11/6,例,2,有两个煤厂,A,B,，每月分别进煤不小于,60t,，,100t,，它们负担供应三个居民区用煤任务，这三个居民区每月需用煤分别是,45t,75t,和,40t,，,A,厂到这三个居民区单位运费分别是,10,千元,/,吨,5,千元,/,吨，,6,千元,/,吨，,B,厂到这三个居民区单位运费分别是,4,千元,/,吨,8,千元,/,吨,15,千元,/,吨,问这两个煤厂如何分配供煤，才使总运费最少？请写出相应的数学模型。,例,3,用长度为,500cm,的条材，截成长度分别为,98cm,和,78cm,二种毛坯，要求共截出长,98cm,的毛坯,10000,根，,78cm,的,20000,根，问怎样截法，才使所用的原料最小？写出相应的数学模型。,2024/11/6,例,4,某房地产开发商准备在两片开发区上分别圈出一块长方形土地，并砌围墙将这两块土地分别围起来，每块土地的面积不得小于,1000,平米，围墙的高度不能低于,2,米。能够用于砌墙的每块砖是一样的，每块砖的高度为,10c