1

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?

Try:

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.

Community
  • 1
James
  • 3,997

1 Answers1

0

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$.

Rafael Colares
  • 168