Hi guys, [SOLVED: thanks for the hints!] how do i show that a primal has multiple solutions if it has a nondegenerate solution and its dual has degenerate? asked 02 Mar '12, 07:05 secondrate yeesian 
You know the following :
At least this is the intuitive way to think of it, not sure it's what you are looking for. answered 02 Mar '12, 07:28 Bo Jensen ♦ hi bo, i'm a bit confused by what you said...why is it that if the dual is degenerate, there exists a non basic variable with reduced cost zero?
(02 Mar '12, 07:54)
secondrate
A primal degenerated basis has a basic variable on a bound i.e in the simple case with x >= 0 => x = 0. A dual degenerated basis means a dual variable (i.e reduced cost) is zero on at least one of the non basic variables. So to answer your question, then it's actually the definition of dual degeneracy :)
(02 Mar '12, 08:10)
Bo Jensen ♦
hi bo, did you mean, a dual degenerate basis has a dual basic variable with value instead? Also, I know that the reduced cost of the primal variables = (dual variables). so how can you say "a non basic variable with reduced cost zero"? Hmm, is there a simpler solution to this problem? thanks bo!
(02 Mar '12, 08:17)
secondrate

So was this homework? Since Bo has already answered... Look at the proof of the strong duality theorem. Most proofs are constructive, i.e., given a basic optimal primal solution, the proof shows you how to construct a corresponding complementary basic optimal dual solution. If you look carefully at the case where that dual solution is degenerate, you'll see that the corresponding primal solution has a nonbasic variable with zero reduced costdual slacks represent primal reduced costs. If you pivot that variable in, you'll move to a distinct primal solution with the same objective value. answered 02 Mar '12, 11:20 Matthew Salt... ♦ Hey matthew, ok I got that part now. But I'm confused with this "ray" when a leaving solution can't be found.
(02 Mar '12, 11:42)
secondrate
Pivoting a nonbasic variable into the basis corresponds to increasing it from its bound value of zero and adjusting the values of basic variables to maintain feasibility of the structural constraints. The ratio test tells the maximum amount that variable can increase before a basic variable violates its bound. Every value of the entering variable up to that point represents a feasible but not basic solution. If the ratio test fails, that just means you can keep increasing the entering variable without bound. If the entering variable has zero reduced cost, the objective doesn't change.
(02 Mar '12, 12:23)
Matthew Salt... ♦
Geometrically, increasing the value of a nonbasic variable corresponds to moving along an edge (onedimensional face) of the feasible region. If the ratio test fails, that edge is a "ray", i.e., you can travel along it forever.
(02 Mar '12, 12:25)
Matthew Salt... ♦

Here's another (I think) way to look at it. Since the dual of the dual is the primal, let's flip the question: if the primal solution is degenerate, how do we know the dual has multiple optima? (I'll give the "intuitive graphical" argument; nailing down details may or may not be easy.) If the primal solution is degenerate, there's at least one constraint binding at the optimum such that if you relax the constraint, the optimum does not move. So the shadow price for relaxation is zero. On the other hand, tightening that constraint will cut off the current optimum. Since we're also assuming the dual solution is nondegenerate, the primal cannot have multiple optima, so cutting off the solution "hurts" the objective value by a nonzero amount ... which means the shadow price for tightening is nonzero. That gives us two different shadow prices for the same constraint, depending on which way we perturb it, so the dual must have multiple solutions. answered 03 Mar '12, 11:28 Paul Rubin ♦♦ 
(1) If you've received a satisfactory answer, please accept the answer so that the system shows your question as answered. (2) One possible boundary case (ruled out by your assumptions) is where both primal and dual are degenerate at optimality. In that case, you'll have a primal nonbasic variable with zero reduced cost (because the dual is degenerate), but it could be the case that moving that variable off its bound would force the degenerate basic variable to violate its bound. In that case, you can't tell from the current basic solution whether there are multiple optima. answered 21 Oct '12, 15:41 Matthew Salt... ♦ 
No need to edit the titles to add "Solved". Just "accept" an answer to highlight it and show it answered in the question list.