Question

For the linear program

$\begin{array}{l}\mathbf{max}{\mathbf{x}}_{\mathbf{1}}\mathbf{-}\mathbf{2}{\mathbf{x}}_{\mathbf{3}}\\ {\mathbf{x}}_{\mathbf{1}}\mathbf{-}{\mathbf{x}}_{\mathbf{2}}\mathbf{\le }\mathbf{1}\\ \mathbf{2}{\mathbf{x}}_{\mathbf{2}}\mathbf{-}{\mathbf{x}}_{\mathbf{3}}\mathbf{\le }\mathbf{1}\\ {\mathbf{x}}_{\mathbf{1}}\mathbf{,}{\mathbf{x}}_{\mathbf{2}}\mathbf{,}{\mathbf{x}}_{\mathbf{3}}\mathbf{\ge }\mathbf{0}\end{array}$

Prove that the solution$\mathbf{(}{\mathbf{x}}_{\mathbf{1}}\mathbf{,}{\mathbf{x}}_{\mathbf{2}}\mathbf{,}{\mathbf{x}}_{\mathbf{3}}\mathbf{)}\mathbf{=}\mathbf{(}\mathbf{3}\mathbf{/}\mathbf{2}\mathbf{,}\mathbf{1}\mathbf{/}\mathbf{2}\mathbf{,}\mathbf{0}\mathbf{)}$ is optimal

Short answer

The solution $({\mathrm{x}}_1,{\mathrm{x}}_2,{\mathrm{x}}_3)=(3/2,1/2,0)$is the optimal solution.

Step-by-step solution

Introduction to problem

Consider the three variables namely${\mathrm{x}}_1,{\mathrm{x}}_2,{\mathrm{x}}_3$and the two linear inequalities as follows,

$\begin{array}{l}{\mathrm{x}}_1-{\mathrm{x}}_2\le 1\\ 2{\mathrm{x}}_2-{\mathrm{x}}_3\le 1\end{array}$

with a condition, ${\mathrm{x}}_1,{\mathrm{x}}_2,{\mathrm{x}}_3\ge 0$

Assume the inequalities be an equation of the form,

$\begin{array}{l}\left[1\right]{\mathrm{x}}_1-{\mathrm{x}}_2=1\\ \left[2\right]2{\mathrm{x}}_2-{\mathrm{x}}_3=1\\ \left[3\right]{\mathrm{x}}_1,{\mathrm{x}}_2,{\mathrm{x}}_3=0\end{array}$

Equation’s last line signifies those variables${\mathrm{x}}_1,{\mathrm{x}}_2,{\mathrm{x}}_3$ can never be negative.

Consider the three cases:

Case (I): ${\mathrm{x}}_1=0$

Case (II):${\mathrm{x}}_2=0$

Case (III):$x_3=0$

Evaluate case  x1=0

In this case, Substitute ${\mathrm{x}}_1=0$in Equation [1],

$\begin{array}{c}\left[1\right]{\mathrm{x}}_1-{\mathrm{x}}_2=1\\ 0-{\mathrm{x}}_2=1[\because {\mathrm{x}}_1=0]\\ {\mathrm{x}}_2=-1\\ \end{array}$

But no variable can be negative.

Hence, discard the Case (I)

Evaluate case  x2=0

In this case, substitute$x_2=0$in Equation [1] as follows,

$\begin{array}{c}\left[1\right]x_1-x_2=1\\ x_1-0=1[\because x_2=0]\\ x_1=1\\ \end{array}$

Substitute$x_2=0$in Equation [2] as follows,

$\begin{array}{c}\left[2\right]2x_2-x_3=1\\ 0-x_3=1[\because x_2=0]\\ x_3=-1\end{array}$

But no variable can be negative.

Hence, discard the Case (II).

Evaluate case  x2=0

In this case, substitute$x_3=0$in Equation as follows,

$\begin{array}{c}\left[2\right]2x_2-x_3=1\\ 2x_2-0=1[\because x_3=0]\\ 2x_2=1\\ x_2=\frac{1}{2}\end{array}$

Substitute${\mathrm{x}}_2=\frac{1}{2}$in Equation [1] as follows,

$\begin{array}{c}\left[1\right]x_1-x_2=1\\ x_1-\frac{1}{2}=1\text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}}[\because x_2=\frac{1}{2}]\\ x_1=1+\frac{1}{2}\\ x_1=\frac{3}{2}\end{array}$

Therefore, this case is possible.

Finding  max x1−2x3

The maximum of $x_1-2x_3$ can be calculated as follows,

$\begin{array}{c}{x}_1-2x_3=\frac{3}{2}-2\times 0\\ =\frac{3}{2}\end{array}$

Therefore, the optimal solution at$({\mathrm{x}}_1,{\mathrm{x}}_2,{\mathrm{x}}_3)$ is $(3/2,1/2,0)$.