Conditions are derived under which optimal replacement rules for systems subject to Markovian deterioration and failure are given by control limit replacement rules. An efficient method of deriving such rules is given which is based on the simplex algorithm.