Como encontrar soluções inteiras não-negativas de ax+by=c e escolher a que minimiza o custo linear p x + q y?

Achar uma solução particular, gerar a família de soluções inteiras \(x=x_0+\tfrac{b}{d}t,\;y=y_0-\tfrac{a}{d}t\), impor x,y\(\ge\)0 e avaliar o custo p x+q y nos valores inteiros de t; escolher o menor.

Exemplo:
Cartelas de 6 unidades por R$4 e de 9 unidades por R$5; precisa exatamente 60 unidades. Resolver \(6x+9y=60\).
Dividindo por 3: \(2x+3y=20\). Para x inteiro, \(20-3y\) deve ser par, logo y é par: \(y=0,2,4,6,\dots\). Testando:
\(y=0\Rightarrow x=10\Rightarrow\) preço \(10\times4=R\$40\).
\(y=2\Rightarrow x=7\Rightarrow\) preço \(7\times4+2\times5=R\$38\).
\(y=4\Rightarrow x=4\Rightarrow\) preço \(4\times4+4\times5=R\$36\).
\(y=6\Rightarrow x=1\Rightarrow\) preço \(1\times4+6\times5=R\$34\).
\(y=8\Rightarrow x=-2\) (impossível).
Logo, o custo mínimo é R$34 obtido em \(x=1,y=6\).