We have an LP problem with 4 extreme points $x_i$, $i=1,2,3,4$ and 4 extreme directions $d_i$ with objective function with coefficients given by vector $c$ such that $c^T x_1 = 7, c^T x_2 = 12, c^Tx_3 = 8, c^Tx_4 = 10$ and $c^Td_1 = -5 $, $c^Td_2=0$, $c^Td_3=2$, $c^T d_4 = 3$.

Question is; Is there an optimal solution to this LP? if so, is it unique?


first, we write the LP problem as follows

$$ \min 7 \lambda_1 + 12 \lambda_2 + 8 \lambda_3 + 10 \lambda_4 - 5 \mu_1 + 2 \mu_3 + 3 \mu_4 $$

where $\sum^4 \lambda_i= 1 $ and $\lambda$'s and $\mu$'s are $\geq 0$.

now, in my notes, it says that this LP is unbounded because $c^T d_1 < 0$ so there is not optimum. Is this true? Am I having hard time understading why this follows.


Your note is absolutely right.

The only constraint bounding $\mu_1$ is $\mu_1 \geq 0$. Thus, one may have a solution where $\lambda_1 = 1$ and $\mu_1 = M$ where $M$ is arbitrarily big (and every other component is zero). In this case, the objective function would be $-5M + 7$.


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.