Possible Duplicate:
Linear programming boundedness
Consider the following LP:
$\max$ $\sum_{i=1}^N b_i \pi_i$
s.t. $\;\;$ $\pi_i-\pi_j\leq 1 $ $\quad$ for each $(i,j) \in \tilde{A}$
$\sum_{i=1}^N a_s^i \pi_i \leq 1$ for each $s \in S$
This LP is always feasible, since zero is a feasible solution. Now, in order to find the optimum value, we relax the LP by multiplying second set of constraints by nonnegative Lagrangian multipliers $\lambda_s, s\in S$ and add them to the objective function. Thereafter, we get the following relaxed dual LP:
$L(\lambda)$: $\max$ $\sum_{i=1}^N (b_i+\sum_{s\in S}\lambda_s a_s^i)\pi_i - \sum_{s\in S}\lambda_s$
s.t. $\pi_i-\pi_j\leq 1$ $\quad$ for each $(i,j) \in \tilde{A}$
Let us consider the Lagrangian dual LP. This LP can be formulated as follows:
LD: $\min$ $L(\lambda)$
s.t. $\lambda \geq 0$
Now, the question is as follows. Both LP and LD problems are feasible (e.g. zero vecor). Moreover, if the LD is bounded so is the LP. What cab be said if the LD is unbounded. Consider that in my case LP is always feasible.
