胡拉哥-CSDN博客

原创线性规划：内点法

介绍求解线性规划的内点法（含代码）。

2021-10-15 18:05:34 3583 3

原创线性规划：单纯形算法之处理退化

单纯形算法第二讲（附完整代码）

2021-08-02 15:13:33 4779 1

原创线性规划：单纯形算法

单纯形算法第一讲（附完整代码）。

2021-07-04 11:33:17 785 9

业务背景网易严选是一家自营电商，每天有数以万计的订单需要拣货、打包和出库。打包的过程就是把订单中的商品用包材进行包裹，常见的打包方式有缠膜、装袋和装箱。袋子和箱子有不同的种类和型号，比如袋子有共挤膜袋、镀铝膜袋、塑料袋等。仓库作业工人需要对商品按订单进行打包。具体来说，主要决策两件事：第一，根据订单的商品选择正确的包材类型。比如服装毛巾等柔软的商品适合用袋子；易碎品、液体和贵重物品适合用纸箱；有些商品自身的包装结实耐磨，可以选择缠膜或者裸发。如果适用的包材类型有冲突，则选择优先级最高的包材。第二，

2021-05-26 10:55:32 2005 3

原创算法设计技巧: Primal-Dual

原始对偶(Primal-Dual)是一种求解优化问题的思想, 在凸优化和组合优化问题中有重要应用. 本文以线性规划问题为例解释原始对偶算法的设计思路, 进而介绍如何设计基于原始对偶的近似算法(一般用于求解NP-hard问题).互补松弛条件考虑线性规划的原始问题(P)和对偶问题(D)如下:min⁡ cTxs.t. Ax≥bx≥0(P)\begin{aligned}\min\ & c^Tx \tag{P}\\\text{s.t. } & Ax \geq b\\&

2020-05-20 10:07:32 10485 4

原创算法设计技巧: 局部搜索(Local Search)

局部搜索的基本步骤如下:构造初始解sss;定义sss的邻域δ(s)\delta(s)δ(s);在邻域δ(s)\delta(s)δ(s)中搜索新的解s′s's′;令s:=s′s:=s's:=s′, 重复上述步骤直到满足停止条件.在实际中局部搜索可以作为其它算法的补充, 目的是进一步提升解的质量. 下面我们以经典的旅行商问题(Traveling Salesman Problem)为例来介...

2020-04-25 08:56:09 7979

原创算法设计技巧: Rounding

本文介绍一种近似算法的设计技巧: Rounding. 具体来说, 它有两种实现思路:Rounding solution. 以整数规划为例, 可以先求其线性规划松弛解, 然后对解进行四舍五入(同时保证可行性), 从而得到整数解.Rounding instance. 修改原问题实例然后求解, 同时保证解的可行性(对原问题而言). 修改实例的目的是使得问题更容易求解.背包问题考虑nnn个商品...

2020-04-22 22:34:34 3084 4

原创算法设计技巧: 深度优先搜索(DFS)

前文介绍了广度优先搜索(Breadth-First-Search)的方法遍历一个图G=(V,E)G=(V,E)G=(V,E). 本文介绍另一种常用的方法: 深度优先搜索(Depth-First-Search). DFS与BFS相比, 它的主要特点是遍历顶点的顺序满足一定的规律, 利用这些规律可以对顶点和边进行分类, 从而应用与其它问题的求解(参考下文).深度优先搜索通过深度优先搜索, 我们可以...

2020-04-19 19:22:05 997

原创算法设计技巧: 广度优先搜索(BFS)

给定一个图G=(V,E)G=(V,E)G=(V,E), 其中VVV代表顶点的集合, EEE代表边的集合. 给定初始点s∈Vs\in Vs∈V, 遍历图GGG所有顶点一般有两种方法: 广度优先(Breadth-first-search)和深度优先(Depth-first-search). 本文介绍广度优先的思想和实现方式.广度优先如下图所示, 从sss开始, 由内向外逐层搜索, 顶点所在的层数...

2020-04-15 21:29:09 438

原创算法设计技巧: 贪心算法(Greedy Algorithm)

