Linear Programming

Definition

A linear programming problem involves finding the optimal value (maximum or minimum) of a linear function of several variables (called the objective function) subject to conditions that the variables are non-negative and satisfy a set of linear inequalities (called linear constraints). Variables are also called decision variables.

Examples of Linear Programming Problems

• Diet problems
• Manufacturing problems
• Transportation problems

Feasible Region

• The common region determined by all constraints (including x ≥ 0, y ≥ 0) is called the feasible region.
• Points inside or on the boundary → feasible solutions.
• Points outside → infeasible solutions.
• Any feasible point that gives the optimal value of the objective function is an optimal solution.

Fundamental Theorems

• Theorem 1: If Z = ax + by is the objective function, the optimal value (max or min) must occur at a corner point (vertex) of the feasible region.
• Theorem 2: If the feasible region R is bounded, Z has both a maximum and a minimum value, each occurring at a corner point.
• If R is unbounded, a maximum or a minimum may not exist. If it does, it must occur at a corner point.

Corner Point Method

1. Find the feasible region and determine its corner points (vertices).
2. Evaluate Z = ax + by at each corner point. Let M = largest value, m = smallest value.
3. If the region is bounded, → M and m are the maximum and minimum values.
4. If the region is unbounded:
   • M is maximum if the half-plane ax + by > M has no common point with the feasible region.
   • m is minimum if the half-plane ax + by < m has no common point with the feasible region.

Special Case

If two corner points both give the same optimal value (max or min), then every point on the line segment joining them is also an optimal solution.