数学建模最优化理论课件.ppt
第1页，此课件共31页哦生活何处不优化l最短路径优化l最省时间优化l管理科学优化l工程设计优化l市场调度优化l城市建设优化第2页，此课件共31页哦建模真题之优化问题l1994年全国赛A题：逢山开路l1996年全国赛A题：最优捕鱼策略l2001年全国赛B题：公交车优化调度l2010年东三省A题：企业的营销管理问题l2010年东三省B题：周游全中国据统计，19922005年全国赛28个赛题中有关优化问题有19个，最优化方法是用的最多的方法之一。第3页，此课件共31页哦旅行商问题这个问题称为旅行商问题(Traveling Salesman Problem)，简称TSP。一个商人拟到n个城市去推销商品，已知每两个城市 和 之间的距离为 ，如何选择一条道路，使得商人每个城市走一遍后回到起点，且所走的路径最短。jAijdiA第4页，此课件共31页哦我们应该怎么做？第5页，此课件共31页哦最优化问题概述最优化问题的定义最优化问题的分类解决最优化问题的方法最优化模型的基本要素第6页，此课件共31页哦最优化问题的定义最优化问题的定义 最优化问题就是在给定条件下寻找最佳方案的问题 即在资源给定时寻找最好的目标，或在目标确定时使用最少的资源第7页，此课件共31页哦最优化问题的分类最优化问题的分类动态规划非线性规划目标规划规划整数规划线性规划数学规划10第8页，此课件共31页哦解最优化问题的方法解最优化问题的方法最优化问题的求解方法一般可以分成解析法、直接法、数值计算法和其他方法 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法 第9页，此课件共31页哦最优化模型基本要素最优化模型基本要素决策变量、目标函数和约束条件（1）决策变量是问题中有待确定的未知因素。（2）目标函数是指对问题所追求的目标的数学描述。（3）约束条件是指实现问题目标的限制因素。第10页，此课件共31页哦旅行商问题问题类别：0-1规划问题也是动态规划问题决策变量：目标函数：约束条件：变 量10ijxjiijijxdzminjinjixnjxnixtsijniijnjij,2,1,1,0,2,1,1,2,1,1.11第11页，此课件共31页哦距离矩阵D：元素为ijd0003212232111312nnnnndddddddddD 决策矩阵X：元素为ijx假设有n个城市，最短路径的排序为1n，则可以得到这样两个矩阵。000101000010X第12页，此课件共31页哦线性规划模型l线性规划 又称线性最优化,当目标函数和约束条件都是决策变量的线性函数时称为线性规划；否则称为非线性规划。l一般形式;0;0;0:221122222121112121112211nnnnnnnnnnnnbxaxaxabxaxaxabxaxaxaSTxaxaxayMax第13页，此课件共31页哦基金使用优化模型某公司有100万元的资金可供投资（要求全部用完)。该公司有六个可选的投资项目，其各种数据如表12所示。投资项目投资项目风险（风险（%）红利（红利（%）增长率（增长率（%）信用度信用度1 118184 422224 42 26 65 57 710103 310109 912122 24 44 47 78 810105 512126 615154 46 68 88 88 86 6该公司想达到的目标为：投资风险最小，每年红利至少为6.5万元，最低平均增长率为12%，最低平均信用度为7。请设计投资计划。第14页，此课件共31页哦（1 1）决策变量）决策变量 本问题的决策变量是在每种投资项目上的投资 额。设 xi为 项 目 i 的 投 资 额（万 元）（i=1,2,6）（2 2）目标函数）目标函数 本问题的目标为总投资风险最小，即123456Min z0.180.060.100.040.120.08xxxxxx第15页，此课件共31页哦（3 3）约束条件）约束条件本问题共有五个约束条件:各项目投资总和为100万元;每年红利至少为6.5万元;最低平均增长率为12%;最低平均信用度为7;非负约束。第16页，此课件共31页哦于是，可以建立线性规划数学模型：12345612345612345612345Min z=0.180.060.100.040.120.08 1000.040.050.090.070.060.086.5 s.t.0.220.070.120.080.150 xxxxxxxxxxxxxxxxxxxxxxx6123456123456.0812 4 10 2 10 4 6700 0 xxxxxxxxxxxxx，这是个典型的线性规划模型，为了解这个模型，我们可以借助LINGO、MATLAB等软件或者直接用单纯形法来解决。第17页，此课件共31页哦多目标规划模型在多指标的最优化问题背景下所建立起来的数学规划问题即为多目标规划问题。（多目标决策）在实际问题中，可能会同时考虑几个方面都达到最优，比如企业可能会要求产量最高，成本最低，质量最好，利润最大，环境达标，运输满足等。多目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。多目标规划可以按照实际情况分主次，轻重缓急来考虑问题。第18页，此课件共31页哦多目标规划的解法一、将多目标转化为单目标l 优选法l 线形加权法l 平方和加权法l 乘除法l 分层序列法二、直接用数学方法求非劣解第19页，此课件共31页哦pi,2 假定要求 个目标 的最优值，约束条件为 。如果其中一个目标比较关键，如 希望它取极小值，使其他目标满足一定条件，如使 p xfxfxfp,21Rx xf1 xf1minRx iiifxff RxpifxffRii,2,11.优选法优选法（使主要目标优化兼顾其它目标）而把问题转化为单目标规划问题第20页，此课件共31页哦 当 个目标 都要求最小时，可以给每个目标相应的权系数 ，且 ，构成新的目标函数 p xfxfxfp,210i11pii xfxFipii1然后使这个新的目标函数取极小值。这里的权系数大小根据每个目标函数的相对重要性来确定。2.线性加权法线性加权法第21页，此课件共31页哦首先确定各个目标 的希望目标值 ，要求所有的目标值和相应的希望目标值尽可能接近。此时采用下列评价函数：然后求 。xfi*if 21*piiifxfxF xFmin3.平方和加权法平方和加权法第22页，此课件共31页哦式中，为加权系数，可按各目标被重视的程度给出。如果对其中不同的目标重视程度不同，则可采用加权的平方和作为评价函数，即求：21minkiipiiRxfxfxFi第23页，此课件共31页哦4.乘除法乘除法 设有 个目标 。式中，有 个要求极小值，例如设 ，而余下 的要求其极大值，并假定 。这时，采用以下评价函数：p xfxfxfp,21 xfxfxfk,21 xfxfxfpkk,21 0,21xfxfxfpkkk xfxfxfxfxfxfxFpkkk2121作为单目标问题求极小值。第24页，此课件共31页哦5.分层序列法分层序列法 将目标按重要性的次序分成最重要目标、次重要目标，如 。然后按顺序将一个多目标规划问题转化为一系列单目标优化问题来求解。xfxfxfp,21第25页，此课件共31页哦 最后所求出的 为最优解。步骤：主要目标 的最优集合为 ，再在集合内求次重要目标 的最优解，设此时的最优解集合为 ，如此继续进行，直到求出最后一个目标函数的最优解。第一步 第二步 第 步 xf11R1R xf22R 1110minxfxfRx 2221minxfxfRxp pppRxxfxfp1minpx第26页，此课件共31页哦 某公司计划购进一批新卡车，可供选择的卡车有如下4种类型：A1，A2，A3，A4。现考虑6个方案属性：维修期限f1(年)，每100升汽油所跑路程f2(里)，最大载重f3(吨)，价格f4(万元)，可靠性f5，灵敏性f6。这4种型号的卡车分别关于目标属性的指标值fij如下表所示。fijf1f2f3f4f5f6A12.01500455一般高A22.527003.665低一般A32.020004.245高很高A42.21800450很高一般第27页，此课件共31页哦首先对不同度量单位和不同数量级的指标值进行标准化处理。先将定性指标定量化：效益型指标很低低一般高很高13579很高高一般低很低 成本型指标可靠性和灵敏性都属于效益型指标，其打分如下可靠性一般低高很高5379灵敏性高一般很高一般7595第28页，此课件共31页哦按以下公式作无量纲的标准化处理1)(99maxminmaxffffaijij其中：ijiijffffminmaxminmax变换后的指标值矩阵为：第29页，此课件共31页哦aijf1f2f3f4f5f6A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.751001假设权系数向量为评价函数为：925.57)(max*27.40)(925.57)(6.40)(34)(36144613361226111AUUUaAUaAUaAUaAUjjjjjjjjjjjj故最优方案为选购A3型卡车61)(jijjiawAU）（0.31,0.1,0.2,0.2,0.1,0.w 第30页，此课件共31页哦第31页，此课件共31页哦