贪心算法是一种启发式(Heuristic)算法, 它的基本思想是在每一步决策时选择局部最优的策略. 贪心算法一般在设计和实现上比较容易, 因此在求解实际问题中应用广泛.编码问题考虑如下的编码问题: 给定字符的集合CCC, 例如C={a,b,c,d,e}C=\{a, b, c, d, e\}C={a,b,c,d,e}. 每个字符α∈C\alpha\in Cα∈C的使用频次为fαf_{\alpha...

2020-04-15 21:26:22 1567

原创算法设计技巧: 动态规划 (Dynamic Programming)

动态规划(Dynamic Programming)是一种求解优化问题的技巧. 考虑这样一类优化问题: 原问题的最优解的结构包含了其子问题的最优解. 例如斐波那契(Fibonacci)数列, 已知F(n−1)F(n-1)F(n−1)和F(n−2)F(n-2)F(n−2)的值, 我们可以在O(1)O(1)O(1)内计算F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(...

2020-04-04 14:20:39 304

原创用正六边形分割地图

给定地图上的区域(用多边形顶点的经纬度表示), 我们用正多边形(三角形/正方形/六边形)对地图上的区域进行填充. 在一些实际应用中, 我们这样做的是为了提供标准的作业单元, 例如定义共享自行车的骑行范围, 物流的配送范围, 外卖骑手的接单范围等.效果如下:问题描述给定地图区域边界顶点的集合V={(x1,y1),(x2,y2),…,(xn,yn)}V=\{(x_1, y_1), (x_2, y...

2020-03-31 23:15:00 3379 4

原创算法设计技巧: 分治法 (Divide & Conquer)

分治法是一种非常通用的算法设计技巧. 在很多实际问题中, 相比直接求解, 分治法往往能显著降低算法的计算复杂度. 常见的可以用分治法求解的问题有: 排序, 矩阵乘法, 整数乘法, 离散傅里叶变换等. 分治法的一般思路如下:[Divide] 把原问题拆分成同类型的子问题.[Conquer] 用递归的方式求解子问题.[Combine] 根据子问题的解构造原问题的解.分治法最关键的步骤是如何...

2020-03-29 16:26:08 653 2

原创线性规划技巧: Dantzig&Wolfe Decompostion

介绍DW分解（含完整代码）

2020-03-24 21:03:13 4051 3

原创 Python的装饰器

在Python中使用装饰器可以在不修改代码的前提下为已有的函数添加新功能. 例如计算函数的运行时间, 打印函数的运行日志, 缓存数据, 用户授权等.为什么需要装饰器为什么需要把某个功能用装饰器的方式实现? 换句话说, 为什么不直接在函数中实现某个功能? 或者为什么不单独用一个类(class)来实现某个功能, 然后在函数中调用?以提供缓存功能的装饰器为例. 假如我们的业务代码负责向数据库读取数...

2020-03-23 20:07:46 181

原创一些聚类问题

假设我们是一家大型零售公司, 客户分布在全国各地. 为了方便管理和提供更好的服务, 我们需要把客户按照地理位置进行分类, 例如按城市或街道的维度把客户划分成区块, 每个区块是客户的集合. 主要考虑如下因素:区块包含客户的地理位置尽可能集中区块大小(客户数量)有限制客户有权重, 例如客户分为普通客户和VIP客户.下文总结几个可能需要求解的聚类问题.问题列表1. 等量的聚类问题(E...

2020-03-21 00:34:13 938

原创一些三维装箱问题

三维装箱问题在电商业务中有重要应用, 例如订单打包和商品装车. 下面我们列举一些电商业务中可能用到的三维装箱问题.基本概念首先我们把问题分为两类:判定问题(Decision Problem). 这类问题的答案只有两种: 是或否.优化问题(Optimiation Problem). 这类问题一般有一个优化目标, 问题的最优解使得目标达到最优.为了方便描述, 我们先介绍一些术语和假...

2020-03-20 19:30:43 7707 1

原创在线资料和工具

统计/预测课程 - STAT 501 - Regression Methods课程 - STAT 510 - Applied Time Series Analysis教材 - Forecasting: Principles and Practice算法CS 168: The Modern Algorithmic ToolboxORIE 6300: Mathematical Progra...

2020-03-20 19:29:16 162

原创一个三维装箱问题的搜索树算法

三维装箱问题的业务场景可以参考电商业务中的纸箱推荐问题. 文中考虑了如下问题.输入 : 长宽高为(L,W,H)(L, W, H)(L,W,H)的箱子和nnn个物品, 其长宽高为(li,wi,hi)(l_i, w_i, h_i)(li,wi,hi), i=1,2,…,ni=1,2,\ldots,ni=1,2,…,n. 假设物品是长方体, 长度不可变(没有弹性). 装箱时可以对商品进行90...

2020-03-20 17:52:04 7003 7

原创一个简单的零售经营模型

假设我们经营一家零售公司. 思考如下问题:如何分析成本结构?关注什么目标?如何用数据驱动的方式决策?我们把成本结构和业务目标称为经营模型. 本文的目的是抛砖引玉. 先给出一个简单的经营模型, 然后以试图解释数据驱动的决策.成本结构假设该零售公司的业务流程如下:我们考虑如下的成本结构.固定成本定义 : 支撑业务运转的成本, 不包含业务环节相关的成本. 它与存货数量无直接关...

2020-03-20 17:49:24 863

原创电商业务中的预测场景与实践

本文主要阐述预测技术在电商业务的应用场景, 实践思路和技术挑战. 一方面它列举了预测相关的业务场景和目标, 便于技术方案与业务目标保持高度契合; 另一方面它从技术的角度阐述了预测的方法和实践, 方便业务方了解技术的效果和瓶颈, 从而更好地利用预测数据.业务场景假设我们是一家自营电商. 基本的业务模式是向供应商采购商品, 然后通过自有渠道(例如APP和线下店)向用户出售商品. 在这个过程中, 我...

2020-03-20 17:48:16 1690 1

原创零售商品的定价策略

本文调研了经济学中常用的定价策略, 为了方便介绍, 把它们分为三类:基于用户心理的定价策略. 从心理学的角度分析用户的购买行为, 并制定相应的定价策略.基于企业长期利益的定价策略. 通过定价策略实现市场份额和销售利润的增长.基于企业短期利益的定价策略. 通过定价策略实现短期销售利润的最大化.注: 本文绝大部分内容参考自网络12.1. 基于用户心理的定价策略1.1 奇数定价(Odd ...

2020-03-20 17:45:58 3347

原创销量预测中的误差指标分析

引言本文介绍了一些销量预测相关的误差指标. 它们可以被分为两类: 绝对误差和绝对百分比误差. 前2节介绍销量预测问题及相关概念. 第3节我们介绍3种绝对误差, 并比较它们对异常值的敏感性. 由于绝对误差不适合比较多个商品或多个时段的预测结果, 在第4节我们介绍3种百分比误差. 在这一节, 我们重点强调了它们的优点和缺陷. 第5节是误差指标比较结果的汇总. 在第6节中, 我们用一个例子充分说明了百...

2020-03-20 17:44:34 3491

原创报童问题 (The Newsvendor Problem)

引言本文介绍了一个经典的商品采购模型(报童问题)及其解法. 该模型通过考虑需求的不确定性来最大化销售利润. 注: 本文的主要内容参考Gallego1.1. 报童问题这是一个关于卖报商人采购报纸的问题. 每天早上, 卖报商以批发价0.3元(每份)向报社采购当天的报纸, 然后以零售价1元(每份)进行售卖. 如果报纸在当天没有卖完, 他会把报纸以0.05元(每份)的价格卖给废品回收站. 那么卖...

2020-03-20 17:42:26 20128 1

原创如何在商品采购中考虑不确定性

商品采购是库存管理的重要环节, 它的主要内容是制定商品的需求计划, 向供应商下采购单, 协调相关的资源(供应商, 人力, 车辆等), 最终满足企业在成本, 质量和效率等方面的综合指标. 本文探讨如何在采购时考虑销量的随机性, 从而降低库存管理的风险.1. 销量预测销量预测是制定需求计划的重要工具. 常见的做法是预测未来一段时间的总销量值作为需求. 因此销量预测的准确度直接决定了库存的风险:...

2020-03-20 17:40:11 2167 3

原创时间序列模型简介

目录平稳序列判断样本的平稳性时间序列模型参数选择实验代码1. 平稳序列时间序列是一列观测值XtX_tXt的集合, 其中每个观测值是在时段ttt观测所得(ttt是自然数 ). 给定时间序列{Xt}t=1n\{X_t\}_{t=1}^n{Xt}t=1n, 如果对任意的t=1,…,nt=1,\ldots,nt=1,…,n, 它满足下列条件:i. var(Xt)<∞\tex...

2020-03-20 17:35:19 2435

原创电商业务中的纸箱推荐问题

背景在电商业务中, 一个核心的生产环节是打包: 把用户购买的商品打包装入纸箱.纸箱成本一般与纸板面积成正比. 为了节约打包成本, 我们希望从候选纸箱中选择最小的纸箱来装用户购买的商品. 在实际操作中, 工人一般倾向于选择较大的纸箱, 不仅能减少选择纸箱的时间, 而且能降低装箱难度, 从而加快生产效率. 但这样做会显著增加生产成本.能不能利用算法来告诉工人如何选择纸箱, 从而节约纸箱成本?...

2020-03-20 17:30:39 2773 4

原创博弈论在零售业务中的应用

在零售业的供应链管理中, 我们经常会遇到一些资源分配问题, 例如商品的供需平衡, 销售利润分摊, 运输成本分摊等. 常见的分配方式有平均分和按权重(比例)分. 在某些应用场景下, 我们需要体现分配方案的"公平性", 那么如何科学地定义公平性, 又如何计算公平的分配方案? 本文从合作博弈论的角度思考如何解决这些实际问题.1. 合作博弈考虑某个自营电商的销售场景: 电商平台(例如网易严选)从供应...

2020-03-20 17:24:07 791

原创破产问题 (The Bankruptcy Problem)

我们从2000年前古巴比伦犹太法典《塔木德》(Talmud) 中描述的一个案例为出发点, 介绍一种资源分配的策略. 从合作博弈论的角度来理解, 这种分配策略是Nucleolus分配. 值得一提的是, 我们已经在供应链相关的多个业务场景中使用该资源分配方案.注意: 本文绝大部分内容参考了Robert J. Aumann和Michael Maschler 1.1. 争大衣问题《塔木德》2源于公元...

2020-03-20 17:19:06 1277

原创库存平衡与调拨系统的算法架构

1. 业务背景电子商务公司或传统零售公司在生产销售中, 一般会自建或租用多个仓库来存储商品. 这些仓库一般分布在不同地区用来覆盖区域中的客户. 当客户下达订单后, 商品一般会从客户所在区域的仓库发货, 然后通过承运商送达客户手中. 由于不同客户购买的商品和数量可能不同, 因此单个仓库的商品可能会发生供需不均的情况.例如, 某个商品在仓库A发生了缺货, 但在仓库B却可能产生积压. 这样一来, 仓...

2020-03-20 17:16:29 2740

原创编程思想: 面向切面编程(Aspect-Oreinted Programming - AOP)

面向对象编程(Object-Orentied Programming - OOP)的特点是继承, 多态和封装, 其中封装指的是把属性和方法按类(Class)进行划分, 从而复用代码并降低编程的复杂性. 随着业务的变化, 项目中的类越来越多, 开发者又发现了新的问题:不同类之间重复的代码越来越多. 例如每个类的方法中都要打日志.方法中除了业务逻辑之外, 要实现大量与业务无关的功能, 例如调试,...

2020-03-19 23:28:23 441 2

原创编程思想: 控制反转(Inversion of Control - IoC)

本文参考PHP开发框架phalcon的文档1. 它从一个简单的例子出发, 描述了编码中遇到的一系列问题, 然后一步步去解决, 最后得到一个解决方案. 在这个例子中我们了解到:一种设计模式: 依赖注入(Dependency Injection)控制反转是什么?控制反转是为了解决什么问题?在这个例子中, 我们要写一个类SomeComponent来实现某个功能. 由于它依赖连接数据库, 我们...

2020-03-19 23:26:47 357

原创面向对象设计原则: The SOLID Principles

本文主要参考Robert C. Martin. Design Principles and Design Patterns1和butUncleBob.com2.设计糟糕的表现(Symptoms of Rotting Design)僵化(Rigidity)软件变得难以修改, 每次修改都会造成对应依赖模块的修改. 换句话说, 模块之间耦合性太严重, 因此在中大型项目中多人合作难以协同.脆弱(F...

2020-03-19 23:24:48 516