优化类数学模型课件.ppt

优化类数学模型优化类数学模型线性规划模型线性规划模型 非线性规划模型非线性规划模型 整数规划模型整数规划模型C语言程序设计语言程序设计（第三版）（第三版）http:/ 21 1 最优化问题最优化问题11 最优化问题概念（1）最优化问题 在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。最优化问题的目的有两个：求出满足一定条件下，函数的极值或最大值最小值；求出取得极值时变量的取值。最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。C语言程序设计语言程序设计（第三版）（第三版）http:/ 3（2 2）变量）变量 变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。设问题中涉及的变量为x1,x2.xn；我们常常也用X=(x1,x2.xn)表示。C语言程序设计语言程序设计（第三版）（第三版）http:/ 4（3 3）约束条件）约束条件 在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设计问题时，变量必须服从电路基本定律，这也是一种限制等等。在研究问题时，这些限制我们必须用数学表达式准确地描述它们。用数学语言描述约束条件一般来说有两种：等式约束条件 不等式约束条件 注：在最优化问题研究中，由于解的存在性十分复杂，一般来说，我们不考虑不等式约束条件。这两种约束条件最优化问题最优解的存在性较复杂。C语言程序设计语言程序设计（第三版）（第三版）http:/ 5（4 4）目标函数）目标函数 在最优化问题中，与变量有关的待求其极值（或最大值最小值）的函数称为目标函数。目标函数常用表示F(x)=f(x1,x2.xn)表示。当目标函数为某问题的效益函数时，问题即为求极大值；当目标函数为某问题的费用函数时，问题即为求极小值等等。求极大值和极小值问题实际上没有原则上的区别，因为求的极小值，也就是要求的极大值，两者的最优值在同一点取到。C语言程序设计语言程序设计（第三版）（第三版）http:/ 61 1 1 12 2 2 2 最优化问题分类最优化问题分类最优化问题分类最优化问题分类 最优化问题种类繁多，因而分类的方法也有许多。可以按变量的性质分类，按有无约束条件分类，按目标函数的个数分类等等。一般来说，变量可以分为确定性变量，随机变量和系统变量等等，相对应的最优化问题分别称为：普通最优化问题，统计最优化问题和系统最优化问题。(1)按有无约束条件分类：无约束最优化问题，有约束最优化问题。(2)按目标函数的个数分类：单目标最优化问题，多目标最优化问题。(3)按约束条件和目标函数是否是线性函数分类：线性最优化问题（线性规划），非线性最优化问题（非线性规划）。(4)按约束条件和目标函数是否是时间的函数分类：静态最优化问题和动态最优化问题（动态规划）。C语言程序设计语言程序设计（第三版）（第三版）http:/ 73 3 3 3 最优化问题的求解步骤和数学模型最优化问题的求解步骤和数学模型最优化问题的求解步骤和数学模型最优化问题的求解步骤和数学模型（1）最优化问题的求解步骤 最优化问题的求解涉及到应用数学，计算机科学以及各专业领域等等，是一个十分复杂的问题，然而它却是需要我们重点关心的问题之一。怎样研究分析求解这类问题呢？其中最关键的是建立数学模型和求解数学模型。一般来说，应用最优化方法解决实际问题可分为四个步骤进行：C语言程序设计语言程序设计（第三版）（第三版）http:/ 8 求解步骤求解步骤步骤1：建立模型提出最优化问题，变量是什么？约束条件有那些？目标函数是什么？建立最优化问题数学模型：确定变量，建立目标函数，列出约束条件建立模型。步骤2：确定求解方法分析模型，根据数学模型的性质，选择优化求解方法确定求解方法。步骤3：计算机求解编程序（或使用数学计算软件），应用计算机求最优解计算机求解。步骤4：结果分析对算法的可行性、收敛性、通用性、时效性、稳定性、灵敏性和误差等等作出评价结果分析。线性规划（线性规划（Linear Programming）运筹学的一个分支，主要用于生产计划、物资运输、运筹学的一个分支，主要用于生产计划、物资运输、库存、劳动力分配以及最优设计问题等。类似于条件极库存、劳动力分配以及最优设计问题等。类似于条件极值问题，只是其目标函数和约束条件都是线性函数。值问题，只是其目标函数和约束条件都是线性函数。线性规划模型的特点线性规划模型的特点1.1.比例性比例性:每个决策变量对目标函数和每个约束条件右每个决策变量对目标函数和每个约束条件右端项的端项的“贡献贡献”与该变量的取值成比例；与该变量的取值成比例；2.2.可加性可加性:每个决策变量对目标函数和每个约束条件右每个决策变量对目标函数和每个约束条件右端项的端项的“贡献贡献”与其他变量的取值无关；与其他变量的取值无关；3.3.连续性连续性:每个决策变量的取值是连续的。每个决策变量的取值是连续的。线性规划模型的三个要素线性规划模型的三个要素决策变量：决策变量：根据实际问题所选择的可以控制的因素；根据实际问题所选择的可以控制的因素；目标函数：目标函数：以线性函数形式表示所追求的目标；以线性函数形式表示所追求的目标；约束条件：约束条件：决策变量需要满足的限定条件，一般是一组决策变量需要满足的限定条件，一般是一组线性等式或不等式。线性等式或不等式。C语言程序设计语言程序设计（第三版）（第三版）http:/ 10二、线性规划模型的求解二、线性规划模型的求解（一）图解法（一）图解法（n 总需求量总需求量(300)每个水库最大供水量都提高一倍每个水库最大供水量都提高一倍利润利润 =收入收入(900)其它费用其它费用(450)引水管理费引水管理费利润利润(元元/千吨千吨)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/供应供应限制限制B,C 类似处理类似处理问题讨论问题讨论 确定送水方案确定送水方案使利润最大使利润最大需求约束可以不变需求约束可以不变C语言程序设计语言程序设计（第三版）（第三版）http:/ 19求解求解 OBJECTIVE FUNCTION VALUE 1)88700.00 VARIABLE VALUE REDUCED COST X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 40.000000 X14 0.000000 20.000000 X21 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000 这类问题一般称为这类问题一般称为“运输问题运输问题”(Transportation Problem)总利润总利润 88700（元）（元）A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030C语言程序设计语言程序设计（第三版）（第三版）http:/ 20非线性规划模型非线性规划模型，可以，可以用用LINGO求解求解非线性规划（非线性规划（None-linear Programming）例例4 板材切割问题板材切割问题 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出从钢管厂进货时得到的割后售出从钢管厂进货时得到的原料钢管都是原料钢管都是19m长长(1)现有一个客户需要现有一个客户需要50根根4m、20根根6m和和15根根8m长的钢管长的钢管应如何下料最节省应如何下料最节省?(2)零售商如果采用的切割模式太多，将会导致生产过零售商如果采用的切割模式太多，将会导致生产过程的复杂性，从而增加生产和管理成本，所以程的复杂性，从而增加生产和管理成本，所以该零售商该零售商规定采用的不同切割模式不能超过规定采用的不同切割模式不能超过3种种此外，该客户此外，该客户除需要上述的三种钢管外，还需要除需要上述的三种钢管外，还需要10根根5m长长的钢管，的钢管，应如何下料最节省应如何下料最节省?首先，应当确定哪些切割模式是首先，应当确定哪些切割模式是可行可行的，所谓一个切割模式，是的，所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合其次，应当指按照客户需要在原料钢管上安排切割的一种组合其次，应当确定哪些切割模式是确定哪些切割模式是合理合理的通常假设一个合理的切割模式的余的通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸料不应该大于或等于客户需要的钢管的最小尺寸在这种合理性在这种合理性假设下，切割模式一共有假设下，切割模式一共有7种，如下表种，如下表LINGO中中 GIN(r);表示变量表示变量r为整数为整数C语言程序设计语言程序设计（第三版）（第三版）http:/ 25第三讲第三讲 整数规划建模方法整数规划建模方法一、从现实问题到整数规划模型一、从现实问题到整数规划模型二、二、整数整数规划模型的求解规划模型的求解三、三、整数整数规划的建模实例规划的建模实例C语言程序设计语言程序设计（第三版）（第三版）http:/ 264.1 4.1 4.1 4.1 整数规划简介整数规划简介整数规划简介整数规划简介要求所有要求所有 x xj j 的解为整数，称为纯整数规划的解为整数，称为纯整数规划要求部分要求部分 x xj j 的解为整数，称为混合整数规划的解为整数，称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的，最优解不一定发生在极点整数规划的解是可数个的，最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解整数规划的最优解不会优于其松弛问题的最优解C语言程序设计语言程序设计（第三版）（第三版）http:/ 274.2 4.2 4.2 4.2 整数规划的整数规划的整数规划的整数规划的分枝定界法分枝定界法分枝定界法分枝定界法3、求解分枝的松弛问题、求解分枝的松弛问题 定界过程定界过程设两个分枝的松弛问题分别为问题设两个分枝的松弛问题分别为问题 1 和问题和问题 2，它们的最优解有如，它们的最优解有如下情况下情况 4.2.1 思路与解题步骤思路与解题步骤只解松弛问题只解松弛问题1、在全部可行性域上解松弛问题、在全部可行性域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最优解若松弛问题最优解为整数解，则其也是整数规划的最优解2、分枝过程分枝过程若松弛问题最优解中某个若松弛问题最优解中某个 xk=bk 不是整数，令不是整数，令 bk 为为 bk 的整数部分的整数部分构造两个新的约束条件构造两个新的约束条件 xk bk 和和 xk bk +1，分别加于原松弛问，分别加于原松弛问题，形成两个新的整数规划题，形成两个新的整数规划C语言程序设计语言程序设计（第三版）（第三版）http:/ 28 4.2.2 4.2.2 4.2.2 4.2.2 分枝定界法举例分枝定界法举例分枝定界法举例分枝定界法举例 例例4.1.1 解解：松弛问题的最优解为：松弛问题的最优解为 x1=2.5,x2=2,OBJ=23 由由 x1=2.5 得到两个分枝如下：得到两个分枝如下：C语言程序设计语言程序设计（第三版）（第三版）http:/ 29 表表表表4.2.3 4.2.3 4.2.3 4.2.3 分枝问题的松弛解分枝问题的松弛解分枝问题的松弛解分枝问题的松弛解问题问题II的解即原整数问题的最优解（的解即原整数问题的最优解（X1=3，X2=1）可能存在两个分枝都是非整数解的情况，则需要两边同时可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程继续分枝，直到有整数解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝即广又深，在最坏情当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解况下相当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题，一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如只有少数特殊问题有好的算法，如任务分配问题任务分配问题、匹配问题匹配问题C语言程序设计语言程序设计（第三版）（第三版）http:/ 30例.某厂拟用集装箱托运甲,乙两种货物。已知货物体积(米3/箱)重量(吨/箱)利润(百元/箱)甲9740乙72090托运限制5670问：如何安排利润最大？设甲乙分别托运设甲乙分别托运x1,x2箱箱模型建立模型建立 IP(1)-(4)称为与(IP)相对应的线性规划(LP)求解(LP)得x1=4.81,x2=1.82,z=356C语言程序设计语言程序设计（第三版）（第三版）http:/ 31分枝定界法(branch and bound method)(IP)x1*,x2*,z*(LP)x1=4.81,x2=1.82,z0=356(LP1)x1=4,x2=2.1,z0=349X14X15(LP2)x1=5,x2=1.57,z0=341(z*349定界定界)(LP3)x1=4,x2=2,z0=340X22X23(LP4)x2=3,x1=1.42,z0=327(z*340 定界定界)(LP5)x2=1,x1=5.44,z0=308X21(LP6)无可行解X22X14X15分枝：分枝：C语言程序设计语言程序设计（第三版）（第三版）http:/ 32设每月生产小、中、大型设每月生产小、中、大型汽车的数量分别为汽车的数量分别为x1,x2,x3汽车厂生产计划汽车厂生产计划 ,任一型号任一型号汽车要生产至少汽车要生产至少8080辆辆模型建立模型建立 小型小型 中型中型 大型大型 现有量现有量钢材钢材 1.5 3 5 600时间时间 280 250 400 60000利润利润 2 3 4 线性线性规划规划模型模型(LP)C语言程序设计语言程序设计（第三版）（第三版）http:/ 33模型模型求解求解 3）模型中增加条件：模型中增加条件：x1,x2,x3 均为整数，重新求解。均为整数，重新求解。OBJECTIVE FUNCTION VALUE 1)632.2581VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 0.731183 3)0.000000 0.003226结果为小数，结果为小数，怎么办？怎么办？1）舍去小数：取）舍去小数：取x1=64，x2=167，算出目标函数值，算出目标函数值z=629，与，与LP最优值最优值632.2581相差不大。相差不大。2）试试探探：如如取取x1=65，x2=167；x1=64，x2=168等等，计计算算函函数数值值z，通过比较可能得到更优的解。，通过比较可能得到更优的解。但必须检验它们是否满足约束条件。为什么？但必须检验它们是否满足约束条件。为什么？C语言程序设计语言程序设计（第三版）（第三版）http:/ 34IP可用可用LINDO直接求解直接求解整数规划整数规划(Integer Programming,简记简记IP)“gin 3”表示表示“前前3个变量为个变量为整数整数”，等价于：，等价于：gin x1gin x2gin x3 IP 的最优解的最优解x1=64，x2=168，x3=0，最优值，最优值z=632 max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3 OBJECTIVE FUNCTION VALUE 1)632.0000VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000 模型求解模型求解 IP 结果输出结果输出整数规划整数规划例例5 最佳组队问题最佳组队问题 有一场由有一场由四个项目四个项目(高低杠、平衡木、跳马、高低杠、平衡木、跳马、自由体操自由体操)组成的女子体操团体赛，赛程规定：每个队至多允组成的女子体操团体赛，赛程规定：每个队至多允许许1010名运动员参赛，每一个项目名运动员参赛，每一个项目可以有可以有6 6名选手参加名选手参加每个选每个选手参赛的成绩评分从高到低依次为：手参赛的成绩评分从高到低依次为：1010至至0 0每个代表队的每个代表队的总总分是参赛选手所得总分之和分是参赛选手所得总分之和，总分最多的代表队为优胜者总分最多的代表队为优胜者此此外，还规定外，还规定每个运动员只能参加全能比赛每个运动员只能参加全能比赛(四项全参加四项全参加)与单项与单项比赛这两类中的一类比赛这两类中的一类，参加，参加单项比赛的每个运动员至多只能参单项比赛的每个运动员至多只能参加三项单项加三项单项每个队每个队应有应有4 4人参加全能比赛人参加全能比赛，其余运动员参加，其余运动员参加单项比赛现某代表队的教练已经对其所带领的单项比赛现某代表队的教练已经对其所带领的1010名运动员参名运动员参加各个项目的成绩进行了大量测试，教练发现每个运动员在每加各个项目的成绩进行了大量测试，教练发现每个运动员在每个单项上的成绩得分期望值如下表所示请建立模型为该队排个单项上的成绩得分期望值如下表所示请建立模型为该队排出一个出场阵容，使该队团体总分尽可能高下表是运动员各出一个出场阵容，使该队团体总分尽可能高下表是运动员各项目得分期望表项目得分期望表LINGO中中 GIN(r);表示变量表示变量r为整数为整数 BIN(r);表示变量表示变量r取值为取值为0或或1iMATLAB中线性规划命令中线性规划命令 linprog 非线性规划命令非线性规划命令 fmincon