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

Homework Help: Linear programming proofs PLEASE HELP!

  1. Feb 9, 2012 #1
    1. The problem statement, all variables and given/known data

    Let C be the set of all points (x,y) in the plane satisfying x≥0, y≥0, -x-2y≤-8.

    a. Show that C is nonempty and unbounded.
    b. Prove that the LP problem: Max M=2x+3y subject to the constraint that (x,y) lie in C has no feasible, optimal solution.
    c. Show that the LP problem: Max M=-3x-6y subject to the constraint that (x,y) lie in C does have a feasible, optimal solution.

    2. Relevant equations

    3. The attempt at a solution

    a. I graphed the constraints and showed that the feasible region is the entire first quadrant, and therefore C is nonempty and unbounded (provided attachment of my work - is this enough?)

    b. I could "show" this but I have no idea how to "prove" it. Does it involve the simplex method?

    c. Same question as above

    Attached Files:

  2. jcsd
  3. Feb 10, 2012 #2


    User Avatar
    Homework Helper

    You plotted the wrong line in the figure.It should be -x-2y=-8.

    As for b and c: It is a good start to show. Do it.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook