📂Optimization

Linear Programming Problem in Equation Form

Definition ¹

For matrices $A \in \mathbb{R}^{m \times n}$, $\mathbf{b} \in \mathbb{R}^{m \times 1}$, and $\mathbf{c} \in \mathbb{R}^{n}$, the following linear programming problem is called in standard form or equational form. $$\begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix}$$

---

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

Description

Conversion to Standard Form

In principle, any linear programming problem can be converted into standard form. Consider the following maximization problem, for example.

$$\begin{matrix} \text{Maximize} & 3 x_{1} - 2 x_{2} \\ \text{subject to} & 2 x_{1} - x_{2} \le 4 \\ & x_{1} + 3 x_{2} \ge 5 \\ & x_{2} \ge 0 \end{matrix}$$

The basic idea of conversion is ‘consolidating inequalities’. The first constraint $$2 x_{1} - x_{2} \le 4$$ can in fact be represented as $$2 x_{1} - x_{2} + x_{3} = 4$$ without any issue, regarding some $x_{3} \ge 0$. Because $2 x_{1} - x_{2}$ supplements the amount by which $4$ is smaller. Variables that serve to loosen the equation in this manner are called slack variables. The second constraint $$x_{1} + 3 x_{2} \ge 5$$ can be handled by multiplying both sides by $-1$ and introducing a new slack variable $x_{4}$, just as with the first constraint, becoming $$- x_{1} - 3 x_{2} + x_{4} = - 5$$. At a glance, $$\begin{matrix} \text{Maximize} & 3 x_{1} - 2 x_{2} \\ \text{subject to} & 2 x_{1} - x_{2} + x_{3} = 4 \\ & - x_{1} - 3 x_{2} + x_{4} = - 5 \\ & x_{2}, x_{3}, x_{4} \ge 0 \end{matrix}$$ seems to meet the conditions for equational form, but since there’s yet no constraint for $x_{1} \ge 0$, it needs to be accommodated. Given that $x_{1}$ is allowed to be any real number, breaking it into the difference $x_{1} = y_{1} - z_{1}$ of two positive numbers removes $x_{1}$ from the equation, allowing it to be presented in equational form as follows. $$\begin{matrix} \text{Maximize} & 3 \left( y_{1} - z_{1} \right) - 2 x_{2} \\ \text{subject to} & 2 \left( y_{1} - z_{1} \right) - x_{2} + x_{3} = 4 \\ & - \left( y_{1} - z_{1} \right) - 3 x_{2} + x_{4} = - 5 \\ & y_{1}, z_{1}, x_{2}, x_{3}, x_{4} \ge 0 \end{matrix}$$

Geometry of Equational Form

Equation $A \mathbf{x} = \mathbf{b}$ forms a general plane, a hyperplane, and taking only the part that forms a cone shape within the Euclidean space according to condition $\mathbf{x} \ge \mathbf{0}$. With the introduction of slack variables, the dimension increases, but the space to be explored for optimization is significantly simplified.

This solution space is none other than a simplex, and herein lies the idea for the simplex method.