One way to interpret the problem is as an integer programming problem in 3-dimensions. If one has 3 points $(a_i/c_i,b_i/c_i) \in \mathbb{R}^2, i=1,2,3$
with $gcd(a_i, b_i, c_i) =1$ and $c_i \geq 1$, then take the three lattice points $P_i=(a_i, b_i, c_i) \in \mathbb{Z}^3$.

Take the cone C spanned by positive integer combinations of $P_i$ (this is the projective region sitting above the triangle). Then one wants to find the lattice point of $\mathbb{Z}^3$ inside the interior of this cone with smallest z-coordinate. This may be interpreted as an integer linear programming problem. However, I don't know enough about integer programming to know if this will help (Scarf seems to have thought about precisely this problem, but doesn't address the computational complexity). The following gives one possible approach, but might not be any better than Nikokoshev's approach except in certain regimes.

These vectors generate a sublattice $\Lambda \subset \mathbb{Z}^3$ of index D, where D is the determinant of the matrix $[P_1,P_2,P_3]$, and is the volume of the parallelepiped F spanned by these vectors. One can see that a lattice vector in this cone with minimal z-coordinate must lie in this F, since F is a fundamental domain for the action of $\Lambda\cap C$. A brute-force approach is to compute the finite abelian group $\mathbb{Z}^3/\Lambda$, finding a basis (which will consist of at most 2 vectors since $P_i$ is primitive). Then translate these vectors into the fundamental domain F, and take enough positive linear combinations to generate all coset representatives of $\mathbb{Z}^3/\Lambda$ inside C. Then subtract elements from the positive semigroup $\Lambda\cap C$, until you find all coset representatives in the fundamental domain F, and find the one with minimal z-coordinate. This approach should be pretty effective when D is small or the group $\mathbb{Z}^3/\Lambda$ is cyclic, but I'm not sure how the size of D correlates with the size of the final solution. For example, if $D=1$, then the minimal vector will be $P_1+P_2+P_3$ with denominator $c_1+c_2+c_3$. If $D\geq 2$, the minimal denominator will be $<(c_1+c_2+c_3)/2$ by the symmetry of F.