Hyperplane

---

Definition:
Let \(\pmb{\bar{c}} = [c_{1}, c_{2}, \dots, c_{n}]\) be a nonzero vector in \(n\)-dimensional Euclidean space \(\mathbb{E}^{n}\) and let \(z \in \mathbb{R}\). The set of points \[ \pmb{\bar{x}} = [x_{1}, x_{2}, \dots, x_{n}] \] satisfying \[ \pmb{\bar{c} \cdot \bar{x}} = c_{1}x_{1} + c_{2}x_{2} + \cdots + c_{n}x_{n} = z \] is called a hyperplane. This hyperplane effectively divides the space into regions, making it a fundamental tool for delineating feasible areas in linear programming.

Open Half Spaces

---

Definition:
With the same vector \(\pmb{\bar{c}}\) and scalar \(z\), an open half space consists of all points \(\pmb{\bar{x}}\) satisfying either \[ \pmb{\bar{c} \cdot \bar{x}} < z \quad \text{or} \quad \pmb{\bar{c} \cdot \bar{x}} > z. \] Specifically, we define: \[ H_{1} = \{\pmb{\bar{x}} : \pmb{\bar{c} \cdot \bar{x}} < z\} \quad \text{and} \quad H_{2} = \{\pmb{\bar{x}} : \pmb{\bar{c} \cdot \bar{x}} > z\}. \] These open half spaces help in identifying regions where optimal solutions might exist.

Closed Half Spaces

---

Definition:
A closed half space includes the boundary. Given \(\pmb{\bar{c}}\) and \(z\), the set of points satisfying \[ \pmb{\bar{c} \cdot \bar{x}} \leq z \quad \text{or} \quad \pmb{\bar{c} \cdot \bar{x}} \geq z \] is defined as: \[ H_{3} = \{\pmb{\bar{x}} : \pmb{\bar{c} \cdot \bar{x}} \leq z\} \quad \text{and} \quad H_{4} = \{\pmb{\bar{x}} : \pmb{\bar{c} \cdot \bar{x}} \geq z\}. \] Including the boundary is crucial for determining the limits of feasible solutions in LPP.

Line

---

Definition:
Let \(\pmb{\bar{\alpha}} = [\alpha_{1}, \alpha_{2}, \dots, \alpha_{n}]\) and \(\pmb{\bar{\beta}} = [\beta_{1}, \beta_{2}, \dots, \beta_{n}]\) be two distinct points in \(\mathbb{E}^{n}\). The set of all points \[ \pmb{\bar{x}} = \lambda \pmb{\bar{\alpha}} + (1-\lambda) \pmb{\bar{\beta}}, \quad \forall \lambda \in \mathbb{R}, \] represents the line that joins \(\pmb{\bar{\alpha}}\) and \(\pmb{\bar{\beta}}\). This concept is central to describing the boundaries within a linear programming model.

Line Segment

---

Definition:
Using the points \(\pmb{\bar{\alpha}}\) and \(\pmb{\bar{\beta}}\) in \(\mathbb{E}^{n}\), a line segment is defined as: \[ \pmb{\bar{x}} = \lambda \pmb{\bar{\alpha}} + (1-\lambda) \pmb{\bar{\beta}}, \quad \forall \lambda \in [0, 1]. \] By restricting \(\lambda\) to the interval \([0, 1]\), the line segment remains bounded, which is vital when representing finite feasible regions.

Convex Combinations

---

Definition:
Suppose you have \(r\) points \(\pmb{\bar{x}_{1}}, \pmb{\bar{x}_{2}}, \dots, \pmb{\bar{x}_{r}}\) in \(\mathbb{E}^{n}\). A point \(\pmb{\bar{x}}\) is a convex combination of these points if it can be expressed as: \[ \pmb{\bar{x}} = \lambda_{1}\pmb{\bar{x}_{1}} + \lambda_{2}\pmb{\bar{x}_{2}} + \cdots + \lambda_{r}\pmb{\bar{x}_{r}}, \] with the conditions \[ \lambda_{1} + \lambda_{2} + \cdots + \lambda_{r} = 1 \quad \text{and} \quad \lambda_{i} \geq 0 \text{ for each } i. \] Convex combinations are key to constructing the feasible set in linear programming.

