Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Sep 29, 2011 #1
    Suppose you have the following Linear Programming problem P


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


    [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?
  2. jcsd
  3. Oct 2, 2011 #2


    User Avatar
    Homework Helper

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook