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

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