U45 Linear Programming (LP) Essential Formulas

General Form of a Linear Programming Problem

A linear programming problem consists of an objective function to be maximized or minimized, subject to a set of linear constraints (inequalities or equations) and non-negativity constraints $x, y \ge 0$.

Subject to constraints of the form $c_1x + d_1y \le (\text{or } \ge, =) \, k_1$, $c_2x + d_2y \le (\text{or } \ge, =) \, k_2$, etc., where $a, b, c_i, d_i, k_i$ are constants.

Steps for Graphical Solution

1. Treat each inequality constraint as a linear equation and plot its boundary line.
2. Determine the correct half-plane for each inequality by testing a point (e.g., the origin $(0,0)$ if it is not on the line).
3. The intersection of all half-planes (including $x \ge 0, y \ge 0$) is the feasible region. It is a convex polygon.
4. The optimal solution (if it exists) occurs at a corner point (vertex) of the feasible region.

Finding the Optimal Value

If a linear programming problem has an optimal solution, then at least one of the corner points of the feasible region is an optimal solution. To find it:

where $(x_i, y_i)$ are the coordinates of all corner points. Evaluate the objective function $P = ax + by$ at each vertex. The largest value is the maximum, the smallest is the minimum.

Unbounded Region and No Solution

Unbounded Feasible Region: The region extends infinitely in some direction. An optimal solution may still exist if the objective function is bounded in the direction of optimization.
No Feasible Solution: Occurs when the constraints are contradictory, resulting in an empty feasible region.
Multiple Optimal Solutions: If the objective function line is parallel to a boundary line of the feasible region, then all points on that edge are optimal.