# If the primal is unbounded, then the dual is infeasible.

 -1 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 non-basic 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 8●3●12 accept rate: 0% If you use weak duality, you will get your proof right away. (20 Apr '16, 03:16) Sune @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? (20 Apr '16, 10:03) BCLC 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. (20 Apr '16, 14:27) Sune @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? (22 Apr '16, 05:56) BCLC A finite sum of finite numbers is usually finite. (22 Apr '16, 06:32) Sune Thanks @Sune ^-^ Post as answer? (23 Apr '16, 00:39) BCLC showing 5 of 6 show 1 more comments
Be the first one to answer this question!
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×231
×20
×17
×8
×3