精华内容
下载资源
问答
  • 从哪些方面分析原理的最优化
    千次阅读
    2020-12-07 08:26:08

    从推公式到写代码:代码是联系理论和现实的桥梁,本书通过代码实现*优化算法,将理论与实践相结合,在编程中思考算法的计算过程,并通过代码将算法应用在实际问题中,以达到解决问题的目的。

    本书以理论结合编程开发为原则,使用Python作为开发语言,讲解*优化算法的原理和应用,详细介绍了Python基础、Gurobi优化器、线性规划、整数规划、多目标优化、动态规划、图与网络分析、智能优化算法。对于算法部分的每一种算法都包含原理和编程实践,使读者对*优化算法的认识更加深入。

    本书分为3篇共9章。篇(~3章)是*优化算法与编程基础:章介绍了什么是*优化算法及其在生产和生活中的应用;第2章介绍Python编程基础和Python数据分析库及绘图库;第3章讲解Gurobi优化器的基础和不错特性。第2篇(第4~6章)是数学规划方法:第4章详细讲解线性规划的知识,包括单纯形法、内点法、列生成法、拉格朗日乘子法、对偶问题;第5章讲解整数规划解法的分支定界法和割平面法;第6章讲解多目标优化的概念及基于单纯形法的目标规划法。第3篇(第7~9章)是启发式算法:第7章介绍动态规划算法;第8章讲解图与网络分析,介绍很小生成树、很短路径、网络流、路径规划等问题的建模;第9章讲解了粒子群算法和遗传算法求解各种类型优化算法问题的方法。

    本书内容丰富,实例典型,实用性强,适合各个层次从事*优化算法研究和应用的人员,尤其适合有一定算法基础而没有编程基础的人员阅读。

    苏振裕,厦门大学金融学硕士,现任SHEIN 智慧供应链资深算法工程师。知乎专栏《从推公式到写代码》作者,运筹优化论坛(optimize.fun)的创建人。在大数据、人工智能、运筹优化和供应链方面,具有多年的相关算法研究及应用经验。

    | 篇 最优化算法与编程基础 |

    章 最优化算法概述 2

    1.1 最优化算法简介 3

    1.2 最优化算法的内容 4

    1.2.1 规划论 4

    1.2.2 库存论 5

    1.2.3 图论 6

    1.2.4 排队论 7

    1.2.5 可靠性理论 8

    1.2.6 对策论 8

    1.2.7 决策论 8

    1.2.8 搜索论 9

    1.3 本章小结 9

    第2章 Python编程方法 10

    2.1 开发环境安装 11

    2.2 编程基础:Python语法 17

    2.2.1 基础数据结构与基本运算 18

    2.2.2 关于Python的列表、元组、字典、集合 18

    2.2.3 程序控制语句 21

    2.2.4 函数 21

    2.2.5 类与实例 22

    2.2.6 迭代 23

    2.3 数据分析:NumPy基础 24

    2.3.1 NumPy基础数据结构 24

    2.3.2 NumPy的随机数 26

    2.3.3 NumPy矩阵运算 28

    2.3.4 NumPy线性代数 31

    2.4 Pandas基础 32

    2.4.1 Pandas基础数据结构 32

    2.4.2 Pandas基础统计函数 35

    2.4.3 Pandas基础数据处理 37

    2.4.4 分组统计 39

    2.4.5 apply函数 41

    2.5 Python绘图 42

    2.5.1 常用图形 43

    2.5.2 图形属性 47

    2.5.3 组合图和子图 49

    2.5.4 三维图 51

    2.5.5 动态图 55

    2.6 本章小结 57

    第3章 Gurobi优化器 58

    3.1 Gurobi的数据结构 59

    3.1.1 Multidict 59

    3.1.2 Tuplelist 60

    3.1.3 Tupledict 61

    3.1.4 应用范例 62

    3.2 Gurobi的参数和属性 65

    3.2.1 参数类型 65

    3.2.2 修改参数 75

    3.2.3 修改参数的例子 75

    3.2.4 属性类型 77

    3.2.5 查看修改属性 85

    3.2.6 修改属性的例子 85

    3.3 Gurobi线性化技巧 85

    3.3.1 优选值max 86

    3.3.2 最小值min 88

    3.3.3 绝对值abs 89

    3.3.4 逻辑与and 90

    3.3.5 逻辑或or 90

    3.3.6 指示函数indicator 90

    3.3.7 带固定成本约束 91

    3.3.8 分段线性函数 91

    3.4 Gurobi多目标优化 92

    3.5 callback函数 96

    3.5.1 回调函数callback定义 97

    3.5.2 状态where与值what 97

    3.5.3 callback函数的功能 98

    3.6 本章小结 102

    | 第2篇 数学规划方法 |

    第4章 线性规划 104

    4.1 线性规划的标准型 105

    4.2 单纯形法 105

    4.2.1 单纯形法的原理 106

    4.2.2 单纯形法的过程 106

    4.2.3 单纯形法代码 111

    4.3 单纯形的数学规范型 113

    4.4 内点法 114

    4.4.1 内点法的原理 114

    4.4.2 内点法过程 115

    4.4.3 内点法代码 118

    4.5 列生成法 120

    4.5.1 列生成法的原理 120

    4.5.2 列生成的过程 123

    4.6 对偶问题 126

    4.6.1 对偶问题的形式 127

    4.6.2 对称形式对偶 128

    4.6.3 对偶单纯形 129

    4.6.4 对偶问题的应用 130

    4.7 拉格朗日乘子法 130

    4.7.1 无约束优化 131

    4.7.2 等式约束优化 131

    4.7.3 不等式约束优化 132

    4.7.4 拉格朗日对偶 134

    4.8 本章小结 137

    第5章 整数规划 138

    5.1 快速掌握Gurobi整数规划 139

    5.2 分支定界法 140

    5.3 割平面法 142

    5.4 本章小结 147

    第6章 多目标优化 148

    6.1 多目标优化的一般形式 149

    6.2 Pareto最优解 149

    6.3 多目标优化求解方法 151

    6.4 目标规划法 152

    6.4.1 偏差变量 153

    6.4.2 优先等级和权重系数 153

    6.4.3 目标规划单纯形法 154

    6.4.4 目标规划Gurobi实现 158

    6.5 NSGA-Ⅱ 159

    6.6 本章小结 160

    | 第3篇 启发式算法 |

    第7章 动态规划 162

    7.1 多阶段决策问题 163

    7.2 动态规划的基本概念 164

    7.3 动态规划的最优化原理 165

    7.4 最短路径问题 166

    7.5 使用整数规划解最短路径问题 169

    7.6 背包问题 170

    7.7 本章小结 175

    第8章 图与网络分析 176

    8.1 图的基本概念 177

    8.2 图的矩阵表示 178

    8.3 最小生成树 179

    8.4 最短路径问题 183

    8.5 网络优选流问题 187

    8.6 路径规划 190

    8.7 VRP问题 196

    8.8 本章小结 203

    第9章 智能优化算法 204

    9.1 粒子群算法 205

    9.1.1 粒子群算法原理 205

    9.1.2 粒子群求解无约束优化问题 207

    9.1.3 粒子群求解约束优化问题 211

    9.1.4 粒子群求解旅行商问题 218

    9.2 遗传算法 225

    9.2.1 遗传算法原理 225

    9.2.2 遗传算法的编码方法 227

    9.2.3 遗传算法的选择操作 230

    9.2.4 遗传算法求解无约束优化问题 231

    9.2.5 遗传算法库Geatpy的介绍 233

    9.2.6 使用Geatpy求解约束优化问题 239

    9.2.7 使用Geatpy求解多目标优化问题 241

    9.3 本章小结 242

    更多相关内容
  • Elasticsearch:写入原理谈写入优化

    千次阅读 2021-04-06 00:17:33
    写入优化十三:推荐使用官方客户端 推荐使用官方 Elasticsearch API,因为官方在连接池和保持连接状态方面优化。 高版本 JAVA API 推荐:官方的High-level-Rest API。 其他写入优化 待补充...... 6、写入过程中...

    1、线上实战问题

    问题 1:想要请问一下,我这边需求是每分钟利用 sparksteaming 插入按天的索引150万条数据。一般情况下还好,索引7个分片,1副本,但是偶尔会出现延迟很高的情况。比如:一般情况下1分钟插入150万能正常插入,可能突然就出现了需要5分钟才能插入成功,然后又正常了。很头疼。

    请问这种情况我需要怎么去查看一下是否正常。我已经把副本设置成了0,还把批量插入的参数从 5000 设置成 2 万。我节点是 12 个 16g 的,但是好像还是没有改观。

    问题 2:由于使用了多个分词器的原因造成数据写入慢,请问有什么优化的方法吗?

    问题 3:求问:现在日志 收集链路 kafka-logstash-es,压力测试 logstash输出70M/s,而 Elasticsearch 索引写入一半不到。这边的性能损失可能是什么原因呢?需要怎么调优呢?

    类似问题还有很多、很多......

    2、问题分析

    以上三个问题各有各自特点,但基本都是基于不同的数据源向 Elasticsearch 写入过程中遇到的问题。

    可以简单归结为:Elasticsearch 写入问题或者写入优化问题。Elasticsearch 写入问题涉及写入流程、写入原理及优化策略。

    本文针对如上几点展开讨论。

    3、基于单文档/批量文档写入流程谈写入优化

    单个文档写入对应 Index 请求,批量写入对应 Bulk 请求,Index 和 Bulk 是相同的处理逻辑,请求统一封装到 BulkRequest中。

    流程拆解如下:

    第一:客户端向 Node 1 发送写数据请求。

    注意,此时Node1 便充当协调节点(cooridiniate)的角色。

    第二:节点Node1 使用文档的 _id 确定文档属于分片 0 。请求会被转发到 Node 3,因为分片 0 的主分片目前被分配在 Node 3 上。

    使用文档的 _id 确定文档所属分片的方法是:路由算法。

    路由算法计算公式:

    shard = hash(routing) % number_of_primary_shards
    
    • routing:文档 _id。

    • number_of_primary_shards: 主分片个数。

    • shard: 文档 _id 所属分片号。

    第三:Node 3 在主分片上面执行写入操作。如果写入成功了,它将请求并行转发到 Node 1 和 Node 2 的副本分片上。一旦所有的副本分片都报告成功, Node 3 将向协调节点报告写入成功,协调节点向客户端报告写入成功。

    如上流程拆解后的注意点:

    • 写操作必须在主分片执行成功后,才能复制到相关的副本分片。

    • 主分片写入失败,则整个请求被认为是写失败。

    • 如果有部分副本写失败(前提:主分片写入成功),则整个请求被认为是写成功。

    如果设置了副本,数据会先写入主分片,主分片再同步到副本分片,同步操作会加重磁盘 IO,间接影响写入性能。

    基于以上分析,既然主分片的写入起到写入成败的决定性作用。那么写入前将:副本分片写入前置为0,待写入完成后复原副本,是不是就能提升写入性能了呢?

    是的!

    写入优化一:副本分片写入前置为0,等完成写入后复原副本

    PUT test-0001
    {
      "settings": {
        "number_of_replicas": 0
      }
    }
    

    写入优化二:优先使用系统自动生成 id

    文档的_id 的生成有两种方式,

    • 第一:系统自动生成id。

    • 第二:外部控制自增id。

    但,如果使用外部 id,Elasticsearch 会先尝试读取原来文档的版本号,以判断是否需要更新。

    也就是说,使用外部控制 id 比系统自动生成id要多一次读取磁盘操作。

    所以,非特殊场景推荐使用系统自动生成的 id。

    4、基于 Elasticsearch 写入原理谈写入优化

    Elasticsearch 中的 1 个索引由一个或多个分片组成,每个分片包含多个segment(段),每一个段都是一个倒排索引。如下图所示:

    在 lucene 中,为了实现高索引速度,使用了segment 分段架构存储。一批写入数据保存在一个段中,其中每个段最终落地为磁盘中的单个文件。

    将文档插入 Elasticsearch 时,它们会被写入缓冲区中,然后在刷新时定期从该缓冲区刷新到段中。刷新频率由 refresh_interval 参数控制,默认每1秒刷新一次。

    也就是说,新插入的文档在刷新到段(内存中)之前,是不能被搜索到的。如下图所示:

    刷新的本质是:写入数据由内存 buffer 写入到内存段中,以保证搜索可见。

    来看个例子,加深对 refresh_inteval 的理解,注释部分就是解读。

    PUT test_0001/_doc/1
    {
      "title":"just testing"
    }
    
    # 默认一秒的刷新频率,秒级可见(用户无感知)
    
    GET test_0001/_search
    

    如下设置后,写入后 60s 后才可见。

    DELETE test_0001
    # 设置了60s的刷新频率
    PUT test_0001
    {
      "settings": {
        "index":{
          "refresh_interval":"60s"
        }
      }
    }
     
    PUT test_0001/_doc/1
    {
      "title":"just testing"
    }
    # 60s后才可以被搜索到
    GET test_0001/_search
    

    关于是否需要实时刷新:

    • 如果新插入的数据需要近乎实时的搜索功能,则需要频繁刷新。

    • 如果对最新数据的检索响应没有实时性要求,则应增加刷新间隔,以提高数据写入的效率。

    所以,自然我们想到的优化是:调整刷新频率。

    写入优化三:合理调整刷新频率

    调整方法如下:

    方法1:写入前刷新频率设置为 -1,写入后设置为业务实际需要值(比如:30s)。

    PUT test-008
    {
      "settings": {
        "refresh_interval": -1
      }
    }
    

    方法2:直接设置为业务实际需要值(比如:30s)

    PUT test-008
    {
      "settings": {
        "refresh_interval": "30s"
      }
    }
    

    写入优化四:合理调整堆内存中索引缓冲区(index_buffer)大小

    堆内存中 index_buffer 用于存储新索引的文档。

    填满后,缓冲区中的文档将最终写入磁盘上的某个段。

    index_buffer_size 默认值如下所示,为堆内存的 10%。

    indices.memory.index_buffer_size: 10%
    

    例如,如果给 JVM 31GB的内存,它将为索引缓冲区提供 3.1 GB的内存,一般情况下足以容纳大量数据的写入操作。

    但,如果着实数据量非常大,建议调大该默认值。比如:调整为堆内存的 20%。

    调整建议:必须在集群中的每个数据节点上进行配置。

    缓存区越大,意味着能缓存数据量越大,相同时间段内,写盘频次低、磁盘 IO 小,间接提升写入性能。

    写入优化五:给堆外内存也留够空间(常规要求)

    这其实算不上写入优化建议,而是通用集群配置的常规配置。

    内存分配设置堆内存比例官方建议:机器内存大小一半,但不超过 32 GB。

    一般设置建议:

    • 如果内存大小 >= 64 GB,堆内存设置:31 GB。

    • 如果内存大小 < 64 GB,堆内存设置:内存大小一半。

    堆内存之外的内存留给:Lucene 使用。

    推荐阅读:干货 | 吃透Elasticsearch 堆内存

    写入优化六:bulk 批量写入而非单个文档写入

    批量写入自然会比单个写入性能要好(批量写入意味着相同时间产生的段会大,段的总个数自然会少),但批量值的设置一般需要慎重,不要盲目一下搞的很大。

    一般建议:递增步长测试,直到达到资源使用上限。

    比如:第一次批量值设置:100,第二次:200,第三次:400,以此类推......

    批量值 bulk 已经 ok 了,但集群尚有富余资源,资源利用并没有饱和怎么办?

    上多线程,通过并发提升写入性能。

    写入优化七:多线程并发写入

    这点,在 logstash 同步数据到 Elasticsearch,基于spark、kafka、Flink 批量写入 Elasticsearch时,经常会出现:Bulk Rejections 的报错。

    当批量请求到达集群中的某个节点时,整个请求将被放入批量队列中,并由批量线程池中的线程进行处理。批量线程池处理来自队列的请求,并将文档转发到副本分片,作为此处理的一部分。子请求完成后,将响应发送到协调节点。

    Elasticsearch 具有有限大小的请求队列的原因是:为了防止集群过载,从而增加了稳定性和可靠性。

    如果没有任何限制,客户端可以很容易地通过恶意攻击行为将整个集群搞宕机。

    这里就引申出下面的优化点。

    写入优化八:合理设置线程池和队列大小

    关于线程池和队列,参考:Elasticsearch 线程池和队列问题,请先看这一篇

    核心建议就是:结合 CPU 核数和 esrally 的测试结果谨慎的调整 write 线程池和队列大小。

    为什么要谨慎设置?

    针对批量写入拒绝(reject)的场景,官方建议:

    增加队列的大小不太可能改善集群的索引性能或吞吐量。相反,这只会使集群在内存中排队更多数据,这很可能导致批量请求需要更长的时间才能完成。

    队列中的批量请求越多,将消耗更多的宝贵堆空间。如果堆上的压力太大,则可能导致许多其他性能问题,甚至导致集群不稳定。

    推荐阅读:

    https://www.elastic.co/cn/blog/why-am-i-seeing-bulk-rejections-in-my-elasticsearch-cluster

    5、其他写入优化建议

    写入优化九:设置合理的Mapping

    实战业务场景中不推荐使用默认 dynamic Mapping,一定要手动设置 Mapping。

    • 举例1:默认字符串类型是:text 和 keyword 的组合类型,就不见得适用所有业务场景。要结合自己业务场景设置,正文 cont 文本内容一般不需要设置 keyword 类型(因为:不需要排序和聚合操作)。

    • 举例2:互联网采集数据存储场景,正文需要全文检索,但包含 html 样式的文本一般留给前端展示用,不需要索引。这时候Mapping 设置阶段要果断将 index 设置为 false。

    写入优化十:合理的使用分词器

    分词器决定分词的粒度,常见的中文分词 IK 可细分为:

    • 粗粒度分词:ik_smart。

    • 细粒度分词:ik_max_word。

    从存储角度基于 ik_max_word 分词的索引会比基于 ik_smart 分词的索引占据空间大。

    而更细粒度自定义分词 ngram 会占用大量资源,并且可能减慢索引速度并显着增加索引大小。

    所以要结合检索指标(召回率和精准率)、结合写入场景斟酌选型。

    写入优化十一:必要时,使用 SSD 磁盘

    SSD 很贵,但很香。

    尤其针对写入密集型场景,如果其他优化点都考虑了,这可能是你最后一根“救命稻草“。

    写入优化十二:合理设置集群节点角色

    这也是经常被问到的问题,集群规模小的时候,一般节点会混合多种角色,如:主节点 + 数据节点、数据节点 + 协调节点混合部署。

    但,集群规模大了之后,硬件资源相对丰富后,强烈建立:独立主节点、独立协调节点。

    让各个角色的节点各尽其责,对写入、检索性能都会有帮助。

    写入优化十三:推荐使用官方客户端

    推荐使用官方 Elasticsearch API,因为官方在连接池和保持连接状态方面有优化。

    高版本 JAVA API 推荐:官方的High-level-Rest API。

    其他写入优化

    待补充......

    6、写入过程中做好监控

    如下是 kibana 监控截图,其中:index Rate 就是写入速率。

    • index rate: 每秒写入的文档数。

    • search rate:每秒的查询次数(分片级别,非请求级别),也就意味着一次查询请求命中的分片数越多,值越大。

    7、小结

    Elasticsearch 写入优化没有普适的最优优化建议,只有适合自己业务场景的反复试验、调优,形成属于自己业务场景的最佳实践。

    你的业务场景做过哪些写入优化?欢迎留言讨论交流。


    参考:

    • https://www.elastic.co/guide/en/elasticsearch/reference/7.2/tune-for-indexing-speed.html

    • 《Elasticsearch源码解析与优化实战》

    • https://wx.zsxq.com/dweb2/index/search/%E5%88%86%E7%89%87%E6%95%B0/alltopics

    • https://t.zsxq.com/v7qNNRz

    • https://opster.com/blogs/improve-elasticsearch-indexing-rate/

    • 国外博客



    推荐:

    展开全文
  • 这次就详细说说,项目优化,都分哪些。 上目录: 目录 代码优化 业务优化 数据库优化 1、缓存 2、SQL优化 3、热点数据分离 4、数据库读写分离 5、页面静态化 6、合并数据库操作 7、分布式数据库 8、...

    优化很笼统的词汇,这说明它包含的信息量很大,要处理的事情很多。

    这次就详细说说,项目优化,都分哪些。

    上目录:

    目录

    代码优化

    业务优化

    数据库优化

    1、缓存

    2、SQL优化

    3、热点数据分离

    4、数据库读写分离

    5、页面静态化

    6、合并数据库操作

    7、分布式数据库

    8、NoSQL 和 Hadoop

    项目优化

    1、缓存

    2、数据库连接池应该设多大

    3、高并发方案


    一个一个来,先说

    代码优化

    代码优化主要对代码结构层次的优化,目的就是更加方便代码的可维护性与可读性

    代码结构层次的优化

    例如:

    1. 代码注释(代码规范)
    2. 工具类的封装(方便代码维护,使结构更加清晰,保证团队代码质量一致)
    3. 公共部分的提取
    4. 代码极简化(适度即可)
    5. 遇见多重if else 可以试试“策略模式”

    这些是对代码层次的优化所提出的建议,其他的都不说,只针对最后一项,代码极简化这一问题提出一些方案

    ☞各位太君~里面请~《Java代码-极简之道》☜

    看完之后~继续咱的聊啊~然后就是

    代码性能优化

    列如:

    1. 使用一些性能比较高的类(bufferInputStream)
    2. 缓冲区块的大小(4k或者8k)
    3. 通常要用stringbuffer替代string加号拼接
    4. 解析大文件的xml数据使用sax替代dom4j,使用分段批量提交来完成大数据量的插入。
    5. 根据业务情况使用缓存减少对数据库的访问。
    6. 单线程应尽量使用 HashMap, ArrayList,因为HashTable,Vector使用了同步机制,降低了性能。
    7. 在finally块中关闭流,断开连接,释放资源。
    8. 避免在循环条件中使用复杂表达式 。

    等等等等这些类似的

    然后就是

    业务优化

    我们做项目的时候业务优化这方面最主要是从用户体验度角度进行考虑,减少用户操 作的步骤提高工作效率,通常有以下几种:

    1. 可以通过tabindex属性来改变tab键盘的操作顺序
    2. 可以通过回车键来进行搜索或者提交操作
    3. 对于单选按钮和复选按钮可以通过操作后面的文本来选择前面的单选按钮以及复选按钮
    4. 添加的信息要按照id倒序进行排列
    5. 进行搜索操作时加入js loading操作(不仅告诉用户所进行的请求正在被处理,而且防止用户多次点击提交操作)
    6. 当进行删除操作的时候要弹出提示框,警告用户要进行删除操作,是否确认,如果删除成功则弹出提示框告诉用户。
    7. 根据returnURL在用户登录成功后直接跳到想要访问的资源。
    8. 进行删除操作时通过confirm提示用户是否确认删除操作,操作完后提示操作是否成功。
    9. 减少用户操作的步骤
    10. 使用autocomplete插件快速进行搜索

    等等等等... ...这些都是从业务角度来说的,

    然后就是

    数据库优化

    1、缓存

    首先第一种解决方案就是缓存了。

    缓存,我们可以将数据直接缓存在内从中,例如 Map、也可以使用缓存框架如 Redis 等,将一些需要频繁使用的热点数据保存在缓存中,每当用户来访问的时候,就可以直接将缓存中的数据返回给用户,这样可以有效降低服务器的压力。

    可以缓存起来使用的数据,一般都不能对实时性要求太高。

    2、SQL优化

    很多时候程序跑得慢,不是因为设备落后,而是因为数据库 SQL 写的太差劲。

    要解决海量数据的问题,数据库优化肯定也是不可避免的。一般来说,我们可以从 SQL 优化、表结构优化、以及数据库分区分表等多个方面来对数据库进行优化。

    现在说说最常见的SQL优化的基本常识:

    1. 外键必须加索引。
    2. 避免在 where 子句中对有索引的字段进行运算,这会导致索引失效,从而进行全表扫描。
    3. 在 where 及 order by 涉及的列上建立索引,要尽量避免全表扫描。
    4. 在设计表时要避免表中字段出现null的情况,通常要为其设置默认值。
    5. 避免在查找时放弃使用索引而进行全表扫描。
    6. SELECT语句中避免使用'*’,只查询需要返回的字段 ,这样可以减少oracle解析sql语句的时间。
    7. 用NOT EXISTS 替换 NOT IN 操作符,用 EXISTS  替换 IN

    这些,当然,还有就是其他的

    说其他的之前我先解释一下上面第六条的解释

    链接:《SELECT * 执行效率低的原因在哪里?》

    然后就是另外一个需要考虑优化的地方

    链接:《数据量很大,分页查询很慢的优化方案?》

    3、热点数据分离

    数据库中的数据,虽然是海量数据,但是这些数据并不见得所有数据都是活跃数据,例如用户注册,有的用户注册完就消失的无影无踪了,而有的用户则在不停的登录,因此,对于这两种不同的用户,我们可以将活跃用户分离出来,在主要操作的数据表中只保存活跃用户数据。每次用户登录,先去主表中查看有没有记录,有的话,直接登录,没有的话,再去查看其他表。

    通过判断用户在某一段时间内的登录次数,就可以很快分离出热点数据。

    (我先声明啊~这只是解题思路~)

    4、数据库读写分离

    读写分离之后,一方面可以提高数据库的操作效率,另一方面也算是对数据库的一个备份。

    5、页面静态化

    emmmmm~不知道为啥~很多开发者也好其他架构也好,不是很喜欢页面静态化的写法,但是不得不说,这样确实能一定程度上减轻压力

    而页面静态化其实可以算作是缓存的另外一种形式,相当于直接将相关的页面渲染结果缓存起来。

    在我们的 Web 项目中,资源分为两大类:

    • 静态资源
    • 动态资源

    静态资源就是我们常见的 HTML、CSS、JavaScript、图片等资源,这些资源可以不经过服务端处理,就可以直接返回给前端浏览器,浏览器就可以直接显示出来。

    动态资源则是指我们项目中的 Servlet 接口、Jsp 文件、Freemarker 等,这些需要经过服务端渲染之后,才可以返回前端的资源。

    在实际项目中,静态资源的访问速度要远远高于动态资源,动态资源往往很容易遇到服务器瓶颈、数据库瓶颈,因此,对于一些不经常更新的页面,或者说更新比较缓慢的页面,我们可以通过页面静态化,将一个动态资源保存为静态资源,这样当服务端需要访问的时候,直接将静态资源返回,就可以避免去操作数据库了,降低数据库的压力。

    当然还要考虑到数据的长度已经浏览器的容量问题,总不能都一股脑的都塞浏览器里吧~

    一般来说,Freemarker、Velocity 等都有相关的方法可以帮助我们快速将动态页面生成静态页面。

    这就是页面静态化。

    6、合并数据库操作

    这个方案的宗旨其实是减少数据库操作的次数,例如多次插入操作,我们可以合并成一条 SQL 搞定。多个不同条件的查询,如果条件允许的话,也可以合并成为一个查询,尽量减少数据库的操作,减少在网络上消耗,同时也降低数据库的压力。

    7、分布式数据库

    数据库读写分离之后,无形中增大了代码的复杂度,所以一般还需要借助分布式数据库中间件,这样可以有效提高数据库的弹性,可以方便的随时为数据库扩容,同时也降低代码的耦合度。

    8、NoSQL 和 Hadoop

    另外,引入 NoSQL 和 Hadoop 也是解决方案之一。NoSQL 突破了关系型数据库中对表结构、字段等定义的条条框框,使用户可以非常灵活方便的操作,另外 NoSQL 通过多个存储块存储数据的特点,使得天然具备操作大数据的优势(快)。不过,老实说,NoSQL 目前还是在互联网项目中比较常见,在传统的企业级应用中还是比较少见。

    Hadoop 就不必说了,大数据处理利器。

    项目优化

    1、缓存

    不说,这一块儿的教学太多了,告辞~直接蹦下一个~

    2、数据库连接池应该设多大

    ☞以下内容95%译自这篇文章,各位太君~里面请~☜

    接下来是正文

    数据库连接池的配置是开发者们常常搞出坑的地方,在配置数据库连接池时,有几个可以说是和直觉背道而驰的原则需要明确。

    你有一个网站,压力虽然还没到Facebook那个级别,但也有个1万上下的并发访问——也就是说差不多2万左右的TPS。那么这个网站的数据库连接池应该设置成多大呢?结果可能会让你惊讶,因为这个问题的正确问法是:

    “这个网站的数据库连接池应该设置成多小呢?”

    ☞这个视频是Oracle Real World Performance Group发布的,有兴趣的太君~里面请~☜

    因为这视频是英文解说且没有字幕,我替大家做一下简单的概括:

    视频中对Oracle数据库进行压力测试,9600并发线程进行数据库操作,每两次访问数据库的操作之间sleep 550ms,一开始设置的中间件线程池大小为2048:

    压测跑起来之后是这个样子的:

    每个请求要在连接池队列里等待33ms,获得连接后执行SQL需要77ms

    此时数据库的等待事件是这个熊样的:

    各种buffer busy waits,数据库CPU在95%左右

    接下来,把中间件连接池减到1024(并发什么的都不变),性能数据变成了这样:

    获取链接等待时长没怎么变,但是执行SQL的耗时减少了。下面这张图,上半部分是wait,下半部分是吞吐量

    能看到,中间件连接池从2048减半之后,吐吞量没变,但wait事件减少了一半。

    接下来,把数据库连接池减到96,并发线程数仍然是9600不变。

    96个连接时的性能数据

    队列平均等待1ms,执行SQL平均耗时2ms。

    wait事件几乎没了,吞吐量上升。

    没有调整任何其他东西,仅仅只是缩小了中间件层的数据库连接池,就把请求响应时间从100ms左右缩短到了3ms。

    为什么nginx只用4个线程发挥出的性能就大大超越了100个进程的Apache HTTPD?

    即使是单核CPU的计算机也能“同时”运行数百个线程。但我们都[应该]知道这只不过是操作系统用时间分片玩的一个小把戏。一颗CPU核心同一时刻只能执行一个线程,然后操作系统切换上下文,核心开始执行另一个线程的代码,以此类推。给定一颗CPU核心,其顺序执行A和B永远比通过时间分片“同时”执行A和B要快,这是一条计算机科学的基本法则。一旦线程的数量超过了CPU核心的数量,再增加线程数系统就只会更慢,而不是更快。

    这几乎就是真理了……

    上面的说法只能说是接近真理,但还并没有这么简单,有一些其他的因素需要加入。当我们寻找数据库的性能瓶颈时,总是可以将其归为三类:CPU、磁盘、网络。把内存加进来也没有错,但比起磁盘和网络,内存的带宽要高出好几个数量级,所以就先不加了。

    如果我们无视磁盘和网络,那么结论就非常简单。在一个8核的服务器上,设定连接/线程数为8能够提供最优的性能,再增加连接数就会因上下文切换的损耗导致性能下降。数据库通常把数据存储在磁盘上,磁盘又通常是由一些旋转着的金属碟片和一个装在步进马达上的读写头组成的。读/写头同一时刻只能出现在一个地方,然后它必须“寻址”到另外一个位置来执行另一次读写操作。所以就有了寻址的耗时,此外还有旋回耗时,读写头需要等待碟片上的目标数据“旋转到位”才能进行操作。使用缓存当然是能够提升性能的,但上述原理仍然成立。

    在这一时间段(即"I/O等待")内,线程是在“阻塞”着等待磁盘,此时操作系统可以将那个空闲的CPU核心用于服务其他线程。所以,由于线程总是在I/O上阻塞,我们可以让线程/连接数比CPU核心多一些,这样能够在同样的时间内完成更多的工作。

    那么应该多多少呢?这要取决于磁盘。较新型的SSD不需要寻址,也没有旋转的碟片。可别想当然地认为“SSD速度更快,所以我们应该增加线程数”,恰恰相反,无需寻址和没有旋回耗时意味着更少的阻塞,所以更少的线程[更接近于CPU核心数]会发挥出更高的性能。只有当阻塞创造了更多的执行机会时,更多的线程数才能发挥出更好的性能。

    网络和磁盘类似。通过以太网接口读写数据时也会形成阻塞,10G带宽会比1G带宽的阻塞少一些,1G带宽又会比100M带宽的阻塞少一些。不过网络通常是放在第三位考虑的,有些人会在性能计算中忽略它们。

    上图是PostgreSQL的benchmark数据,可以看到TPS增长率从50个连接数开始变缓。在上面Oracle的视频中,他们把连接数从2048降到了96,实际上96都太高了,除非服务器有16或32颗核心。

    计算公式

    下面的公式是由PostgreSQL提供的,不过我们认为可以广泛地应用于大多数数据库产品。你应该模拟预期的访问量,并从这一公式开始测试你的应用,寻找最合适的连接数值。

    连接数 = ((核心数 * 2) + 有效磁盘数)

    核心数不应包含超线程(hyper thread),即使打开了hyperthreading也是。
    如果活跃数据全部被缓存了,那么有效磁盘数是0,随着缓存命中率的下降,有效磁盘数逐渐趋近于实际的磁盘数。
    这一公式作用于SSD时的效果如何尚未有分析。

    按这个公式,你的4核i7数据库服务器的连接池大小应该为((4 * 2) + 1) = 9。取个整就算是是10吧。是不是觉得太小了?跑个性能测试试一下,我们保证它能轻松搞定3000用户以6000TPS的速率并发执行简单查询的场景。如果连接池大小超过10,你会看到响应时长开始增加,TPS开始下降。

    这一公式其实不仅适用于数据库连接池的计算,大部分涉及计算和I/O的程序,线程数的设置都可以参考这一公式。

    公理:你需要一个小连接池,和一个充满了等待连接的线程的队列

    如果你有10000个并发用户,设置一个10000的连接池基本等于失了智。1000仍然很恐怖。即是100也太多了。你需要一个10来个连接的小连接池,然后让剩下的业务线程都在队列里等待。连接池中的连接数量应该等于你的数据库能够有效同时进行的查询任务数(通常不会高于2*CPU核心数)。

    我们经常见到一些小规模的web应用,应付着大约十来个的并发用户,却使用着一个100连接数的连接池。这会对你的数据库造成极其不必要的负担。

    请注意

    连接池的大小最终与系统特性相关。

    比如一个混合了长事务和短事务的系统,通常是任何连接池都难以进行调优的。最好的办法是创建两个连接池,一个服务于长事务,一个服务于短事务。

    再例如一个系统执行一个任务队列,只允许一定数量的任务同时执行,此时并发任务数应该去适应连接池连接数,而不是反过来。

    3、高并发方案

    (这一块儿我又得单独拉一块儿~先写干货吧~)

    纵向扩展(scale-up)

    它的目标是提升单机的处理能力,方案又包括:

    1. 提升单机的硬件性能:通过增加内存、CPU核数、存储容量、或者将磁盘升级成SSD等堆硬件的方式来提升。
    2. 提升单机的软件性能:使用缓存减少IO次数,使用并发或者异步的方式增加吞吐量。

    横向扩展(scale-out)

    因为单机性能总会存在极限,所以最终还需要引入横向扩展,通过集群部署以进一步提高并发处理能力,又包括以下2个方向: 

    1、做好分层架构:

    这是横向扩展的提前,因为高并发系统往往业务复杂,通过分层处理可以简化复杂问题,更容易做到横向扩展。

    上面这种图是互联网最常见的分层架构,当然真实的高并发系统架构会在此基础上进一步完善。比如会做动静分离并引入CDN,反向代理层可以是LVS+Nginx,Web层可以是统一的API网关,业务服务层可进一步按垂直业务做微服务化,存储层可以是各种异构数据库。

    2、各层进行水平扩展:

    无状态水平扩容,有状态做分片路由。业务集群通常能设计成无状态的,而数据库和缓存往往是有状态的,因此需要设计分区键做好存储分片,当然也可以通过主从同步、读写分离的方案提升读性能。

    高性能的实践方案

    1. 集群部署,通过负载均衡减轻单机压力。
    2. 多级缓存,包括静态数据使用CDN、本地缓存、分布式缓存等,以及对缓存场景中的热点key、缓存穿透、缓存并发、数据一致性等问题的处理。
    3. 分库分表和索引优化,以及借助搜索引擎解决复杂查询问题。
    4. 考虑NoSQL数据库的使用,比如HBase、TiDB等,但是团队必须熟悉这些组件,且有较强的运维能力。
    5. 异步化,将次要流程通过多线程、MQ、甚至延时任务进行异步处理。
    6. 限流,需要先考虑业务是否允许限流(比如秒杀场景是允许的),包括前端限流、Nginx接入层的限流、服务端的限流。
    7. 对流量进行削峰填谷,通过MQ承接流量。
    8. 并发处理,通过多线程将串行逻辑并行化。
    9. 预计算,比如抢红包场景,可以提前计算好红包金额缓存起来,发红包时直接使用即可。
    10. 缓存预热,通过异步任务提前预热数据到本地缓存或者分布式缓存中。
    11. 减少IO次数,比如数据库和缓存的批量读写、RPC的批量接口支持、或者通过冗余数据的方式干掉RPC调用。
    12. 减少IO时的数据包大小,包括采用轻量级的通信协议、合适的数据结构、去掉接口中的多余字段、减少缓存key的大小、压缩缓存value等。
    13. 程序逻辑优化,比如将大概率阻断执行流程的判断逻辑前置、For循环的计算逻辑优化,或者采用更高效的算法。
    14. 各种池化技术的使用和池大小的设置,包括HTTP请求池、线程池(考虑CPU密集型还是IO密集型设置核心参数)、数据库和Redis连接池等。
    15. JVM优化,包括新生代和老年代的大小、GC算法的选择等,尽可能减少GC频率和耗时。
    16. 锁选择,读多写少的场景用乐观锁,或者考虑通过分段锁的方式减少锁冲突。

    上述方案无外乎从计算和 IO 两个维度考虑所有可能的优化点,需要有配套的监控系统实时了解当前的性能表现,并支撑你进行性能瓶颈分析,然后再遵循二八原则,抓主要矛盾进行优化。

    高可用的实践方案

    1. 对等节点的故障转移,Nginx和服务治理框架均支持一个节点失败后访问另一个节点。
    2. 非对等节点的故障转移,通过心跳检测并实施主备切换(比如redis的哨兵模式或者集群模式、MySQL的主从切换等)。
    3. 接口层面的超时设置、重试策略和幂等设计。
    4. 降级处理:保证核心服务,牺牲非核心服务,必要时进行熔断;或者核心链路出问题时,有备选链路。
    5. 限流处理:对超过系统处理能力的请求直接拒绝或者返回错误码。
    6. MQ场景的消息可靠性保证,包括producer端的重试机制、broker侧的持久化、consumer端的ack机制等。
    7. 灰度发布,能支持按机器维度进行小流量部署,观察系统日志和业务指标,等运行平稳后再推全量。
    8. 监控报警:全方位的监控体系,包括最基础的CPU、内存、磁盘、网络的监控,以及Web服务器、JVM、数据库、各类中间件的监控和业务指标的监控。
    9. 灾备演练:类似当前的“混沌工程”,对系统进行一些破坏性手段,观察局部故障是否会引起可用性问题。

    而高可用的方案主要从冗余、取舍、系统运维3个方向考虑,同时需要有配套的值班机制和故障处理流程,当出现线上问题时,可及时跟进处理。

    高扩展的实践方案

    1. 合理的分层架构:比如上面谈到的互联网最常见的分层架构,另外还能进一步按照数据访问层、业务逻辑层对微服务做更细粒度的分层(但是需要评估性能,会存在网络多一跳的情况)。
    2. 存储层的拆分:按照业务维度做垂直拆分、按照数据特征维度进一步做水平拆分(分库分表)。
    3. 业务层的拆分:最常见的是按照业务维度拆(比如电商场景的商品服务、订单服务等),也可以按照核心接口和非核心接口拆,还可以按照请求源拆(比如To C和To B,APP和H5)。

    高并发确实是一个复杂且系统性的问题,由于篇幅有限,诸如分布式Trace、全链路压测、柔性事务都是要考虑的技术点。另外,如果业务场景不同,高并发的落地方案也会存在差异,但是总体的设计思路和可借鉴的方案基本类似。

    高并发设计同样要秉承架构设计的3个原则:简单、合适和演进。“过早的优化是万恶之源”,不能脱离业务的实际情况,更不要过度设计,合适的方案就是最完美的。

    本人才疏学浅,难免犯错,若发现文中有错误遗漏,望不吝赐教。

    展开全文
  • 数学建模之优化模型详解

    千次阅读 多人点赞 2022-03-09 21:51:29
    全文共8090个字,码字总结不易,老铁们来个三连:点赞、关注、评论作者:[左手の明天] 原创不易,转载请联系作者并... 这些问题都是“最优化问题”,也是数学建模中的典型问题,解决最优化问题的数学方法就是“最优化..

    全文共8090个字,码字总结不易,老铁们来个三连:点赞、关注、评论
    作者:[左手の明天]
     原创不易,转载请联系作者并注明出处
    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    “优化”是生活中经常使用的词:坐出租车时希望司机不绕弯路、走优化路线;逛超市时考虑各种优惠活动,希望获得最大优惠;企业推出新产品要综合考虑成本与市场吸引力,对资金进行优化配置,等等。 这些问题都是“最优化问题”,也是数学建模中的典型问题,解决最优化问题的数学方法就是“最优化方法”。

    最优化方法的出发点是系统思维,最优化方法的基本思路是在一定的约束条件下,保证各方面资源的合理分配, 最大限度地提升系统某一性能或系统整体性能,最终实现最理想结果。运用最优化方法建立并求解数学模型,主要包括以下步骤:

    (1)明确目标,分析问题背景,确定约束条件,搜集全面的客观数据和信息;
    (2)建立数学模型,构建变量之间的数学关系,设立目标函数;
    (3)分析数学模型,综合选择最适合该模型的优化方法;
    (4)求解模型,通常借助计算机和数学分析软件完成;
    (5)对最优解进行检验和实施。

    目录

    数学规划的一般模型

    MATLAB 求解优化问题的主要函数

    模型及基本函数

    优化函数的输入变量

    优化函数的输出变量

    无约束最优化问题

    数学描述

    解析解法和图解法

    数值解法

    全局最优解和局部最优解

    带约束最优化问题

    线性规划问题

    情况一

    情况二

    二次规划问题

    非线性规划问题

    定义

    求解算法1:间接法

    求解算法2:直接法

    求解算法3:最速下降法(steepest descent method)

    Matlab求解步骤

    示例

    0-1规划问题

    钢管的订购与运输问题

    问题

    问题1的基本模型和解法

    总费用最小的优化问题

    基本模型:二次规划

    Floyd算法求解步骤 

    最优化方法在数学建模中的应用 

    梯度下降法

    惩罚函数法

    遗传算法

    蚁群算法


    数学规划的一般模型

    其中,x~决策变量;f(x)~目标函数;gi(x)≤0~约束条件


    MATLAB 求解优化问题的主要函数

    模型及基本函数

    优化函数的输入变量

    优化函数的输出变量


    无约束最优化问题

    数学描述

    解析解法和图解法

     举例:用解析和图解法求解下列方程

    <<syms t; 
    y=exp(-3*t)*sin(4*t+2)+4*exp(-0.5*t)*cos(2*t)-0.5;
    ezplot(y,[0 4])
    y1=diff(y);
    ezplot(y1,[0 4])
    t0=solve(y1)
    y2=diff(y1);
    b=subs(y2,t,t0)

    数值解法

     命令形式1:

    x=fminsearch(fun,x0)   %简单形式
    
    [x,f,flag,out]=fminsearch(fun,x0,opt,p1,p2,…) %一般形式

    功能:与fsolve()中的参数控制形式类似。

    注:若函数时多元的,要表达成向量的形式。

    命令形式2:

    x=fminunc(fun,x0)   %简单形式
    
    [x,f,flag,out]=fminunc(fun,x0,opt,p1,p2,…) %一般形式

    功能:与fsolve()中的参数控制形式类似。

    举例:

    >>f=inline('(x(1)^2-2*x(1))*exp(-x(1)^2-x(2)^2-x(1)*x(2))','x');
    x0=[0,0];
    ff=optimset;ff.Display='iter';
    x=fminsearch(f,x0,ff)
    
    >>x=fminunc(f,x0,ff)
    

    全局最优解和局部最优解

    一元函数极小

    X=fminbnd(fun,x1,x2)

    多元无约束极小

    X=fminunc(fun,x0) (牛顿法)
    X=fminsearch(fun,x0)

    举例1:(初值的影响力)设目标函数为

     试观察不同的初值得出的最小值。

    >> f=inline('exp(-2*t)*cos(10*t)+exp(-3*(t+2))*sin(2*t)','t');
    t0=1;[t1,f1]=fminsearch(f,t0)
    
    t1=0.92275390625000,f1=-0.15473299821860
    
    >> t0=0.1;[t2,f2]=fminsearch(f,t0)
    
    t2=0.29445312500000,f2=-0.54362463738706
    
    
    >> syms t; 
    y=exp(-2*t)*cos(10*t)+exp(-3*(t+2))*sin(2*t);
    ezplot(y,[0,2.5]); axis([0 2.5 -0.6 1])

    举例2:对边长为3米的正方形铁板,在四个角剪去相等的正方形以制成方形无盖水槽,问如何剪法使水槽的容积最大?

    建立模型: 

    设剪去的正方形的边长为x,,则水槽的容积为:

    建立无约束优化模型为:

    模型求解:

    先编写M文件如下:

    function f=myfun(x)
    f=-(3-2*x).^2*x;

    调用fminbnd:

    [x,fval]=fminbnd(@myfun,0,1.5)

    运算结果为:

    x = 0.5000,fyal =2.0000.

    即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米。


    带约束最优化问题

    线性规划问题

    目标函数:

     约束条件:

    情况一

    目标函数:

    其中,C为价值向量

    约束条件:

     其中,b为资源向量;X为决策变量向量

    其中:

     

    命令形式1:

    [X,lag,how]=lp(C,A,b,v1,v2,x0)

    功能:

    • C,A,b的意义如矩阵表示里参数;
    • v1,v2表示决策变量的上界和下界(其维数可以小于X,但表示前几个分量的上下界);
    • x0表示初始值;X时输出最优解;
    • lag是lagrange乘子,维数等于约束条件的个数,非零的向量是起作用的约束条件;
    • how给出错误信息:infeasible(无可行解),unbounded(无界解),ok(求解成功).

     举例:

    >> c=[13,-1,5];
    A=[-1,-1,0;0,1,1];
    b=[-7,10];
    v0=[2,0,0];
    [X,lag,how]=lp(c,A,b,v0)
    

    情况二

    目标函数:

     约束条件:

    命令形式2:  

    [X,f,flag,c]=linprog(C,A,b,Aeq,Beq,xm,xM,x0,opt)

    功能:各个参数的解释如前,若各个约束条件不存在,则用空矩阵来代替。

    • x: 解
    • f: 最优值
    • flag:大于零表示求解成功,否则求解出问题
    • c:求解信息
    • x0:搜索点的初值
    • opt:最优化控制项

    举例1:

    >> c=[-2,-1,-4,-3,-1];
     A=[0 2 1 4 2;3 4 5 -1 -1];
     b=[54,62];
     Ae=[];Be=[];
     xm=[0,0,3.32,0.678,2.57];
     ff=optimset;
     ff.LargeScale='off';
     ff.TolX=1e-15;
     ff.Display='iter';
     [X,f,flag,c]=linprog(c,A,b,Ae,Be,xm,[],[],ff)
    

    举例2:某车间生产A和B两种产品,为了生产A和B,所需的原料分别为2个和3个单位,所需的工时分别为4个和2个单位。现在可以应用的原料为100个单位,工时为120个单位。每生产一台A和B分别可获得利润6元和4元。应当生产A和B各多少台能获得最大利润?

    分析:

     模型建立:

    设生产A产品x1 台,生产B产品 x2台

     模型求解:

    f=[-6,-4]';
    A=[2 3;4 2];
    B=[100;120];
    Ae=[];
    Be=[];
    xm=[0,0];
    ff=optimset;
    ff.LargeScale='off'; % 不用大规模问题求解
    ff.TolX=1e-15;
    ff.TolFun=1e-20; 
    ff.TolCon=1e-20;
    ff.Display='iter';
    [x,f_opt,key,c]=linprog(f,A,B,Ae,Be,xm,[],[],ff)

    举例3:(任务分配问题)某车间有甲、乙两台机床,可用于加工三种工件。假定这两台车床的可用台时数分别为 800 和 900,三种工件的数量分别为 400、600 和 500,且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务,才能既满足加工工件的要求,又使加工费用最低?

    模型建立:

    设在甲车床上加工工件 1、2、3 的数量分别为 x1、x2、x3,在乙车床上加工工件 1、2、3 的数量分别为 x4、x5、x6。可建立以下线性规划模型:

    模型求解:

    f = [13 9 10 11 12 8];
    A = [0.4 1.1 1 0 0 0
    0 0 0 0.5 1.2 1.3];b = [800; 900];
    Aeq=[1 0 0 1 0 0
    0 1 0 0 1 0
    0 0 1 0 0 1];
    beq=[400 600 500];
    vlb = zeros(6,1);
    vub=[];
    [x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub)

    举例4:某厂每日 8 小时的产量不低于 1800 件。为了进行质量控制,计划聘请两种不同水平的检验员。一级检验员的标准为:速度 25 件/小时,正确率 98%,计时工资 4 元/小时;二级检验员的标准为:速度 15 小时/件,正确率 95%,计时工资 3 元/小时。检验员每错检一次,工厂要损失 2 元。为使总检验费用最省,该工厂应聘一级、二级检验员各几名?

    模型建立:

    设需要一级和二级检验员的人数分别为 x1、x2 人,则应付检验员的工资为:

     因检验员错检而造成的损失为:

    故目标函数为:

    约束条件为:

     

     线性规划模型:

     

     模型求解:

    c = [40;36];
    A=[-5 -3];
    b=[-45];
    Aeq=[];
    beq=[];
    vlb = zeros(2,1);
    vub=[9;15];
    %调用 linprog 函数:
    [x,fval] = linprog(c,A,b,Aeq,beq,vlb,vub)

    结果:

    x =
    9.0000
    0.0000
    fval =360

    即只需聘用 9 个一级检验员。

    二次规划问题

    目标函数:

    约束条件: 

    命令形式:

     [X,f,flag,c]=quadprog(H,C,A,b,Aeq,Beq,xm,xM,x0,opt)

    功能:

    各个参数的解释如前,若各个约束条件不存在,则用空矩阵来代替。

    举例:

     

    >> c=[-2,-1,-4,-3,-1];
      A=[0 2 1 4 2;3 4 5 -1 -1];
      b=[54,62];
      Ae=[];Be=[];
      xm=[0,0,3.32,0.678,2.57];
      ff=optimset;
      ff.LargeScale='off';
      ff.TolX=1e-15;
      ff.Display='iter';
      [X,f,flag,c]=linprog(c,A,b,Ae,Be,xm,[],[],ff)
    

    非线性规划问题

    定义

    如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题.

    一般形式:

     其中

     

     是定义在 En 上的实值函数,简记:

     

    其它情况:

    求目标函数的最大值或约束条件为小于等于零的情况,都可通过取其相反数化为上述一般形式.

     

    其中X为n维变元向量,G(X)与Ceq(X)均为非线性函数组成的向量,其它变量的含义与线性规划、二次规划中相同.

    求解算法1:间接法

    在非线性最优化问题当中,如果目标函数能以解析函数表示,可行域由不等式约束确定,则可以利用目标函数和可行域的已知性质,在理论上推导出目标函数为最优值的必要条件,这种方法就称为间接法(也称为解析法) 。 一般要用到目标函数的导数。

    求解算法2:直接法

    直接法是一种数值方法。这种方法的基本思想是迭代,通过迭代产生一个点序列{ X(k) },使之逐步接近最优点。 只用到目标函数。 如黄金分割法、Fibonacci、随机搜索法。

    迭代法一般步骤

     注意:数值求解最优化问题的计算效率取决于确定搜索方向P (k)和步长的效率。

    求解算法3:最速下降法(steepest descent method)

    由法国数学家Cauchy于1847年首先提出。在每次迭代中,沿最速下降方向(负梯度方向)进行搜索,每步沿负梯度方向取最优步长,因此这种方法称为最优梯度法。

    特点:

    方法简单,只以一阶梯度的信息确定下一步的搜索方向,收敛速度慢; 越是接近极值点,收敛越慢; 它是其它许多无约束、有约束最优化方法的基础。 该法一般用于最优化开始的几步搜索。

    最速下降法算法:

    Matlab求解步骤

    用Matlab求解上述问题,基本步骤分三步:

    1. 首先建立M文件fun.m,定义目标函数F(X):

    function f=fun(X); 
    f=F(X);

     3. 建立主程序.非线性规划求解的函数是fmincon,命令的基本格式如下:       

    (1) x=fmincon(‘fun’,X0,A,b)    
    
    (2) x=fmincon(‘fun’,X0,A,b,Aeq,beq)    
    
    (3) x=fmincon(‘fun’,X0,A,b, Aeq,beq,VLB,VUB)          
    
    (4) x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’)
    
    (5) x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’,options)
    
    (6) [x,fval]= fmincon(...)
    
    (7) [x,fval,exitflag]= fmincon(...)  
    
    (8) [x,fval,exitflag,output]= fmincon(...)

    输入参数的几点说明:

    模型中如果没有A,b,Aeq,beq,VLB,VUB的限制,则以空矩阵[ ]作为参数传入;

    nonlcon:如果包含非线性等式或不等式约束,则将这些函数编写一个Matlab函数

    nonlcon就是定义这些函数的程序文件名;

    不等式约束  G(x)<=0

    等式约束     Ceq(x)=0.

    如果nonlcon=‘mycon’ ; 则myfun.m定义如下

    function [G,Ceq] = mycon(x)
    
    G= ... % 计算非线性不等式约束在点x处的函数值
    
    Ceq= ... %计算机非线性等式约束在点x处的函数值 

    示例

    例子1:

    2个不等式约束, 2个等式约束 3个决策变量x1,x2,x3 如果nonlcon以‘test’作为参数值,则程序test.m如下

    function [G,Ceq]=test(x)
    G(1)=x(1)*x(1)+x(2)*x(2)+x(3)*x(3)-100
    G(2)=60-x(1)*x(1)+10*x(3)*x(3)
    Ceq(1)=x(1)+x(2)*x(2)+x(3)- 80
    Ceq(2)=x(1)^3+x(2)*x(2)+x(3)- 80
    

    注意:

    [1] fmincon函数提供了大型优化算法和中型优化算法。默认时,若在fun函数中提供了梯度(options参数的GradObj设置为’on’),并且只有上下界存在或只有等式约束,fmincon函数将选择大型算法。当既有等式约束又有梯度约束时,使用中型算法。

    [2] fmincon函数可能会给出局部最优解,这与初值X0的选取有关。

    例子2:

     1.先建立M文件 fun.m,定义目标函数:

    function f=fun(x);
    
    f=exp(x(1)) *(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

     2.再建立M文件mycon.m定义非线性约束:

    function [g,ceq]=mycon(x)
    
    g=[1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10];
    
    ceq=[];

    3.主程序为:

    x0=[-1;1];
    A=[];b=[];
    Aeq=[1 1];
    beq=0; 
    vlb=[];
    vub=[];
    [x,fval]=fmincon('fun4',x0,A,b,Aeq,beq,vlb,vub,'mycon')

    4.运算结果为:

    x = -1.2250    1.2250        
    
    fval = 1.8951

    0-1规划问题

    数学描述:自变量的取值只能为0或1

    matlab解:

    X=bintprog(f,A,B,Aeq,Beq)

    小规模问题可以穷举

    举例:求解下面的0-1线性规划问题

     

    f=[-3,2,-5]; A=[1 2 -1; 1 4 1; 1 1 0; 0 4 1]; 
    B=[2;4;5;6];
    x=bintprog(f,A,B,[],[])'

    钢管的订购与运输问题

    要铺设一条A1→A2 →……→ A15的输送天然气的主管道,如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有 。图中粗线表示铁路,单细线表示公路,双细线表示要铺设的管道(假设沿管道或者原来有公路,或者建有施工公路),圆圈表示火车站,每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。

    为方便计,1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管,至少需要生产
    500个单位。钢厂Si在指定期限内能生产该钢管的最大数量为Si个单位,钢管出厂销价1单位钢管为pi万元,如下表:

     1单位钢管的铁路运价如下表:

     

    1000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元(不足
    整公里部分按整公里计算)。钢管可由铁路、公路运往铺设地点(不只是运到点A1,A2,……,A15 ,而是管道全线)。

    问题

    (1)制定钢管的订购和运输计划,使总费用最小.
    (2)分析对购运计划和总费用影响:哪个钢厂钢管销价的变化影响最大;哪个钢厂钢管产量上限的变化影响最大?
    (3)讨论管道为树形图的情形

    问题1的基本模型和解法

    总费用最小的优化问题

     

    基本模型:二次规划

    Floyd算法求解步骤 

     Floyd算法过程描述如下:

    • 1、 首先S以边集M初始化,得到所有的直接连通代价;
    • 2、 依次考虑第k个结点,对于S中的每一个S[i][j],判断是否满足:S[i][j]>S[i][k]+S[k][j],如果满足则用S[i][k]+S[k][j]代替S[i][j],此为第k步;
    • 3、 k循环取遍所有结点,算法结束时,S为最终解。

     


    最优化方法在数学建模中的应用 

    梯度下降法

    梯度下降法是经典的最优化方法之一[4],其核心思想是高等数学中的导数理论。 梯度下降法实现最优化的原理是,每次迭代更新目标函数时,都以该变量导数(即梯度)的反方向作为更新参数的方向,最终解一定会收敛于最优解。 这个原理类似于走下坡路时,总是沿着最陡峭的方向向下走,最后就一定会走到坡底。梯度下降法的实现简单, 但是求解计算时间长,因此基于梯度下降法发展了很多改进算法,包括随机梯度下降法、小批量梯度下降法等,能够有效改善计算成本高的问题。

    惩罚函数法

    惩罚函数法,指的是引入惩罚因子和惩罚函数的最优化方法[5]。 具体来说,惩罚函数的思想是:将最优化问题中的约束条件视为围墙,而迭代更新的解视为在围墙内运动的粒子,一旦粒子靠近围墙,对应的惩罚因子数值就会增大,导致惩罚函数值增大,反之,粒子远离围墙时,惩罚函数值就减小。 建立了这种惩罚机制后,在每次迭代过程中,模型为了“避免被惩罚”,逐渐趋近于约束边界,从而找到了最优解。惩罚函数法对模型的训练虽然“简单粗暴”,但是原理直观、实现门槛低,是实际工程中备受青睐的最
    优化方法。

    遗传算法

    不同于梯度下降法和惩罚函数法,遗传算法并非依据导数理论提出的算法[6],而是一种模拟生物在自然届中进化规律的一种智能算法。 自然界的生物进化遵循适者生存和优胜劣汰,即能够适应环境变化或基因变异的个体才能够参与到进化。 遗传算法的优化原理与之类似:每一次迭代时,通过计算各个个体的适应度,从中随机地选择两个个体作为父母,繁殖后代,同时诱发子代的染色体变异,重复迭代,当出现最大适应度的子代时,即认为获得了最优解,循环结束。与梯度下降法、惩罚函数法相比,遗传算法以生物进化为原型,收敛性较好,在计算精度要求时,具有计算时间少、鲁棒性高的优势。

    蚁群算法

    与遗传算法类似,蚁群算法也是受启发于生物的一种最优化方法[7]。 生物科学家发现蚂蚁经过的路上都会有一种特殊物质,并且蚁群中的蚂蚁对该物质高度敏感,由于该物质浓度越高,代表着路途长度越短,想要走“捷径”的蚁群们都会选择浓度较高的道路行走,“捷径”经过的蚂蚁越多,特殊物质的浓度就越高,物质浓度积累到一定程度,所有蚂蚁都会被吸引到最佳捷径上来,都能以最快速度找到食物了。 蚁群算法解决最优化问题,就是利用了其分布计算和信息正反馈的特点。

    展开全文
  • 数据库索引原理优化

    千次阅读 2019-03-07 09:20:00
    下面详细介绍内存和磁盘存取原理,然后再结合这些原理分析B-/+Tree作为索引的效率。 存存取原理 目前计算机使用的主存基本都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,这里本文抛却具体差别,抽象...
  • Android二维码原理优化方向

    万次阅读 多人点赞 2020-03-03 16:37:31
    } 优化相机设置 二维码扫描解码除了上述因素外,还有一个重大的相关因素就是相机设置方面的。如果我们预览的图片模糊、或者二维码拉伸、图片过小、图片旋转或者扭曲等,都会导致很难定位到二维码,解析二维码困难。...
  • Android 性能优化四个方面总结

    千次阅读 2018-12-17 16:56:49
    目录一、四个方面二、卡顿优化1、Android系统显示原理2、卡顿根本原因3、性能分析工具(1)Profile GPU Rendering(2)TraceView(3)Systrace UI 性能分析4、优化建议(1)布局优化(2)避免过度绘制(3)启动优化...
  • Java性能优化的七个方向

    千次阅读 多人点赞 2022-03-08 20:03:57
    本文对Java性能优化的7种技术手段进行了简单的介绍。
  • 起源:在2015年,Seyedali Mirjalili学者受到自然规律启发,根据飞蛾飞行时的导航机制,在模拟飞蛾螺旋飞行的路径中提出一种新型群智能优化算法:飞蛾火焰优化算法(moth-flame optimization,MFO)。 定义:飞蛾...
  • 一、启动原理解析 Android是基于Linux内核的,当手机启动,加载完Linux内核后,会由Linux系统的init祖先进程fork出Zygote进程,所有的Android应用程序进程以及系统服务进程都是这个Zygote的子进程(由它fork出来的)...
  • 内容简介《最优化方法及其Matlab程序设计》较系统地介绍了非线性最优化问题的基本理论和算法,以及主要算法的Matlab程序设计,主要内容包括(精确或非精确)线搜索技术、最速下降法与(修正)牛顿法、共轭梯度法、拟牛顿...
  • 数据库索引底层原理优化

    千次阅读 多人点赞 2018-09-11 14:11:18
    下面详细介绍内存和磁盘存取原理,然后再结合这些原理分析B-/+Tree作为索引的效率。 3.2 主存存取原理 目前计算机使用的主存基本都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,这里本文抛却...
  • 增强分析技术原理与实践

    千次阅读 2020-06-15 08:30:00
    文章作者:马玥、丁建栋 阿里巴巴编辑整理:Hoh内容来源:作者授权出品平台:DataFunTalk注:欢迎转载,转载请留言。导读:去年,增强分析 ( Augmented Analytic...
  • Hive原理及查询优化(杨卓荦)

    千次阅读 2018-05-25 16:49:42
    今天,我想和大家简单介绍一下Hive原理和查询优化。由于时间有限,很多内容简要介绍一下,欢迎私下多交流。Hive是构建在Hadoop上的数据仓库软件框架,支持使用SQL来读,写和管理大规模数据集合。Hive入门非常简单,...
  • Kubernetes资源优化方案详解
  • 最优化方法matlab实现

    万次阅读 多人点赞 2017-04-13 11:32:54
    优化问题测试函数: ... 利用Matlab的优化工具箱,可以求解线性规划、非线性规划和多目标规划问题。具体而言,包括线性、非线性最小化,最大最小化,二次规划,半无限问题,线性、非线性方
  • SQL优化最干货总结 - MySQL(2020最新版)

    万次阅读 多人点赞 2020-06-29 16:55:47
    MySQL - SQL优化干货总结(吐血版),别辜负了自己的梦想,欢迎白嫖、点赞、收藏。
  • 对于涉及依赖注入、面向切面、缓存、数据访问、异步编程等通用化的功能组件,理论联系实际,实现机制和内部原理角度出发详细分析组件背后的架构思想以及设计方法,并给出源码级的系统讲解。 对每个Spring Boot...
  • Android性能优化方面解析

    千次阅读 2017-05-15 11:47:59
    一、性能优化。二、高级UI。三、JNI/NDK开发。四、架构师。五、RN开发。这也许将会是我的进阶趋势。早已知道在瓶颈期的我,似乎看到了突破的希望的。初级进阶中级也好,中级进阶高级也罢,现在的市场无非是根据经验...
  • 计算机组成原理详细笔记

    万次阅读 多人点赞 2021-01-21 14:26:44
    参考:《王道计算机组成原理》学习笔记总目录+思维导图 2019 王道考研 计算机组成原理 第一章 计算机系统概述 1.1 计算机发展历程 1.1.1 计算机硬件的发展 计算机系统=硬件+软件 计算机硬件的发展: 第一代计算机...
  • 文章目录1. 常见内存泄漏1.1 “单例模式” 造成的内存泄漏1.2 “静态实例” 造成内存泄漏1.3 “Handler” 造成的内存泄漏1.4 “线程” 造成的内存... 在《Android性能优化(1):常见内存泄漏与优化(一)》和《An...
  • 又称帕累托分析法或巴雷托分析法、柏拉图分析、主次因分析法 、ABC分析法、分类管理法、物资重点管理法、ABC管理法、abc管理、巴雷特分析法,平常我们也称之为“80对20”规则,EMBA、MBA等主流商管教育均对ABC分类法...
  • 最优化问题广泛的存在于社会生产活动当中,我们一直努力寻求更高效、更准确的解决方式来应对这类问题。通常,最优化问题可以表述为一种数学规划的形式,对于变量在可行域中的不同组合进行搜索,以得到目标函数的最优...
  • 用人话讲明白AHP层次分析法(非常详细原理+简单工具实现)
  • Java编译原理 什么是字节码、机器码、本地代码? 字节码是指平常所了解的 .class 文件,Java 代码通过 javac 命令编译成字节码 机器码和本地代码都是指机器可以直接识别运行的代码,也就是机器指令 字节码是不能...
  • MySQL索引原理以及查询优化

    千次阅读 2021-07-01 08:32:48
    一般的应用系统,读写比例在10:1左右,而且插入操作和一般的更新操作很少出现性能问题,在生产环境中,我们遇到最多的,也是容易出问题的,还是一些复杂的查询操作,因此对查询语句的优化显然是重中之重。...
  • 前端项目的性能优化几个方面

    千次阅读 2019-03-03 18:11:33
    1. 利用打包工具打包压缩前端代码 拿目前流行的webpack为例: webpack 可以将前端代码压缩差不多你未压缩之前的一半体积或更多,...常见的优化方式是,用 include 或 exclude 来帮我们避免不必要的转译如(node...
  • 目录 简介 synchronized使用层面 synchronized JVM层面 synchronized的优化层面 ...多线程一直是面试中的重点和难点,无论你现在...你可以synchronized使用层面,synchronized的JVM层面,synchronized的优化层.

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 185,786
精华内容 74,314
关键字:

从哪些方面分析原理的最优化

友情链接: blog_swan_cqnbtp.rar