We analyze properties of closed-loop systems based on explicit model predictive control (MPC) when parameters of the controllers are changing. Formulation of the problem in the framework of MPC with a cost based on piecewise linear norms leads to the generalized multi-parametric linear program containing parameters both in the cost and in the constraints. The focus of the paper is on describing a novel simplex-based algorithm for solving such a class of problems. The algorithm uses the concept of lexicographic perturbation to resolve problems caused by degeneracy