英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
产品协同下的logit回归模型分类优化
Assortment optimization under the multinomial logit model with product synergies
摘要
在协同分类优化中，一个产品的吸引力随着其他产品的提供而变化。我们用图形表示协同结构。顶点表示产品。优势是指两种产品之间的协同作用，当两种产品同时提供时，会增加它们的吸引力。一般来说，找到一个能使零售商预期利润最大化的商品组合是NP-困难的。当图形是路径、树或树宽较低时，我们提出了有效的算法。给出了一个恢复路径最优分类的线性规划。
关键词
分类优化，协同，多项logit模型
1.简介
模仿顾客的购买行为在零售经营中是至关重要的，因为它影响了零售商为了最大化利润而提供何种产品的决策。早期的库存管理工作假定需求独立于所提供的分类。收入管理的后续工作认识到，如果客户有更多的选择，对产品的需求可能会减少。然而，大多数选择模型不考虑协同效应。协同作用可以增加对产品的需求，当它与其他产品一起出现时。
我们研究了多项式模型(MNL)的一个协同版本下的分类优化问题。客户将偏好权重与每个产品相关联，并且偏好权重可以通过协同作用增加。当零售商在他的分类中同时提供两种产品时，即使顾客最多购买一种产品，也会产生协同作用。其中一个产品的购买概率可能增加或减少，这取决于偏好权重的增加和另一个产品的权重。市场调查显示，零售商可以通过提供不太吸引人的产品来突出目标产品来增加需求。分类优化问题是为了使零售商的期望利润最大化，选择要提供的产品子集。
我们的意义：我们考虑一个零售商售卖产品。每个产品都有一个基本偏好权重，它描述了客户在单独查看产品时的偏好。每对产品，和，也有一对协同权值，它描述了如何协同从产品作用于，反之亦然。一个产品的购买概率与它在提供的分类中的偏好权重成正比。我们使用一个图来描述具有正协同作用的成对产品，当它们一起被看到时。对于一般协同图而言，协同MNL下的配组优化问题是NP-hard问题。我们限制了协同作用下的产品对，并研究了协同路径和协同树的特殊情况。我们提出了一种通过动态规划来寻找最优商品组合的算法，该算法的运行时间是产品数量的多项式。我们扩展了我们的动态规划来考虑具有低树宽的协同图。在协同路径的情况下，我们提出了一个线性规划，可以恢复最优的品种。
文献综述：本文的灵感来自于[9]基于福利的选择模型。作者引入了一个福利函数，它将商品分类的福利定义为其产品效用的函数。购买概率由各产品的福利函数梯度给出。福利函数有三个性质。当所有效用增加时，单调性保证了福利增加。平移不变性表示，如果所有效用增加相同数量，则购买概率保持不变。凸性确保一个高效用产品比多个低效用产品更能提高福利。
作者定义了基于福利的选择模型的运算，建立了新的基于福利的选择模型[9]。一个结果模型是我们协同MNL的基础。在他们的模型中，如果两个产品产生协同作用，那么它们的协同权值之和等于它们的基本偏好权重的加权几何平均值。我们允许协同权值为任何非负的值。他们专注于定义一种新的选择模型，而没有考虑分类优化。我们集中讨论后一个问题。
协同作用的证据存在于营销文献中。当一种劣质产品被引进时，产品的销售量会增加。在一项研究中，一个卖面包机的零售商给他的商店引进了第二个价格过高的面包机。尽管面包种类增多了，但对原来的面包机的需求还是增加了。有些产品会引发偏好的改变[11]发现，如果餐厅提供苹果酱，饼干销量会增加，但如果提供绿豆，饼干销量不会增加。
传统的选择建模方法是通过效用最大化。在随机效用模型中，顾客对产品的效用是其平均效用加上随机噪声的总和。MNL是这类中最著名的模型，每个产品的随机噪声服从一个独立的标准耿贝尔分布[15]，[18]。一个产品的偏好权重是它的平均效用的指数，它的购买概率与它在分类中的偏好权重成正比。MNL具有无关替代(IIA)属性的独立性：无论提供什么其他产品，两种产品的购买概率之比是不变的。
我们的模型遵循MNL，即购买概率与偏好权重成正比，但不受IIA的约束，因为协同作用会增加产品的偏好权重。我们描述了对MNL的扩展;这些选择模型的细节可以在[26]中找到。在嵌套的logit模型中，产品通过相似性被划分到嵌套中。客户选择一个商品分支，然后在她选择的分支中选择一个产品。零售商可以通过分支添加产品来增加客户选择该分支的概率，但这可能不会增加单个产品的购买概率。事实上，将协同合并到嵌套的logit模型中可能会牺牲它的效用最大化属性。嵌套的logit模型已经扩展到d（dgt;2）级嵌套的logit模型，在广义极值模型中，产品属于多个集合[26]。
在混合logit模型(MMNL)中，不同的客户类型有不同的偏好权重集[5]、[17]、[21]。MMNL可以近似任何随机效用选择模型[17]，而[6]给出了一个全多项式时间近似方案(FPTAS)来计算保证分类—最佳预期利润的一部分。
效用的随机噪声不一定服从耿贝尔分布。在概率模型中，噪声服从多元正态分布，模型不具有IIA特性[25]。随机效用模型类外的选择模型包括马尔科夫链选择模型[1]、[8]和非参数选择模型[12]、[16]。[7]研究了一个非参数选择模型的特殊情况，其中客户为一些小的，固定的最多考虑种产品。
我们的基本参数问题要求在二元变量下最大化二次函数。无约束二次二进制规划是NP-hard规划，可以写成整数规划。该问题可以根据其底层图(其中顶点)进行分类，顶点代表变量，如果二次项的系数存在是非零的，边存在。[19]研究了图和相关的整数规划，确定了可行域的顶点集合是整数的情况。利用该方法对协同MNL下的产品分类优化问题进行了分类，有效地解决了协同MNL下的产品分类优化问题。二次二进制规划的调查可以在[13]中找到。
我们在协同路径下寻找最优分类的线性程序类似于[10]描述的基于销售的线性程序(SBLP)。作者研究了MNL推广下的网络收益管理问题，其中零售商在资源约束下随时间提供分类。当有一个销售周期，然后他们的SBLP恢复为他们的模型的最佳分类。我们构造我们的版本的SBLP采取对偶的线性规划公式化的动态规划。
组织:在第二部分，我们描述了协同MNL模型及其相应的参数问题，以及协同图。在第三节中，我们重点讨论协同路径和协同树，并使用动态规划来解决参数问题。在第四节中，我们提出了一个线性程序，当我们有一个协同路径时，可以恢复最优的搭配。在第5节中，我们考虑了协同权的其他形式，并将协同作用合并到MMNL中。我们在第6节结束。
2.一般模型和np -难度
对一般模型和参数化问题进行了描述，证明了一般协同作用下的分类优化问题是np -困难的。
2.1模型
零售商可以获取n种产品：。产品被顾客购买时产生利润。我们不需要对于所有的产品，只需要至少有一种产品利润为正。请注意，如果零售商增加了高利润产品的需求，他们可以提供负利润的产品。零售商从中集合挑选一个商品类，我们用一个二进制向量来表示这样产品在分类时否则。
我们用偏好权重来描述顾客的偏好，而购买概率与这些权重成正比。产品的偏好权重是分类的功能，因为来自其他产品的协同作用可以增加其偏好权重。当产品是唯一在分类的产品时，基本偏好权重为。当产品添加到分类中时，产品和之间的协同作用能增加产品的偏好权重。我们用表示产品对产品有协同效应，用定义产品作用于产品使其增加的偏好权重。给定一个分类，产品被提供时的偏好权重是。
我们在第5节中讨论了负协同权的可能性，但是我们指出了通过设置和，即便在相反的方向没有协同，产品为产品创造协同效应是可能的。当产品添加到分类中时，卖出产品的概率可能增加，但产品添加到分类时，卖出产品j的概率不能增加。
当面临各种分类，无购物选项时，顾客购买产品的概率与产品的偏好权重成正比。无购物选项是顾客可以没有购买就离开商店。我们将不购买选项的偏好权重调整为1，而不损失一般性。与分类对应，顾客购买产品概率是:
客户最多只购买一种产品，而协同只是让产品在同时提供时看起来更有吸引力。零售商的问题在于怎样找到一种分类使他的期望利润最大化：
为了使概念更清晰，我们定义为产品和利润的加权平均值，为产品和同时出现时，由于协同作用而使产品组合偏好权重增加总和，并且约束。当时，双方都没有协同作用，因此且。否则定义且。
在以上定义下，我们分类优化模型目标函数表达式为：
2.2参数问题
我们将标准参数化技术应用于分数组合问题[20]。假设存在一个分类预期利润大于或等于。通过重新排列,我们观察到：
我们可以所有分类的左边最大化，不平等性仍然存在。问题(1)所对应的参数问题是：
声明1：定义如上所述，产品分类优化问题的最优预期利润为，下述为真：
假设我们可以用相应的最优的客观价值解决问题(2)。因为，是单调递减到0，找到的一个方法是牛顿的方法。用定义一组的数量，并且。我们可以把通过引入新的二进制变量和约束用线性函数重写分子分母里的二次函数[19]。牛顿的方法是在对的迭代计算找到，此时可行域为的一个子集。因此，对于一般的协同图，如果我们能在多项式时间内解决问题(2)，我们就能在多项式时间内解决问题(1)。
不幸的是，问题(2)是二次二进制编程的特例，一般是np-困难的[13]。通过对极大独立集问题的约简，在下一个定理中证明了问题(1)是np-困难的。所有的证据都能在网络上补充。
定理2：协同MNL下的分类优化问题是NP困难
相反，一种来分类二次二进制程序和识别可以多项式时间内解决的案例的方法就是考虑底层图。构建一张图表，顶点代表变量并且如果二次项的系数非零，则一条边从顶点延伸到。在问题（2）中，系数随着而改变，我们想要考虑所有可能值的二次二进制程序，因此我们增加一条边并且任何时候下。这样且，且，我们将这张图称为协同图（图1）
图1：五种产品的协同图，顶点代表产品，边代表这些产品的协同作用，在参数问题里，顶点值分别为和，边值为
不断增加的烘烤区域amp;权重
图2：便携式格栅的协同图是垂直分化—箭头指向协同创建的方向。
从这里开始，我们用图表概念来表示问题(1)和(2)，除非G是一条路径，使得产品有一个清晰的顺序。
如果我们的协同图至少有两个组件，那么问题(2)可以分解为更小的子问题，这些子问题只包含组件中的产品。在不失一般性的前提下，我们假设我们的协同图是连通的。实际上，在任意对产品之间不存在协同作用。我们将重点放在协同图是路径或树的情况下，并扩展我们的结果以考虑具有低树宽的协同图。
3.基于协同路径和树的分类优化
当协同图是路径、树或树宽较低时，我们给出了求解问题(2)的动态规划。
3.1协同路径
协同路径对垂直差异化的产品进行建模。考虑图2中的便携式烤架，它们的重量随着烹饪面积的增大而增加[22,24]。一个中型烧烤被视为一个极端的选择时变得更有吸引力，因为它提供了两个特点之间的一个妥协。在存在A的情况下，B可能感觉更大，因为它不是最小的选项[24]。在有E的情况下，D可能感觉更轻，因为它不是最重的烧烤架。在这个例子中，A的存在对B产生了正的协同作用，E的存在对D产生了正的协同作用。
由于协同图是一条路径，我们能将产品排序，这样产品只对产品和产品产生协同作用，但我们考虑协同路径时，使对所有有和。问题（2）简化为：
我们使用动态规划计算的值。对于，定义值函数为产品到能给问题（2）的目标函数实现的最大值，规定产品定状态为。在产品1中，没有需要考虑其状态的前产品。我们将产品和之间的协同作用归因于产品，并给出了决策。因此,我们价值函数可以写成如下，
一旦我们决定是否提供产品，产品的存在与否不影响产品到，。如果产品被提供，那么它的贡献是。第一项是产品和之间的协同作用，这是在决定提供产品的情况下。第二项是产品的基础贡献。我们可以使用和的定义重写价值函数来得到动态规划。
我们的基本情况是，我们从产品到向后进行动态规划计算。如果我们决定，那么，我们立即失去产品和产品的协同以及产品基值。如果我们决定，然后。
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[239358]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
