Is this theory correct? Unbounded set implies unbounded optimium (2D only)

  • Thread starter flyingpig
  • Start date
  • #1
2,571
1
Suppose you have the following Linear Programming problem P

Max

[tex]z = ax + by[/tex]

s.t.

[tex]cx + dy = E[/tex]

[tex]fx + gy = H[/tex]

For [tex]x,y, \geq 0[/tex]

Suppose I also tell you that the region formed by the two constraints are unbounded and hence the corner points of the feasible region will tell you only the min. (so something like either [tex]x \geq M[/tex] or [tex]y \geq M[/tex] for some M) Can you comment that the linear programming problem P is also unbounded?


SO my take is that if cx + dy = E and fx + gy = H are parallel and if somehow the constraints [tex]x,y, \geq 0[/tex] could disappear, I would get an unbounded feasible region and you could theoretically change z to get an optimal.

But what if z is fixed? Or [tex]x,y, \geq 0[/tex] has to stay?

Any takers?
 

Answers and Replies

  • #2
Pyrrhus
Homework Helper
2,178
1
This is a mathematical program with equality constraints. Thus, they are always binding, and the matrix of first order partial derivatives must be full rank (Jacobian Assumption) to guarantee a solution.

For a LP, the constraint set is a flat (a set of hyperplanes), and thus they must have at least one point in common (because of equality) for it to have a solution, which also depends on the degrees of freedom of the problem.
 

Related Threads on Is this theory correct? Unbounded set implies unbounded optimium (2D only)

Replies
5
Views
2K
Replies
38
Views
1K
Replies
2
Views
1K
Replies
12
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
946
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
4
Views
620
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
5
Views
1K
Top