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\).

6. \(A = \left( {\begin{array}{*{20}{c}}2&3\\4&1\end{array}} \right),{\rm{ }}{\mathop{\rm b}\nolimits} = \left( {\begin{array}{*{20}{c}}{18}\\{16}\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\\4\end{array}} \right),\left( {\begin{array}{*{20}{c}}0\\6\end{array}} \right)} \right\}\).

Step-by-step solution

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

The matrix inequalities \(A{\bf{x}} \le {\bf{b}}\) yield the following system of inequalities:

1. \(2{{\mathop{\rm x}\nolimits} _1} + 3{{\mathop{\rm x}\nolimits} _2} \le 18\)
2. \(4{{\mathop{\rm x}\nolimits} _1} + {{\mathop{\rm x}\nolimits} _2} \le 16\)

Determine the \({{\mathop{\rm x}\nolimits} _1}\)-intercept and \({{\mathop{\rm x}\nolimits} _2}\)-intercept of the two 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} {{\mathop{\rm x}\nolimits} _2} = 0} \right)\) of the two lines are 9 and 4, so \(\left( {4,0} \right)\) is a vertex.

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

Determine the intersection point corresponds to inequalities

The intersection of (a) is at \({{\mathop{\rm P}\nolimits} _{\mathop{\rm a}\nolimits} } = \left( {3,4} \right)\). Testing \({{\mathop{\rm P}\nolimits} _a}\) in (b) gives \(4\left( 3 \right) + 4 = 16\), so \({{\mathop{\rm P}\nolimits} _a}\) is in \({\mathop{\rm P}\nolimits} \).

Determine the minimal representation of the polytope

The set \(\left\{ {{{\mathop{\rm v}\nolimits} _1},..,{{\mathop{\rm v}\nolimits} _k}} \right\}\) is aminimal representation of the polytope\(P\)when \(P = {\mathop{\rm conv}\nolimits} \left\{ {{{\mathop{\rm v}\nolimits} _1},...,{{\mathop{\rm v}\nolimits} _k}} \right\}\) and for each \(i = 1,...,k\), \({{\mathop{\rm v}\nolimits} _1} \notin \left\{ {{{\mathop{\rm v}\nolimits} _j}:j \ne i} \right\}\).

The four vertices of the polytope are \(\left( {0,0} \right),\left( {4,0} \right)\left( {3,4} \right),\,\,{\mathop{\rm and}\nolimits} \,\,\left( {0,6} \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\\4\end{array}} \right),\left( {\begin{array}{*{20}{c}}0\\6\end{array}} \right)} \right\}\).