مقایسه راه حل های عددی برای مسائل برنامه ریزی خطی با فاصله زمانی بر اساس نرخ پوشش و اعتبار
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|25472||2014||9 صفحه PDF||سفارش دهید||4420 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Applied Mathematical Modelling, Volume 38, Issue 3, 1 February 2014, Pages 1092–1100
In this paper, two-step method (TSM), alternative solution method (SOM-2) and best-worst case (BWC) method are introduced to solve a type of interval linear programming (ILP) problem. To compare the performance of the methods, Monte Carlo simulation is also used to solve the same ILP problem, whose solutions are assumed to be real solutions. In the comparison, two scenarios corresponding with two assumptions of distribution functions are considered: (i) all the input parameters obey normal distribution; (ii) all the input parameters obey uniform distribution. Based on the simulation results, coverage rate (CR) and validity rate (VR) are proposed as new indicators to measure the quality of the numerical solutions obtained from the methods. Results from a numerical case study indicate that the TSM and SOM-2 solutions can cover the majority of valid values (CR > 50%, VR > 50%), compared to the conventional BWC method. In addition, from the point of CR, TSM is more applicable since the solutions of TSM can identify more feasible solutions. However, from the point of VR, SOM-2 is preferred since it can exclude more baseless solutions (this means more feasible solutions are contained in the SOM-2 solutions). In general, TSM would be preferred when only the range of the system objective needs to be determined, while SOM-2 would be much useful in identifying the effective values of the objective.
In the past decades, much work has been focused on solving interval linear programming (ILP) problems during the last two decades , , , , , , , , , , , , , , , ,  and . For example, a grey linear programming (GLP) model was introduced to the civil engineering area in 1992, where GLP allowed uncertainties in the model inputs to be communicated into the optimization process, and thereby derived solutions reflecting the inherent uncertainties . In 1995 , a grey inter programming (GIP) method was introduced to facility expansion planning under uncertainty. GIP made uncertain information to be communicated into the optimization process and the resulting solutions. After GIP, Huang et al. used a gray linear-programming model to determine the optimal planning of waste-flow allocation for the regional municipality of Hamilton-Wentworth, Ontario. This approach can effectively reflect the interactive relationships between uncertain system components . Afterwards, Lu et al. developed an interval-parameter fuzzy-stochastic programming (IPFSP) approach for planning air quality management systems under uncertainty; the results indicate that optimal management strategies with minimized system operation cost could be generated for facilitating decision-making. However, a generalized algorithm could increase the computational efforts when a number of interval parameters are involved in, and can hardly handle interval linear inequalities. Sensitivity analysis could be used to solve ILP models, but the computational cost is still a major challenge when many of the parameters are expressed as intervals . Thus it is not suitable to be applied to real-world cases where thousands or tens of thousands of interval parameters need to be addressed. In addition, best-worst case (BWC) method can be used to solve ILP problems . However, similar to TSM, BWC needs to convert the ILP problem into two submodels. However, on the one hand, the two submodels generated by BWC are not equivalent to the original ILP problem; on the other hand, the BWC solutions may result in an infeasible decision space although it does produce the best and worst solutions. Interval linear programming (i.e., Min f±=C±X±f±=C±X±, s.t. A±X±⩽B±A±X±⩽B±, X±⩾0X±⩾0) was developed and applied in municipal solid waste management . In this paper, Huang proposed a two-step method (TSM) to solve an ILP problem based on the interrelationship between system objective and constraints. In the method, two submodels with deterministic parameters were formulated; by solving the two submodels, solutions for the optimized interval objective View the MathML source([fopt-,fopt+]) and interval decision variables View the MathML source([Xopt-,Xopt+]) can be obtained. Compared to conventional interval programming methods, TSM has the following advantages: (1) uncertain information presented as intervals can be directly incorporated into the optimization process in the ILP model; (2) it does not lead to heavy computation; (3) interval solutions obtained through ILP allow managers to interpret and adjust their decisions according to practical situations. However, one problem associated with TSM is that the two submodels are not completely equivalent to the original ILP model. To address this issue, specific combinations of interval parameters may be considered in TSM. According to the above analysis, two main concerns for ILP are computational cost and transformation equivalence. At present, few solution methods can address these two concerns simultaneously. Considering the applicability to real-world cases, a set of solution methods without introducing significant computational cost (i.e., TSM, BWC) are compared. Take TSM as an example. The validity and representiveness of solutions obtained through TSM will be demonstrated since the two submodels in TSM do not represent the original ILP problem. In this paper, an alternative solution method (i.e., SOM-2) which is parallel to TSM is developed considering different combinations of interval parameters in ILP. SOM-2 also does not lead to heavy computation. TSM, SOM-2 and BWC methods are used to solve a numerical case, with their solutions being compared subsequently. To examine the performance of the solutions obtained through TSM and SOM-2, Monte Carlo simulation (MC) is also introduced to solve the numerical case for comparison. In the MC method, two scenarios are developed based on the assumption that the confidence interval could be replaced by the confidence interval of a given random variable with known distribution. In Scenario 1, the random variables are assumed to be normally distributed, while uniform distribution is assumed in Scenario 2.
نتیجه گیری انگلیسی
Three solution methods (TSM, SOM-2 and BWC) were used to solve an ILP problem. Solutions obtained through these methods were then compared to investigate the performance in solving the ILP problem. Moreover, Monte Carlo simulation was introduced to solve the ILP problem under two scenarios: one assumes that all the input parameters to have normal distributions, and the other assumes that they have uniform distributions. Solutions obtained through the Monte Carlo simulation were used to exam how many percents of solutions will fall in the effective range. Coverage and valid rates were proposed to measure the performance of TSM and SOM-2 from different perspectives. Solutions obtained through TSM and SOM -2 covered the majority of valid values (CR > 50%, VR > 50%) and thus appropriate for practical systems. Specifically, the values of CR and VR shows that solutions obtained through TSM contain more feasible solutions while those of SOM-2 are more effective in both scenarios 1 and 2. Therefore, TSM would be preferred when only the range of the system objective needs to be determined, while SOM-2 would be much useful in identifying the effective values of the objective. This study was undertaken to solve ILP problems by introducing SOM-2 and exam the superiority of the optimization results over those obtained through conventional methods using Monte Carlo simulation. This would help decision makers determine which method is more appropriate to be used to solve a real-world ILP problem. However, in the Monte Carlo simulation, only normal and uniform distributions were assumed to represent the interval parameters. Further studies will be based on other distributions (especially asymmetrical distributions) to understand the superiority of solutions with enhanced accuracy. Moreover, an integrated interval and Monte Carlo simulation could be introduced in future studies to improve the accurateness and applicability of the method in solving real-world ILP problems.