优化模型ppt课件.ppt
优化模型ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望 1.1.引言引言 在工程技术、经济管理、科学研究和日常生活等诸多领域中，人们经常遇到的一类决策问题：在一系列客观或主观限制条件下，寻求所关注的某个或多个指标达到最大（或最小）的决策。例如，生产计划要按照产品工艺流程和顾客需求，制定原料、零件、部件等订购、投产的日程和数量，尽量降低成本使利润最高；运输方案要在满足物资需求和装载条件下安排从各供应点到各需求点的运量和路线，使运输总费用最低。它们的特点就是：在若干可能的方案中寻求某种意义它们的特点就是：在若干可能的方案中寻求某种意义下的最优方案。数学上称为最优化问题下的最优方案。数学上称为最优化问题,而研究处理这而研究处理这种问题的方法叫最优化的方法。种问题的方法叫最优化的方法。优化模型是一类既重要又特殊的数学模型，而优化建模优化模型是一类既重要又特殊的数学模型，而优化建模方法是也一种特殊的数学建模方法。优化模型一般有下方法是也一种特殊的数学建模方法。优化模型一般有下面三个要素：面三个要素：(1)(1)决策变量，决策变量，它通常是该问题要求解的那些未知量。（2）目标函数，）目标函数，通常是该问题要优化（最大或最小）的那个目标的数学表达式，它是决策变量的函数。（3）约束条件，）约束条件，由该问题对决策变量的限制条件给出。优化模型从数学上可表示成如下一般形式：优化模型从数学上可表示成如下一般形式：opt (opt表示最优化(optimize)的意思)s.t.()()如果 均为线性函数，则上述模型称为线性规划线性规划（Linear Programming,简记为LP），否则称为非线性规划非线性规划(NLP)问题求解的难度增加问题求解的难度增加上图是优化模型的简单分类和求解难度上图是优化模型的简单分类和求解难度2.优化模型的基本类型优化模型的基本类型3.13.1线性规划问题几个概念：线性规划问题几个概念：线性规划问题有解线性规划问题有解：指能找出一组满足约束条件的向量，并称这组为问题的可行解。线性规划问题无解：线性规划问题无解：指不存在可行解或最优趋向无限大。可行域：可行域：指全部可行解组成的集合。最优解：最优解：指可行域中使目标函数值达到最优的可行解。3.3.线性规划线性规划 (目标函数和约束条件都是线性函数目标函数和约束条件都是线性函数)3.2 3.2 线性规划模型的解的几种情况线性规划模型的解的几种情况线性规划问题线性规划问题有可行解有可行解无可行解无可行解有最优解有最优解无最优解无最优解3.3 3.3 求解一般方法求解一般方法：(1)(1)图解法：图解法：对于只含2个变量的线性规划问题，可通过在平面上作图的方法求解。步骤如下：在平面上建立直角坐标系；图示约束条件，找出可行域；图示目标函数，即为一直线；将目标函数直线沿着其法线方向向可行解域边界平移，直至与可行解域第一次相切为止，这个切点就为最优点(2)(2)用用EXCELSolver,Matlab,LINDO/LINGOEXCELSolver,Matlab,LINDO/LINGO软件实现软件实现3.43.4线性规划模型的实例线性规划模型的实例例1 家具生产的安排 家具公司生产桌子和椅子，用于生产的劳力共计450个工时，木材共有4立方米,每张桌子要使用15个工时，0.2立方木材售价80元。每张椅子使用10个工时，0.05立方木材售价45元。问为达到最大的收益，应如何安排生产？分析：分析：1.1.求什么？求什么？生产多少桌子？x1 生产多少椅子？x2 2.2.优化什么？优化什么？收益最大 Max f=80 x1+45 x2 3.3.限制条件？限制条件？原料总量 0.2 x1+0.05 x2 4 劳力总数 15 x1+10 x2 450模型：模型：以产值为目标取得最大收益.设：生产桌子 x1张,椅子 x2张,(决策变量)将目标优化为：max f=80 x1+45x2 对决策变量的约束：0.2x1+0.05x24 （）15x1+10 x2 450,（）x1 0,x2 0,模型求解：模型求解：（1）图解法）图解法（用于决策变量是2维）15x1+10 x2=450 x1x20.2x1+0.05x2=4线性规划问题的目标函数(关于不同的目标值是一族平行直线)目标值的大小描述了直线离原点的远近,并且最优解一定在可行解集的某个极点上达到(穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点).（2 2）用）用EXCELSolverEXCELSolver实现实现模型中的数据直接输入EXCEL工作表中。其中决策变量初始的值可以任意给出，它们是可变的，软件最后将给出最优解的值。SUMPRODUCT是EXCEL的一个内置函数，表示两个向量或矩阵对应元素乘积的和。引用工具引用工具规划求解（需要工具规划求解（需要工具加载宏安装）加载宏安装）（3）用）用Matlab实现实现-lp 线性优化函数线性优化函数线性优化问题即目标函数和约束条件均为线性函数的问题。其标准形式为标准形式为：MinMin Sub.to:Ax=b 其中 （通常 ），均为数值矩阵。max f=80 X1+45 X2 sub.to 0.2 X1+0.05 X24 15 X1+10 X2 450 X1 0,X2 0 化为化为 min f=-80 X1-45 X2 sub.to 0.2 X1+0.05 X24 15 X1+10 X2 450 X1 0,X2 0程序如下：程序如下：c=-80,-45;a=0.2,0.05;15,10;b=4,450;vlb=0,0;vub=;x,lam=lplp(c,a,b,vlb,vub)（参数vlb,vub给出变量的上下边界的约束）x=14.0000 24.0000lam=100.0000 4.0000 0 0说明：x x解为最优解解为最优解，lam说明约束条件发挥了作用。（4 4）用）用LINDO/LINGOLINDO/LINGO实现实现我们可以直接在下面的窗口输入LP模型（图（4）1）图（4）1 输入简单的优化模型 输入后，用鼠标单击LINDO软件工具栏中的图标 ，或从菜单中选择SolveSolve(Ctrsl+S)命令，则LINDO开始编译这个模型，编译没错误马上开始求解，求解时会显示如图（4）2所示LINDO求解器运行状态窗口（里面的“Objective”就是最优解，即：2200）。图（4）2 图（图（4）3 这个例子中的LP模型太小了，我们可能还没来得及看清（4）2的界面，最优解就出来了，并马上弹出如图 （4）3的对话框，这个对话框询问你是否需要作灵敏性分析，可以先选择“否N”按钮，这个窗口就回关闭，然后在关闭图（4）2。如果你在屏幕上没有看到求解的结果，那么可以用鼠标选择LINDO的主菜单“Window”,会发现有一个子菜单项“Reports Window”，这就是最终结果的报告窗口。用鼠标选择“WindowReports Window”，就可以查看到窗口的内容（图（4）4）图（图（4 4）44“LP OPTIMUM FOUND AT STEP 2”表示单纯形法在两次迭代后得到最优解。“OBJECTIVE FUNCTION VALUE 1)2200.000”表示最优目标值为2200.000（在LINDO中目标函数所在的行总是被认为是第1行，这就是这里“1）”的含义）。VALUE”给出最优解中各变量的值：X1=14.000000，X2=24.000000 “SLACK OR SURPLUS（松弛或剩余）”给出约束对应的松弛变量的值：第2、3行松弛变量均为0，说明对于最优解来讲，两个约束均取等号，即都是紧约束。“DUAL PRICES”给出对偶价格的值。“NO.ITERATIONS=2”表示用单纯形法进行了两次迭代（旋转）。例例2 2 服务员聘用问题（整数线性规划模型）服务员聘用问题（整数线性规划模型）某服务部门一周中每天需要不同数目的雇员：周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人，现规定应聘者需要连续工作5天，试确定聘用方案，即周一到周日每天聘用多少人，使在满足需要的条件下聘用总人数最少。（通过例2主要想说明用LINDO求解时与例1的不同：一般的整数变量可用命令GIN（general integer的缩写），对整数变量的说明只能放在模型的“END”语句之后，如图例21)图例图例21
