📂Optimization

Definition of Linear Programming Problem

Definition ¹

A linear programming problem, shortly referred to as LP, is an optimization problem that is linear in both its objective function and constraints. Simply put, a linear problem looks to find $\mathbf{x} \in \mathbb{R}^{n}$ for which the objective function $f: \mathbb{R}^{n} \to \mathbb{R}$, given vectors $\mathbf{c} \in \mathbb{R}^{n}$, is $$f \left( \mathbf{x} \right) := \mathbf{c}^{T} \mathbf{x}$$ and for given matrices $A \in \mathbb{R}^{m \times n}$ and $\mathbf{b} \in \mathbb{R}^{m \times 1}$, it satisfies $$A \mathbf{x} \le \mathbf{b}$$ while optimizing the function value of $f$. It is generally represented as follows. $$\begin{matrix} \text{Optimize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} \le \mathbf{b} \end{matrix}$$ In such problems, any solution that meets the constraint conditions is called a Feasible Solution, among which the one that maximizes or minimizes the objective function is known as the Optimal Solution.

---

• $\mathbf{c}^{T}$ means transpose.
• Optimization refers to either maximization or minimization.

Explanation

Definition

The term linear is aptly named because both the objective function and constraints involved are linear. This means that the equations do not contain squared terms, logarithms, or any other form of nonlinear functions, and the constraints must also be in the form of (in)equality matrix expressions. This contrasts with problems expressed in equalities primarily dealt with in [Matrix Algebra](../../categories/Linear Algebra), [Linear Algebra](../../categories/Linear Algebra). $$A \mathbf{x} = \mathbf{b}$$

Program here does not refer to computer applications as we commonly understand, but rather to schedules or tasks. In practical applications of linear programming, each variable $x_{1} , \cdots , x_{n}$ can represent various elements such as time, energy, resources, etc.

For example, in economics or business management, maximizing these elements would likely correspond to utility, while minimizing them pertains to costs. If it involves creating an optimal work schedule by allocating employees with varying efficiencies and work hours to certain tasks, linear programming would be the foremost method to consider.

Examples ²

$$\begin{matrix} \text{Optimize} & x_{1} + x_{2} \\ \text{subject to} & x_{1} \ge 0 \\ & x_{2} \ge 0 \\ & x_{2} - x_{1} \le 1 \\ & x_{1} + 6 x_{2} \le 15 \\ & 4 x_{1} - x_{2} \le 10 \end{matrix}$$

Let’s consider the linear problem as mentioned above. While it may seem complicated at first glance due to the five conditions, the variables involved are only $x_{1}$ and $x_{2}$. When these are plotted on a $2$-dimensional plane, the following illustration shows the region that satisfies the conditions.

All points within this region are feasible solutions, as they, at a minimum, meet the constraint conditions. The goal is to find the point among these where the objective function $\Lambda \left( x_{1} , x_{2} \right) = x_{1} + x_{2}$ is maximized. Geometrically, this is where the line of feasible solutions intersects $x_{1} + x_{2} = \lambda$ in such a way that $\lambda$ is maximized, or in other words, the point where the $y$-intercept of the line is the greatest.

The actual solution to this example is such that $\lambda = 5$ is met by $\left( x_{1} , x_{2} \right) = (3,2)$. Interestingly, this solution might feel familiar. If one has gone through the standard educational curriculum, they might have encountered similar problems around their first year of high school. Thus, the basic idea behind this is simple enough that even students just graduated from middle school could grasp it. The term ’linear’ itself indicates that, regardless of how the solution is derived, the concept is straightforward.