优化建模与LINGO第01章课件.ppt

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

2、优劣 建立数学模型，求解最优策略建立数学模型，求解最优策略最优化最优化:在一定条件下，寻求使目标最大在一定条件下，寻求使目标最大(小小)的决策的决策 优化问题三要素：优化问题三要素：决策变量决策变量；目标函数目标函数；约束条件约束条件约约束束条条件件决策变量决策变量优化问题的一般形式优化问题的一般形式njiDxljxgmixhtsxf,.,1,0)(,.,1,0)(.)(min 无约束优化无约束优化(没有约束没有约束)与约束优化与约束优化(有约束有约束)可行解（只满足约束）与最优解可行解（只满足约束）与最优解(取到最优值取到最优值)目标函数目标函数局部最优解与整体最优解局部最优解与整体最优解

3、局部最优解局部最优解(Local Optimal Solution,如如 x1)整体最优解整体最优解(Global Optimal Solution,如如 x2)x*f(x)x1x2o优化模型的优化模型的简单分类简单分类 线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数 非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数 二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性 整数规划整数规划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数 整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(

4、INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)一般整数规划，一般整数规划，0-1（整数）规划（整数）规划njiDxljxgmixhtsxf,.,1,0)(,.,1,0)(.)(min连连续续优优化化离离散散优优化化数学规划数学规划优化模型的简单分类和求解难度优化模型的简单分类和求解难度 优化线性规划非线性规划二次规划连续优化整数规划 问题求解的难度增加 2.优化问题的建模实例优化问题的建模实例 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订

5、生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到 30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：线性规划模型例线性规划模型例1.1:奶制品生产计划奶制品生产计划 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 获利获利 243x1 获利获利 164 x2 原料供

6、应原料供应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 216472xxzMax每天获利每天获利约束条件约束条件非负约束非负约束 0,21xx线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型分析与假设模型分析与假设 比比例例性性 可可加加性性 连续性连续性 xi对目标函数的对目标函数的“贡献贡献”与与xi取值取值成正比成正比 xi对约束条件的对约束条件的“贡献贡献”与与xi取值取值成正比成正比 xi对目标函数的对目标函数的“贡献贡献”与与xj取值

7、取值无关无关 xi对约束条件的对约束条件的“贡献贡献”与与xj取值取值无关无关 xi取值连续取值连续 A1,A2每公斤的获利是与各每公斤的获利是与各自产量无关的常数自产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和的数量和时间是与各自产量无关的常数时间是与各自产量无关的常数A1,A2每公斤的获利是与相每公斤的获利是与相互产量无关的常数互产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和的数量和时间是与相互产量无关的常数时间是与相互产量无关的常数加工加工A1,A2的牛奶桶数是实数的牛奶桶数是实数 线性规划模型线性规划模型模型求解模型求解 图解法图解法 x1x20ABCDl1

8、l2l3l4l55021 xx48081221 xx10031x0,21xx约约束束条条件件50:211 xxl480812:212 xxl1003:13xl0:,0:2514xlxl216472xxzMax目标目标函数函数 Z=0Z=2400Z=3600z=c(常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形 目标函数的等值线为直线目标函数的等值线为直线 最优解一定在凸多边最优解一定在凸多边形的某个顶点取得。形的某个顶点取得。求解求解LP的基本思想的基本思想思

9、路：从可行域的某一顶点开始，只需在有限多个思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到顶点中一个一个找下去，一定能得到最优解最优解。LP的约束和目标函数均为线性函数的约束和目标函数均为线性函数2维维可行域可行域 线段组成的凸多边形线段组成的凸多边形目标函数目标函数 等值线为直线等值线为直线最优解最优解 凸多边形的某个顶点凸多边形的某个顶点n维维超平面组成的凸多面体超平面组成的凸多面体等值线是超平面等值线是超平面凸多面体的某个顶点凸多面体的某个顶点LPLP的通常解法是单纯形法的通常解法是单纯形法(G.B.Dantzig,1947)(G.B.Dantzig,1947

10、)内点算法内点算法(Interior point method)20世纪世纪80年代人们提出的一类新的算法年代人们提出的一类新的算法内点算法内点算法也是迭代法，但不再从可行域的一个顶点转换到另一个也是迭代法，但不再从可行域的一个顶点转换到另一个顶点，而是直接从可行域的内部逼近最优解。顶点，而是直接从可行域的内部逼近最优解。LPLP其他算法其他算法有效集有效集(Active Set)方法方法 LP是是QP的特例（只需令所有二次项为零即可）的特例（只需令所有二次项为零即可）可以用可以用QP的算法解的算法解QP(如如:有效集方法有效集方法)线性规划模型的解的几种情况线性规划模型的解的几种情况 线性规

11、划问题线性规划问题有可行解有可行解(Feasible)无可行解无可行解（Infeasible）有最优解（有最优解（Optimal）无最优解无最优解(Unbounded)牌牌号号产量成本价格甲甲x1q1p1乙乙x2q2p2假设假设A产销平衡产销平衡假设假设Bp随随x(两种牌号两种牌号)增加而减小，呈线性关系增加而减小，呈线性关系12111211121211111,0,aaaabxaxabp某厂生产两个牌号的同一种产品，如何确定产量使利润最大某厂生产两个牌号的同一种产品，如何确定产量使利润最大21222221222212122,0,aaaabxaxabp二次规划模型例二次规划模型例1.21.2：产

12、销计划问题：产销计划问题22211121,)()(),(max21xqpxqpxxzxx目标目标利润最大利润最大=（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)非线性规划模型例非线性规划模型例1.31.3：选址问题：选址问题某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai,bi)(单位：公里单位：公里

13、),水泥日用量水泥日用量di(单位：吨）单位：吨）ia1.258.750.55.7537.25b1.250.754.7556.57.75d35476111)现有 2 料场，位于 A(5,1),B(2,7),记(xj,yj),j=1,2,日储量 ej各有 20 吨。假设：假设：料场料场和工地之间和工地之间有直线道路有直线道路目标：制定每天的供应计划，即从 A,B 两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。用例中数据计算，最优解为i1234561ic（料料场场 A）3507012ic（料料场场 B）00406102,1,6,.,1,.)()(min612121612/122jecidc

14、tsbyaxcjijiiijjjiijijij线性规划模型线性规划模型(LP)决策变量：决策变量：ci j(料场料场j到到工地工地i的的运量）运量）12维维选址问题：选址问题：NLPNLP2）改建两个新料场，需要确定新料场位置）改建两个新料场，需要确定新料场位置(xj,yj)和和运量运量cij，在其它条件不变下使总吨公里数最小。，在其它条件不变下使总吨公里数最小。2,1,6,.,1,.)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij决策变量：决策变量：ci j，(xj,yj)16维维非线性规划模型非线性规划模型(NLP)整数规划整数规划 -例例

15、1.4:1.4:聘用方案聘用方案某 服 务 部 门 一 周 中 每 天 需 要 不 同 数 目 的 雇员：周 一 到 周 四 每 天 至 少 50 人，周 五 和 周 日每 天 至 少 80 人，周 六 至 少 90 人。决策变量决策变量：周一至周日每天：周一至周日每天(新新)聘用人数聘用人数 x1,x2,x7目标函数目标函数：7天天(新新)聘用人数之和聘用人数之和约束条件约束条件：周一至周日每天需要人数：周一至周日每天需要人数现 规 定 应 聘 者 需 连 续 工 作5 天，试 确 定 聘 用方 案，即 周 一 到 周 日 每 天 聘 用 多 少 人，使 在满 足 需 要 的 条 件 下 聘

16、 用 总 人 数 最 少。80908050505050.min765436543254321743217632176521765417654321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxz连续工作连续工作5天天5017654xxxxx周一工作的应是周一工作的应是(上上)周四至周一聘用的周四至周一聘用的设系统已进入稳态（不是开始的几周）设系统已进入稳态（不是开始的几周）聘用方案聘用方案即为非负整数，Zxi整数规划整数规划模型模型(IP)(IP)丁的蛙泳成绩退步到丁的蛙泳成绩退步到115”2；戊的自由泳成绩进；戊的自由泳成绩进步到步到57”5,组成接

17、力队的方案是否应该调整组成接力队的方案是否应该调整？如何选拔队员组成如何选拔队员组成4 4 100100米混合泳接力队米混合泳接力队?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

18、 的比赛，记的比赛，记xij=1,否则记否则记xij=0 0-1规划模型规划模型 cij(秒秒)队员队员i 第第j 种泳姿的百米成绩种泳姿的百米成绩约束约束条件条件每人最多入选泳姿之一每人最多入选泳姿之一 ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.44151jiijijxcZMin每种泳姿有且只有每种泳姿有且只有1 1人人 5,1,141ixjij4,1,151jxiij0-1规划规划:整数规划的特例整数规划的特例整数规划问题整数规划问题一般形

19、式一般形式ljxgmixhtsxfjiZxn,.,1,0)(,.,1,0)(.)(min 整数线性规划整数线性规划(ILP)目标和约束均为线性函数目标和约束均为线性函数 整数非线性规划整数非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数整数规划问题的分类整数规划问题的分类 纯纯(全全)整数规划整数规划(PIP)决策变量均为整数决策变量均为整数 混合整数规划混合整数规划(MIP)决策变量有整数，也有实数决策变量有整数，也有实数 0-1规划规划 决策变量只取决策变量只取0或或1取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题整数规划问题对应

20、的松弛问题整数规划问题对应的松弛问题松弛问题松弛整数规划问题最优解最优解整数非整数整数舍入下界（对Min问题）上界（对Max问题）非最优解用连续优化方法求解松弛问题，如果松弛问题最优解（分量）全为整数，则也是原整数规划问题的最优解对松弛问题的最优解（分量）舍入为整数，得到的往往不是原整数规划问题的最优解（甚至不是可行解）IPIP可行解对应于整点可行解对应于整点A(2,2)A(2,2)和和B(1,1),B(1,1),而最优解为而最优解为A A点点.但但LPLP松弛的最优解为松弛的最优解为C(3.5,2.5)C(3.5,2.5)目标函数下降方向目标函数下降方向 x1 1x2 2CABO且为整数0,

21、45956.85max21212121xxxxxxtsxxzx1x20Po69Zmax56去掉整数限制后，可行域为点（0,0),(6,0),(0,5),P(2.25,3.75)围成的4边形LP最优解PP的舍入解最靠近P的可行解IP最优解（2.25，3.75）（2，4）（2，3）（0，5）z=41.25不可行z=34z=40从LP最优解经过简单的“移动”不一定能得到IP最优解例例1.6基本思想：基本思想：隐式地枚举一切可行解（隐式地枚举一切可行解（“分而治之”）所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分枝（或称子域），

