This paper is concerned with the practical real-time implementability of robustly stable model predictive control (MPC) when constraints are present on the inputs and the states. We assume that the plant model is known, is discrete-time and linear time-invariant, is subject to unknown but bounded state disturbances and that the states of the system are measured. In this paper we introduce a new stage cost and show that the use of this cost allows one to formulate a robustly stable MPC problem that can be solved using a single linear program. Furthermore, this is a multi-parametric linear program, which implies that the receding horizon control (RHC) law is piecewise affine, and can be explicitly pre-computed, so that the linear program does not have to be solved on-line.