Exercises · Half-spaces and polyhedra

Exercises · Chapter 2 · each solution opens with a click · Chapter 2: Half-spaces and polyhedra · Exercises, volume 1 (PDF)

In the exercises of this chapter the intersection point of two supporting hyper-planes in \(\R^2\) is computed by solving a system of two linear equations in two variables, with the following formula:

Given \(a_{11},a_{12},a_{21},a_{22},b_1,b_2 \in \R\), if \((a_{11} \; a_{22} - a_{12} \; a_{21}) \neq 0\), we have:

\[\begin{equation*} \left\{ \begin{array}{ll} a_{11} \; {x}_1 + a_{12} \; {x}_2 & = b_1\\[2ex] a_{21} \; {x}_1 + a_{22} \; {x}_2 & = b_2 \end{array} \right. ~~\Longrightarrow~~ \begin{pmatrix} x_1 \\[0.5ex] x_2 \end{pmatrix} = \begin{pmatrix} \frac{b_1 \; a_{22}-a_{12}\;b_2}{a_{11} \; a_{22} - a_{12} \; a_{21}} \\[2ex] \frac{a_{11}\;b_2 - b_{1} \; a_{21}}{a_{11} \; a_{22} - a_{12} \; a_{21}} \end{pmatrix} \end{equation*}\]

Exercise 2.1: Polyhedra (P2)

Consider the following half-spaces in \(\R^2\):

\[ \begin{array}{rrrrrrrrrrrrr} & {-} 4\, {x_1} & {+} & 10 \, {x_2} & {\le} & 35 \\[2ex] & 3\, {x_1} & {+} & \, {x_2} & {\le} & 12 \\[2ex] & {x_1} & & & { \ge} & {0} \\[2ex] & & & {x_2} & { \ge} & {0} \end{array} \]

Questions

1. Draw a plot of their supporting hyper-planes.

2. Draw the polyhedron given by the intersection of the half-spaces. Is it a polytope?

Solution

1. The supporting hyper-planes associated with the half-spaces and the intersection points with the axis are:

   	\(-\)4  \(x_1\)	\(+\)	10  \(x_2\)	\(=\)	35				\(\begin{pmatrix} -\dfrac{35}{4} \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] \dfrac{7}{2} \end{pmatrix}\)
   	3  \(x_1\)	\(+\)	\(x_2\)	\(=\)	12				\(\begin{pmatrix} 4 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 12 \end{pmatrix}\)
   	\(x_1\)			\(=\)	\(0\)
   			\(x_2\)	\(=\)	\(0\)

   Their plot is shown below.

   

   We compute the intersection point:

   \[\begin{equation*} \left\{ \begin{array}{ll} -4 \; {x}_1 + 10 \; {x}_2 & = 35\\[2ex] 3 \; {x}_1 + \; {x}_2 & = 12 \end{array} \right. ~~\Longrightarrow~~ \begin{pmatrix} x_1 \\[0.5ex] x_2 \end{pmatrix} = \begin{pmatrix} \frac{35 \cdot 1 - 10 \cdot 12}{(-4) \cdot 1 - 10 \cdot 3} \\[2ex] \frac{(-4) \cdot 12 - 35 \cdot 3}{(-4) \cdot 1 - 10 \cdot 3 } \end{pmatrix} = \begin{pmatrix} \frac{5}{2} \\[0.5ex] \frac{9}{2} \end{pmatrix} \end{equation*}\]

2. The polyhedron, given by the intersection of the half-spaces, is:

   

   A polyhedron is a polytope if it is bounded (definitions of bounded polyhedron and of polytope in the chapter «Half-spaces and polyhedra»); equivalently, if there exist \({\boldsymbol \alpha},{\boldsymbol \beta} \in \R^n\) such that \(\alpha_j \le x_j \le \beta_j\) for every \({\boldsymbol x} \in P\) and every \(j \in \{1,2,\dots,n\}\).

   This polyhedron \(P\) is bounded since for every \(\begin{pmatrix} x_1 \\[0.5ex] x_2 \end{pmatrix} \in P\), we have for instance:

   \[\begin{align*} 0 \le & ~~x_1~ \le 4\\[1ex] 0 \le & ~~x_2~ \le \frac{9}{2} \end{align*}\]

   Accordingly this polyhedron is also a polytope.

Exercise 2.2: Polyhedra (P10)

Consider the following half-spaces in \(\R^2\):

\[ \begin{array}{rrrrrrrrrrrrr} & {-} \, {x_1} & {+} & 3 \, {x_2} & {\le} & 12 \\[2ex] & {x_1} & {+} & 2 \, {x_2} & {\le} & 12 \\[2ex] & {3} \, {x_1} & {-} & 2 \, {x_2} & {\le} & {8} \\[2ex] & {x_1} & & & { \ge} & {0} \\[2ex] & & & {x_2} & { \ge} & {0} \end{array} \]

Questions

1. Draw a plot of their supporting hyper-planes.

2. Draw the polyhedron given by the intersection of the half-spaces. Is it a polytope?

3. What happens if we add the constraint \(~ x_1 \ge 5 ~\) to the polyhedron? What if we add the constraint \(~ x_1 \le 5 ~\)?

Solution

1. The supporting hyper-planes associated with the half-spaces and the intersection points with the axis are:

   	\(-\)  \(x_1\)	\(+\)	3  \(x_2\)	\(=\)	12				\(\begin{pmatrix} -12 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 4 \end{pmatrix}\)
   	\(x_1\)	\(+\)	2  \(x_2\)	\(=\)	12				\(\begin{pmatrix} 12 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 6 \end{pmatrix}\)
   	3  \(x_1\)	\(-\)	2  \(x_2\)	\(=\)	8				\(\begin{pmatrix} \dfrac{8}{3} \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] -4 \end{pmatrix}\)
   	\(x_1\)			\(=\)	\(0\)
   			\(x_2\)	\(=\)	\(0\)

   Their plot is shown below.

   

   We compute the intersection points:

   \[\begin{equation*} \left\{ \begin{array}{ll} -\; {x}_1 + 3 \; {x}_2 & = 12\\[2ex] \; {x}_1 + 2 \; {x}_2 & = 12 \end{array} \right. ~~\Longrightarrow~~ \begin{pmatrix} x_1 \\[0.5ex] x_2 \end{pmatrix} = \begin{pmatrix} \frac{12 \cdot 2 - 3\cdot 12}{(-1) \cdot 2 - 3 \cdot 1} \\[2ex] \frac{(-1) \cdot 12 - 12 \cdot 1}{(-1) \cdot 2 - 3 \cdot 1} \end{pmatrix} = \begin{pmatrix} \frac{12}{5} \\[0.5ex] \frac{24}{5} \end{pmatrix} \end{equation*}\]
   \[\begin{equation*} \left\{ \begin{array}{ll} \; {x}_1 + 2 \; {x}_2 & = 12\\[2ex] 3 \; {x}_1 - 2 \; {x}_2 & = 8 \end{array} \right. ~~\Longrightarrow~~ \begin{pmatrix} x_1 \\[0.5ex] x_2 \end{pmatrix} = \begin{pmatrix} \frac{12 \cdot (-2)-2 \cdot 8}{1 \cdot (-2) - 2 \cdot 3} \\[2ex] \frac{1 \cdot 8 - 12 \cdot 3}{1 \cdot (-2) - 2 \cdot 3} \end{pmatrix} = \begin{pmatrix} 5 \\[0.5ex] \frac{7}{2} \end{pmatrix} \end{equation*}\]

2. The polyhedron, given by the intersection of the half-spaces, is:

   

   A polyhedron is a polytope if it is bounded (definitions of bounded polyhedron and of polytope in the chapter «Half-spaces and polyhedra»); equivalently, if there exist \({\boldsymbol \alpha},{\boldsymbol \beta} \in \R^n\) such that \(\alpha_j \le x_j \le \beta_j\) for every \({\boldsymbol x} \in P\) and every \(j \in \{1,2,\dots,n\}\).

   This polyhedron \(P\) is bounded since for every \(\begin{pmatrix} x_1 \\[0.5ex] x_2 \end{pmatrix} \in P\), we have for instance:

   \[\begin{align*} 0 \le & ~~x_1~ \le 5\\[1ex] 0 \le & ~~x_2~ \le \frac{24}{5} \end{align*}\]

   Accordingly this polyhedron is also a polytope.

3. If we add constraint \(~x_1 \ge 5~\) the polyhedron reduces to the point \(\left (~5,~ \frac{7}{2}~\right)\). If we add constraint \(~x_1 \le 5~\) the polyhedron does not change.

Exercise 2.3: Polyhedra (P21)

Consider the following half-spaces in \(\R^2\):

\[ \begin{array}{rrrrrrrrrrrrr} & {- }\, {x_1} & {-} & \, {x_2} & {\le} & {-2} \\[2ex] & {4} \, {x_1} & {-} & {2} \, {x_2} & {\le} & {7} \\[2ex] & {x_1} & {+} & {5} \, {x_2} & {\le} & {21} \\[2ex] & {x_1} & & & { \ge} & {0} \\[2ex] & & & {x_2} & { \ge} & {0} \end{array} \]

Questions

1. Draw a plot of their supporting hyper-planes.

2. Draw the polyhedron given by the intersection of the half-spaces. Is it a polytope?

Solution

1. The supporting hyper-planes associated with the half-spaces and the intersection points with the axis are:

   	\(-\)  \(x_1\)	\(-\)	\(x_2\)	\(=\)	\(-2\)				\(\begin{pmatrix} 2 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 2 \end{pmatrix}\)
   	4  \(x_1\)	\(-\)	2  \(x_2\)	\(=\)	7				\(\begin{pmatrix} \dfrac{7}{4} \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] -\dfrac{7}{2} \end{pmatrix}\)
   	\(x_1\)	\(+\)	5  \(x_2\)	\(=\)	21				\(\begin{pmatrix} 21 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] \dfrac{21}{5} \end{pmatrix}\)
   	\(x_1\)			\(=\)	\(0\)
   			\(x_2\)	\(=\)	\(0\)

   Their plot is shown below.

   

   We compute the intersection points:

   \[\begin{equation*} \left\{ \begin{array}{ll} {x}_1 + 5 \; {x}_2 & = 21\\[2ex] 4\; {x}_1 - 2 \; {x}_2 & = 7 \end{array} \right. ~~\Longrightarrow~~ \begin{pmatrix} x_1 \\[0.5ex] x_2 \end{pmatrix} = \begin{pmatrix} \frac{21 \cdot (-2) - 5\cdot 7}{ 1 \cdot (-2) - 5 \cdot 4} \\[2ex] \frac{1 \cdot 7 - 21 \cdot 4}{1 \cdot (-2) - 5 \cdot 4} \end{pmatrix} = \begin{pmatrix} \frac{7}{2} \\[0.5ex] \frac{7}{2} \end{pmatrix} \end{equation*}\]
   \[\begin{equation*} \left\{ \begin{array}{ll} -\; {x}_1 - \; {x}_2 & = -2\\[2ex] 4 \; {x}_1 - 2 \; {x}_2 & = 7 \end{array} \right. ~~\Longrightarrow~~ \begin{pmatrix} x_1 \\[0.5ex] x_2 \end{pmatrix} = \begin{pmatrix} \frac{(-2) \cdot (-2)-(-1) \cdot 7}{(-1) \cdot (-2)-(-1) \cdot 4} \\[2ex] \frac{(-1) \cdot 7 - (-2) \cdot 4}{(-1) \cdot (-2)-(-1) \cdot 4} \end{pmatrix} = \begin{pmatrix} \frac{11}{6} \\[0.5ex] \frac{1}{6} \end{pmatrix} \end{equation*}\]

2. The polyhedron, given by the intersection of the half-spaces, is:

   

   A polyhedron is a polytope if it is bounded (definitions of bounded polyhedron and of polytope in the chapter «Half-spaces and polyhedra»); equivalently, if there exist \({\boldsymbol \alpha},{\boldsymbol \beta} \in \R^n\) such that \(\alpha_j \le x_j \le \beta_j\) for every \({\boldsymbol x} \in P\) and every \(j \in \{1,2,\dots,n\}\).

   This polyhedron \(P\) is bounded since for every \(\begin{pmatrix} x_1 \\[0.5ex] x_2 \end{pmatrix} \in P\), we have for instance:

   \[\begin{align*} 0 \le & ~~x_1~ \le \frac{7}{2}\\[1ex] 0 \le & ~~x_2~ \le \frac{21}{5} \end{align*}\]

   Accordingly this polyhedron is also a polytope.

Exercise 2.4: Polyhedra (P41)

Consider the following half-spaces in \(\R^3\):

\[ \begin{array}{rrrrrrrrrrrrr} & \, {x_1} & {+} & \, {x_2} & {+} & \, {x_3} & {\le} & {4} \\[1.5ex] & & & \, {x_2} & & & {\le} & {2} \\[1.5ex] & & & & & \, {x_3} & {\le} & {3} \\[1.5ex] & 3\, {x_1} & & & {+} & \, {x_3} & {\le} & {6} \\[1.5ex] & {x_1} & & & & & {\ge} & {0} \\[1.5ex] & & & {x_2} & & & {\ge} & {0} \\[1.5ex] & & & & & {x_3} & {\ge} & {0} \end{array} \]

Questions

1. Draw a plot of their supporting hyper-planes.

2. Draw the polyhedron given by the intersection of the half-spaces. Is it a polytope?

Solution

1. The supporting hyper-planes associated with the half-spaces and the intersection points with the axis are:

   	\(x_1\)	\(+\)	\(x_2\)	\(+\)	\(x_3\)	\(=\)	4		\(\begin{pmatrix} 4 \\[0.5ex] 0 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 4 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 0 \\[0.5ex] 4 \end{pmatrix}\)
   			\(x_2\)			\(=\)	2		\(\begin{pmatrix} 0 \\[0.5ex] 2 \\[0.5ex] 0 \end{pmatrix}\)
   					\(x_3\)	\(=\)	3		\(\begin{pmatrix} 0 \\[0.5ex] 0 \\[0.5ex] 3 \end{pmatrix}\)
   	3  \(x_1\)			\(+\)	\(x_3\)	\(=\)	6		\(\begin{pmatrix} 2 \\[0.5ex] 0 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 0 \\[0.5ex] 6 \end{pmatrix}\)
   	\(x_1\)					\(=\)	\(0\)
   			\(x_2\)			\(=\)	\(0\)
   					\(x_3\)	\(=\)	\(0\)

   Their plot is shown below.

   

2. The polyhedron given by the intersection of the half-spaces in \(\R^3\) is:

   

   A polyhedron is a polytope if it is bounded (definitions of bounded polyhedron and of polytope in the chapter «Half-spaces and polyhedra»); equivalently, if there exist \({\boldsymbol \alpha},{\boldsymbol \beta} \in \R^n\) such that \(\alpha_j \le x_j \le \beta_j\) for every \({\boldsymbol x} \in P\) and every \(j \in \{1,2,\dots,n\}\).

   This polyhedron \(P\) is bounded since for every \(\begin{pmatrix} x_1 \\[0.5ex] x_2 \\[0.5ex] x_3 \end{pmatrix} \in P\), we have for instance:

   \[\begin{align*} 0 \le & ~~x_1~ \le 2\\[1ex] 0 \le & ~~x_2~ \le 2\\[1ex] 0 \le & ~~x_3~ \le 3 \end{align*}\]

   Accordingly this polyhedron is also a polytope.

Exercise 2.5: Polyhedra (P42)

Consider the following half-spaces in \(\R^3\):

\[ \begin{array}{rrrrrrrrrrrrr} & \, {x_1} & {+} & \, {x_2} & {+} & 2 \, {x_3} & {\le} & 4 \\[1.5ex] & 2 \, {x_1} & & & {+} & 3 \, {x_3} & {\le} & 5 \\[1.5ex] & 2 \, {x_1} & {+} & \, {x_2} & {+} & 3 \, {x_3} & {\le} & 7 \\[1.5ex] & {x_1} & & & & & {\ge} & {0} \\[1.5ex] & & & {x_2} & & & {\ge} & {0} \\[1.5ex] & & & & & {x_3} & {\ge} & {0} \end{array} \]

Questions

1. Draw a plot of their supporting hyper-planes.

2. Draw the polyhedron given by the intersection of the half-spaces. Is it a polytope?

Solution

1. The supporting hyper-planes associated with the half-spaces and the intersection points with the axis are:

   	\(x_1\)	\(+\)	\(x_2\)	\(+\)	2  \(x_3\)	\(=\)	4		\(\begin{pmatrix} 4 \\[0.5ex] 0 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 4 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 0 \\[0.5ex] 2 \end{pmatrix}\)
   	2  \(x_1\)			\(+\)	3  \(x_3\)	\(=\)	5		\(\begin{pmatrix} \tfrac{5}{2} \\[0.5ex] 0 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 0 \\[0.5ex] \tfrac{5}{3} \end{pmatrix}\)
   	2  \(x_1\)	\(+\)	\(x_2\)	\(+\)	3  \(x_3\)	\(=\)	7		\(\begin{pmatrix} \tfrac{7}{2} \\[0.5ex] 0 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 7 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 0 \\[0.5ex] \tfrac{7}{3} \end{pmatrix}\)
   	\(x_1\)					\(=\)	\(0\)
   			\(x_2\)			\(=\)	\(0\)
   					\(x_3\)	\(=\)	\(0\)

   Their plot is shown below.

   

2. The polyhedron given by the intersection of the half-spaces in \(\R^3\) is:

   

   A polyhedron is a polytope if it is bounded (definitions of bounded polyhedron and of polytope in the chapter «Half-spaces and polyhedra»); equivalently, if there exist \({\boldsymbol \alpha},{\boldsymbol \beta} \in \R^n\) such that \(\alpha_j \le x_j \le \beta_j\) for every \({\boldsymbol x} \in P\) and every \(j \in \{1,2,\dots,n\}\).

   This polyhedron \(P\) is bounded since for every \(\begin{pmatrix} x_1 \\[0.5ex] x_2 \\[0.5ex] x_3 \end{pmatrix} \in P\), we have for instance:

   \[\begin{align*} 0 \le & ~~x_1~ \le 10\\[1ex] 0 \le & ~~x_2~ \le 10\\[1ex] 0 \le & ~~x_3~ \le 10 \end{align*}\]

   Accordingly this polyhedron is also a polytope.

Exercise 2.6: Polyhedra (P44)

Consider the following half-spaces in \(\R^3\):

\[ \begin{array}{rrrrrrrrrrrrr} & {x_1} & {+} & 2 \, {x_2} & {-} & 2 \, {x_3} & {\le} & 1 \\[1.5ex] & 2 \, {x_1} & {-} & \, {x_2} & {-} & 3 \, {x_3} & {\le} & 4 \\[1.5ex] & {x_1} & {+} & 2 \, {x_2} & {+} & 5 \, {x_3} & {\le} & 2 \\[1.5ex] & {x_1} & & & & & {\ge} & {0} \\[1.5ex] & & & {x_2} & & & {\ge} & {0} \\[1.5ex] & & & & & {x_3} & {\ge} & {0} \end{array} \]

Questions

1. Draw a plot of their supporting hyper-planes.

2. Draw the polyhedron given by the intersection of the half-spaces. Is it a polytope?

Solution

1. The supporting hyper-planes associated with the half-spaces and the intersection points with the axis are:

   	\(x_1\)	\(+\)	2  \(x_2\)	\(-\)	2  \(x_3\)	\(=\)	1		\(\begin{pmatrix} 1 \\[0.5ex] 0 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] \tfrac{1}{2} \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 0 \\[0.5ex] -\tfrac{1}{2} \end{pmatrix}\)
   	2  \(x_1\)	\(-\)	\(x_2\)	\(-\)	3  \(x_3\)	\(=\)	4		\(\begin{pmatrix} 2 \\[0.5ex] 0 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] -4 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 0 \\[0.5ex] -\tfrac{4}{3} \end{pmatrix}\)
   	\(x_1\)	\(+\)	2  \(x_2\)	\(+\)	5  \(x_3\)	\(=\)	2		\(\begin{pmatrix} 2 \\[0.5ex] 0 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 1 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 0 \\[0.5ex] \tfrac{2}{5} \end{pmatrix}\)
   	\(x_1\)					\(=\)	\(0\)
   			\(x_2\)			\(=\)	\(0\)
   					\(x_3\)	\(=\)	\(0\)

   Their plot is shown below.

   

2. The polyhedron given by the intersection of the half-spaces in \(\R^3\) is:

   

   A polyhedron is a polytope if it is bounded (definitions of bounded polyhedron and of polytope in the chapter «Half-spaces and polyhedra»); equivalently, if there exist \({\boldsymbol \alpha},{\boldsymbol \beta} \in \R^n\) such that \(\alpha_j \le x_j \le \beta_j\) for every \({\boldsymbol x} \in P\) and every \(j \in \{1,2,\dots,n\}\).

   This polyhedron \(P\) is bounded since for every \(\begin{pmatrix} x_1 \\[0.5ex] x_2 \\[0.5ex] x_3 \end{pmatrix} \in P\), we have for instance:

   \[\begin{align*} 0 \le & ~~x_1~ \le 10\\[1ex] 0 \le & ~~x_2~ \le 10\\[1ex] 0 \le & ~~x_3~ \le 10 \end{align*}\]

   Accordingly this polyhedron is also a polytope.

Exercise 2.7: Polyhedra (P51)

Consider the following half-spaces in \(\R^3\):

\[ \begin{array}{rrrrrrrrrrrrr} & & \, {x_1} & {-} & {x_2} & {-} & 3 \, {x_3} & {\le} & {-} 5 \\[2ex] & {-} & 3 \, {x_1} & {-} & 2 \, {x_2} & {+} & 2 \, {x_3} & {\le} & {-}2 \\[2ex] & & {x_1} & & & & & {\ge} & {0} \\[1.5ex] & & & & {x_2} & & & {\ge} & {0} \\[1.5ex] & & & & & & {x_3} & {\ge} & {0} \end{array} \]

