Linear Programming Theory, Optimality Criterion Question

[ayas]

Linear Programming Theory, "Optimality Criterion" Question

In a (theory oriented) linear programming class, I am studying the simplex method. The basic feasible solution represented by a tableau is said to be 'optimal' when it respects the Optimality Criterion:
'If the objective row of a tableau has zero entries in the columns labeled by basic variables and no negative entries in the columns labeled by nonbasic variables, then the solution represented by the tablau is optimal'
I don't know how to convince myself that it is always true!)
Can you explain why it is always true?
Thks,

How I see it:

Let's say we have m basic variables and n nonbasic variables.The objective row in the first tableau has:
- only negative values (or sometimes 0) corresponding to the coefs of the nonbasic variables
- all zero values corresponding to the coefs of the basic variables Then by successive tableaux, we manage to have only nonnegative values in the objective row. WHEN WE GET HERE, the Optimality Criterion says 'you're done, z is at its maximum value'. But what tells me that there is no way to arrange the values of the basic variables (without making them zero, just changing from positive to another positive) so that z grows again?

PS: beyond answering this question, I would be very glad if someone had an internet link to a website that explains deeply (and maybe play arround with) the theory of linear programming. I'd like to have an intuitive approach to the theory; i.e. be able to explain every detail 'because it will feel obvious'. A link to a book be great too. The book that I'm using so far is the one by Kolman and Beck.

 

[trambolin]

Well, I am not an expert and the answer is not short, but I can give you two main items for better understanding,

First is optimality will always be attained on one of the vertices (by some reasonable assumptions). Proof is not that complicated.

Second is, suppose the nonbasic variables are not positive but the point is optimum. Then, I can say that going in that direction will give me another optimum, but it should be a vertex also, from the first item. Then, this is a contradiction. Similar argument can be done with the basic variables.

So, regarding to your latter question, since we have the optimality on one of the vertices, We are always on two or more active constraints that makes the basic variables zero, in other words, on the corners of the feasible set. I hope this sentence rings a bell (pen and paper is so much easier for these)

If you elaborate these ideas, I am sure you will end up with a more consistent understanding. And if I did some error please correct me.