The substantial spatial and temporal heterogeneity observed in patient tumors poses considerable challenges for the design of effective drug combinations with predictable outcomes. Currently, the implications of tissue heterogeneity and sampling bias during diagnosis are unclear for selection and subsequent performance of potential combination therapies. Here, we apply a multiobjective computational optimization approach integrated with empirical information on efficacy and toxicity for individual drugs with respect to a spectrum of genetic perturbations, enabling derivation of optimal drug combinations for heterogeneous tumors comprising distributions of subpopulations possessing these perturbations. Analysis across probabilistic samplings from the spectrum of various possible distributions reveals that the most beneficial (considering both efficacy and toxicity) set of drugs changes as the complexity of genetic heterogeneity increases. Importantly, a significant likelihood arises that a drug selected as the most beneficial single agent with respect to the predominant subpopulation in fact does not reside within the most broadly useful drug combinations for heterogeneous tumors. The underlying explanation appears to be that heterogeneity essentially homogenizes the benefit of drug combinations, reducing the special advantage of a particular drug on a specific subpopulation. Thus, this study underscores the importance of considering heterogeneity in choosing drug combinations and offers a principled approach toward designing the most likely beneficial set, even if the subpopulation distribution is not precisely known.