Chapter 6, Problem 35RP

Explanation of Solution

Optimal solution:

• Consider the linear programming problem given below:
• max z= $c_1{x}_1+c_2{x}_2$
• Subject to constraints:
  • $a_{11}{x}_1+a_{12}{x}_2\le b_1$
  • $a_{21}{x}_1+a_{22}{x}_2\le b_2$
  • $x_1,x_2\ge 0$
• The optimal table for this LP is

z	$x_1$	$x_2$	$s_1$	$s_2$	B
1	0	0	2	3	$\frac{5}{2}$
0	1	0	3	2	$\frac{5}{2}$
0	1	1	1	1	1

• Here, to calculate $b_1$ and $b_2$, evaluate the following expression:
• Right-hand side of constraints in the optimal table= $B^{-1}b$
• The right-hand side of the constraint in the optimal row is known,
• It is: $\left[\begin{array}{c}\frac{5}{2}\\ 1\end{array}\right]$
• Now, find the matrix $B^{-1}$ from the optimal table. It contains the columns for the slack variables in the constraints of the optimal table. Thus:
  • $B^{-1}=\left[\begin{array}{cc}3& 2\\ 1& 1\end{array}\right]$
• Thus the expression will be
• $\left[\begin{array}{c}\frac{5}{2}\\ 1\end{array}\right]$=$\left[\begin{array}{cc}3& 2\\ 1& 1\end{array}\right]\left[\begin{array}{c}{b}_1\\ b_2\end{array}\right]$
• Further solving the equation yields
• ${\left[\begin{array}{cc}3& 2\\ 1& 1\end{array}\right]}^{-1}\left[\begin{array}{c}\frac{5}{2}\\ 1\end{array}\right]=\left[\begin{array}{c}{b}_1\\ b_2\end{array}\right]$
• $\left[\begin{array}{cc}1& -2\\ -1& 3\end{array}\right]\left[\begin{array}{c}\frac{5}{2}\\ 1\end{array}\right]=\left[\begin{array}{c}{b}_1\\ b_2\end{array}\right]$
• $\left[\begin{array}{c}\frac{1}{2}\\ \frac{1}{2}\end{array}\right]=\left[\begin{array}{c}{b}_1\\ b_2\end{array}\right]$
• Hence, $b_1=\frac{1}{2}$, $b_2=\frac{1}{2}$
• Now, to calculate $a_{11},a_{12},a_{21},a_{22}$, evaluate the following expression
• Column for $x_i$ in the optimal table= $B^{-1}{a}_i$
• Hence, to calculate $a_{11}$ and $a_{21}$, we use column $x_1$ of the optimal table which is $\left[\begin{array}{c}1\\ 0\end{array}\right]$
• Thus the expression is
• $\left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{cc}3& 2\\ 1& 1\end{array}\right]\left[\begin{array}{c}{a}_{11}\\ a_{21}\end{array}\right]$
• Further solving the equation yields
• ${\left[\begin{array}{cc}3& 2\\ 1& 1\end{array}\right]}^{-1}\left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{c}{a}_{11}\\ a_{21}\end{array}\right]$
• $\left[\begin{array}{cc}1& -2\\ -1& 3\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{c}{a}_{11}\\ a_{21}\end{array}\right]$
• $\left[\begin{array}{c}1\\ -1\end{array}\right]=[\begin{array}{c}{a}_{11}\\ a_{21}\end{array}$