How can I show the corresponding dual solution is unique when the given primal solution is nondegenerate, basic feasible?

2.1k Views Asked by At

the given problem is to show that

if $x_1,...,x_n$ is a nondegenerate basic feasible solution of the primal LP

max $\sum_{j=1}^{n}c_jx_j$

s.t. $\sum_{j=1}^na_{ij}x_j\leq b_i, \forall i\in\{1,...,m\}$

$x_j\geq 0, \forall j\in\{1,...,n\}$

then the problem given as

$\sum_{i=1}^m a_{ij}y_i =c_j$ whenever $x_j>0$

$y_i=0$ whenever $\sum_{j=1}^n a_{ij}x_j < b_i$

has a unique solution.

If $B$ denote the corresponding basis of the given basic solution, letting $y^T= c_B^TB^{-1}$ guarantees the existence of the solution, where $c_B$ denotes the coefficients of the objective functions in the primal corresponding to the given basis.

Now I let $z\neq y$ be a solution of the problem below and tried to induce the contradiction, but could not proceed further. What can I do here? Or is there simpler version rather than this apagogic approach?