Linear Programming - at most 3 variables are not zero

Question

We have the following LP problem:

$\max \ c_1 x_1+c_2 x_2+\dotsb+c_n x_n$

$\sum^n_{j=1}a_{ij}x_j\le b_i \ : \ i \in \{1,2,3\}$

$x_1,x_2,\dotsc,x_n \ge 0$

Assume that there exist a feasible solution,and that the problem is bounded.

Prove that there exists an optimal solution,which has at most 3 variables which are not equal to $0$.

Any ideas??? Or hints?

Answer 1

The following constructive algorithm builds an optimal solution with at most $3$ variables which are not equal to $0$:

For i = 1,2,3 :

1. Order the variables by non increasing order of the ratio $c_j/a_{ij}$.
2. Let $F_i$ be the index of the variable that comes first in the list.

3. If $F_i$ has not been selected yet:

   $\quad$ Set $x_{F_i} = b_i/a_{ij}$

   Else:

   $\quad$ Let $\alpha$ be the value of $x_{F_i}$. Set $x_{F_i}=\min\{\alpha, b_i/a_{ij}\}$

Set $x_j=0\; \forall j \notin \{F_1,F_2,F_3 \}.$

For each constraint, you select the variable that has highest cost and lowest contribution to the left hand side of the constraint (step $1$), and you set its value the maximum value possible (step $3$). In the worst case, the selected variable is different for each $i=1,2,3$, so you have $3$ variables that have a positive value.