# On the bounds of the objective function in a standard LP

Consider a standard linear programming (LP) such as: \begin{align} \sum_{i=1}^{N}\frac{a_{i}}{b_{i}}x_{i}\end{align}

\begin{align}\text{s.t. }\left ( \sum_{i=1}^{N}x_{i}=1 \; , \; \sum_{i=1}^{N}b_{i}x_{i}=c>0\right )\end{align} Note: The variables and coefficients are positive.

Can we determine lower- and upper-bounds for the objective function, in terms of $a_{i},b_{i}, c$?

In general, the simple expressions, in terms of $a_i,b_i,c$, for the required upper and lower bounds are $\max\left\{ \dfrac{a_i}{b_i} : 1 \le i \le N \right\}$ and $\min\left\{ \dfrac{a_i}{b_i} : 1 \le i \le N \right\}$ respectively.

As a consequence of the Fundamental Theorem of Linear Programming, I'll just consider the basic solutions of this LPP.

Suppose that $x_i,x_j$ (with $1 \le i < j \le N$ for convenience) are chosen as the basic variables. Then we have the basis matrix

\begin{equation*} B = \begin{bmatrix} 1 & 1 \\ b_i & b_j \end{bmatrix}, x_B = \begin{bmatrix}x_i \\ x_j\end{bmatrix}, b = \begin{bmatrix}1 \\ c\end{bmatrix}. \end{equation*}

$\therefore Bx_B = b$. If $x_i,x_j \ge 0$, from the first constraint $x_i + x_j = 1$, we know that the value of the objective function is the convex combination of $\dfrac{a_i}{b_i}$ and $\dfrac{a_j}{b_j}$.

\begin{align*} & \quad\sum_{i=1}^{N}\frac{a_{i}}{b_{i}}x_{i} \\ & = \frac{a_i}{b_i} x_i + \frac{a_j}{b_j} x_j \\ & = \frac{a_i}{b_i} x_i + \frac{a_j}{b_j} (1 - x_j) \\ & \in \left[ \min\left\{ \frac{a_i}{b_i},\frac{a_j}{b_j} \right\},\max\left\{ \frac{a_i}{b_i},\frac{a_j}{b_j} \right\} \right] \end{align*}

Hence, the problem is done. I include more conditions for the feasibility of $x_B = (x_i,x_j)^T$.

Case 1: $b_i = b_j$

If the basic solution is feasible, then $b_i = b_j = c$ and $x_B = (0,1)^T$ or $(1,0)^T$.

Case 2: $b_i \ne b_j$

Then $B$ is invertible.

\begin{equation*} B^{-1} = \frac{1}{b_j - b_i} \begin{bmatrix} b_j & -1 \\ -b_i & 1 \end{bmatrix} \end{equation*}

Compute $x_B = B^{-1} b$. Note that it should be non-negative.

\begin{equation*} x_B = \begin{bmatrix}x_i \\ x_j\end{bmatrix} = \frac{1}{b_j - b_i} \begin{bmatrix} b_j & -1 \\ -b_i & 1 \end{bmatrix} \begin{bmatrix}1 \\ c\end{bmatrix} = \begin{bmatrix} \dfrac{b_j - c}{b_j - b_i} \\ \dfrac{c - b_i}{b_j - b_i} \end{bmatrix} \ge 0 \end{equation*}

If you assume either $b_j > b_i$ or $b_i > b_j$, then we have $b_i \le c \le b_j$ or $b_j \le c \le b_i$.