The initial tableau of a linear programming problem is given. Use the simplex method to solve the problem.
$\left[\begin{array}{rrrrrr|r} x _1 & x _2 & s_1 & s_2 & s_3 & z & \\ 1 & 4 & 1 & 0 & 0 & 0 & 11 \\ 2 & 1 & 0 & 1 & 0 & 0 & 14 \\ 1 & 1 & 0 & 0 & 1 & 0 & 6 \\ \hline-4 & -2 & 0 & 0 & 0 & 1 & 0\end{array}\right]$
The maximum is $\square$ when $x_1=$ $\square$ . $x_2=$ $\square$ $s_1=$ $\square$ $. s _2=$ $\square$ , and $s _3=$ $\square$.
(Type integers or simplified fractions.)
Answer (1)
Identify the pivot column by selecting the most negative entry in the last row.
Determine the pivot row by dividing the rightmost column by the corresponding entries in the pivot column and selecting the smallest non-negative result.
Perform row operations to make the pivot element 1 and all other entries in the pivot column 0.
Read the solution from the final tableau: The maximum is 24 when x 1 = 6 , x 2 = 0 , s 1 = 5 , s 2 = 2 , and s 3 = 0 .
Explanation
Understanding the Problem We are given the initial tableau of a linear programming problem and asked to use the simplex method to find the maximum value of z and the corresponding values of x 1 , x 2 , s 1 , s 2 , and s 3 .
Identifying the Pivot Column The initial tableau is: x 1 1 2 1 − 4 x 2 4 1 1 − 2 s 1 1 0 0 0 s 2 0 1 0 0 s 3 0 0 1 0 z 0 0 0 1 11 14 6 0
The most negative entry in the last row is -4, so the pivot column is x 1 .
Identifying the Pivot Row and Element To find the pivot row, we divide the rightmost column by the corresponding entries in the pivot column: 11/1 = 11 14/2 = 7 6/1 = 6 The smallest non-negative result is 6, so the pivot row is the third row. The pivot element is the entry at the intersection of the pivot row and pivot column, which is 1.
Performing Row Operations Now, we perform row operations to make the pivot element 1 (it already is) and all other entries in the pivot column 0. The row operations are: R1 = R1 - R3 R2 = R2 - 2 R3 R4 = R4 + 4 R3
Applying these operations, we get the new tableau: x 1 0 0 1 0 x 2 3 − 1 1 2 s 1 1 0 0 0 s 2 0 1 0 0 s 3 − 1 − 2 1 4 z 0 0 0 1 5 2 6 24
Since there are no negative entries in the last row, we have reached the solution.
Reading the Solution From the final tableau, we can read the solution: The maximum value of z is 24. x 1 = 6 x 2 = 0 s 1 = 5 s 2 = 2 s 3 = 0
Examples
Linear programming is used in business to maximize profits or minimize costs. For example, a company might use linear programming to determine the optimal mix of products to produce, given constraints on resources such as labor and materials. The simplex method is a common algorithm for solving linear programming problems. In this case, we found the maximum profit (z) given constraints represented by the equations in the tableau.