22、要计算原所谓定界，是指对于每个分枝（或称子域），要计算原问题的最优解的下界（对极小化问题）问题的最优解的下界（对极小化问题）.这些下界用来这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分，在求解过程中判定是否需要对目前的分枝进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举也就是尽可能去掉一些明显的非最优点，避免完全枚举.分枝定界法（分枝定界法（B&B:Branch and Bound）对于极小化极小化问题，在子域上解LP，其最优值是IP限定在该子域时的下界；IP任意可行点的函数值是IP的上界。这里仅介绍整数线性规划的分枝定界算法这里仅介绍整数线性规划的分枝定界算法无无约约

23、束束优优化化更多的优化问题更多的优化问题线线性性规规划划非非线线性性规规划划网网络络优优化化组组合合优优化化整整数数规规划划不不确确定定规规划划多多目目标标规规划划目目标标规规划划动动态态规规划划连续优化连续优化离散优化离散优化从其他角度分类从其他角度分类 应用广泛：应用广泛：生产和运作管理、经济与金融、图论和网生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等以及更加综合、更加复杂的决策问题等 实际问题规模往往较大，用软件求解比较方便实际问题规模往往较大，用软件求解比较方便3.LI

24、NDO/LINGO软件简介软件简介常用优化软件常用优化软件 1.LINDO/LINGO软件软件2.MATLAB优化工具箱优化工具箱/Mathematic的优化功能的优化功能3.SAS(统计分析统计分析)软件的优化功能软件的优化功能4.EXCEL软件的优化功能软件的优化功能5.其他（如其他（如CPLEX等）等）MATLABMATLAB优化工具箱优化工具箱能求解的优化模型能求解的优化模型优化工具箱优化工具箱3.0(MATLAB 7.0 R14)连续优化连续优化离散优化离散优化无约束优化无约束优化非线性非线性极小极小fminunc非光滑非光滑(不可不可微微)优化优化fminsearch非线性非线性方