Questions

1. Draw a plot of their supporting hyper-planes.

2. Draw the polyhedron given by the intersection of the half-spaces. Is it a polytope?

Solution

1. The supporting hyper-planes associated with the half-spaces and the intersection points with the axis are:

   	\(x_1\)	\(-\)	\(x_2\)	\(-\)	3  \(x_3\)	\(=\)	\(-5\)		\(\begin{pmatrix} \!-5 \\[0.5ex] 0 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 5 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 0 \\[0.5ex] \tfrac{5}{3} \end{pmatrix}\)
   	\(-3\, x_1\)	\(-\)	2  \(x_2\)	\(+\)	2  \(x_3\)	\(=\)	\(-2\)		\(\begin{pmatrix} \tfrac{2}{3} \\[0.5ex] 0 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 1 \\[0.5ex] 0 \end{pmatrix}\), \(\begin{pmatrix} 0 \\[0.5ex] 0 \\[0.5ex] -1 \end{pmatrix}\)
   	\(x_1\)					\(=\)	\(0\)
   			\(x_2\)			\(=\)	\(0\)
   					\(x_3\)	\(=\)	\(0\)

   Their plot is shown below.

   

2. The polyhedron given by the intersection of the half-spaces in \(\R^3\) is:

   

   A polyhedron is a polytope if it is bounded (definitions of bounded polyhedron and of polytope in the chapter «Half-spaces and polyhedra»); equivalently, if there exist \({\boldsymbol \alpha},{\boldsymbol \beta} \in \R^n\) such that \(\alpha_j \le x_j \le \beta_j\) for every \({\boldsymbol x} \in P\) and every \(j \in \{1,2,\dots,n\}\).

   This polyhedron \(P\) is not bounded, accordingly it is not a polytope.

