lingo讲解课件优化建模与LINGO第一次上午1章节幻灯片.pptVIP

内点算法(Interior point method) 　20世纪80年代人们提出的一类新的算法——内点算法 　也是迭代法，但不再从可行域的一个顶点转换到另一个顶点，而是直接从可行域的内部逼近最优解。 LP其他算法 有效集(Active Set)方法 LP是QP的特例（只需令所有二次项为零即可） 可以用QP的算法解QP(如: 有效集方法) 线性规划模型的解的几种情况 线性规划问题 有可行解(Feasible) 无可行解（Infeasible） 有最优解（Optimal） 无最优解(Unbounded) 选址问题：NLP 2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij ，在其它条件不变下使总吨公里数最小。 决策变量： ci j，(xj,yj)~16维 非线性规划模型 (NLP) 整数规划 - 例1.4: 聘用方案 决策变量：周一至周日每天(新)聘用人数 x1, x2,?x7 目标函数：7天(新)聘用人数之和 约束条件：周一至周日每天需要人数 丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5, 组成接力队的方案是否应该调整？ 如何选拔队员组成4?100米混合泳接力队? 0-1规划 －混合泳接力队的选拔 ? 甲 乙 丙 丁 戊 蝶泳 1’06”8 57”2 1’18” 1’10” 1’07”4 仰泳 1’15”6 1’06” 1’07”8 1’14”2 1’11” 蛙泳 1’27” 1’06”4 1’24”6 1’09”6 1’23”8 自由泳 58”6 53” 59”4 57”2 1’02”4 例1.5： 5名候选人的百米成绩 穷举法：组成接力队的方案共有5!=120种。 目标函数 若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0 0-1规划模型 cij(秒)~队员i 第j 种泳姿的百米成绩 约束条件 每人最多入选泳姿之一 cij 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规划:　 整数规划的特例 整数规划问题一般形式 整数线性规划(ILP) 目标和约束均为线性函数 整数非线性规划(NLP) 目标或约束中存在非线性函数 整数规划问题的分类 纯(全)整数规划(PIP) 决策变量均为整数 混合整数规划(MIP) 决策变量有整数，也有实数 0-1规划 决策变量只取0或1 取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题 整数规划问题对应的松弛问题 松弛问题 松弛 整数规划问题 最优解 最优解 整数 非整数 整数 舍入 下界（对Min问题） 上界（对Max问题） 非最优解 用连续优化方法求解松弛问题，如果松弛问题最优解（分量）全为整数，则也是原整数规划问题的最优解 对松弛问题的最优解（分量）舍入为整数，得到的往往不是原整数规划问题的最优解（甚至不是可行解） IP可行解对应于整点A(2,2)和B(1,1),而最优解为A点. 但LP松弛的最优解为C(3.5,2.5) 目标函数下降方向 x1 x2 C A B O ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． x1 x2 0 P o 6 9 Zmax 5 6 去掉整数限制后，可行域为点（0,0), (6,0), (0,5), P (2.25,3.75) 围成的4边形 从LP最优解经过简单的 “移动”不一定能得到IP最优解 例1.6 基本思想：隐式地枚举一切可行解（“分而治之”） 所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分枝（或称子域），要计算原问题的最优解的下界（对极小化问题）. 这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举. 分枝定界法（BB: Branch and Bound） 无约束优化 更多的优化问题 线性规划 非线性规划 网络优化 组合优化 整数规划 不确定规划 多目标规划 目标规划 动态规划 连续优化 离散优化 从其他角度分类 应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等 实际问题规模往往较大，用软件求解比较方便 常用优化软件 1. LINDO/LINGO软件 2. MATL