# Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate and unique?

 -1 How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate and unique? What I tried: Let the primal be $$\max z=cx$$ subject to $$Ax \le b, x \ge 0$$ Let the dual be $$\min z'=b^Ty$$ subject to $$A^Ty \le c^T, y \ge 0$$ Let the primal solution be basic variables: $$x_{B_1}, x_{B_2}, ..., x_{B_i}$$ non-basic variables: $$x_{NB_1}, x_{NB_2}, ..., x_{NB_i}$$ Let a dual solution be basic variables: $$y_{BB_1}, y_{BB_2}, ..., y_{BB_i}$$ non-basic variables: $$y_{NBB_1}, y_{NBB_2}, ..., y_{NBB_i}$$ By degeneracy of primal solution, one of the basic variables is zero: $$x_{B_{i_0}} = 0$$ Zero or not, since it's a primal basic variable, we have: $$z_{B_{i_0}} - c_{B_{i_0}} = 0 = y_{B_{i_0}}$$ Note that $$y_{B_{i_0}}$$ is not necessarily the same as $$y_{B'_{i_0}}$$ By uniqueness of primal solution, all of the non-basic variables of primal have positive reduced cost: $$z_{NB_1} - c_{NB_1} > 0$$ $$\vdots$$ $$z_{NB_i} - c_{NB_i} > 0$$ To show that the dual has alternative solutions, we must show that one of these is true: $$z_{NBB_1} - b_{NBB_1} = 0$$ $$\vdots$$ $$z_{NBB_i} - b_{NBB_i} = 0$$ I think I could prove this assuming $$\text{non-basic = slack}$$ which is not necessarily true of course. How would I prove this? asked 07 May '16, 09:23 BCLC 8●3●13 accept rate: 0%
Be the first one to answer this question!
 toggle preview community wiki

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "Title")
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×231
×17
×6
×5

Asked: 07 May '16, 09:23

Seen: 750 times

Last updated: 07 May '16, 09:38

### Related questions

OR-Exchange! Your site for questions, answers, and announcements about operations research.