Linear Programming (LPP): Formulation, Graphical Solution, Duality (Basics)

1) What is Linear Programming?

Linear Programming Problem (LPP) is an optimization problem where:

• objective function is linear,
• constraints are linear,
• decision variables are continuous and usually non-negative.

Economic uses:

• cost minimization with limited resources,
• profit maximization under capacity constraints,
• diet problem, transportation (advanced), production planning.

2) Standard form of an LPP

Maximize (or minimize):

Subject to:

Key terms:

• Decision variables: $x_1, x_2$
• Objective function: Z
• Constraints: linear inequalities/equalities
• Feasible region: set of all points satisfying constraints
• Optimal solution: feasible point maximizing/minimizing Z

3) Graphical solution method (2-variable LPP)

Steps:

1. Convert each inequality constraint to equality to draw boundary line.
2. Identify feasible side for each constraint.
3. Feasible region is intersection of all feasible half-planes + $x_1,x_2\ge 0$.
4. Find corner points (vertices).
5. Evaluate Z at each corner point → choose best.

Corner-point theorem (key result)

If an optimal solution exists, at least one optimal solution lies at a corner point of feasible region.