Tag Info

Questions on linear programming, the optimization of a linear function subject to linear constraints.

A linear programming problem may be defined as the problem of maximizing or minimizing a linear function subject to linear constraints. The constraints may be equalities or inequalities.

Linear programs are problems that can be expressed in canonical form as \begin{align}\max\quad&c^\top x\\\text{s.t.}\quad& Ax\le b\\\quad& x\ge 0\end{align} where $$x$$ represents the vector of variables (to be determined), $$c$$ and $$b$$ are vectors of (known) coefficients, $$A$$ is a (known) matrix of coefficients, and $${\displaystyle (\cdot )^{\top}}$$ is the matrix transpose.

The expression to be maximized or minimized is called the objective function ($$c^{\top}x$$ in this case).

The inequalities $$Ax \le b$$ and $$x \ge 0$$ are the constraints which specify a convex polytope over which the objective function is to be optimized. The inequality $$x \ge 0$$ is called non-negativity constraints and are often found in linear programming problems. The other inequality $$Ax \le b$$ is called the main constraints.

Applications:

Linear programming can be applied to various fields of study. It is widely used in mathematics, and to a lesser extent in business, economics, and for some engineering problems. Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proven useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design.

References: