Linear Programming: Formulation, Graphical Solution and Sensitivity (Basics)

Meaning of LPP and why it is used

Linear Programming Problem (LPP) is a technique to find the best (optimal) value of an objective (profit/cost/time) when resources are limited and the relationships are linear.

Typical business uses (exam points):

• maximize profit given labour/material limits
• minimize cost given demand requirements
• product mix decisions
• production planning and allocation

Assumptions of linear programming

1. Linearity: objective and constraints are linear.
2. Additivity: total resource usage is sum of individual usages.
3. Divisibility: decision variables can be fractional (continuous) in model.
4. Certainty: coefficients are known and constant.
5. Non-negativity: variables cannot be negative.

Components: decision variables, objective, constraints

• Decision variables: unknowns to be chosen (x, y, …)
• Objective function: maximize or minimize Z = ax + by
• Constraints: resource/requirement limits like 2x + y ≤ 100
• Non-negativity: x ≥ 0, y ≥ 0

Formulation steps (word problem → model)

Step 1: Define decision variables.

• Example: x = units of product A, y = units of product B

Step 2: Write objective function.

• Profit: Max Z = 40x + 30y

Step 3: Write constraints from resources.

• Labour: 2x + y ≤ 100
• Material: x + 2y ≤ 80

Step 4: Add non-negativity.

• x ≥ 0, y ≥ 0

Exam tip: Always state units (hours, kg, ₹) with constraints.

Standard form and types of constraints (≤, ≥, =)

Common constraint types:

• ≤ (resource availability): 2x + y ≤ 100
• ≥ (minimum requirement): x + y ≥ 50
• = (exact requirement): x + y = 50

Graphical method is easiest with ≤ constraints. For ≥ constraints, the feasible region lies on the other side of the line.

Graphical solution method (two variables)

Used when there are only two decision variables.

Steps:

1. Convert each constraint into an equation to draw the line.
2. Find intercepts or use two points to plot each line.
3. Identify the half-plane that satisfies each inequality.
4. Intersection of all half-planes gives feasible region.
5. List corner points (vertices) of feasible region.
6. Evaluate Z at each corner point.
7. Best Z gives the optimal solution.

Feasible region and corner point theorem

• Feasible region: set of all points satisfying all constraints.
• Corner point theorem: In linear programming, optimal solution (if it exists) occurs at a corner point (vertex) of feasible region.

If feasible region is unbounded, optimum may still exist depending on objective direction.

Maximization vs minimization (basic handling)

• Maximization: push objective line upward/right (depending on coefficients).
• Minimization: push objective line toward origin (commonly) while still touching feasible region.

In exams, we usually solve both using corner point evaluation.

Slack and surplus variables (interpretation)

• For ≤ constraint: slack shows unused resource.
  • 2x + y ≤ 100 → 2x + y + s = 100, s ≥ 0
• For ≥ constraint: surplus shows excess above minimum.
  • x + y ≥ 50 → x + y − s = 50, s ≥ 0

Interpretation: slack = 0 at binding constraint (fully used resource).

Sensitivity basics (shadow idea + what-if)

At basic level, sensitivity means:

• how optimal solution changes if resources/profit coefficients change.

Simple what-if checks:

• Increase RHS of a binding constraint may increase max profit.
• If a constraint has slack at optimum, small increase in its RHS often does not change optimum.

(Full shadow price and simplex sensitivity is beyond basics; but concept is frequently asked.)

Worked example (complete)

A firm makes products A and B. Profit per unit: A = ₹40, B = ₹30. Labour limit: 2x + y ≤ 100. Material limit: x + 2y ≤ 80. Find x and y to maximize profit.

Step 1: Variables Let x = units of A, y = units of B.

Step 2: Objective Max Z = 40x + 30y

Step 3: Constraints 2x + y ≤ 100 x + 2y ≤ 80 x ≥ 0, y ≥ 0

Step 4: Corner points (by intercepts and intersection)

• (0,0)
• On 2x+y=100 with y=0 → x=50 → (50,0)
• On x+2y=80 with x=0 → y=40 → (0,40)
• Intersection of 2x+y=100 and x+2y=80: From first: y = 100 − 2x Put in second: x + 2(100 − 2x) = 80 x + 200 − 4x = 80 −3x = −120 → x = 40 y = 100 − 2(40) = 20 So intersection = (40,20)

Step 5: Evaluate Z

• Z(0,0) = 0
• Z(50,0) = 40×50 = 2000
• Z(0,40) = 30×40 = 1200
• Z(40,20) = 40×40 + 30×20 = 1600 + 600 = 2200

Optimal solution: x = 40, y = 20 with maximum profit Z = ₹2200.

Common mistakes and exam tips

• Not writing x ≥ 0, y ≥ 0.
• Shading wrong half-plane for inequalities.
• Missing a corner point.
• Using a point that is not feasible.
• Arithmetic errors in intersection.

Tip: Always verify each corner point satisfies all constraints.

Key terms explained

• Decision variables — quantities to decide (x, y).
• Objective function — maximize/minimize Z.
• Constraints — limitations/requirements.
• Feasible region — set of all feasible solutions.
• Corner point — vertex of feasible region.
• Slack — unused resource in ≤ constraint.
• Surplus — extra above minimum in ≥ constraint.

Quick recap (1-minute revision)

• LPP = optimize linear objective with linear constraints.
• Steps: variables → objective → constraints → feasible region → corner points → evaluate Z.
• Optimum occurs at a corner point.
• Slack shows unused resources.