数据带你领略，超市货架的摆放艺术

定义我们的问题

在商店里，一个产品的位置很大程度上影响了它的销售情况。为不同的产品，不同类别分配适当的空间和布局，在零售业中起着至关重要的作用。从零售商的角度来看，鉴于货架位置的价值，确保零售空间的充分利用，对于商店价值最大化的工作至关重要。

一般来说，POS机附近的货架会为客户提供最大的曝光度。顾客在排队结账时客观上必须浏览这些列表商品。尽管这些商品的价格只有几块钱，如果在正确的时间，正确的地点，以正确的数量销售正确的商品，就可以帮助商店卖出更多的商品，这是零售业收入和盈利能力的关键。

这一方面导致了品牌间的战争——胜者才能占据商店中最好的展示位；另一方面，商店也需要考虑到所有不同商品的销售情况，通过整体规划优化其盈利能力。

虽然这个逻辑很好理解，但应用起来可并不简单。空间优化所需的信息在整个业务中的大部分时间都是模糊、复杂、分散的。某些产品在整个营销中可能扮演的是至关重要的角色; 其他产品可能只是附属品，用来提供更高的边际效用。因此，仅仅使用一个变量来衡量他们就变得非常困难。更何况，平均一个零售商店里就有将近3万个SKU（stock keeping unit库存单位）。每年在零售店还会推出数千种的新产品。面对如此大数据量的问题，优化就变得非常困难。

但是我们的目标很明确：就是通过整合摆放策略，最大化超市的销售总额。

用线性规划来优化的策略

在分析正式开始前，我们再来说一点基础知识。首先，什么是优化呢？说起来很简单，优化就是在特定约束条件（constrains）下找到最佳解决方案的科学过程。

我们每天其实都会遇到各种优化的问题。优化可以是找到工作场所和办公室之间的最短路径; 可以是最大限度地提高收入/客户的幸福感，或者最小化成本/债务，不一而足。一句话，优化就是把一个真实世界的问题，用数学的方法进行建模，然后用数学方法在约束条件下求解。优化在市场营销，制造业，金融，在线广告，机器学习以及任何你可以想象的所有领域都很有用。

线性规划（Linear Programming，也称为线性优化）是指在需求由线性关系表示的数学模型中实现最佳结果（如最大利润或最低成本）的方法。线性程序可以表示为：

1. 决策变量

2. 目标函数：必须是线性的

3. 限制：必须是线性等式或不等式。

线性规划算法在可行空间中找到一个点，其中如果存在这样一个点，则目标函数具有最小（或最大）的值。单纯形法（simplex algorithm）是最常用的线性规划算法。

整数规划是线性规划的一个特殊情况，其中决策变量被限制为整数。对于整数规划的问题，我们一般只有二元输出结果，即非0即1。

下面我们就以一个简单的例子来说明优化是具体如何操作的。这虽然是一个很小的问题，但是相同的概念可以被扩展到更大的问题上。让我们现在小数据的情况下来了解问题。

假设一个有3个货架的零售店：货架1，货架2和货架3。每个货架分别有3个、3个和4个架子（如下表所示）。我们必须出售3家公司的产品：Unilever（联合利华，英荷联合公司），Godrej（戈德瑞，印度公司）和Dabur（印度草药公司）。Unilever, Godrej和Dabur三家公司分别有3种、3种、2种不同的产品。

我们在矩阵中看到的数字是将特定产品放置在特定一排（rack）中的特定一个货架（shelf）上实现的销售增量（lift）。

现在，由于产品的利润率/库存成本/需求/过期时间等差异，商店希望优化每个产品在货架上的位置，并最大化销售总额（产品数量），同时考虑到一些已有的限制条件。

决策变量将采用与lift矩阵（10* 8）相同大小的矩阵的形式。矩阵内的元素是一个二元变量：1表示产品/货架的匹配是对的（Yes）；0表示产品/货架的匹配是错的（No）。我们将从所有元素都是0的矩阵开始，并允许求解器在需要时更改为1。

要注意的是：我们目标函数的目标就是最大化所有商品的总销售额。

这里用的限制是：

1. 一个货架（shelf）上最多只能有某个公司的一个产品（行约束）

2. 产品不能摆放超过一定数量的货架。这是按照上图所示的产品顺序给出的列约束。产品的最大出现情况如下。这些限制可以归因于产品类型/利润率/需求或任何其他适用于商店的理由。

上图的意思是是联合利华的产品1不能销售一次以上；Godrej的产品1不能上架超过两次。其他情况依次类推。（根据不同商店对不同商品的策略和理解不同，实际情况中可能会有多种多样的限制。但我们这里只是希望展示如何实际解决线性优化的问题，所以就只给出一个简单的限制条件。）

当我们确定了目标函数、限制约束条件后，这种简单的线性优化就可以使用EXCEL中的solver功能进行操作。我们最终目标函数算出来最大的销售量是4197。最大情况下给出的决策矩阵如下图。

但是Excel有个致命的缺陷，就是它无法处理大样本的数据。另外，如果有很多限制条件的话，Excel跑起来也会非常地吃力。但还好我们有Python来救场。

数据太“大”怎么办？Python说这个它能干

用EXCEL来进行优化太繁琐了，不利于用于日常操作。Python可以很容易地解决数据大小的问题，只会受到计算速度的限制。此外，一旦编码/自动化，这个程序就可以应用于任何数据量的问题；任何新的约束条件也可以随时加入进来。