25、程方程(组组)fzerofsolve全局全局优化优化暂缺暂缺非线性非线性最小二乘最小二乘lsqnonlinlsqcurvefit线性规划线性规划linprog纯纯0-1规划规划 bintprog一般一般IP(暂缺暂缺)非线性规划非线性规划fminconfminimaxfgoalattainfseminf上下界约束上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性约束线性最小二乘最小二乘lsqnonneglsqlin约束优化约束优化二次规划二次规划quadprogLINDO LINDO 公司软件产品简要介绍公司软件产品简要介绍 美国芝加哥美国芝加哥(Chica

26、go)大学的大学的Linus Schrage教授于教授于1980年前后开发年前后开发,后来成立后来成立 LINDO系统公司（系统公司（LINDO Systems Inc.），），网址：网址：http:/ LINDO:Linear INteractive and Discrete Optimizer (V6.1)LINDO API:LINDO Application Programming Interface(V4.1)LINGO:Linear INteractive General Optimizer (V10.0)Whats Best!:(SpreadSheet e.g.EXCEL)(V8.

27、0)演示演示(试用试用)版、高级版、超级版、工业版、扩展版版、高级版、超级版、工业版、扩展版（求解（求解问题规模问题规模和和选件选件不同）不同）LINDO/LINGO软件能求解的模型软件能求解的模型优化优化线性规划线性规划非线性规划非线性规划二次规划二次规划连续优化连续优化整数规划整数规划 LINDOLINGOLINGO软件的功能与特点软件的功能与特点LINGO模型的优点模型的优点 集成了线性集成了线性(非线性非线性)/连续连续(整数整数)优化功能优化功能 具有多点搜索具有多点搜索/全局优化功能全局优化功能 提供了灵活的编程语言提供了灵活的编程语言(矩阵生成器矩阵生成器)，可方便地，可方便地输

