We consider the problem of constructing a portfolio of finitely many assets whose returns are described by a discrete joint distribution. We propose mean-risk models which are solvable by linear programming and generate portfolios whose returns are nondominated in the sense of second-order stochastic dominance. Next, we develop a specialized parametric method for recovering the entire mean-risk efficient frontiers of these models and we illustrate its operation on a large data set involving thousands of assets and realizations.