在这里，我使用了python中的Pulp库。求解器（solver）我用的是开源的CBC。当然还有其他一些商用的solver，如CPLEX，GUROBI等，这些solver可用于data size的问题，因为它们的速度更快，结果更好。

当我们重复一遍上述过程后，你会发现Python得到的结果和Excel得到的结果完全一致。再次印证了结论，4197是总销售增量的最大值。

现在我们来讨论下大数据会带来什么样的问题。在这个例子中，我们知道每个决策变量可以取值为0或1，即2 ^ 1也就是2个可能的值。如果现在是2个决策变量，可能组合的总数可以是2 ^ 2也就是4，其中一个/多个都可以给出目标函数的优化值。当情况需要考虑的有80个决策变量时，总的组合是2 ^ 80。决策变量增多带来的问题是指数性增加的而不是线性的。（用计算复杂性理论（Computational complexity theory）的理论来说，就是指数时间算法O（2 ^ n）]。即使是最好的电脑，指数时间算法的问题也是非常大强度的。正如在我们的例子中，所有2 ^ 80组合都需要被评估以找到优化的解决方案。）

这里开始就需要商业理解和专业知识的帮助了。一名行业专家可以很快地排除掉不合适的组合，通过使用合适的约束条件，减少需要排查的可能组合的总数，从而大大降低了计算量。

生活中无处不在的“优化”商机

上面我们展示优化问题的基本实现过程，接下来让我们来了解优化问题在其他领域的一些应用。

谷歌的AdWords：Google使用线性规划来优化在线广告。Google在其搜索页面上有不同的广告窗口，并基于PPC（每次点击的价格），CTR（点击率）和广告客户的预算——这些约束条件，来分配广告窗口和播放次数（这个是决策变量）以最大化其收入（目标函数）。AdWords帐户约占Google收入的97％。

航空公司的收益管理（Revenue Management）：航空公司使用线性优化来决定提供多少打折机票（决策变量），在考虑到预测的需求（约束条件）和飞机型号（有限的座位，也是约束条件）情况下，最大化其收入（目标函数）。

癌症治疗：线性规划用于通过辐射来治疗癌症患者。在有限的辐射水平下（约束条件）向肿瘤细胞进行靶定位辐射，并且同时健康组织应暴露于最少量的辐射下（使目标函数最小化）。

电视频道的推广广告：一个电视频道有数十个节目，但却有数以千计的促销，且广告需要在这几十个节目中穿插。通过线性优化，他们决定在哪个广告位进行电视广播，并保持高收视率（目标函数）。这里的约束条件可以是每次广告的预算，一个广告最大的出现次数等等。

约会网站：线性优化也被用于线上约会网站，比如eHarmony。基于每个用户填写的问卷，eHarmony计算两个人之间的匹配值，并使用线性规划等优化算法来确定用户的最佳匹配对象。这里可能的限制是男性只与女性相匹配; 男性用户需要匹配的是女性，反之亦然。

这次给大家演示的只是一个非常简单的例子，如果是真实的货架优化问题，那涉及到的可是成百上千个货架。而相应的约束条件也会增加到成百上千个。所有这一切的目的就是让一个商品出现在正确的地方，从而使得销售量最大化。

（注：本文仅代表作者观点。）

备注

1. 本文编译自 Deepesh Singh 的博客文章 A Beginner’s guide to Shelf Space Optimization using Linear Programming，文中图片除特殊标注外，均来自原文。

2. 在原文中，作者详细地列出了EXCEL和Python的操作代码及步骤，为了保证阅读流畅度，我们没有将其罗列在文中。感兴趣的读者可以阅读原文重复作者的步骤

3. 在优化货架问题中，作者还尝试了“贪婪算法”来代入优化模型。不过贪婪算法本身的算法逻辑并不适合本文的整体优化问题，DT君编译时省略了这部分尝试的内容。

数据侠门派

本文数据侠 Deepesh Singh 是一位数据科学爱好者。他是一名持续的学习者，热爱探索数据科学的不同领域。他是NIT Silchar的一名工程师，拥有IIM-L和KSB（印第安纳大学）商业分析一年的证书，目前正在解决分析机构班加罗尔办事处的业务问题。在工作之外，他喜欢会议主持人，在健身房锻炼，练习、教导空手道。

加入数据侠

数据侠计划是由第一财经旗下DT财经发起的数据社群，包含数据侠专栏、数据侠实验室系列活动和数据侠联盟，旨在聚集大数据领域精英，共同挖掘数据价值。申请入群请添加微信公号dtcaijing002并备注“数据社群”，合作请联系datahero@dtcj.com。

DT字幕组

感谢“数问”团队对本文的翻译贡献。

数问数据科学平台是一个一站式数据玩家的驿站，目前有问答，竞赛，工作，线下活动等内容版块。任何数据爱好者都都可以在平台，提问题、找答案、分享学习资料、经验、对接资源等。他们希望帮助给各个阶层的数据使用者解决“从哪里来”，“到哪里去”的问题。欢迎登录数问的网站，针对数据分析提出你的各种疑问，会有各路高手过来解答。

“DT字幕组”致力于发掘和传播全球数据领域的优质内容，长期招募组员，欢迎邮件联系：chengyixiang@yicai.com。

（了解更多有趣又有料的商业数据分析，欢迎关注DT财经微信公众号“DTcaijing”，下载“DT·一财”APP）