# Linear programming without use Gauss-Jordan row operations

I want some help for the following LP:

\begin{align} \mbox{maximize} \quad& 24 x_1 + 22 x_2 + 45 x_3 \\ \mbox{subject to} \quad& 2x_1+x_2+3x_3 \leq 42 \\ & 2x_1 + x_2 + 2x_3 \leq 40 \\ & x_1 + \tfrac{1}{2}x_2 + x_3 \leq 45 \\ & x_1, x_2, x_3, x_4 \geq 0 \\ \end{align}

The above problem has to be solved by inspection without use the Gauss-Jordan rows operations.

• remember to use mathjax to typeset math in order to improve readability – Lorenzo Stella Jul 31 '16 at 16:47

Note that

1. $x_4$ can be thrown away.
2. The third constraint multiplied by two $2x_1 + x_2 + 2x_3 \le 90$ is redudant due to the second constraint $2x_1 + x_2 + 2x_3 \le 40$.

So the original LP is actually

\begin{align} \max \quad& 24 x_1 + 22 x_2 + 45 x_3 \\ \mbox{s.t.} \quad& 2x_1+x_2+3x_3 \leq 42 \tag{#}\label{OP}\\ & 2x_1 + x_2 + 2x_3 \leq 40 \\ & x_1, x_2, x_3 \geq 0 \\ \end{align}

By adding slack variables $s_1,s_2$ to the LP, we have

\begin{align} \max z= \quad& 24 x_1 + 22 x_2 + 45 x_3 \tag{$\star$}\label{z1} \\ \text{s.t.} \quad& 2x_1+x_2+3x_3+s_1 = 42 \tag{1}\label{c11} \\ & 2x_1 + x_2 + 2x_3+s_2 = 40 \tag{2}\label{c12} \\ & x_1, x_2, x_3, s_1, s_2 \geq 0 \tag{FC}\label{fc} \end{align}

Since the question asks us to solve this LP by inspection, we start from the most obvious feasible solution to \eqref{c11} and \eqref{c12}: $(x_1,x_2,x_3)=(0,0,0)$.

We can regard $z$ in \eqref{z1} as a linear function of $x_1,x_2$ and $x_3$ "around the origin $(0,0,0)$". (More rigourously, $z$ is a linear function from $\Bbb R^3$ to $\Bbb R$ restricted to a neighbourhood around the origin.) This is because we can make $s_i$ the subject of constraint $(\rm i)$.

\begin{align} \max z= \quad& 24 x_1 + 22 x_2 + 45 x_3 \tag{$\star$} \\ \text{s.t.} \quad& s_1 = 42 - (2x_1+x_2+3x_3) \tag{1'}\label{f11} \\ & s_2 = 40 - (2x_1 + x_2 + 2x_3) \tag{2'}\label{f12} \\ & x_1, x_2, x_3, s_1, s_2 \geq 0 \tag{FC} \end{align}

When $x_i$'s change, we can adjust $s_j$'s according to \eqref{f11} and \eqref{f12} so that \eqref{c11} and \eqref{c12} are satisfied as long as $x_i$'s aren't too large.

From \eqref{z1}, it's natural to consider increasing $x_3$ so as to increase $z$. \eqref{c11} and \eqref{c12} impliy $x_3 \le 42/3 = 14$ and $x_3 \le 40 /2 = 20$ respectively, so $x_3 \le 14$. Check that $(x_1,x_2,x_3) = (0,0,14)$ verifies \eqref{OP}.

To look at the behavior of the function $z$ "around (0,0,14)", we make $x_3$ a variable depending on $x_1,x_2$ and $s_1$.

Make $x_3$ the subject of \eqref{c11}, and substitute it into $\eqref{z1}$. The objective function then becomes

\begin{align} z =& 24x_1+22x_2+45(14-\frac23x_1-\frac13x_3-\frac13s_1) \\ =& 630 - 6x_1 + 7x_2 -15s_1 \tag{$\star'$} \label{z2} \end{align}

By a similar reasoning, we can regard $z$ in \eqref{z2} as an affine function of $x_1,x_2$ and $s_1$. Since it has a positive coefficient (7) of $x_2$, by increasing $x_2$. So, we keep $x_2$ and $x_3$, and try to see how they depend on $x_1,s_1$ and $s_2$

$\eqref{c11}-\eqref{c12}: x_3 + s_1 - s_2 = 2$ so $$x_3 = 2 - s_1 + s_2.\tag{3}\label{x3}$$ Substitute \eqref{x3} into \eqref{c12}.

\begin{align} 2x_1 + x_2 + 2(2 - s_1 + s_2) + s_2 &= 40 \\ x_2 &= 36 - 2x_1 + 2s_1 - 3s_2 \tag{4}\label{x2} \end{align}

Substitute the above equation into \eqref{z2}.

\begin{align} z =& 630 - 6x_1 + 7x_2 -15s_1 \\ =& 630 - 6x_1 + 7(36 - 2x_1 + 2s_1 - 3s_2) - 15s_1 \\ =& 630 - 6x_1 + 252 - 14x_1 + 14s_1 - 21s_2 - 15s_1 \\ =& 882 - 20x_1 - s_1 - 21s_2 \tag{$\diamondsuit$}\label{z3} \\ \le& 882 \quad \text{due to \eqref{fc}} \end{align}

We finally arrive at an expression for the objective function $z$ which contains no positive coefficients. We set $x_1, s_1$ and $s_2$ to zero, and find the corresponding values of $x_2$ and $x_3$.

\begin{align} x_3 \stackrel{\eqref{x3}}=& 2 \\ x_2 \stackrel{\eqref{x2}}=& 36 \end{align}

Hence, the optimal solution is $(x_1,x_2,x_3) = (0,36,2)$ and maximal value is 882.