Degeneracy, redundant constraints, multiple optimal solutions in LP

Question

I am not sure about the relationship among degeneracy, redundant constraints, and multiple optimal solutions in linear programming problems. In the book INTRODUCTION TO OPERATIONS RESEARCH by Hillier and Lieberman, 7th edition, page 130, the authors says,

Whenever a problem has more than one optimal BF solution, at least one of the nonbasic variables has a coefficient of zero in the final row 0, so increasing any such variable will not change the value of objective function.

Note that this statement is made in terms of a simplex tableau, which from what I understand is saying, an LP has multiple optimal solutions if it has degeneracy.

However, let's consider the following problem:

$$\text{minimize: } x_1 + x_2$$ Subject to, $$x_1+x_2 = 2 $$ $$x_1-x_2 = 2 $$ $$x_1 = 2 $$ $$x_1,x_2\geq0$$

Here, we have redundant constraints since all three lines meet at a single point but the optimal solution is unique $(2,0)$.

Is there anything wrong with my understanding of the above problem?

Whenever we encounter degeneracy in the simplex method, can we conclusively say anything about having redundant constraints and/or multiple optimal solutions?

Answer 1

In my opinion, your constraints do not represent the situation. You can have more than one optimal basic solution if the slope of the objective function is equal to one of the constraints. Then the objective function lies on a line, between two corners of the feasible region. I give you an example with the corresponding graph:

$\textrm{max} \ Z=500x_{1}+300x_{2}$

s.t.

$15x_{1}+5x_{2}\leq 300$

$10x_{1}+6x_{2}\leq 240$

$8x_{1}+12x_{2}\leq 450$

$x_{1},x_{2}\geq 0$

The corresponding graph is

To make the graph we have to solve the (in-)equalities for $x_2$. I focus on the the objective function and on the constraint with the same slope.

1. $\textrm{Objective function}$

$Z=500x_{1}+300x_{2}$

$Z-500x_{1}=300x_{2}$

$\frac{Z}{300}-\frac53x_1=x_2$

The slope is $-\frac53$

2. $\textrm{Second constraint}$

$6x_{2}\leq 240-10x_{1}$

$x_{2}\leq 40-\frac{10}6x_{1}$

The slope is $-\frac53$ as well.

So you may have multiple solution if at least one of the constraints have the same slope as the objective function. In this case you have two optimal BFS: $(x_1,x_2)=\left(\frac52, \frac{215}{6} \right), (x_1,x_2)=\left(15, 15 \right)$

And between the two corners on the green line the solution are optimal as well. The multiple optimal solution can be written as $(x_1^*,x_2^*)=\left(x_1, \ 40-\frac{10}6x_{1}\right) \ \ \forall \ \frac52 \leq x_1\leq 15$