2.1 Further reading: drawing polyhedra with SageMath

• The polyhedra of the exercises can be drawn with SageMath, which can be used online at sagecell.sagemath.org/, without installing anything.

• A polyhedron is given by the list of its half-spaces (the H-representation). SageMath writes every half-space in the form

  \[ b + a_1\,x_1 + a_2\,x_2 + \dots + a_n\,x_n \ge 0 \]

  and describes it by the tuple \((b, a_1, a_2, \dots, a_n)\). A constraint \({\boldsymbol a}'{\boldsymbol x} \le b\) is first written as \(b - {\boldsymbol a}'{\boldsymbol x} \ge 0\), so its tuple is \((b, -a_1, \dots, -a_n)\); a non-negativity constraint \(x_j \ge 0\) has the tuple with \(0\) in the first position and \(1\) in position \(j+1\).

• The method Hrepresentation() lists the half-spaces, Vrepresentation() lists the extreme points and the extreme rays, and plot() draws the polyhedron (in \(\R^2\) or in \(\R^3\)).

Example in \(\R^2\) (Exercise with the polyhedron \(P2\)).

SageMath code: a polyhedron in \(\R^2\)

# Define the polyhedron using inequalities (Hyperplane Representation)
p = Polyhedron(ieqs=[
    (35,  4, -10),     # ( 4, -10) x + 35 >= 0
    (12, -3, -1),      # (-3,  -1) x + 12 >= 0
    (0,   1,  0),      # ( 1,   0) x + 0 >= 0
    (0,   0,  1)       # ( 0,   1) x + 0 >= 0
])

