1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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: Feasible solution for Linear Optimization

  1. Sep 23, 2011 #1
    1) How to justify if there is a tie for the minimum b-ratio at some iteration of the phase II simplex algorithm, then the next basic feasible solution is degenerate.

    I have no idea how to justify it. Please give me some direction

    2) Max. z = transpose of C * the vector x
    s.t. Ax less or = b
    & X bigger or = to 0

    Suppose d belong in R^n satisfies Ad=0 and d bigger or equal to 0
    a) Prove that if u belongs to R^n is a feasible solution of P, then so is u+td for all 0 less than or equal to t belongs to R.
    b) Use part (a) to prove that if the transpose of C * d >= 0, the P is unbounded.

    I think the big problem here is that I do not know how to approach part a.
    please give some insight for how to at least begin to solve this problem?

    Thank you!
    I appreciate your time!
  2. jcsd
  3. Sep 23, 2011 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    About your first question: if a nonbasic variable xj increases from 0 to t and drives TWO (or more) basic variables xr and xs to zero at the same time, then we can decide to let, say, xs leave the basis (to be replaced by xj). The other variable xr remains basic but will be zero (because xj = t will be the new value of xj and we know already that xj = t drives xr to zero).

    By the way, you can just write x >= 0, rather than writing out "x bigger or = 0"; similarly for Ax <= b, etc.

    If your undefined problem P means the LP you wrote, then supposing Ad=0, d>=0, what can you say about x = u + td, t >= 0? Does it satisfy all the constraints of P? What is the resulting value of z(x) = c.x? (Here c,x are vectors, "." = inner product.)

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