Linear Programming

Optimizing outcomes within constraints through mathematical modeling.

Abstract

Linear programming is a mathematical method used to find the best outcome, such as maximum profit or minimum cost, in a mathematical model whose requirements are represented by linear relationships. It involves optimizing a linear objective function, subject to a set of linear inequalities or equations known as constraints. Commonly used in fields like economics, business, and engineering, linear programming helps in resource allocation decisions, where resources are limited and need to be used efficiently.

Simple mathematical expression of linear programming

Problems of linear programming, like the one we’ve already seen, can be mathemically expressed in a single line.

$$\begin{array}{}\text{(11.1)}& \underset{\mathbf{x}}{max}\{{\mathbf{c}}^{\mathrm{\top }}\mathbf{x}\mid \mathbf{x}\in {\mathbb{R}}^n\wedge \mathbf{A}\mathbf{x}\le \mathbf{b}\wedge \mathbf{x}\ge \mathbf{0}\}\end{array}$$

We maximize the objective function ${\mathbf{c}}^{\mathrm{\top }}\mathbf{x}$, that is, the matrix multiplication of the transposed vector with the objective function coefficients $\mathbf{c}$ and the vector of the variables $\mathbf{x}$. In the end, this function is therefore always the sum of all products of coefficients and variables.

$$\begin{array}{}\text{(11.2)}& {\mathbf{c}}^{\mathrm{\top }}\mathbf{x}=\sum _{i=1}^n{c}_i{x}_i=c_1{x}_1+c_2{x}_2+c_3{x}_3+...c_n{x}_n\end{array}$$