Degeneracy in simplex algorithm and feasible solutions in linear programming

Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
1 reply · 2K views
hkus10
Messages
50
Reaction score
0
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!
 

Discussion

Physics news on Phys.org
hkus10 said:
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!

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.)

RGV