linear programs

Work in Progress

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:

  1. Variables cannot be multiplied or divided by other variables.
  2. Strict inequalities are not allowed; use , , or .
  3. 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 , inventory , demand , and capacity , the central balance is

Given , minimizing shifts purchases toward cheap periods while respecting storage and demand. Holding cost adds .

To minimize the maximum purchase, introduce , impose for every , and minimize . At optimum ; otherwise could decrease.

Application

Production planning uses nonnegative production variables, resource-capacity constraints, and profit (revenue minus cost). Optimization is iterative: practical problem mathematical model solver validation. See multiperiod models, integer programs, and nonlinear programs.