优化建模与lingo第01章

《优化建模与lingo第01章》由会员分享，可在线阅读，更多相关《优化建模与lingo第01章（40页珍藏版）》请在金锄头文库上搜索。

1、 优 化 建 模优化建模与LINDO/LINGO软件第 1 章 引 言原书相关信息 谢金星, 薛毅编著, 清华大学出版社, 2005年7月第1版. http:/ 化 建 模内容提要1. 优化模型的基本概念2. 优化问题的建模实例3. LINDO/LINGO 软件简介优 化 建 模1. 优化模型的基本概念优 化 建 模最优化是工程技术、经济管理、科学研究、社 会生活中经常遇到的问题, 如:优化模型和算法的重要意义结构设计资源分配生产计划运输方案解决优化问题的手段 经验积累，主观判断 作试验，比优劣 建立数学模型，求解最优策略最优化: 在一定条件下，寻求使目标最大(小)的决策 优 化 建 模优化问

2、题三要素：决策变量；目标函数；约束条件约 束 条 件决策变量优化问题的一般形式 无约束优化(没有约束)与约束优化(有约束) 可行解（只满足约束）与最优解(取到最优值)目标函数优 化 建 模 局部最优解与整体最优解 局部最优解 (Local Optimal Solution, 如 x1 ) 整体最优解 (Global Optimal Solution, 如 x2 )x*f(x)x1x2o优 化 建 模 优化模型的 简单分类 线性规划(LP) 目标和约束均为线性函数 非线性规划(NLP) 目标或约束中存在非线性函数 二次规划(QP) 目标为二次函数、约束为线性 整数规划(IP) 决策变量(全部或部

3、分)为整数 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整数）规划连 续 优 化离 散 优 化数学规划优 化 建 模优化模型的简单分类和求解难度 优化线性规划非线性规划二次规划连续优化整数规划 问题求解的难度增加 优 化 建 模2. 优化问题的建模实例 优 化 建 模1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最

4、多是每小时几元? A1的获利增加到 30元/公斤，应否改变生产计划？ 每天：线性规划模型例1.1: 奶制品生产计划 优 化 建 模1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利约束条件非负约束 线性 规划 模型 (LP)时间480小时 至多加工100公斤A1 50桶牛奶 每天优 化 建 模 模型分析与假设 比 例 性 可 加 性 连续性 xi对目标函数的“贡 献”与xi取值成正比 xi对约束条件的“贡 献”与xi取

5、值成正比 xi对目标函数的“贡 献”与xj取值无关 xi对约束条件的“贡 献”与xj取值无关 xi取值连续 A1,A2每公斤的获利是与各 自产量无关的常数每桶牛奶加工出A1,A2的数量和 时间是与各自产量无关的常数A1,A2每公斤的获利是与相 互产量无关的常数每桶牛奶加工出A1,A2的数量和 时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数 线性规划模型优 化 建 模 模型求解 图解法 x1x20ABCDl1l2l3l4l5约 束 条 件目标 函数 Z=0Z=2400Z=3600z=c (常数) 等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数 可行域为直线段围成的凸

6、多边形 目标函数的等值线为直线 最优解一定在凸多边 形的某个顶点取得。 优 化 建 模求解LP的基本思想思路：从可行域的某一顶点开始，只需在有限多个 顶点中一个一个找下去，一定能得到最优解。LP的约束和目标函数均为线性函数2维可行域 线段组成的凸多边形目标函数 等值线为直线最优解 凸多边形的某个顶点n维超平面组成的凸多面体 等值线是超平面 凸多面体的某个顶点LP的通常解法是单纯形法(G. B. Dantzig, 1947)优 化 建 模内点算法(Interior point method) 20世纪80年代人们提出的一类新的算法内点算法 也是迭代法，但不再从可行域的一个顶点转换到另一个 顶点，

7、而是直接从可行域的内部逼近最优解。 LP其他算法有效集(Active Set)方法 LP是QP的特例（只需令所有二次项为零即可） 可以用QP的算法解QP(如: 有效集方法) 优 化 建 模 线性规划模型的解的几种情况 线性规划问题有可行解(Feasible) 无可行解（ Infeasible）有最优解（Optimal ）无最优解 (Unbounded)优 化 建 模假设A产销平衡假设Bp随x (两种牌号)增加而减小，呈线性关系某厂生产两个牌号的同一种产品，如何确定产量使利润最大二次规划模型例1.2：产销计划问题优 化 建 模 目标利润最大= （100-x1-0.1 x2-2）x1+（280-0

