91Ó°ÊÓ

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

1. \({x_1} + 3{x_2} \le 18\)
2. \({x_1} + {x_2} \le 10\)
3. \(4{x_1} + {x_2} \le 28\)

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 three lines are 18, 10, and 7, so \(\left( {7,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 three lines are 6, 10, and 28, then \(\left( {0,6} \right)\) is a vertex.

The intersection of (a) and (b) is at \({{\mathop{\rm P}\nolimits} _{{\mathop{\rm a}\nolimits} {\mathop{\rm b}\nolimits} }} = \left( {6,4} \right)\). Testing \({{\mathop{\rm P}\nolimits} _{{\mathop{\rm ab}\nolimits} }}\) in (c) gives \(4\left( 6 \right) + 4 = 28\), so \({{\mathop{\rm P}\nolimits} _{{\mathop{\rm ab}\nolimits} }}\) is in \({\mathop{\rm P}\nolimits} \).

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( {7,0} \right)\left( {6,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}}7\\0\end{array}} \right),\left( {\begin{array}{*{20}{c}}6\\4\end{array}} \right),\left( {\begin{array}{*{20}{c}}0\\6\end{array}} \right)} \right\}\).