📂Optimization

Infinity of the Objective Function in Linear Programming

Description

$$\begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix}$$

Given matrix $A \in \mathbb{R}^{m \times n}$, $\mathbf{b} \in \mathbb{R}^{m \times 1}$, and $\mathbf{c} \in \mathbb{R}^{n}$, let’s say a linear programming problem is represented in an equation form as above. Despite following the constraints, the objective function can become unbounded.

A picture is worth a thousand words¹. Geometrically thinking about the simplex method, if the objective function is unbounded, it means initially, simplex itself cannot be constructed. In such cases where the objective function is not bounded, even though it’s a maximization problem, the objective value can keep increasing.

Decision Method

$$\begin{align*} \zeta &=& \bar{\zeta} &+& \sum_{j \in \mathcal{N}} \bar{c}_{j} x_{j} \\ x_{n+i} &=& \bar{b}_{i} &-& \sum_{j \in \mathcal{N}} \bar{a}_{ij} x_{j} \end{align*}$$

In the given problem, by representing a dictionary or tableau with a bar on top of the coefficients that change as the solution progresses like above, if the leaving variable is $x_{i}$, then it can be understood that the objective function is unbounded if all $$\bar{a}_{i1} \bar{b}_{i}, \cdots , \bar{a}_{in} \bar{b}_{i}$$ are not positive².