Show that the variable that becomes nonbasic in one iteration of the simplex

method cannot become basic in the next iteration.

Printable View

- April 17th 2011, 12:04 PMveronicak5678Simplex Method Proof
Show that the variable that becomes nonbasic in one iteration of the simplex

method cannot become basic in the next iteration. - April 17th 2011, 08:59 PMTKHunny
What are the selection criteria for the next entering nonbasic variable?

- April 17th 2011, 09:45 PMveronicak5678
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. - April 18th 2011, 10:05 AMTKHunny
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?

- April 18th 2011, 07:11 PMveronicak5678
I'm not sure what you mean... the value in that row depends on the problem, right?

- April 18th 2011, 09:24 PMTKHunny
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.

- April 18th 2011, 09:50 PMveronicak5678
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?

- April 18th 2011, 10:27 PMTKHunny
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. - April 18th 2011, 10:30 PMTKHunny
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.