0
$\begingroup$

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.

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

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.

$\endgroup$

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.