Question

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

5. \(A = \left( {\begin{array}{*{20}{c}}1&2\\3&1\end{array}} \right),{\rm{ }}{\bf{b}} = \left( {\begin{array}{*{20}{c}}{{\bf{10}}}\\{{\bf{15}}}\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}}5\\0\end{array}} \right),\left( {\begin{array}{*{20}{c}}4\\3\end{array}} \right),\left( {\begin{array}{*{20}{c}}0\\5\end{array}} \right)} \right\}\).

Step-by-step solution

The two inequalities in \(A{\bf{x}} \le {\bf{b}}\)

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

1. \({{\mathop{\rm x}\nolimits} _1} + 2{{\mathop{\rm x}\nolimits} _2} \le 10\)
2. \(3{{\mathop{\rm x}\nolimits} _1} + {{\mathop{\rm x}\nolimits} _2} \le 15\)

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

The \({{\mathop{\rm x}\nolimits} _2}\)-intercepts\(\left( {{\mathop{\rm If}\nolimits} {\rm{ }}{{\mathop{\rm x}\nolimits} _1} = 0} \right)\) of the two lines are 5 and 15, then \(\left( {0,5} \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( {4,3} \right)\). Testing \({{\mathop{\rm P}\nolimits} _a}\) in (b) gives \(3\left( 4 \right) + 3 = 15\), so \({{\mathop{\rm P}\nolimits} _a}\) 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( {5,0} \right)\left( {4,3} \right),\,\,{\mathop{\rm and}\nolimits} \,\,\left( {0,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}}5\\0\end{array}} \right),\left( {\begin{array}{*{20}{c}}4\\3\end{array}} \right),\left( {\begin{array}{*{20}{c}}0\\5\end{array}} \right)} \right\}\).