Multiparametric Linear Programming

The multiparametric linear programming (MLP) problem for the right-hand sides (RHS) is to maximize z = c T x subject to Ax = b(λ), x ≧ 0, where b(λ) be expressed in the form [Formula: see text] where F is a matrix of constant coefficients, and λ is a vector-parameter. The multiparametric linear programming (MLP) problem for the prices or objective function coefficients (OFC) is to maximize z = c T (v)x subject to Ax = b, x ≧ 0, where c(I) can be expressed in the form c(v) = c* + Hv, and where H is a matrix of constant coefficients, and v a vector-parameter. Let B i be an optimal basis to the MLP-RHS problem and R i be a region assigned to B i such that for all λ ϵ R i the basis B i is optimal. Let K denote a region such that K = U i R i provided that the R i for various I do not overlap. The purpose of this paper is to present an effective method for finding all regions R i that cover K and do not overlap. This method uses an algorithm that finds all nodes of a finite connected graph. This method uses an algorithm that finds all nodes of a finite connected graph. An analogus method is presented for the MLP-OFC problem.

• 저널Management Science · 18(7) · 406–422
• 토픽Operations Management Techniques · Management Science and Operations Research
• DOI10.1287/mnsc.18.7.406
• 저자Tomáš Gál, Josef Nedoma