linear programs
Concept
Affine functions
- linear equation plus a constant translation
- related to affine spaces
Linear functions
Linear programs
A linear program (LP) has:
- decision variables: the unknown quantities being chosen;
- constraints: finitely many affine equalities or non-strict inequalities defining feasible solutions;
- objective function: a linear function to minimize or maximize.
A compact form is
Rules for an LP formulation:
- Variables cannot be multiplied or divided by other variables.
- Strict inequalities are not allowed; use
, , or . - There must be finitely many constraints.
To validate a formulation, map practical solutions to model solutions and back, preserving feasibility and objective value.
Multiperiod models
Multiperiod models couple decisions through time. With purchase
Given
To minimize the maximum purchase, introduce
Application
Production planning uses nonnegative production variables, resource-capacity constraints, and profit (revenue minus cost). Optimization is iterative: practical problem