Operations Research

Linear Programming: Formulation and the Graphical Method

Operations Research Study guides

Linear programming picks the best value of a linear objective under linear limits. Learn to define variables, write constraints, draw the feasible region and test corner points.

A linear programming (LP) problem maximizes or minimizes a linear objective function subject to linear constraints and non-negativity. To formulate one, first define the decision variables (for example x = units of product A, y = units of product B). Then write the objective, such as maximize Z = 40x + 30y for profit. Then write one constraint per limited resource, such as 2x + y <= 100 for machine hours, and add x >= 0 and y >= 0.

The graphical method works for two variables. Draw each constraint as a line, shade the side that satisfies it, and the overlap of all shaded sides is the feasible region. If the feasible region is not empty and the objective is bounded, an optimal solution is always at a corner point (extreme point) of the region. So find every corner by solving pairs of constraint lines, compute Z at each corner, and pick the largest (for maximize) or smallest (for minimize).

Special cases appear in exams. If the objective line is parallel to a binding constraint, there are multiple optimal solutions along an edge. If the feasible region is unbounded in the direction of improvement, the problem is unbounded. If the constraints conflict and have no common region, the problem is infeasible. A constraint that touches the optimal point is binding and has zero slack, while the others have slack or surplus left over.

Key points

  • Define variables, objective, constraints, non-negativity.
  • Feasible region = intersection of all constraints.
  • Optimum is at a corner point of the feasible region.
  • Parallel objective gives multiple optima.
  • Unbounded and infeasible are the special cases.

Worked example

Maximize Z = 40x + 30y subject to 2x + y <= 100, x + y <= 70, x, y >= 0. Corners: (0, 0) with Z = 0; (50, 0) with Z = 2000; (0, 70) with Z = 2100; and the intersection of 2x + y = 100 and x + y = 70, which gives x = 30, y = 40, with Z = 1200 + 1200 = 2400. The maximum is Z = 2400 at (30, 40).

Common questions

Why is the optimum at a corner point?

Because the objective is linear, its value changes steadily across the region, so the best value is reached at an extreme point.

What does an infeasible LP mean?

The constraints contradict each other, so no point satisfies all of them.

Related topics

BASMAGLY is an independent student project, not an official Delta University site. Check lectures and your instructor for the final word.