Convex Sets

---

Definition:
A set \(X \subset \mathbb{E}^{n}\) is a convex set if, for any two points \(\pmb{\bar{x}_{1}}\) and \(\pmb{\bar{x}_{2}}\) in \(X\), the line segment joining them lies entirely within \(X\). In formal terms, for every \(\lambda \in [0, 1]\), \[ \lambda \pmb{\bar{x}_{1}} + (1-\lambda) \pmb{\bar{x}_{2}} \in X. \] Convex sets are important because they guarantee that any local optimal solution is also globally optimal in LPP.

Example: Proving a Convex Set

---

1. Problem: Prove that \[ X = \{\pmb{\bar{x}} : |\pmb{\bar{x}}| \leq 2\} \] is a convex set.
   
   Solution:
   Let \(\pmb{\bar{x}_{1}}, \pmb{\bar{x}_{2}} \in X\) so that \(|\pmb{\bar{x}_{1}}| \leq 2\) and \(|\pmb{\bar{x}_{2}}| \leq 2\). Firstly, consider any point on the line segment between them: \[ \pmb{\bar{x}} = \lambda \pmb{\bar{x}_{1}} + (1-\lambda) \pmb{\bar{x}_{2}}, \quad \lambda \in [0,1]. \] Next, by applying the triangle inequality we have: \[ |\pmb{\bar{x}}| \leq \lambda |\pmb{\bar{x}_{1}}| + (1-\lambda)|\pmb{\bar{x}_{2}}| \leq 2\lambda + 2(1-\lambda) = 2. \] Thus, \(\pmb{\bar{x}} \in X\), which confirms that \(X\) is convex.

Extreme Points

---

Definition:
In a convex set \(X \subset \mathbb{E}^{n}\), a point \(\pmb{\bar{x}} \in X\) is an extreme point if it cannot be represented as a convex combination of any two distinct points in \(X\). Extreme points are of great interest in linear programming since optimal solutions often occur at these points.

Convex Hull

---

Definition:
The convex hull of a set \(X \subset \mathbb{E}^{n}\) is the smallest convex set that contains \(X\). It is defined as the set of all convex combinations of points in \(X\): \[ \text{conv}(X) = \left\{\sum_{i=1}^{r} \lambda_{i} \pmb{\bar{x}_{i}} : \pmb{\bar{x}_{i}} \in X,\; \lambda_{i} \geq 0,\; \sum_{i=1}^{r} \lambda_{i} = 1\right\}. \] This concept plays a crucial role in determining the boundaries of feasible regions.

Convex Polyhedron

---

Definition:
If \(X\) is a finite set in \(\mathbb{E}^{n}\), the convex polyhedron generated by \(X\) is the set of all convex combinations of its points: \[ P = \left\{\sum_{i=1}^{r} \lambda_{i} \pmb{\bar{x}_{i}} : \pmb{\bar{x}_{i}} \in X,\; \lambda_{i} \geq 0,\; \sum_{i=1}^{r} \lambda_{i} = 1\right\}. \] Convex polyhedra are central to linear programming, as they define the feasible region over which optimization occurs.

Conclusion

---

In conclusion, mastering these LPP Definitions is essential for solving linear programming problems. By understanding hyperplanes, half spaces, lines, convex combinations, and convex sets, you equip yourself with the tools necessary to characterize and find optimal solutions. Additionally, these definitions lay the groundwork for advanced optimization techniques and further exploration in linear programming. We hope this guide has provided clear insights into the geometric foundations of LPP.