28、入模型输入模型 提供与其他数据文件的接口提供与其他数据文件的接口 提供与其他编程语言的接口提供与其他编程语言的接口 LINDO API 可用于自主开发可用于自主开发 运行速度较快运行速度较快 LP QP NLP IP 全局优化全局优化(选选)ILP IQP INLP LINGOLINGO软件的求解过程软件的求解过程 LINGO预处理程序预处理程序线性优化求解程序线性优化求解程序非线性优化求解程序非线性优化求解程序分枝定界管理程序分枝定界管理程序1.确定常数确定常数2.识别类型识别类型1.单纯形算法单纯形算法2.内点算法内点算法(选选)1、顺序线性规划法、顺序线性规划法(SLP)2、广义既约梯度

29、法、广义既约梯度法(GRG)(选选)3、多点搜索、多点搜索(Multistart)(选选)建模时需要注意的几个基本问题建模时需要注意的几个基本问题 1、尽量使用实数优化，减少整数约束和整数变量尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求如：尽量少使用绝对值、符号函数、多个变量求最大最大/最小值、四舍五入、取整函数等最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变尽量使用线性模型，减少非线性约束和非线性变量的个数量的个数 （如（如x/y 5 改为改为x5y）4、合理设定变量上下界，尽可能给出变量初始值合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当模型中使用的参数数量级要适当 (如小于如小于103)自己练习，或课上布置自己练习，或课上布置布置作业内容布置作业内容Thank you very much!Thank you very much!