a very quick linear programming question

[Random Variable]

Can a linear program in two variables ever have more than one solution but not infinitely-many solutions? I say that it can't.

EDIT: I should have stated that the solutions are optimal.

 

[hypn0tik]

Originally posted by: Random Variable
Can a linear program in two variables ever have more than one solution but not infinitely-many solutions? I say that it can't.

The simplest way is to think about the intersection of 2 lines. You can either have 0, 1 or infinitely many points of intersection. I'd have to agree with you unless I'm misinterpreting the question

 

[drinkmorejava]

you can have a curve intersecting a line many many times but not infinitely. Since when does linear programming mean no curves? The two variable part of you question makes no sense; you can manipulate any one variable to get a curve out of it...or just do x^2 and you get a parabola that can hit a line twice. Anyone could easily write a linear program to find the two intersection points.

 

[Random Variable]

Originally posted by: hypn0tik

Originally posted by: Random Variable
Can a linear program in two variables ever have more than one solution but not infinitely-many solutions? I say that it can't.

The simplest way is to think about the intersection of 2 lines. You can either have 0, 1 or infinitely many points of intersection. I'd have to agree with you unless I'm misinterpreting the question

My rationale was that for every two points that are solutions, the line segment connecting the two points contain infintely-many solutions.

 

[Random Variable]

Originally posted by: drinkmorejava
you can have a curve intersecting a line many many times but not infinitely. Since when does linear programming mean no curves? The two variable part of you question makes no sense; you can manipulate any one variable to get a curve out of it...or just do x^2 and you get a parabola that can hit a line twice. Anyone could easily write a linear program to find the two intersection points.

because a curve is not a linear equation

 

[Howard]

Originally posted by: Random Variable

Originally posted by: hypn0tik

Originally posted by: Random Variable
Can a linear program in two variables ever have more than one solution but not infinitely-many solutions? I say that it can't.

The simplest way is to think about the intersection of 2 lines. You can either have 0, 1 or infinitely many points of intersection. I'd have to agree with you unless I'm misinterpreting the question

My rationale was that for every two points that are solutions, the line segment connecting the two points contain infintely-many solutions.

Why?

 

[Random Variable]

Originally posted by: Howard

Originally posted by: Random Variable

Originally posted by: hypn0tik

Originally posted by: Random Variable
Can a linear program in two variables ever have more than one solution but not infinitely-many solutions? I say that it can't.

The simplest way is to think about the intersection of 2 lines. You can either have 0, 1 or infinitely many points of intersection. I'd have to agree with you unless I'm misinterpreting the question

My rationale was that for every two points that are solutions, the line segment connecting the two points contain infintely-many solutions.

Why?

because the feasible region is convex

 

[eLiu]

Originally posted by: drinkmorejava
you can have a curve intersecting a line many many times but not infinitely. Since when does linear programming mean no curves? The two variable part of you question makes no sense; you can manipulate any one variable to get a curve out of it...or just do x^2 and you get a parabola that can hit a line twice. Anyone could easily write a linear program to find the two intersection points.

No... linear programming works on stuff like this:
maximize: c1*x1 + c2*x2 + ... + cn*xn
with constraints:
a11*x1 + a12*x2 + ...+ a1n*xn <= b1
...
an1*x1 + .... ... + ann*xn <= bn

Also possible to enforce something like xi>=0, for certain i

Edit: Are you counting corner solutions? B/c if I enforce x1, x2>=0, then the solutions are the intersections of the 2 lines, and the intersections with the coordinate axes. So it could be that the corner solutions are both optimal...

 

[Random Variable]

Originally posted by: eLiu

Originally posted by: drinkmorejava
you can have a curve intersecting a line many many times but not infinitely. Since when does linear programming mean no curves? The two variable part of you question makes no sense; you can manipulate any one variable to get a curve out of it...or just do x^2 and you get a parabola that can hit a line twice. Anyone could easily write a linear program to find the two intersection points.

No... linear programming works on stuff like this:
maximize: c1*x1 + c2*x2 + ... + cn*xn
with constraints:
a11*x1 + a12*x2 + ...+ a1n*xn <= b1
...
an1*x1 + .... ... + ann*xn <= bn

Also possible to enforce something like xi>=0, for certain i

Edit: Are you counting corner solutions? B/c if I enforce x1, x2>=0, then the solutions are the intersections of the 2 lines, and the intersections with the coordinate axes. So it could be that the corner solutions are both optimal...

The only choices you have for optimal solutions are corner points. And if two corner points both optimize the objective function, that the the level line of Z(optimal) is parallel to the line segment that connects the two points. So there must be infinitely-many solutions That's my understanding anyways. Maybe I'm wrong.

 

[Stuxnet]

If I maximize the corners vs. minimize them, everything looks optimized. You can also click the 'X' to close the window.

 

[WildHorse]

Just 1 OPTIMAL basic feasible solution.


Edit: typo fix