优化问题及其数学模型.ppt
2023/6/15,第一讲优化问题及其数学模型,原书相关信息谢金星,薛毅编著,清华大学出版社,2005年7月第1版.http:/,内容提要,1.优化模型的基本概念2.优化问题的建模实例,2023/6/15,最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如:,优化模型和算法的重要意义,结构设计,资源分配,生产计划,运输方案,解决优化问题的手段,经验积累，主观判断,作试验，比优劣,建立数学模型，求解最优策略,最优化:在一定条件下，寻求使目标最大(小)的决策,1.优化模型的基本概念,2023/6/15,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式,无约束优化(没有约束)与约束优化(有约束)可行解（只满足约束）与最优解(取到最优值),2023/6/15,局部最优解与整体最优解,局部最优解(Local Optimal Solution,如 x1)整体最优解(Global Optimal Solution,如 x2),2023/6/15,优化模型的简单分类,线性规划(LP)目标和约束均为线性函数 非线性规划(NLP)目标或约束中存在非线性函数二次规划(QP)目标为二次函数、约束为线性 整数规划(IP)决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划,连续优化,离散优化,数学规划,2023/6/15,优化模型的简单分类和求解难度,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,问题求解的难度增加,2023/6/15,2.优化问题的建模实例,2023/6/15,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,线性规划模型例1.1:奶制品生产计划,2023/6/15,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,2023/6/15,模型求解,图解法,约束条件,目标函数,z=c(常数)等值线,在B(20,30)点得到最优解,LP的通常解法是单纯形法(G.B.Dantzig,1947),2023/6/15,线性规划模型的解的几种情况,2023/6/15,某厂生产两个牌号的同一种产品，如何确定产量使利润最大,二次规划模型例1.2：产销计划问题,2023/6/15,假设C,假设F,求甲、乙产量，使总利润最大？,2023/6/15,=（100-x1-0.1 x2-2）x1+（280-0.2x1-2x2-3）x2=98 x1+277 x2 x12 0.3 x1 x2 2x22,约束,x1+x2 100 x1 2 x2x1,x2 0,二次规划模型(QP),若还要求产量为整数，则是整数二次规划模型(IQP),2023/6/15,非线性规划模型例1.3：选址问题,某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）,假设：料场和工地之间有直线道路,2023/6/15,用例中数据计算，最优解为,总吨公里数为136.2,线性规划模型（LP）,决策变量：ci j(料场j到工地i的运量）12维,2023/6/15,选址问题：NLP,2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。,决策变量：ci j，(xj,yj)16维,非线性规划模型(NLP),2023/6/15,整数规划-例1.4:聘用方案,决策变量：周一至周日每天(新)聘用人数 x1,x2,x7,目标函数：7天(新)聘用人数之和,约束条件：周一至周日每天需要人数,2023/6/15,连续工作5天,设系统已进入稳态（不是开始的几周）,聘用方案,整数规划模型(IP),2023/6/15,丁的蛙泳成绩退步到115”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？,如何选拔队员组成4100米混合泳接力队?,0-1规划 混合泳接力队的选拔,例1.5：5名候选人的百米成绩,穷举法：组成接力队的方案共有5!=120种。,2023/6/15,目标函数,若选择队员i参加泳姿j 的比赛，记xij=1,否则记xij=0,0-1规划模型,cij(秒)队员i 第j 种泳姿的百米成绩,约束条件,每人最多入选泳姿之一,每种泳姿有且只有1人,0-1规划:整数规划的特例,2023/6/15,整数规划问题一般形式,整数线性规划(ILP)目标和约束均为线性函数 整数非线性规划(NLP)目标或约束中存在非线性函数,整数规划问题的分类,纯(全)整数规划(PIP)决策变量均为整数 混合整数规划(MIP)决策变量有整数，也有实数,0-1规划 决策变量只取0或1,2023/6/15,取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题,整数规划问题对应的松弛问题,2023/6/15,去掉整数限制后，可行域为点（0,0),(6,0),(0,5),P(2.25,3.75)围成的4边形,从LP最优解经过简单的“移动”不一定能得到IP最优解,例1.6,2023/6/15,无约束优化,更多的优化问题,线性规划,非线性规划,网络优化,组合优化,整数规划,不确定规划,多目标规划,目标规划,动态规划,连续优化,离散优化,从其他角度分类,应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等 实际问题规模往往较大，用软件求解比较方便,2023/6/15,建模时需要注意的几个基本问题,1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y 5 改为x5y）4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当(如小于103),2023/6/15,课后作业,例 1 一家连琐店公司正在计划明年的广告预算，该公司计划用1000万元在报纸、广播和电视上做广告。下表是他们做规划用的统计数据：,2023/6/15,该公司的目标是使广告影响的人数最多，并且满足下面的条件：至少要影响 500 万人口；至少要影响 100 万已结婚的人口；至少要影响 150 万收入在平均收入以上的人口；在每种媒介上所做的广告要在最高和最低限制数之间。,2023/6/15,例 2 有两个煤厂A,B，每月分别进煤不小于60t，100t，它们负担供应三个居民区用煤任务，这三个居民区每月需用煤分别是45t,75t和40t，A厂到这三个居民区单位运费分别是10千元/吨,5千元/吨，6千元/吨，B厂到这三个居民区单位运费分别是4千元/吨,8千元/吨,15千元/吨,问这两个煤厂如何分配供煤，才使总运费最少？请写出相应的数学模型。,例 3 用长度为500cm的条材，截成长度分别为98cm和78cm二种毛坯，要求共截出长98cm的毛坯10000根，78cm的20000根，问怎样截法，才使所用的原料最小？写出相应的数学模型。,2023/6/15,例 4 某房地产开发商准备在两片开发区上分别圈出一块长方形土地，并砌围墙将这两块土地分别围起来，每块土地的面积不得小于1000平米，围墙的高度不能低于2米。能够用于砌墙的每块砖是一样的，每块砖的高度为10cm，长度为30cm，宽度为15cm（假设砖的宽度就是围墙的宽度）。该开发商希望用10万块砖，使圈出的两块土地的面积之和最大，问应如何圈地？,2023/6/15,例 5某厂生产三种产品I，II，III。每种产品要经过两道工序加工。设该厂有两种规格的设备能完成工序，它们以表示；有三种规格的设备能完成工序，它们以表示。产品I可在任何一种规格设备上加工。产品II可在任何规格的设备上加工，但完成工序时，只能在设备上加工；产品III只能在与设备上加工。已知在各种机床设备的单件工时，原材料费，产品销售价格，各种设备有效台时以及满负荷操作时机床设备的费用如下表，要求安排最优的生产计划，使该厂利润最大。,2023/6/15,2023/6/15,Thats all Thank you!,
