# Simplex Method Proof

• Apr 17th 2011, 11:04 AM
veronicak5678
Simplex Method Proof
Show that the variable that becomes nonbasic in one iteration of the simplex
method cannot become basic in the next iteration.
• Apr 17th 2011, 07:59 PM
TKHunny
What are the selection criteria for the next entering nonbasic variable?
• Apr 17th 2011, 08:45 PM
veronicak5678
Hi,

Since nothing is mentioned, I think the only criteria is that the variable have a negative coefficient in the objective function that we want to maximize.
• Apr 18th 2011, 09:05 AM
TKHunny
And once you have selected the column, you are led to a row, right? What is the value in that row for the column representing the previous non-basic variable?
• Apr 18th 2011, 06:11 PM
veronicak5678
I'm not sure what you mean... the value in that row depends on the problem, right?
• Apr 18th 2011, 08:24 PM
TKHunny
Let's keep rows and columsn straight. After an iteration, you have just created all zeros, except one, in some column. If you then operate on another row, that row will have zero in that previous column.
• Apr 18th 2011, 08:50 PM
veronicak5678
I think I'm confused because we have been using dictionary notation, not matrix notation. I understand that the column that corresponded to the variable that just left is now 0 because that variable is now 0. Can we say that the variable will never be basic again because it will have the wrong sign on the coefficient in the objective function after it has exited the basis?
• Apr 18th 2011, 09:27 PM
TKHunny
I see. Time to back up to the geometry. What are the requirements or assumptions for a solution to exist?

Feasible
Bounded
Concave

Any of these things lead in the right direction?

In other words, as you just created a nonbasic variable, because it was a maximal constraint, the choice to return it to basic on the next iteration would seem to indicate that we didn't use it all.
• Apr 18th 2011, 09:30 PM
TKHunny
Okay, as I read more and more on the subject, I begin to feel old. Almost all that is interesting was written since I last studied the matter. Perhaps one with more current background will bail me out and tell me what I'm trying to say.