Prove: If the primal is unbounded, then the dual is infeasible. What I tried: Let the primal be: Max/Min $z=c_1x_1 + ... + c_nx_n$ s.t. $$a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n \le b_1$$ $$a_{21}x_1 + a_{22}x_2 + ... + a_{2n}x_n \le b_2$$ $$\vdots$$ $$a_{m1}x_1 + a_{m2}x_2 + ... + a_{mn}x_n \le b_m$$ $$x_1, ..., x_n \ge 0$$ Let $l$ represent the $l$th iteration. If we have some basic feasible solution while the primal is unbounded, then there exists some nonbasic variable $x_k$ whose coefficients in the $lth$ iteration are $a_{1kl}, a_{2kl}, ..., a_{mkl} \le 0$ and $z_{kl}  c_k < 0$ where $$z_{kl} = a_{1kl}c_{b_{1l}} + a_{2kl}c_{b_{2l}} + ... + a_{mkl}c_{b_{ml}}$$ where $c_{b_{1l}}, ..., c_{b_{ml}}$ are the coefficients in the objective function corresponding to the $m$ basic variables at iteration $l$, namely, $b_{1l}, ..., b_{ml}$. Then the dual contains a row that looks like: $$a_{1kl}y_1 + a_{2kl}y_2 + ... + a_{mkl}y_m \ge c_k$$ $\because \ a_{1kl}, a_{2kl}, ..., a_{mkl} \le 0$ and $y_j \ge 0$, we have $$a_{1kl}y_1 + a_{2kl}y_2 + ... + a_{mkl}y_m \le 0$$ The primal is infeasible if $z_{kl} \ge 0 \ \because$ we would have $c_k > 0$. What if $z_{kl} < 0$? Since $a_{1kl}, a_{2kl}, ..., a_{mkl}$ and $a_{1kl}c_{b_{1l}} + a_{2kl}c_{b_{2l}} + ... + a_{mkl}c_{b_{ml}} \le 0$, I guess $c_{b_{1l}}, ..., c_{b_{ml}} \ge 0$. I'm not sure how to conclude the dual is infeasible in the case that $z_{kl} < 0$. Did I go wrong somewhere? How can I approach this? Is there another way I can prove this? Also, my book says that this is a corollary to complementary slackness. What's the relevance of complementary slackness? asked 19 Apr '16, 15:21 BCLC
showing 5 of 6
show 1 more comments

If you use weak duality, you will get your proof right away.
@sune Afaik, weak duality says $$cx \le b^{T}y$$ So if $$cx = \infty$$, then $$b^{T}y = \infty$$. If wrong, why? If right, then it seems that the dual is unbounded? If not, why? If so, how does that mean that the dual is infeasible?
Weak duality says that \(b^Ty\geq \infty\) for all \(y\) feasible for the dual. Suppose the dual had a feasible solution, say \(\tilde{y}\). Evaluate the value of \(\tilde{y}\) and get a contradiction.
@Sune I don't quite see what exactly is the contradiction. Are feasible solutions necessarily finite? I just thought they needed to be positive. Oh wait are you saying that $$b^{T}y$$ is going to be negative?
A finite sum of finite numbers is usually finite.
Thanks @Sune ^^ Post as answer?