# Display the inequalities of the polyhedron
p.Hrepresentation()

# Display the extreme points and extreme rays of the polyhedron
p.Vrepresentation()

# Plot the polyhedron (2D)
p.plot()

Example in \(\R^3\) (Exercise with the polyhedron \(P41\)).

SageMath code: a polyhedron in \(\R^3\)

# Define the polyhedron using inequalities (Hyperplane Representation)
p = Polyhedron(ieqs=[
    (4, -1, -1, -1),   # (-1, -1, -1) x + 4 >= 0
    (2,  0, -1,  0),   # (0, -1, 0) x + 2 >= 0
    (3,  0,  0, -1),   # (0, 0, -1) x + 3 >= 0
    (6, -3,  0, -1),   # (-3, 0, -1) x + 6 >= 0
    (0,  1,  0,  0),   # (1, 0, 0) x + 0 >= 0
    (0,  0,  1,  0),   # (0, 1, 0) x + 0 >= 0
    (0,  0,  0,  1)    # (0, 0, 1) x + 0 >= 0
])

# Display the inequalities of the polyhedron
p.Hrepresentation()

# Display the extreme points and extreme rays of the polyhedron
p.Vrepresentation()

# Plot the polyhedron (3D)
p.plot()

The other polyhedra of this chapter are drawn in the same way, by changing the list of tuples.