Markov models are useful in the performance and dependability assessment of systems to obtain quantitative information that helps in making design decisions. The many known analysis techniques can be partitioned into approximate and exact techniques, where the former can be usually applied with limited effort but unknown precision and the latter give exact results but for the price of a computationally expensive calculation. In this paper, we discuss how an optimization method that is used to find an optimal configuration in a design space can make good use of both approximate and exact techniques for Markovian models. We develop a general approach that is formulated for evolutionary strategies and evaluated with Markov models of two queueing systems, a polling server model with real-valued design parameters and a finite buffer queueing network with discrete parameters.