A computer science problem by Christian Daang

Standard form of z: $-2x_{1} + 4x_{2} - 5x_{3} + 6x_{4} = 0$

Standard form of conditions: $\begin{cases} x_{1} + 4x_{2} - 2x_{3} + 8x_{4} + x_{5} = 2 \\ -x_{1} + 2x_{2} + 3x_{3} + 4x_{4} + x_{6} = 1 \end{cases}$

$x_{1} , x_{2} , x_{3}, x_{4} \ge 0$

$x_{5}$ and $x_6$ are basic variables while the rest x are non-basic variable.

Process involving the 1st table

-5 is the most negative from the coefficients of z.

Negative Ratio is not allowed.

automatic, choose 3, intersection of column $x_{3}$ and row $x_{6}$ and make it 1 in the 2nd table.

$\rightarrow x_{3}$ enters the basic variable, $x_{6}$ leaves the basic variable.

Make row z, column $x_{3}$ and row $x_{5}$ , column $x_{3}$ zero in the 2nd table.

Process involving the 2nd table

$-\frac{11}{3}$ is most negative.

5*(row $x_{3}$ in the 2nd table) + row z in the 1st table to obtain the results of row z in the 2nd table.

2*(row $x_{3}$ in the second table) + row $x_{5}$ in the 1st table to obtain the results of row $x_{5}$ in the 2nd table.

Negative ratio is not allow, then, automatically, choosing the intersection of row $x_{5}$ and column $x_{1}$ and make it one in the 3rd table.

$\rightarrow x_{1}$ enters the basic variable, $x_{5}$ leaves the basic variable.

Make row z, column $x_{1}$ and row $x_{3}$ , column $x_{1}$ zero in the 3rd table.

Process involving the 3rd table

11*(row $x_{5}$ in the 2nd table) + row z in the 2nd table to obtain the results of row z in the 3rd table.

row $x_{5}$ in the 2nd table + row $x_{3}$ in the 2nd table to obtain the result of row $x_{3}$ in the 3rd table.

$\rightarrow \text {max} \ x_{1}$ that make z max is 8

$\rightarrow \text{max} \ x_{3}$ that make z max is 3

$\rightarrow \boxed{\text{max} \ z = 31 , x_{1} = 8, x_{3} = 3, x_{2} = x_{4} = 0 }$ .

Relevant wiki: Linear Programming

$\text{For max } z , x_2 \text{ and } x_4 \text{ should be minimum and } x_1 \text{ and } x_3 \text{ should be maximum } \\ \text{For the Given constraints } x_2=x_4=0 \\ \text{The question transforms into a linear optimization problem}\\ \text{Now the new conditions are : } \\ x_1-2x_3\le 2\\ 3x_3-x_1\le 1 \\ x_1,x_3 \ge 0 \\ \text{Drawing a graph between } x_1 \text{ and } x_3 \text{will give us a enclosed area } \\ \text{One of the corner points of feasible area gives us the max value of } z$

$\text{Enclosed area is a quadrilateral with points } (0,0) , (8,3) , (0,\frac{1}{3}),(2,0) \\ \text{Point } x_1=8 \text{ and } x_3=3 \text{ Gives us the Maximum } z \\ z=16+15 = \boxed{31}$

Let $A = x_1 + 4x_2 - 2x_3 + 8x_4 \leq 2$ ,

$B = -x_1 + 2x_2 +3x_3 + 4x_4 \leq 1$ .

$z = 11A + 9B - 66x_2 - 130x_4 \leq 22 + 9 + 0 + 0 = 31$ .

Maximised when $(x_1, x_2, x_3, x_4) = (8,0,3,0)$ .