8、.2x1-2x2-3）x2 =98 x1 + 277 x2 x12 0.3 x1 x2 2x22 约束x1 + x2 100 x1 2 x2 x1 , x2 0 二次规划模型(QP)若还要求产量为整数，则是整数二次规划模型(IQP)优 化 建 模 非线性规划模型例1.3：选址问题某公司有6个建筑工地，位置坐标为(ai, bi) (单位：公里), 水泥日用量di (单位：吨）假设：料场 和工地之间 有直线道路优 化 建 模用例中数 据计算， 最优解为总吨公里数为总吨公里数为136.2136.2线性规划模型(LP)决策变量：ci j ( 料场j到工地i的 运量）12维优 化 建 模 选址问题：NL

9、P2）改建两个新料场，需要确定新料场位置(xj,yj)和 运量cij ，在其它条件不变下使总吨公里数最小。决策变量： ci j，(xj,yj)16维非线性规划模型(NLP)优 化 建 模整数规划 - 例1.4: 聘用方案决策变量：周一至周日每天(新)聘用人数 x1, x2,x7目标函数：7天(新)聘用人数之和约束条件：周一至周日每天需要人数优 化 建 模连续工作5天周一工作的应是(上)周四至周一聘用的设系统已进入稳态（不是开始的几周）聘用方案整数规划模型(IP)优 化 建 模丁的蛙泳成绩退步到115”2；戊的自由泳成绩进 步到57”5, 组成接力队的方案是否应该调整？如何选拔队员组成4100米

10、混合泳接力队?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例1.5： 5名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。优 化 建 模目标 函数若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0 0-1规划模型 cij(秒)队员i 第j 种泳姿的百米成绩约束 条件每人最多入选泳姿之一 ciji=1i=2i=3i=4i=5 j=166.857.2787067.4 j=27

11、5.66667.874.271 j=38766.484.669.683.8 j=458.65359.457.262.4每种泳姿有且只有1人 0-1规划: 整数规划的特例优 化 建 模整数规划问题 一般形式 整数线性规划(ILP) 目标和约束均为线性函数 整数非线性规划(NLP) 目标或约束中存在非线性函数整数规划问题的分类 纯(全)整数规划(PIP) 决策变量均为整数 混合整数规划(MIP) 决策变量有整数，也有实数 0-1规划 决策变量只取0或1优 化 建 模取消整数规划中决策变量为整数的限制（松弛），对 应的连续优化问题称为原问题的松弛问题整数规划问题对应的松弛问题松弛问题松弛整数规划问题

12、最优解最 优 解整数非整数整数舍入下界（对Min问题） 上界（对Max问题）非最优解优 化 建 模用连续优化方法求解松弛问题，如果松弛问题最优解 （分量）全为整数，则也是原整数规划问题的最优解对松弛问题的最优解（分量）舍入为整数，得到的往 往不是原整数规划问题的最优解（甚至不是可行解）IP可行解对应于整点A(2,2)和B(1,1),而最优解为A点.但LP松弛的最优解为C(3.5,2.5) 目标函数下降方向 x1x2 CA BO优 化 建 模x1x20Po69 Zmax56去掉整数限制后，可行域为点（0,0), (6,0), (0,5), P (2.25,3.75) 围成的4边形从LP最优解经过

13、简单的 “移动”不一定能得到IP最优解例1.6优 化 建 模基本思想：隐式地枚举一切可行解（“分而治之”）所谓分枝，就是逐次对解空间（可行域）进行划分；而 所谓定界，是指对于每个分枝（或称子域），要计算原 问题的最优解的下界（对极小化问题）. 这些下界用来 在求解过程中判定是否需要对目前的分枝进一步划分， 也就是尽可能去掉一些明显的非最优点，避免完全枚举 . 分枝定界法（B&B: Branch and Bound）对于极小化问题，在子域上解LP，其最优值是IP限定在 该子域时的下界；IP任意可行点的函数值是IP的上界。这里仅介绍整数线性规划的分枝定界算法优 化 建 模无 约 束 优 化更多的优

14、化问题线 性 规 划非 线 性 规 划网 络 优 化组 合 优 化整 数 规 划不 确 定 规 划多 目 标 规 划目 标 规 划动 态 规 划连续优化离散优化从其他角度分类 应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论， 以及更加综合、更加复杂的决策问题等 实际问题规模往往较大，用软件求解比较方便优 化 建 模3. LINDO/LINGO软件简介优 化 建 模 常用优化软件 1. LINDO/LINGO软件2. MATLAB优化工具箱 / Mathematic的优化功能3. SAS(统计分析)软件的优化功能4. EXCEL软件的优化功能5. 其他

15、（如CPLEX等）优 化 建 模MATLAB优化工具箱能求解的优化模型优化工具箱3.0 (MATLAB 7.0 R14)连续优化离散优化无约束优化非线性 极小 fminunc非光滑(不可 微)优化 fminsearch非线性 方程(组 )fzero fsolve全局 优化暂缺非线性 最小二乘lsqnonlin lsqcurvefit线性规划 linprog纯0-1规划 bintprog 一般IP(暂缺)非线性规划 fmincon fminimax fgoalattain fseminf上下界约束 fminbnd fmincon lsqnonlin lsqcurvefit约束线性 最小二乘lsqnonneg lsqlin约束优化二次规划 quadprog优 化 建 模LINDO 公司软件产品简要介绍 美国芝加哥(Chicago)大学的Linus Schrage教授于1980 年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.）， 网址：http:/ LINDO: Linear INteractive and Discrete Optimizer (V6.1)LINDO API: LINDO Application Progr