Скачать книгу

      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 .

      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)equation

      (2.22a)equation

      (2.22b)equation

      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)

Скачать книгу