LP Simplex & Sensitivity Analysis

Cheatsheet Content

1. LP Problem Definition Maximize $z = -5x_1 + 5x_2 + 13x_3$ Subject to: $-x_1 + x_2 + 3x_3 \le 20$ $12x_1 + 4x_2 + 10x_3 \le 90$ $x_1, x_2, x_3 \ge 0$ Slack variables: $x_4, x_5$ for constraints 1 and 2 respectively. Standard form: Maximize $z = -5x_1 + 5x_2 + 13x_3 + 0x_4 + 0x_5$ Subject to: $-x_1 + x_2 + 3x_3 + x_4 = 20$ $12x_1 + 4x_2 + 10x_3 + x_5 = 90$ $x_1, x_2, x_3, x_4, x_5 \ge 0$ 2. (a) Final Simplex Table (Matrix Approach) Basic Variables: $x_2, x_3$ The basic variables are $x_B = [x_2, x_3]^T$. The non-basic variables are $x_N = [x_1, x_4, x_5]^T$. From the constraints, identify $B$ and $N$ matrices: $A = \begin{pmatrix} -1 & 1 & 3 & 1 & 0 \\ 12 & 4 & 10 & 0 & 1 \end{pmatrix}$ $c = \begin{pmatrix} -5 \\ 5 \\ 13 \\ 0 \\ 0 \end{pmatrix}$ $b = \begin{pmatrix} 20 \\ 90 \end{pmatrix}$ The columns corresponding to $x_2, x_3$ form the basis matrix $B$: $B = \begin{pmatrix} 1 & 3 \\ 4 & 10 \end{pmatrix}$ The columns corresponding to $x_1, x_4, x_5$ form the non-basis matrix $N$: $N = \begin{pmatrix} -1 & 1 & 0 \\ 12 & 0 & 1 \end{pmatrix}$ Calculate $B^{-1}$ $det(B) = (1)(10) - (3)(4) = 10 - 12 = -2$ $B^{-1} = \frac{1}{-2} \begin{pmatrix} 10 & -3 \\ -4 & 1 \end{pmatrix} = \begin{pmatrix} -5 & 3/2 \\ 2 & -1/2 \end{pmatrix}$ Calculate Optimal Basic Solution ($x_B^*$) $x_B^* = B^{-1}b = \begin{pmatrix} -5 & 3/2 \\ 2 & -1/2 \end{pmatrix} \begin{pmatrix} 20 \\ 90 \end{pmatrix} = \begin{pmatrix} -5(20) + (3/2)(90) \\ 2(20) + (-1/2)(90) \end{pmatrix} = \begin{pmatrix} -100 + 135 \\ 40 - 45 \end{pmatrix} = \begin{pmatrix} 35 \\ -5 \end{pmatrix}$ Since $x_3 = -5$, this indicates that the initial assumption of $[x_2, x_3]$ as the optimal basis might be incorrect, or the problem is unbounded/infeasible. However, following the instruction to *construct the complete final simplex table using the matrix approach* assuming it IS the optimal basis: If $x_3$ must be non-negative, this basis is not feasible. Let's re-check the problem or assume the question implies a step in the simplex process, not necessarily the final feasible optimal one. If $x_3 Assuming a typo in the problem statement and $x_3$ should be positive, or we need to present the table for this specified basis regardless of feasibility: The values $x_2 = 35$ and $x_3 = -5$ are the current basic variable values for the table. Calculate Reduced Costs ($\bar{c}_N$) $c_B = \begin{pmatrix} 5 \\ 13 \end{pmatrix}$ (costs for $x_2, x_3$) $c_N = \begin{pmatrix} -5 \\ 0 \\ 0 \end{pmatrix}$ (costs for $x_1, x_4, x_5$) Shadow prices $\pi = c_B^T B^{-1} = \begin{pmatrix} 5 & 13 \end{pmatrix} \begin{pmatrix} -5 & 3/2 \\ 2 & -1/2 \end{pmatrix} = \begin{pmatrix} 5(-5) + 13(2) & 5(3/2) + 13(-1/2) \end{pmatrix} = \begin{pmatrix} -25+26 & 15/2 - 13/2 \end{pmatrix} = \begin{pmatrix} 1 & 1 \end{pmatrix}$ Reduced costs for non-basic variables: $\bar{c}_N^T = c_N^T - \pi N$ $\bar{c}_N^T = \begin{pmatrix} -5 & 0 & 0 \end{pmatrix} - \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} -1 & 1 & 0 \\ 12 & 0 & 1 \end{pmatrix}$ $\bar{c}_N^T = \begin{pmatrix} -5 & 0 & 0 \end{pmatrix} - \begin{pmatrix} 1(-1) + 1(12) & 1(1) + 1(0) & 1(0) + 1(1) \end{pmatrix}$ $\bar{c}_N^T = \begin{pmatrix} -5 & 0 & 0 \end{pmatrix} - \begin{pmatrix} 11 & 1 & 1 \end{pmatrix} = \begin{pmatrix} -16 & -1 & -1 \end{pmatrix}$ Since some reduced costs are negative (e.g., for $x_1$), this basis is not optimal for a maximization problem. However, the question asks for the table for this basis. Calculate the Right-Hand Side (RHS) column: $B^{-1}b$ This was already calculated as $x_B^* = \begin{pmatrix} 35 \\ -5 \end{pmatrix}$. Calculate coefficients for non-basic variables in the tableau: $B^{-1}N$ $B^{-1}N = \begin{pmatrix} -5 & 3/2 \\ 2 & -1/2 \end{pmatrix} \begin{pmatrix} -1 & 1 & 0 \\ 12 & 0 & 1 \end{pmatrix} = \begin{pmatrix} -5(-1) + (3/2)(12) & -5(1) + (3/2)(0) & -5(0) + (3/2)(1) \\ 2(-1) + (-1/2)(12) & 2(1) + (-1/2)(0) & 2(0) + (-1/2)(1) \end{pmatrix}$ $B^{-1}N = \begin{pmatrix} 5 + 18 & -5 + 0 & 0 + 3/2 \\ -2 - 6 & 2 + 0 & 0 - 1/2 \end{pmatrix} = \begin{pmatrix} 23 & -5 & 3/2 \\ -8 & 2 & -1/2 \end{pmatrix}$ Optimal Objective Function Value ($z^*$) $z^* = c_B^T x_B^* = \begin{pmatrix} 5 & 13 \end{pmatrix} \begin{pmatrix} 35 \\ -5 \end{pmatrix} = 5(35) + 13(-5) = 175 - 65 = 110$ Final Simplex Table Structure (for basic variables $x_2, x_3$) Basis $x_1$ $x_2$ $x_3$ $x_4$ $x_5$ RHS $z$ $-16$ $0$ $0$ $-1$ $-1$ $110$ $x_2$ $23$ $1$ $0$ $-5$ $3/2$ $35$ $x_3$ $-8$ $0$ $1$ $2$ $-1/2$ $-5$ NOTE: As $x_3 = -5$, this basis is primal infeasible. This simplex table would typically be an intermediate step in a dual simplex method, or indicates the problem might not have a feasible solution with this basis. 3. (b) Range of RHS Values for Optimal Basis Let the modified RHS be $b' = \begin{pmatrix} b_1' \\ b_2' \end{pmatrix}$. The current basis remains optimal as long as $x_B = B^{-1}b' \ge 0$. $B^{-1}b' = \begin{pmatrix} -5 & 3/2 \\ 2 & -1/2 \end{pmatrix} \begin{pmatrix} b_1' \\ b_2' \end{pmatrix} = \begin{pmatrix} -5b_1' + (3/2)b_2' \\ 2b_1' - (1/2)b_2' \end{pmatrix}$ We need: $-5b_1' + (3/2)b_2' \ge 0 \implies -10b_1' + 3b_2' \ge 0 \implies 3b_2' \ge 10b_1'$ $2b_1' - (1/2)b_2' \ge 0 \implies 4b_1' - b_2' \ge 0 \implies 4b_1' \ge b_2'$ The original RHS was $b = \begin{pmatrix} 20 \\ 90 \end{pmatrix}$. We consider changes to individual $b_i$ values. Range for $b_1'$ (keeping $b_2 = 90$) $-10b_1' + 3(90) \ge 0 \implies -10b_1' + 270 \ge 0 \implies 270 \ge 10b_1' \implies b_1' \le 27$ $4b_1' - 90 \ge 0 \implies 4b_1' \ge 90 \implies b_1' \ge 22.5$ So, $22.5 \le b_1' \le 27$. (This applies if the basis was feasible to begin with). Range for $b_2'$ (keeping $b_1 = 20$) $-10(20) + 3b_2' \ge 0 \implies -200 + 3b_2' \ge 0 \implies 3b_2' \ge 200 \implies b_2' \ge 200/3 \approx 66.67$ $4(20) - b_2' \ge 0 \implies 80 - b_2' \ge 0 \implies b_2' \le 80$ So, $200/3 \le b_2' \le 80$. (This applies if the basis was feasible to begin with). Given the initial basis was infeasible ($x_3 = -5$), this range calculation technically determines the range for which this *specific basis* (even if infeasible) remains the one providing the current dual feasible solution. If the question implies the basis that *was* optimal before the change, then we should use the $B^{-1}$ of the truly optimal basis. Since the problem *states* $[x_2, x_3]$ is the optimal basis, we proceed with calculations based on it, acknowledging the primal infeasibility. 4. (c) New Optimal Solution with Changed RHS New RHS values: $b_1' = 15$, $b_2' = 80$. So, $b' = \begin{pmatrix} 15 \\ 80 \end{pmatrix}$. Assuming the basis $[x_2, x_3]$ is still considered, we calculate the new basic variable values: $x_B' = B^{-1}b' = \begin{pmatrix} -5 & 3/2 \\ 2 & -1/2 \end{pmatrix} \begin{pmatrix} 15 \\ 80 \end{pmatrix}$ $x_B' = \begin{pmatrix} -5(15) + (3/2)(80) \\ 2(15) + (-1/2)(80) \end{pmatrix} = \begin{pmatrix} -75 + 120 \\ 30 - 40 \end{pmatrix} = \begin{pmatrix} 45 \\ -10 \end{pmatrix}$ So, the new values for the basic variables are $x_2 = 45$ and $x_3 = -10$. The non-basic variables are $x_1 = 0, x_4 = 0, x_5 = 0$. The new objective function value: $z' = c_B^T x_B' = \begin{pmatrix} 5 & 13 \end{pmatrix} \begin{pmatrix} 45 \\ -10 \end{pmatrix} = 5(45) + 13(-10) = 225 - 130 = 95$ Again, since $x_3 = -10$, this solution is primal infeasible. This means that if $[x_2, x_3]$ *was* the optimal basis, changing the RHS to $[15, 80]$ makes it infeasible. The optimal basis *would* change, and one would need to apply the dual simplex method starting from this table to find the new optimal (and feasible) solution. However, strictly following the instruction "Determine the new optimal solution if the RHS values... change...", and given the premise that $[x_2, x_3]$ is the "optimal basis", the above calculation provides the solution under the fixed basis. The question implies staying within the same basis structure for sensitivity analysis.