Linear programming is a mathematical optimization technique used to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. It involves maximizing or minimizing a linear objective function subject to a set of linear constraints. Key components of linear programming include: 1. **Objective Function**: This is the function that needs to be maximized or minimized. It is expressed as a linear combination of decision variables.
Articles by others on the same topic
Linear programming optimizes a linear function over finitely many linear equalities and inequalities. A common convention isThe feasible region is a linear polyhedron, so the problem has convex geometry even when it represents a discrete-looking allocation. A linear programming relaxation drops integrality requirements and supplies bounds for an integer program.
For a concrete example, maximize subject to , , , and . The point is feasible and has value ten. Multiplying the first inequality by two and adding the second givesThus this point is globally optimal. The multipliers form a dual linear program certificate; the unused third constraint has zero multiplier. This small calculation captures the purpose of linear programming duality: a feasible solution gives a value, while a feasible dual combination proves that no better value is possible.[ref]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §4.3.1, linear programs; §5.1, Lagrange dual lower bounds
A model can instead be infeasible or unbounded. The simplex method uses changing bases, while interior-point methods approach the optimum through the feasible interior when suitable initialization or embedding is supplied. A chosen numerical algorithm must report which case occurred and respect the input's sign and standard-form conventions.
