供应链管理中的两层规划算法-《物流科技》(2007年11期).docx

龙源版权所有 供应链管理中的两层规划算法作者：徐鸣昊　马晓伟来源：《物流科技》2007年第11期 摘要：文章概述两层规划问题在交通领域、资源分配、委托代理以及供应链管理中的应用并讨论了线性和非线性两种两层规划问题，总结了极点算法、下降迭代、惩罚函数和分支定界算法，并进行了评价，最后进一步探讨了两层规划问题的应用前景和算法的发展方向。 关键词：两层规划；启发式算法；博弈决策 中图分类号：F224 文献标识码：A 文章编号：1002-3100(2007)11-0055-04 Abstract: This paper describes bilevel programming and its application in transportation, resource allocation, principal-agent problem and supply chain management. Both Linear and nonlinear programmings are discussed. Pole algorithm, descending iteration algorithm, penalty function algorithm and branch and bound algorithm are presented and evaluated. At the end of the paper, we also discuss the development direction of bilevel programming and its algorithms. Key words: bilevel programming; heuristic algorithm; game theory 供应链管理指的是对各个设施点之间的物流及信息流进行管理，如供货商、制造商、加工商、分销中心等。在早期的供应链管理中，一般是指局限于对供应链中的每个节点单独优化，而很少考虑供应链节点之间的互动。但随着研究的深入，人们认识到如果对供应链的各个阶段加以集成和协调，将会明显地降低整个供应链的运营费用，提高客户服务水平，从而增强企业的竞争力。尤其是在引入博弈论之后，对供应链之间的博弈决策，并在此基础之上协调整个供应链利益的研究也越来越多。而两层规划算法正是求解博弈问题的一种非常有效的方法。 两层规划是两层决策问题的数学模型，它是一种具有两层递阶结构的系统优化问题，上层问题和下层问题都有各自的目标函数和约束条件。上层问题的目标函数和约束条件不仅与上层决策变量有关，而且还依赖于下层的问题的最优解，而下层问题的最优解又受上层决策变量的影响。下层根据上层的决策结果调整策略使自己的利益最优化，上层根据下层的反应重新做出决策。整个系统在双方博弈中，达到各自满意状态。两层规划的研究起源于经济问题，如有限资源在各自部门中的分配，价格控制问题的研究等。但是两层规划求解是非常复杂的，即使当系统的上、下层的目标函数和约束条件都是线性的，整个系统也可能是非凸问题，并且是处处可微的，所以两层规划虽然在现实世界中有广泛的应用，但是由于其计算的困难性，包括它的非凸性，NP困难性以及它的一些算法的无效性，使得两层规划的理论研究仍有待进一步发展。本文将从两层规划的实际应用和启发式算法发展两个方面对两层规划进行综述。 1两层规划的实际应用 1.1交通领域的应用 兩层规划在交通控制中有着很广泛的应用，如O-D旅行需求估计问题，上层决策者需求整个交通网络的交通拥塞和O-D需求估计偏差最小化，而下层决策则需求网络平衡状态。相关文献如[1]、[2]探讨了O-D旅行需求模型的求解方法。另外，如何进行信号控制，使车辆使用者做出合理反应，减少交通堵塞和延迟，也可以作为两层规划问题进行优化，如文献[3]中的描述。 1.2资源分配中的应用 资源分配是一类比较复杂的管理问题。上层部门将资源分配给多个下层部门，下层部门根据分配的资源和自己已有的资源组织生产，使自己的效益最大化，而上层如何使有限的资源产生最大的效益是上层面临的最大问题。Cassidy等人[4]1971年首先提出了政府部门的资源分配问题，文章描述了一个使中央政府能有效为其他层次的政府部门分配资源的模型，模型指出下层政府部门在拥有独立资源的情况下能独立做出决策。另外，公共设施的建设问题也属于资源分配的一类，如污水处理站的建设，上层决策者制定一些政策使得废物生产公司能尽量少排放废物，最大化社会福利，下层公司最大化自己的···试读结束