تجزیه و تحلیل نقض در روش دو مرحله ای برای برنامه ریزی خطی فاصله زمانی
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|25509||2014||12 صفحه PDF||سفارش دهید||5510 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Information Sciences, Volume 281, 10 October 2014, Pages 85–96
In many real world problems, system parameters or model coefficients may be bounded between lower and upper bounds due to a variety of uncertainties. Over the past decades, intensive research efforts have focused on interval linear programming (ILP) to tackle such uncertainties. As one of the most popular methods for solving ILP problems, Two-Step Method (TSM, proposed by Huang et al. in 1995) allows uncertain information to be directly communicated into the optimization process and resulting solutions such that decision alternatives could be generated through the interpretation of interval solutions. However, part of optimum solution points obtained through TSM may go beyond the decision space in some cases. This phenomenon, referred to as solution violation, may mislead decision makers to unreasonable policies, plans, or strategies which play important roles in the social and economic development. Therefore, this study first investigates and identifies the essential cause for the solution violation of TSM. Following that, an improved solution method (namely, ITSM) is proposed to avoid resulting violation by introducing extra constraints in the solving process. A numeric example is then presented to demonstrate the effectiveness of ITSM in handling solution violation.
In conventional mathematical programming problems, system parameters or model coefficients are usually determined as crisp values. However, in many real world problems, these parameters may be bounded between lower and upper bounds due to a variety of uncertainties. Therefore, interval approaches are often used to describe imprecise and uncertain components existing in a real decision problem. In general, interval uncertainties may exist in the coefficients of both constraints and objective function. A representative form of interval linear programming (ILP) model can be expressed as follows: equation(1.1a) View the MathML sourcemaxf=C±X Turn MathJax on subject to equation(1.1b) A±X⩽B±A±X⩽B± Turn MathJax on where all coefficients (i.e., A±, B± and C±) are involved with interval uncertainties. Thus, both the solutions (i.e., X) and the objective function value (i.e., f) may be achieved as interval. The resulting interval solutions are mostly some approximation sets, but represent an acceptable compromise for decision makers . In some specific cases, not all system parameters are subject to inaccuracy. Two typical situations are: (1) interval uncertainties only exist in the objective function; and (2) interval ones are only present in the right-hand side (RHS) of constraints. The former situation can be treated as a linear programming (LP) problem with interval objective function coefficients. Since the objective function value is only specified by an interval, the objective of maximizing an interval objective function can be interpreted and reformulated as one or several usual objectives. Namely, maximizing the lower bound of the interval, maximizing the upper bound of the interval, maximizing the center of the interval, and maximizing the width of the interval may be adopted to reformulate the objective function , ,  and , the problem thus can be solved through LP methods. Alternatively, the concept of optimality for the combination of multiple parameters can be introduced to treat the interval objective function ,  and . Nevertheless, the final decision method is still required as there might be many possibly optimal solutions. The minimax regret method is often employed to obtain the best solutions based on decision theory , ,  and . Specifically, the final solutions are determined by introducing a minimax regret criterion which is derived from a given reference solution set (namely, the set of possibly optimal solutions). As for the latter situation (i.e., interval RHS), it can be viewed as a multiparametric LP problem with interval domains for parameters. Thus, the optimum solution can be obtained through sensitivity analysis or stochastic optimization which describes interval parameters with probability laws , , , ,  and . Perturbation theory may also give another possibility to handle such interval uncertainties  and . However, the aforementioned approaches are only applicable for solving some special cases in many ILP problems. There are only a few solution methods dedicated to solve the general ILP problems ,  and . The underlying idea of these methods is to divide an ILP model as expressed in (1.1a) and (1.1b) into two extreme LP sub-models to achieve interval solutions. One LP sub-model is solved to obtain the best optimum solution (highest maximum or lowest minimum as appropriate) while the other is for the worst optimum solution (lowest maximum or highest minimum as appropriate). Among them, the Two-Step Method (TSM) proposed by Huang et al.  is the most popular one. The greatest advantage of TSM is that interval uncertainties will be carried forward to the model solutions such that alternative options instead of fixed values can be generated for supporting decision making. Besides, the solution method of TSM is straightforward and easy to follow. In recent years, hundreds of research papers based on the TSM have been published to tackle interval uncertainties in real world problems, including solid waste management , , , , , , , ,  and , water resources allocation , , , , ,  and , water quality management ,  and , energy systems planning , , , , , , ,  and , air quality management  and , as well as many other fields , , ,  and . Nevertheless, it has been informed that the optimum solutions obtained by TSM might go beyond the decision space in some cases . This phenomenon is referred to as solution violation. Although some efforts have been carried out to revise the TSM in terms of its solving process, it is still unknown in what cases solution violation would happen and why it would happen. Therefore, this study will investigate and identify the essential cause for the solution violation of TSM. Following that, an improved solution method (namely, ITSM) will be proposed to avoid resulting violation by introducing extra constraints in the solving process. A numeric example is then presented to demonstrate the effectiveness of ITSM in handling solution violation.
نتیجه گیری انگلیسی
In this study, the essential cause of solution violation for the widely-used TSM method  is thoroughly analyzed. The analysis shows that the TSM might achieve violated solutions due to the constraints considered in its solving process cannot completely cover those ones employed to define the feasible decision space. The idea to avoid solution violation is straightforward, that is to identify those neglected constraints and add them to the solving process of TSM. Therefore, an improved method based on TSM (namely, ITSM) is proposed based on the violation analysis. Following that, a series of comparisons with other approaches (i.e., MILP, ThSMs, and RTSM) were conducted. It is demonstrated that the ITSM can achieve the best optimum objective function value which is the same as that of TSM, meanwhile the size of solution space will not be greatly reduced. Furthermore, the way of identifying extra constraints for ITSM is easy to follow and its solving process is as simple as that of TSM.