the dual variables are not unique in an optimal solution to the dual problem if primal problem has redundant constraints

Question

Show that in the transportation problem the linear equality constraints are not linearly independent, and that in an optimal solution to the dual problem the dual variables are not unique. Generalize this observation to any linear program having redundant equality constraints.

Answer 1

Hint:

Consider the optimization problem

$$\min c^Tx$$

subject to

$$ \begin{bmatrix} A \\ \lambda^TA\end{bmatrix} x= \begin{bmatrix} b \\ \lambda^Tb \end{bmatrix}$$

$$x \geq 0$$

where $A\in \mathbb{R}^{m \times n} $, $\lambda \in \mathbb{R}^{m \times 1}$.

The dual is $$\max p^Tb + q \lambda^Tb$$

$$\begin{bmatrix} p^T & q \end{bmatrix} \begin{bmatrix} A \\ \lambda^TA\end{bmatrix}\leq c $$

Suppose $(p^*,q^*)$ is an optimal solution for the dual, verify that $(p^*+\lambda, q^*-1)$ is another optimal solution.

As for the transportation problem, given the incidence matrix, you should be able to recover the last row given the first $m-1$ rows easily.

Edit: Verifying the new solution is still feasible for dual.

We already know that $$\begin{bmatrix} p^{*T} & q^* \end{bmatrix} \begin{bmatrix} A \\ \lambda^TA\end{bmatrix}=p^{*T}A+q^*\lambda^TA\leq c $$

Check that $$\begin{bmatrix} (p^*+\lambda)^{T} & (q^*-1) \end{bmatrix} \begin{bmatrix} A \\ \lambda^TA\end{bmatrix}=(p^{*}+\lambda )^TA+(q^*-1)\lambda^TA\leq c $$