In recent work Hartmann et al [Phys. Rev. Lett. 102, 057202 (2009)] demonstrated that the classical simulation of the dynamics of open 1D quantum systems with matrix product algorithms can often be dramatically improved by performing time evolution in the Heisenberg picture. For a closed system this was exemplified by an exact matrix product operator solution of the time-evolved creation operator of a quadratic fermi chain with a matrix dimension of just two. In this work we show that this exact solution can be significantly generalized to include the case of an open quadratic fermi chain subjected to master equation evolution with Lindblad operators that are linear in the fermionic operators. Remarkably even in this open system the time-evolution of operators continues to be described by matrix product operators with the same fixed dimension as that required by the solution of a coherent quadratic fermi chain for all times. Through the use of matrix product algorithms the dynamical behaviour of operators in this non-equilibrium open quantum system can be computed with a cost that is linear in the system size. We present some simple numerical examples which highlight how useful this might be for the more detailed study of open system dynamics. Given that Heisenberg picture simulations have been demonstrated to offer significant accuracy improvements for other open systems that are not exactly solvable our work also provides further insight into how and why this advantage arises.