Question

Question: In Exercises 5-8, find the minimal representation of the polytope defined by the inequalities \(A{\mathop{\rm x}\nolimits} \le {\mathop{\rm b}\nolimits} \) and \({\mathop{\rm x}\nolimits} \ge 0\).

8. \(A = \left( {\begin{array}{*{20}{c}}2&1\\1&1\\1&2\end{array}} \right),{\rm{ }}{\mathop{\rm b}\nolimits} = \left( {\begin{array}{*{20}{c}}8\\6\\7\end{array}} \right)\)

Short answer

The minimal representation of the polytope \(P\) is \(\left\{ {\left( {\begin{array}{*{20}{c}}0\\0\end{array}} \right),\left( {\begin{array}{*{20}{c}}4\\0\end{array}} \right),\left( {\begin{array}{*{20}{c}}3\\2\end{array}} \right),\left( {\begin{array}{*{20}{c}}0\\{3.5}\end{array}} \right)} \right\}\).

Step-by-step solution

The three inequalities in \(A{\mathop{\rm x}\nolimits}  \le {\mathop{\rm b}\nolimits} \)

The three matrix inequalities \(A{\mathop{\rm x}\nolimits} \le {\mathop{\rm b}\nolimits} \) yield the following system of inequalities:

1. \(2{x_1} + {x_2} \le 8\)
2. \({x_1} + {x_2} \le 6\)
3. \({x_1} + 2{x_2} \le 7\)

Determine the \({{\mathop{\rm x}\nolimits} _1}\)-intercept and \({{\mathop{\rm x}\nolimits} _2}\)-intercept of the three lines

The condition \({\mathop{\rm x}\nolimits} \ge 0\) places polytope \(P\) in the first quadrant of the plane. One vertex is \(\left( {0,0} \right)\).

The \({{\mathop{\rm x}\nolimits} _1}\)-intercepts\(\left( {{\mathop{\rm If}\nolimits} {x_2} = 0} \right)\) of the three lines are 4, 6, and 7, so \(\left( {4,0} \right)\) is a vertex.

The \({{\mathop{\rm x}\nolimits} _2}\)-intercepts\(\left( {{\mathop{\rm If}\nolimits} {x_1} = 0} \right)\) of the three lines are 8, 6, and 3.5, then \(\left( {0,3.5} \right)\) is a vertex.

Determine the intersection point corresponds to inequalities

The intersection of (a) and (b) is at \({{\mathop{\rm P}\nolimits} _{{\mathop{\rm a}\nolimits} {\mathop{\rm b}\nolimits} }} = \left( {2,4} \right)\). Testing \({{\mathop{\rm P}\nolimits} _{{\mathop{\rm ab}\nolimits} }}\) in (c) gives \(2 + 2\left( 4 \right) = 10 > 7\), so \({{\mathop{\rm P}\nolimits} _{{\mathop{\rm ab}\nolimits} }}\) is not in \({\mathop{\rm P}\nolimits} \). The intersection of (a) and (c) is at \({{\mathop{\rm P}\nolimits} _{{\mathop{\rm a}\nolimits} {\mathop{\rm c}\nolimits} }} = \left( {3,2} \right)\). Testing \({{\mathop{\rm P}\nolimits} _{{\mathop{\rm a}\nolimits} {\mathop{\rm c}\nolimits} }}\) in (b) gives \(3 + 2 = 5 < 6\). So, \({{\mathop{\rm P}\nolimits} _{{\mathop{\rm a}\nolimits} {\mathop{\rm c}\nolimits} }}\) is in \({\mathop{\rm P}\nolimits} \).

Determine the minimal representation of the polytope

The four vertices of the polytope are \(\left( {0,0} \right),\left( {4,0} \right)\left( {3,2} \right),\,\,{\mathop{\rm and}\nolimits} \,\,\left( {0,3.5} \right)\).

Thus, the minimal representation of the polytope \(P\) is \(\left\{ {\left( {\begin{array}{*{20}{c}}0\\0\end{array}} \right),\left( {\begin{array}{*{20}{c}}4\\0\end{array}} \right),\left( {\begin{array}{*{20}{c}}3\\2\end{array}} \right),\left( {\begin{array}{*{20}{c}}0\\{3.5}\end{array}} \right)} \right\}\).