多产品报童问题的直接搜索算法求解.pdf
《多产品报童问题的直接搜索算法求解.pdf》由会员分享,可在线阅读,更多相关《多产品报童问题的直接搜索算法求解.pdf(5页珍藏版)》请在咨信网上搜索。
1、收稿日期:基金项目:国家自然科学基金(;)作者简介:郝爽(),男,山西太原人,上海交通大学安泰经济与管理学院博士研究生,研究方向:供应链管理、随机优化。文章编号:()市场营销多产品报童问题的直接搜索算法求解郝爽张大力董明(上海交通大学 安泰经济与管理学院,上海 )摘要:多产品报童问题假设商品需求服从已知分布,在实践中难以直接应用,可将零售商收益视作表达式未知的随机黑箱函数,通过样本均值对收益的期望进行近似,并利用直接搜索算法最大化零售商收益。数值实验表明,直接搜索算法结合可变数量的样本均值近似可在样本数量极为有限的条件下有效求解多产品报童问题,且求解质量优于已有的启发式算法。关键词:多产品报童
2、问题;随机黑箱优化;直接搜索算法;可变样本数量中图分类号:文献标志码:犎犃 犗犛 犺 狌 犪 狀 犵犣犎犃犖犌犇 犪 犾 犻犇 犗犖犌犕 犻 狀 犵(,):,:;引言报童问题是经典的随机库存管理模型,其基本假设为产品需求为分布已知的随机变量,当订货量过剩时,未售出的商品具有一定的残值,当订货量不足时,未满足的需求将产生惩罚成本,零售商需事先决定产品的订货量以最大化期望收益。报童问题假设产品需求为分布已知的随机变量,在实践中难以直接运用,解决方法主要有三类:一是利用历史数据对需求的分布类型、未知参数进行估计,或以经验分布对需求的累积分布进行近似,此类方法的求解效果依赖于估计量的质量,在小样本情况
3、下求解质量较差;二是各类数据驱动方法的应用,即利用机器学习或人工智能算法对需求进行预测,或对预测模型及库存决策进行联合优化,由于训练预测模型需要使用大量历史数据,以及与需求相关的其他类型数据,所以此类方法对于数据的质量及规模具有更高的要求,实际应用的难度更大;三是鲁棒优化方法,即利用历史数据的统计特征构建满足条件的分布集合,并最大化最差情况的期望收益,但所得的解往往过于保守,实际应用价值不高。实践中零售商通常同时销售多种产品且面临某种资源约束,例如采购成本不能超过预算或库存容量不能超过最大库容,因此多产品报童问题的应用更为广泛。多产品报童问题可分解为报童问题,并分别计算各产品的最优订货量,若能
4、够满足资源约上海管理科学 第 卷第期 年 月 束则求得最优,否则可通过拉格朗日乘子法求解,但高效准确求解拉格朗日乘子较为困难。文献、分别求解了产品需求服从特定类型分布且参数已知时的多产品报童问题,文献 设计了多种启发式方法求解多产品报童问题,其中部分方法仅使用需求量的均值和方差,因而简单易用,数值实验表明在不假设需求量分布已知的前提下,文献 的启发式算法可求得较好的近似解。有别于上述研究,本文假设零售商仅有各商品需求量的少量历史数据且商品需求量的分布未知,将零售商的收益视作随机黑箱函数,利用直接搜索算法进行求解。在直接搜索算法的每轮迭代中,通过控制样本的数量,利用有限的历史数据构造期望收益的样
5、本均值近似。本文提出的方法无须假设商品需求分布已知,数值实验表明在历史数据有限的情况下本方法仍然可以求得高质量的近似解。模型 具有资源约束的多产品报童问题具有资源约束的多产品报童问题描述如下:零售商同时销售狀种产品,产品间不存在需求的替代及互补效应;零售商在销售期前决定各种产品的订货量犙犻,犻,狀;对于产品犻,其需求量狓犻为随机变量,具有概率密度函数犳犻();产品犻的采购成本、销售价格、未售出残值及缺货惩罚分别为狏犻、狆犻、犵犻、犅犻;零售商具有某种资源约束,其资源总量为犛,单位产品犻的资源消耗量为狊犻。产品犻的收益函数为:犻(犙犻,狓犻)狆犻狓犻狏犻犙犻犵犻(犙犻狓犻),犙犻狓犻狆犻犙犻狏犻
6、犙犻犅犻(狓犻犙犻),犙犻狓犻()产品犻的期望收益为:犈犻(犙犻)犙犻狆犻狓犻狏犻犙犻犵犻(犙犻狓犻)犳犻(狓犻)狓犻犙犻狆犻犙犻狏犻犙犻犅犻(狓犻犙犻)犳犻(狓犻)狓犻()具有资源约束的多产品报童问题优化模型为:狀犻犈犻(犙犻)狀犻狊犻犙犻犛()随机黑箱多产品报童问题为方便表述,下文将零售商的期望收入最大化问题转为最小化问题,同时针对资源约束狀犻狊犻犙犻犛,引入惩罚因子,具有资源约束的多产品报童问题可表示为:犌(犙,犙狀)犈犵(犙,犙狀,狓,狓狀)()其中,犵(犙,犙狀,狓,狓狀)狀犻犻(犙犻,狓犻)狀犻狊犻犙犻犛,为随机函数,当随机需求狓犻,犻,狀的分布函数犳犻(),犻,狀未知时,犌(犙,
7、犙狀)的表达式未知,问题()是一个随机黑箱优化问题。将多产品报童问题视作随机黑箱问题为建模及实际应用提供了诸多便利。首先,随机黑箱问题假设随机参数的分布未知,避免了由参数估计造成的解的质量下降;其次随机黑箱问题不要求目标函数具有明确的表达式,对于替代性需求、需求依赖价格、存在其他随机参数等不同类型的报童问题同样适用,扩展了模型的应用范围。具有可变样本量的直接搜索算法由于黑箱函数的表达式未知,无法利用各类基于梯度的优化方法求解,所以其求解主要通过各类无梯度优化方法,包括随机近似、响应面法、信赖域法及各类直接搜索算法,例如单纯形搜索、广义模式搜索、网格自适应搜索,其中直接搜索算法由于易于实现、鲁棒
8、性强,得到了广泛应用。直接搜索算法属于迭代算法,通过比较当前解与一组候选解的目标函数值,逐步更新当前解以及步长等算法参数。针对随机黑箱问题,目标函数值无法准确计算,需要以样本均值对目标函数值进行近似。以问题()为例,假设商品需求的样本为狓犼犻犻,狀;犼,犿,其目标函数的样本均值近似为:珚犌(犙)犿犿犼狀犻犻(犙犻,狓犼犻)狀犻狊犻犙犻犛,()其中,犙犙,犙狀。等研究得出了达到给定近似精度所需的样本数量,但实际问题中的样本数量往往较少,难以满足精度要求。本文依据 等提出的直接搜索算法框架,针对问题()设计了具有可变样本数量的直接搜索算法,步骤如下:算法具有可变样本数量的直接搜索算法初始化初始可行
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 产品 报童 问题 直接 搜索 算法 求解
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。