hrcak mascot   Srce   HID

Izvorni znanstveni članak
https://doi.org/10.17535/crorr.2018.0019

The Worst Case Finite Optimal Value in Interval Linear Programming

Milan Hladik   ORCID icon orcid.org/0000-0002-7340-8491 ; Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic

Puni tekst: engleski, pdf (375 KB) str. 245-254 preuzimanja: 294* citiraj
APA 6th Edition
Hladik, M. (2018). The Worst Case Finite Optimal Value in Interval Linear Programming. Croatian Operational Research Review, 9 (2), 245-254. https://doi.org/10.17535/crorr.2018.0019
MLA 8th Edition
Hladik, Milan. "The Worst Case Finite Optimal Value in Interval Linear Programming." Croatian Operational Research Review, vol. 9, br. 2, 2018, str. 245-254. https://doi.org/10.17535/crorr.2018.0019. Citirano 05.08.2021.
Chicago 17th Edition
Hladik, Milan. "The Worst Case Finite Optimal Value in Interval Linear Programming." Croatian Operational Research Review 9, br. 2 (2018): 245-254. https://doi.org/10.17535/crorr.2018.0019
Harvard
Hladik, M. (2018). 'The Worst Case Finite Optimal Value in Interval Linear Programming', Croatian Operational Research Review, 9(2), str. 245-254. https://doi.org/10.17535/crorr.2018.0019
Vancouver
Hladik M. The Worst Case Finite Optimal Value in Interval Linear Programming. Croatian Operational Research Review [Internet]. 2018 [pristupljeno 05.08.2021.];9(2):245-254. https://doi.org/10.17535/crorr.2018.0019
IEEE
M. Hladik, "The Worst Case Finite Optimal Value in Interval Linear Programming", Croatian Operational Research Review, vol.9, br. 2, str. 245-254, 2018. [Online]. https://doi.org/10.17535/crorr.2018.0019

Sažetak
We consider a linear programming problem, in which possibly all coefficients are subject to uncertainty in the form of deterministic intervals. The problem of computing the worst case optimal value has already been thoroughly investigated in the past. Notice that it might happen that the value can be infinite due to infeasibility of some instances. This is a serious drawback if we know a priori that all instances should be feasible. Therefore we focus on the feasible instances only and study the problem of computing the worst case finite optimal value. We present a characterization for the general case and investigate special cases, too. We show that the problem is easy to solve provided interval uncertainty affects the objective function only, but the problem becomes intractable in case of intervals in the righthand side of the constraints. We also propose a finite reduction based on inspecting candidate bases. We show that processing a given basis is still an NP-hard problem even with non-interval constraint matrix, however, the problem becomes tractable as long as uncertain coefficients are situated either in the objective function or in the right-hand side only.

Ključne riječi
linear programming; interval analysis; sensitivity analysis; interval linear programming; NP-completeness

Hrčak ID: 212390

URI
https://hrcak.srce.hr/212390

Posjeta: 515 *