|
|
2.4.3 Interpretation of the Results
In Table 2.3, it is shown that the solution to problem (2.20) is given by three critical regions. This means that for different demand values, there is a change in which of the constraints in problem (2.20) is active.
The first critical region: For the first critical region, the third and fourth constraints, together with the non‐negativity of , are active. These are the constraints that define the market demand, given from the deterministic values in Eq. (2.17b). Thus, the solution within the first critical region is only concerned with fulfilling the market demand, as the supply limits are not relevant (see second and third critical regions). Consequently, the optimal solution goes along the cheapest transportation routes, which are Seattle to Chicago (cost in objective function: 178) and San Diego to Topeka (cost in objective function: 151). The amount that is transported is thereby given by the market demand, i.e. and .
The second critical region: The second critical region is obtained, when the market demand of Chicago, , exceeds the supply of Seattle, which is 350. This is apparent in the new active set, which includes the supply constraint of Seattle (the first constraint). Then, in order to fulfill the demand, there needs to be a supply from San Diego, and thus , , while the demand from Topeka can still be fulfilled from San Diego with .
The third critical region: Similarly to the second critical region, the third critical region results when San Diego is unable to meet all the demands from Topeka, as the supply limit of 600 is reached. Then, the supply constraint from San Diego becomes active (the second constraint), and in order to fulfill the demand, material will be transported from Seattle to Topeka, and thus , , while the demand from Chicago is met from Seattle with .
Infeasible region: As soon as the sum of the demand, , is greater than the available supply, , there is no possibility to meet all the demands with the supply given. Thus, there is no feasible solution for .
2.5 Literature Review
The idea to consider the variation of a parameter in an LP problem was reportedly first put forth in the unpublished master thesis by William Orchard‐Hays in 1952, as reported in [14], where the variation of the right‐hand side of the constraints was considered:
(2.21)
Subsequently, several researchers proposed algorithms for the treatment of the single parameter case [15–20], but it was not until 1972 when the seminal paper by Gal and Nedoma described for the first time a rigorous strategy for the general solution of mp‐LP problems of type (2.2) based on the connected‐graph theorem [2]. All these developments were captured in the excellent textbook by Gal and Davis from 1979 [21], for which a second edition appeared in 1995 [22].
The algorithm from [2] remained the state‐of‐the‐art for over 25 years (see, e.g. [23,24]), until geometrical algorithms for general mp‐LP problems were developed starting in 2000,5 with the application of multi‐parametric programming to model‐predictive control [26,27]. Although the initial focus was put on mp‐QP problems, quickly publications concerning combination of model predictive control and mp‐LP problems were put forth [28–31], many of which were captured in this excellent review [32]. This new string of developments resulted in a deeper interest in the theoretical properties of mp‐LP problems, specifically in the case of degeneracy (see section 2.2), as well as the question of the presence of parameters in the left‐hand side of the constraints, i.e.
(2.22a)
(2.22b)
where algorithms based on McCormick relaxations [33,34], as well as exact algorithms for the single parameter case [35] have been presented.6
References
1 1 Spjøtvold, J., Tøndel, P., and Johansen, T.A. (2005) A method for obtaining continuous solutions to multiparametric linear programs, in World Congress, IFAC, Elsevier, IFAC proceedings volumes, p. 902, doi: 0703‐6‐CZ‐1902.00903.
2 2 Gal, T. and Nedoma, J. (1972) Multiparametric linear programming. Management Science, 18 (7), 406–422, doi: 10.1287/mnsc.18.7.406.
3 3 Olaru, S. and Dumur, D. (2006) On the continuity and complexity of control laws based on multiparametric linear programs, in 45th IEEE Conference on Decision and Control, 2006, pp. 5465–5470, doi: 10.1109/CDC.2006.377330.
4 4 Jones, C.N., Kerrigan, E.C., and Maciejowski, J.M. (2007) Lexicographic perturbation for multiparametric linear programming with applications to control. Automatica, 43 (10), 1808–1816, doi: 10.1016/j.automatica.2007.03.008. URL http://www.sciencedirect.com/science/article/pii/S0005109807002002.
5 5 Hladík, M. (2010) Multiparametric linear programming: support set and optimal partition invariancy. European Journal of Operational Research, 202 (1), 25–31, doi: 10.1016/j.ejor.2009.04.019. URL http://www.sciencedirect.com/science/article/pii/S0377221709002926.
6 6 Gal, T. and Greenberg, H.J. (1997) Advances in sensitivity analysis and parametric programming, vol. 6, Springer US, Boston, MA, doi: 10.1007/978‐1‐4615‐6103‐3.
7 7 Hadigheh, A.G. and Terlaky, T. (2006) Generalized support set invariancy sensitivity analysis in linear optimization. Journal of Industrial and Management Optimization, 2 (1), 1–18.
8 8 Hadigheh, A.G. and Terlaky, T. (2006) Sensitivity analysis in linear optimization: invariant support set intervals. European Journal of Operational Research, 169 (3), 1158–1175, doi: 10.1016/j.ejor.2004.09.058. URL http://www.sciencedirect.com/science/article/pii/S0377221705002808.
9 9 Hadigheh, A.G., Mirnia, K., and Terlaky, T. (2007) Active constraint set invariancy sensitivity analysis in linear optimization. Journal of Optimization Theory and Applications, 133 (3), 303–315, doi: 10.1007/s10957‐007‐9201‐5. URL http://dx.doi.org/10.1007/s10957-007-9201-5.
10 10 Greenberg, H.J. (1994) The use of the optimal partition in a linear programming solution for postoptimal analysis. Operations Research Letters, 15 (4), 179–185, doi: 10.1016/0167‐6377(94)90075‐2. URL http://www.sciencedirect.com/science/article/pii/0167637794900752.
11 11 Berkelaar, A.B., Roos, K., and Terlaky, T. (1997) The optimal set and optimal partition approach to linear and quadratic programming, in (eds T. Gal and H.J. Greenberg)