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


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.