2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

I think there are some details missing in your question.

Let the primal be the minimization of $c^Tx$, subject to $Ax = b, x\geq 0$. We will show the following: if the optimal simplex tableau gives us a non-degenerate basic feasible solution with $c_i - z_i \geq 0$ for all variables, then the dual has a unique optimal solution.

Use the complementary slackness conditions.
Note that rank$(A^T_{n \times m})$ = rank$(A_{m \times n}) = m$, a common assumption (because we can just delete rows if redundant). This means the basis matrix $B$ is of dimension $m \times m$.
There are $m$ constraints, and so, $m$ dual variables $y_1, \ldots y_m$.

Consider the basic variable $x_{Bi}$ in this optimal BFS $x$, and an optimal solution $y$ of the dual. As the BFS is non-degenerate, $x_{Bi} > 0$. The complementary slackness conditions give, $x_{Bi} (A^Ty - c)_{Bi} = 0$ which imply, $(A^Ty)_{Bi} = a_{Bi}^Ty = c_{Bi}$. Here, $a_{Bi}^T$ is the row corresponding to the basic variable $x_{Bi}$ in $A^T$. Repeating this for all the $m$ basic variables, we get the system of equations, compactly represented as $(A^Ty)_{B} = c_{B}$. By the definition of a basis, the set of all rows $a_{B1}^T, \ldots, a_{Bm}^T$ are all linearly independent. Thus, there exists only a unique solution $y$ to $(A^Ty)_{B} = c_{B}$.
In fact, multiplying by $(B^{-1})^T$ gives us $y = (B^{-1})^Tc_{B}$ as claimed. Thus, this solution is unique.

We must also ensure that $y$ is feasible for the dual. This comes from the fact that $c_i - z_i = c_i - a_i^Ty \geq 0$ for all $i$. The dual's feasible region is given by $A^Ty \leq c$. So, $y$ is feasible as well. This is what we had to show!

$\endgroup$
  • $\begingroup$ I wish this came sooner... haha. Thank you anyway! $\endgroup$ – Ian Lee Apr 14 at 15:56
  • $\begingroup$ No problem! Linear programming can be hard! $\endgroup$ – Ameya Apr 14 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.