Converting Max to Min and Other Reformulations

The standard form of a linear program is a minimization with equality constraints and non-negative variables:

$$\min\ \mathbf{c}^T\mathbf{x} \quad \text{subject to}\quad A\mathbf{x} = \mathbf{b},\quad \mathbf{x} \geq \mathbf{0}.$$

A maximization problem can always be reformulated as a minimization by negating the objective. The key identity is

$$\max\ \mathbf{c}^T\mathbf{x} \;=\; -\min\,(-\mathbf{c}^T\mathbf{x}).$$

The optimal solution $\mathbf{x}^*$ is the same for both problems. Only the sign of the optimal value changes.

For example, the maximization

$$\max\ 5x_1 - 2x_2$$

becomes the equivalent minimization

$$\min\ -5x_1 + 2x_2.$$

If the optimal value of the minimization is $-17$, then the maximum of the original objective is $17$.