Message Boards Message Boards

Generate list of points satisfying constraints

I have constraints for an integer programming problem in two dimensions and I'm trying to generate a list of points that satisfy the constraints. I'd like to display them on a graph to use in class. How can i generate this list? (While I could easily write a couple of for loops to do this, as a Mathematica-programming neophyte, I'd like to see a more elegant way.)

Here's what I have so far to generate my graph:

c1 = ContourPlot [-18 x + 38 y == 133, {x, 0, 10}, {y, 0, 10}, 
   ContourStyle -> {Red}];
c2 = ContourPlot[13 x + 11 y == 125 , {x, 0, 10}, {y, 0, 10}, 
   ContourStyle -> {Blue}];
c3 = ContourPlot[10 x - 8 y == 55 , {x, 0, 10}, {y, 0, 10}, 
   ContourStyle -> {Green}];
fr = RegionPlot[-18 x + 38 y <= 133 && 13 x + 11 y <= 125 && 
    10 x - 8 y <= 55, {x, 0, 10}, {y, 0, 10}];

Show[c1, c2, c3, fr]
POSTED BY: Betty Love
6 Replies

I think we're both ok on that score!

POSTED BY: Betty Love

(That's okay, I know better than to hyphenate them.)

POSTED BY: Daniel Lichtblau

Great! Thanks! I feel stupid about the semicolon! I know better!

POSTED BY: Betty Love

Remove the semi-colon at the end as that suppresses output. Or do

solns = Solve[{-18 x + 38 y <= 133, 13 x + 11 y <= 125, 10 x - 8 y <= 55, x >= 0, y >= 0}, {x, y}, Integers];

Now you can get those points, e.g. doing

pointvals = {x,y}/.solns
POSTED BY: Daniel Lichtblau

I'm sorry; I wasn't clear; I want a list of nonnegative integer points satisfying the inequalities. Your response gave me the idea to try this:

Solve[{-18 x + 38 y <= 133, 13 x + 11 y <= 125, 10 x - 8 y <= 55, x >= 0, y >= 0}, {x, y}, Integers];

But I don't get any output from it.

POSTED BY: Betty Love

I don't think there are any points satisfying all the constraints.

In[6]:= Reduce[-18 x + 38 y == 133 && 13 x + 11 y == 125 && 
  10 x - 8 y == 55 && -18 x + 38 y <= 133 && 13 x + 11 y <= 125 && 
  10 x - 8 y <= 55]

Out[6]= False
POSTED BY: Frank Kampas
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract