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$$


$$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$$


$$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's gravatar image

accept rate: 0%

edited 07 May '16, 09:38

Be the first one to answer this question!
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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



Asked: 07 May '16, 09:23

Seen: 750 times

Last updated: 07 May '16, 09:38

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