Chapter 6, Problem 36RP

Explanation of Solution

Optimal solution:

• In this case, this LP contains three $\le$ constraints with the respective right-hand sides(rhs) as 10,15, and 20 is considered.
• It is also given that in the optimal table, $s_2$ is a basic variable in the second constraint which has a right-hand side of 12.
• Based on the given information, the range of values of $b_2$ for which the current basis remains optimal is to be determined.
• Let the variables $b_1$, $b_2$ and $b_3$ denote the original right-hand sides RHS of constraints, while the variables $b_1^{\text{'}}$, $b_2^{\text{'}}$ and $b_3^{\text{'}}$ denote the RHS of the constraints in the optimal table.
• Assume that B denotes the basis matrix.
• Since, it is given that $s_2$ is a basic variable in the second constraint, which has a right-hand side of 12 in the optimal table. This implies that the second column of $B^{-1}$ will be $s_2$ and therefore the columns for $s_2$ and RHS in the optimal table will be:

$s_2$	RHS
0	z
0	$b_1^{\text{'}}$
1	$b_2^{\text{'}}=12$
0	$b_3^{\text{'}}$

• Now from the theory of sensitivity analysis, on changing the RHS of a constraint the following relation is obtained:
  • If the right-hand side of the i^th constraint is increased by $\Delta$ then the right-hand side of the optimal table is given by,
  • (Original RHS of the optimal table) + $\Delta$ (Column i of $B^{-1}$)