The rim multiparametric linear programming problem (RMPLP) is a parametric problem with a vector-parameter in both the right-hand side and objective function (i.e., in the “rim”). The RMPLP determines the region K* ⊂ E* such that the problem, maximize z(λ) = c T (λ)x, subject to Ax = b(λ), x ≧ 0, has a finite optimal solution for all λ ∈ K*. Let B i be an optimal basis to the given problem, and let R i *, be a region assigned to B i such that for all λ ∈ R i * the basis B i is optimal. The goal of the RMPLP problem is to cover K* by the R i * such that the various R i * do not overlap. The purpose of this paper is to present a solution method for finding all regions R i * that cover K* and do not overlap. This method is based upon an algorithm for a multiparametric problem described in an earlier paper by Gal and Nedoma.

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.