CODEWITHSUNDEEP
wolfram-mathematica
Qiang Li
Qiang Li

Reputation: 10865

non-negative integer solutions to system of linear equations in mathematica

Related to my previous question, just wonder how to solve a system of linear equations with non-negative integral solutions, for example:

c11*x+c12*y+c13*z=d1
c21*x+c22*y+c23*z=d2

Thanks a lot!

Edit

I meant efficiently. For example, I could have used FrobeniusSolve to get two solution lists and try to find the intersection. But sometimes, the individual solution list is probably hugely large. Or try to verify each individual solution returned by one FrobeniusSolve to see whether they satisfy all the remaining equations, but that suffers from the same drawback.

Upvotes: 2

Views: 1840

Answers (1)

Simon
Simon

Reputation: 14731

Reduce is able to solve these types of problems.

To answer the specific case in your comment above: 

In[1]:= solns =  Reduce[x1 + 2 x2 + 5 x3 + 7 x4 == 40 &&
                        x1 + x2 + 2 x3 + x4 == 20 &&
                        x1 > 0 && x2 > 0 && x3 > 0 && x4 > 0, 
                       {x1, x2, x3, x4}, Integers]

Out[1]= (x1 == 6 && x2 == 11 && x3 == 1 && x4 == 1) ||
        (x1 == 7 && x2 == 8 && x3 == 2 && x4 == 1) ||
        (x1 == 8 && x2 == 5 && x3 == 3 && x4 == 1) ||
        (x1 == 9 && x2 == 2 && x3 == 4 && x4 == 1) ||
        (x1 == 11 && x2 == 5 && x3 == 1 && x4 == 2) ||
        (x1 == 12 && x2 == 2 && x3 == 2 && x4 == 2)

Edit:

You can check that this is the same solution you get by solving the two equations separately and taking the intersection of their solutions:

In[2]:= a = Reduce[x1 + 2 x2 + 5 x3 + 7 x4 == 40 && 
                   x1 > 0 && x2 > 0 && x3 > 0 && x4 > 0, 
                  {x1, x2, x3, x4}, Integers];

        b = Reduce[x1 + x2 + 2 x3 + x4 == 20 && 
                   x1 > 0 && x2 > 0 && x3 > 0 && x4 > 0, 
                  {x1, x2, x3, x4}, Integers];

In[4]:= solns == Intersection[a, b]

Out[4]= True

And you can extract the solutions by, e.g., turning the solutions into a list of replacement rules and applying to the variables:

In[5]:= {x1, x2, x3, x4} /. {ToRules[solns]}

Out[5]= {{6, 11, 1, 1}, {7, 8, 2, 1}, {8, 5, 3, 1}, 
         {9, 2, 4, 1}, {11, 5, 1, 2}, {12, 2, 2, 2}}

Upvotes: 5

Related Questions