鲁棒优化方法在供应链柔性合同RSFC问题中的应用与研究
|
摘要
鲁棒优化(RO)作为数学规划的一个新分支最近才发展起来,它是解决不确定规划问题的一种强有力工具。由于测量误差或模型本身的缺陷,或者决策阶段缺乏信息等原因,实际中许多优化问题的数据是受到干扰的或是不确定的,并且概率分布也无法预知。鲁棒优化通过“集合”形式描述数据的不确定性(而不是概率分布),使得约束条件在不确定数据取值于已知集合中所有可能值的情况下都满足,并以此建立最坏情况下最优化目标函数的鲁棒对应模型(RC),从而得到问题的鲁棒最优解。不同的“集合”形式得到不同类型的鲁棒对应模型,其复杂程度也不相同,但对同一个问题使用不同的不确定集合对鲁棒最优解和目标值有什么影响,它们之间存在什么联系,本文将对此进行初步的研究。
另一方面,供应链中需求信息的多变和价格波动的频繁造成供应商和零售商诸多决策问题的困难,所以本文选取供应链管理中零售商-供应商柔性合同RSFC问题为应用背景,从鲁棒优化理论的两种鲁棒模型Ben-Tal & Nemirovski鲁棒模型和Bertsimas & Sim鲁棒模型入手,以不确定线性规划为研究对象,研究两种鲁棒模型的本质区别和内在联系。通过对两种模型中保守度参数的选取,给出两种模型在一定条件下存在相同最优解的必要条件和充分条件,并且结论是“逐条”的,即对每条约束可以独立使用而互不影响。
根据上述性质建立混合鲁棒模型,并通过RSFC问题的算例实验分析说明保守度的选取对RSFC模型决策的影响以及为此所付出的鲁棒代价,以及混合模型的可行性和有效性。
本文的主要贡献如下:
(1)对使用单一保守度的Ben-Tal & Nemirovski鲁棒模型进行局部调整,每条含有不确定数据的约束引入不同的保守度,在不影响约束违反概率的情况下使得模型的保守度降低,从而改进了目标最优值。
(2)研究最优解相同的情况下两种模型保守度参数的选取问题,在一定假设下给出其充分条件和必要条件,并通过算例验证结论的正确性。
(3)建立价格和需求均不确定的RSFC问题的鲁棒对应模型,并利用(2)中结论和其“逐条”性质,建立同时使用两种不确定集合的混合型鲁棒模型。
Robust optimization (RO) is a relatively recent technique as a new branch of maths programming, and it is a powerful methodology used to solve uncertain program problems. Many real-world optimization problems involve input data that are perturbed or uncertain, and the probability distributions of the uncertain data are unknown or unavailable due to measurement or modelling errors, or the unavailability of the information at the time of the decision. RO is based on a description of uncertainty via sets, as opposed to probability distributions. The uncertain parameters are only known to belong to known sets, and one associates with the uncertain problem its robust counterpart (RC) where the constraints are enforced for every possible value of the parameters within their prescribed sets; under such constraints, the worst-case value of the cost function is then minimized to obtain a“robust”solution of the problem. Different type of sets gets different type of robust counterparts, which have different complexities. What are the effects on robust solution and its optimal value when using different type of sets, and what are the relations between them, we’ll try to study these problems.
In this paper we take the retailer-supplier flexible commitment (RSFC) problem in supply chain management as applied background, because in RSFC there are decision problems caused by changefully demand information and fluctuant price.
We study two RC of uncertain RSFC problems: Ben-Tal & Nemirovski RC and Bertsimas & Sim RC, and their essential difference and internal relations. Via the conservativeness parameters of the two RC, we derive the sufficient condition and necessary condition when they have the same solution under some premise. Furthermore, the propositions are“consrtaintwise”: can be used independently in different constraint.
Through case study, the RC is found to provide effective protect from the disruption of uncertain data and the robust price paid at the same time. Comparing two tests’results, it validates the sufficient and necessary conditions.
The contributions of this paper are as follows:
1) We introduce each contaminated constraint of Ben-Tal & Nemirovski RC a proper conservativeness parameters not only a single one, and this modifying improves optimal value without change the probability of constraint violate.
2) After studying the relation between the two RC’s conservativeness parameters when there are existing the same solutions, we derive the sufficient condition and necessary condition under some premise, and they are all testified by case study.
3) The RC of RSFC problems with both uncertain demand and uncertain price is formulated, and by the propositions (2) above, we formulate the mixed-RC model using both two types RC.
另一方面,供应链中需求信息的多变和价格波动的频繁造成供应商和零售商诸多决策问题的困难,所以本文选取供应链管理中零售商-供应商柔性合同RSFC问题为应用背景,从鲁棒优化理论的两种鲁棒模型Ben-Tal & Nemirovski鲁棒模型和Bertsimas & Sim鲁棒模型入手,以不确定线性规划为研究对象,研究两种鲁棒模型的本质区别和内在联系。通过对两种模型中保守度参数的选取,给出两种模型在一定条件下存在相同最优解的必要条件和充分条件,并且结论是“逐条”的,即对每条约束可以独立使用而互不影响。
根据上述性质建立混合鲁棒模型,并通过RSFC问题的算例实验分析说明保守度的选取对RSFC模型决策的影响以及为此所付出的鲁棒代价,以及混合模型的可行性和有效性。
本文的主要贡献如下:
(1)对使用单一保守度的Ben-Tal & Nemirovski鲁棒模型进行局部调整,每条含有不确定数据的约束引入不同的保守度,在不影响约束违反概率的情况下使得模型的保守度降低,从而改进了目标最优值。
(2)研究最优解相同的情况下两种模型保守度参数的选取问题,在一定假设下给出其充分条件和必要条件,并通过算例验证结论的正确性。
(3)建立价格和需求均不确定的RSFC问题的鲁棒对应模型,并利用(2)中结论和其“逐条”性质,建立同时使用两种不确定集合的混合型鲁棒模型。
Robust optimization (RO) is a relatively recent technique as a new branch of maths programming, and it is a powerful methodology used to solve uncertain program problems. Many real-world optimization problems involve input data that are perturbed or uncertain, and the probability distributions of the uncertain data are unknown or unavailable due to measurement or modelling errors, or the unavailability of the information at the time of the decision. RO is based on a description of uncertainty via sets, as opposed to probability distributions. The uncertain parameters are only known to belong to known sets, and one associates with the uncertain problem its robust counterpart (RC) where the constraints are enforced for every possible value of the parameters within their prescribed sets; under such constraints, the worst-case value of the cost function is then minimized to obtain a“robust”solution of the problem. Different type of sets gets different type of robust counterparts, which have different complexities. What are the effects on robust solution and its optimal value when using different type of sets, and what are the relations between them, we’ll try to study these problems.
In this paper we take the retailer-supplier flexible commitment (RSFC) problem in supply chain management as applied background, because in RSFC there are decision problems caused by changefully demand information and fluctuant price.
We study two RC of uncertain RSFC problems: Ben-Tal & Nemirovski RC and Bertsimas & Sim RC, and their essential difference and internal relations. Via the conservativeness parameters of the two RC, we derive the sufficient condition and necessary condition when they have the same solution under some premise. Furthermore, the propositions are“consrtaintwise”: can be used independently in different constraint.
Through case study, the RC is found to provide effective protect from the disruption of uncertain data and the robust price paid at the same time. Comparing two tests’results, it validates the sufficient and necessary conditions.
The contributions of this paper are as follows:
1) We introduce each contaminated constraint of Ben-Tal & Nemirovski RC a proper conservativeness parameters not only a single one, and this modifying improves optimal value without change the probability of constraint violate.
2) After studying the relation between the two RC’s conservativeness parameters when there are existing the same solutions, we derive the sufficient condition and necessary condition under some premise, and they are all testified by case study.
3) The RC of RSFC problems with both uncertain demand and uncertain price is formulated, and by the propositions (2) above, we formulate the mixed-RC model using both two types RC.
引文
[1] Y. Bassok, R. Anupindi. Analysis of supply contracts with total minimum commitment[J]. IIE Trans. 1997b. 29. 373-381.
[2] Anupindi, R., Y. Bassok. Approximation for multiproduct contracts with tochastic demands and business volume discounts: Single supplier case[J]. IIE Trans. 1998. 30. 723-734.
[3] Anupindi, R., Y. Bassok. Supply contracts with quantity commitments and stochastic demand. S. Tayur, M. Magazine, R. Ganeshan, eds. Quantitative Models for Supply Chain Management. Kluwer Academic Publishers, 1999, Norwell, MA.
[4] Bassok, Y., A. Bixby, R. Srinivasan, H. Z. Wiesel. Design of component-supply contracts with commitment-revision flexibility. IBM J. Res. Development, 1997. 41(6) 1–14.
[5] 张龙,宋世吉,刘连臣,吴澄,供需链管理中合同定量研究及其发展[J].控制与决策,2004. 19(10), 1081-1085.
[6] 柳键.基于时变需求的供应链库存决策研究[M].合肥:中国科学技术大学出版社,2005.
[7] Ben-Tal, Golany, Nemirovski, and Vial, A Robust Optimization Approach Retailer-Supplier Commitment Contracts[J]. Manufacturing & Service Operations Management , 2005. 7(3). 248–271.
[8] Bertsimas, D., Thiele .A., A robust optimization approach to inventory theory[J]. O.R, 2006. 54(1). 150-168.
[9] Ben-Tal, A., A. Nemirovski. Robust solutions of linear programming problems contaminated with uncertain data[J]. Math.Programming, 2000. (Series B) 88. 411–424.
[10] Ben-Tal.A, A. Nemirovski, Robust solutions of uncertain linear programs[J]. Oper. Res.Lett., 1999. 25. 1–13.
[11] Ben-Tal.A, Nemirovski.A, Roos.C, Robust solutions of uncertain quadratic and conic-qudratic problems[J]. SIAM J. OPTIM.,2001.Vol. 13, No. 2, pp. 535–560.
[12] Ben-Tal.A., Nemirovski. A., A robust optimization Methodology and applications[J]. Math. Programming 2002. Series B. 92. 453–480.
[13] Ben-Tal. A., Nemirovski. A., Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. MPR-SIAM Series on Optimization, SIAM, Philadelphia 2001.
[14] Ben-Tal, A., Margalit, T., Nemirovski, A. Robust modeling of multi-stage portfolio problems. In: Frenk, H., Roos, C., Terlaky, T., Zhang, S., eds., Higher formance Optimization. Kluwer Academic Publishers, 2000. pp. 303–328.
[15] Ben-Tal, A.,Nemirovski, A., Stable Truss Topology Design via Semidefinite Programming. SIAM.Journal on Optimization, 1997. 7, 991–1016.
[16] Ben-Tal, A., El-Ghaoui, L., Nemirovski, A.: Robust Semidefinite Programming. In Semidefinite Programming and Applications. Kluwer Academic Publishers,Waterloo, Canada, 2000.
[17] Ben-Tal, A., A. Goryashko, E. Guslitzer, A. Nemirovski. Adjusting robust solutions of uncertain linear programs. Math. Programming.2004. 99(2) 351–376.
[18] Soyster.A.L., Convex programming with set_inclusive constraints and applications to inexact linear programming[J]. Oper. Res. 1973. 21. 1154-157.
[19] Lee, H., P. Padmanabhan, S. Whang. Information distortion in a supply chain: The bullwhip effect[J]. Management Sci. 1996. 43 .546–558.
[20] Monahan, J. P. Quantity discount pricing models to increase vendor profits[J]. Management Sci. 1984. 30. 720–726.
[21] Tsay, A. A. The quantity flexibility contracts and supplier-customer incentives[J]. Management Sci. 1999. 45. 1339-1358.
[22] Tsay, A. A., W. S. Lovejoy. Quantity flexible contracts and supply chain performance[J]. Manufacturing Service Oper. Management. 1999. 1 .89–111.
[23] Urban, T. L. Supply contracts with periodic stationary commitments[J]. Production Oper. Management. 2000. 9. 400–413.
[24] Chen, F. Y., D. Krass. Analysis of supply contracts with minimum total commitment and non-stationary demands. Eur. J. Oper. Res., 2001. 131. 309–323.
[25] Van Delft, C., J. P. Vial. A practical implementation of stochastic programming: An applications to the evaluation of option contracts in supply chains. Automatica . 2004. 40. 743–756.
[26] Bertsimas, D., Sim, M., The price of robustness[J], Oper. Res., 2004. 52 (1). 35–53.
[27] Bertsimas, D., Sim, M., Robust Discrete Optimization and Network Flows, Math. Progr., 2003. 98, 49-71
[28] Bertsimas, D., Pachamanova, D., Sim, M., Robust Linear Optimization under General Norms. Operations Research Letters, 2003. 32, 510–516.
[29] Bertsimas, Dimitris, Melvyn Sim, Tractable Approximations to Robust Conic Optimization Problems, Math. Program., 2006. Ser. B 107, 5–36.
[30] El. Ghaoui, Lebret. H, Robust solutions to least_square problems to uncertain data matrices[J]. SIAM J. Matrix Anal. Appl. ,1997.18, 1035-1064.
[31] El-Ghaoui, Lebret, H., Robust solutions to least-square problems to uncertain data matrices. SIAM J. Matrix Anal. Appl., 1997. 18, 1035–1064.
[32] El-Ghaoui, L., Oustry, F., Lebret H.: Robust Solutions to Uncertain Semidefinite Programs. SIAM J. Optim., 1999. 9, 33–52.
[33] Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res., 1998. 23, 769–805.
[34] Tsay, A., S. Nahmias, N. Agrawal. Modeling supply chain contracts: A review. S. Tayur, R. Ganeshan, M. Magazine, eds. Quantitative Models for Supply Chain Management, Chapter 10. Kluwer Academic Publishers, Boston, MA, 1999. 299–336.
[35] Bassok, Y., R. Anupindi. Analysis of supply contracts with commitments and flexibility. 1997a.,Working paper, Northwestern University, Evanston, IL.
[36] Barnes-Schuster, D., Y. Bassok, R. Anupindi. Coordination and flexibility in supply contracts with options. Manufacturing Service Oper. Management. 2002. 4 171–207.
[37] Cachon, G. Supply chain coordination with contracts. S. Graves, T. de Kok, eds. Handbooks in Operations Research and Management Science: Supply Chain Management. North-Holland, Amsterdam, The Netherlands, 2002. 229–340.
[38] Cachon, G., M. Lariviere. Capacity allocation using past sales: When to turn-and-earn. Management Sci., 1999. 45(5) 685–703.
[39] Cachon, G., M. Lariviere. Contracting to assure supply: How to share demand forecasts in a supply chain. Management Sci., 2001. 47(5) 629–646.
[40] Iyer, A., Mark Bergen. Quick response in manufacturer retailer channels. Management Sci., 1997. 43(4).
[41] T. Santoso, Shabbir Ahmed, Marc Goetschalckx, Alexander Shapiro. A stochastic programming approach for supply chain network design under uncertainty, European Journal of Operational Research , 2005. 167. 96–115.
[42] Wang, Y. Z., Y. Gerchak. Periodic review production models with variable capacity, random yield, and uncertain demand[J]. Management Sci. 1996. 42(1) 130–137.
[2] Anupindi, R., Y. Bassok. Approximation for multiproduct contracts with tochastic demands and business volume discounts: Single supplier case[J]. IIE Trans. 1998. 30. 723-734.
[3] Anupindi, R., Y. Bassok. Supply contracts with quantity commitments and stochastic demand. S. Tayur, M. Magazine, R. Ganeshan, eds. Quantitative Models for Supply Chain Management. Kluwer Academic Publishers, 1999, Norwell, MA.
[4] Bassok, Y., A. Bixby, R. Srinivasan, H. Z. Wiesel. Design of component-supply contracts with commitment-revision flexibility. IBM J. Res. Development, 1997. 41(6) 1–14.
[5] 张龙,宋世吉,刘连臣,吴澄,供需链管理中合同定量研究及其发展[J].控制与决策,2004. 19(10), 1081-1085.
[6] 柳键.基于时变需求的供应链库存决策研究[M].合肥:中国科学技术大学出版社,2005.
[7] Ben-Tal, Golany, Nemirovski, and Vial, A Robust Optimization Approach Retailer-Supplier Commitment Contracts[J]. Manufacturing & Service Operations Management , 2005. 7(3). 248–271.
[8] Bertsimas, D., Thiele .A., A robust optimization approach to inventory theory[J]. O.R, 2006. 54(1). 150-168.
[9] Ben-Tal, A., A. Nemirovski. Robust solutions of linear programming problems contaminated with uncertain data[J]. Math.Programming, 2000. (Series B) 88. 411–424.
[10] Ben-Tal.A, A. Nemirovski, Robust solutions of uncertain linear programs[J]. Oper. Res.Lett., 1999. 25. 1–13.
[11] Ben-Tal.A, Nemirovski.A, Roos.C, Robust solutions of uncertain quadratic and conic-qudratic problems[J]. SIAM J. OPTIM.,2001.Vol. 13, No. 2, pp. 535–560.
[12] Ben-Tal.A., Nemirovski. A., A robust optimization Methodology and applications[J]. Math. Programming 2002. Series B. 92. 453–480.
[13] Ben-Tal. A., Nemirovski. A., Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. MPR-SIAM Series on Optimization, SIAM, Philadelphia 2001.
[14] Ben-Tal, A., Margalit, T., Nemirovski, A. Robust modeling of multi-stage portfolio problems. In: Frenk, H., Roos, C., Terlaky, T., Zhang, S., eds., Higher formance Optimization. Kluwer Academic Publishers, 2000. pp. 303–328.
[15] Ben-Tal, A.,Nemirovski, A., Stable Truss Topology Design via Semidefinite Programming. SIAM.Journal on Optimization, 1997. 7, 991–1016.
[16] Ben-Tal, A., El-Ghaoui, L., Nemirovski, A.: Robust Semidefinite Programming. In Semidefinite Programming and Applications. Kluwer Academic Publishers,Waterloo, Canada, 2000.
[17] Ben-Tal, A., A. Goryashko, E. Guslitzer, A. Nemirovski. Adjusting robust solutions of uncertain linear programs. Math. Programming.2004. 99(2) 351–376.
[18] Soyster.A.L., Convex programming with set_inclusive constraints and applications to inexact linear programming[J]. Oper. Res. 1973. 21. 1154-157.
[19] Lee, H., P. Padmanabhan, S. Whang. Information distortion in a supply chain: The bullwhip effect[J]. Management Sci. 1996. 43 .546–558.
[20] Monahan, J. P. Quantity discount pricing models to increase vendor profits[J]. Management Sci. 1984. 30. 720–726.
[21] Tsay, A. A. The quantity flexibility contracts and supplier-customer incentives[J]. Management Sci. 1999. 45. 1339-1358.
[22] Tsay, A. A., W. S. Lovejoy. Quantity flexible contracts and supply chain performance[J]. Manufacturing Service Oper. Management. 1999. 1 .89–111.
[23] Urban, T. L. Supply contracts with periodic stationary commitments[J]. Production Oper. Management. 2000. 9. 400–413.
[24] Chen, F. Y., D. Krass. Analysis of supply contracts with minimum total commitment and non-stationary demands. Eur. J. Oper. Res., 2001. 131. 309–323.
[25] Van Delft, C., J. P. Vial. A practical implementation of stochastic programming: An applications to the evaluation of option contracts in supply chains. Automatica . 2004. 40. 743–756.
[26] Bertsimas, D., Sim, M., The price of robustness[J], Oper. Res., 2004. 52 (1). 35–53.
[27] Bertsimas, D., Sim, M., Robust Discrete Optimization and Network Flows, Math. Progr., 2003. 98, 49-71
[28] Bertsimas, D., Pachamanova, D., Sim, M., Robust Linear Optimization under General Norms. Operations Research Letters, 2003. 32, 510–516.
[29] Bertsimas, Dimitris, Melvyn Sim, Tractable Approximations to Robust Conic Optimization Problems, Math. Program., 2006. Ser. B 107, 5–36.
[30] El. Ghaoui, Lebret. H, Robust solutions to least_square problems to uncertain data matrices[J]. SIAM J. Matrix Anal. Appl. ,1997.18, 1035-1064.
[31] El-Ghaoui, Lebret, H., Robust solutions to least-square problems to uncertain data matrices. SIAM J. Matrix Anal. Appl., 1997. 18, 1035–1064.
[32] El-Ghaoui, L., Oustry, F., Lebret H.: Robust Solutions to Uncertain Semidefinite Programs. SIAM J. Optim., 1999. 9, 33–52.
[33] Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res., 1998. 23, 769–805.
[34] Tsay, A., S. Nahmias, N. Agrawal. Modeling supply chain contracts: A review. S. Tayur, R. Ganeshan, M. Magazine, eds. Quantitative Models for Supply Chain Management, Chapter 10. Kluwer Academic Publishers, Boston, MA, 1999. 299–336.
[35] Bassok, Y., R. Anupindi. Analysis of supply contracts with commitments and flexibility. 1997a.,Working paper, Northwestern University, Evanston, IL.
[36] Barnes-Schuster, D., Y. Bassok, R. Anupindi. Coordination and flexibility in supply contracts with options. Manufacturing Service Oper. Management. 2002. 4 171–207.
[37] Cachon, G. Supply chain coordination with contracts. S. Graves, T. de Kok, eds. Handbooks in Operations Research and Management Science: Supply Chain Management. North-Holland, Amsterdam, The Netherlands, 2002. 229–340.
[38] Cachon, G., M. Lariviere. Capacity allocation using past sales: When to turn-and-earn. Management Sci., 1999. 45(5) 685–703.
[39] Cachon, G., M. Lariviere. Contracting to assure supply: How to share demand forecasts in a supply chain. Management Sci., 2001. 47(5) 629–646.
[40] Iyer, A., Mark Bergen. Quick response in manufacturer retailer channels. Management Sci., 1997. 43(4).
[41] T. Santoso, Shabbir Ahmed, Marc Goetschalckx, Alexander Shapiro. A stochastic programming approach for supply chain network design under uncertainty, European Journal of Operational Research , 2005. 167. 96–115.
[42] Wang, Y. Z., Y. Gerchak. Periodic review production models with variable capacity, random yield, and uncertain demand[J]. Management Sci. 1996. 42(1) 130–137.