Unit 2 – Linear Programming: Problem
Formulation
LECTURE SLIDES
OPERATIONS RESEARCH 1
Learning Objectives
At the end of this unit, students should be able to:
• Define Linear Programming (LP)
• Formulate a Linear Programming model
• Describe characteristics of an LP problem
• LP is a mathematical method for
allocating limited resources.
• 'Linear' → relationships between
variables are proportional.
What is Linear • 'Programming' → using
Programming mathematical techniques to find
the best solution.
?
• Goal: MAXIMIZE profits or
MINIMIZE costs.
➡ Example: Choosing best product
mix, diet plans, or schedules.
Characteristics of an LP Model
1. Objective function → maximize or minimize a
goal (profit/cost).
2. Decision variables → choices we control (e.g.,
units to produce).
3. Constraints → limits due to resources (time,
materials, budget).
4. Linearity → all equations/inequalities are linear.
5. Non-negativity → no negative values for
decision variables.
1. Define the decision
variables.
2. State the objective
function
(maximize/minimize).
Steps in LP 3. Write the constraints
Formulatio (resource limits,
n requirements).
4. Include non-negativity
constraints (x ≥ 0).
➡ Careful formulation
ensures real-world relevance.
Company produces Models A, B,
and C:
• Total production ≤ 100 units
• Paint available = 1,000
gallons
- A requires 5 gallons
Example - B requires 7 gallons
Problem – - C requires 10 gallons
Product Mix • Marketing rules:
- Exactly 20 A’s
- At least 5 B’s
-C≤2×B
• Profits: A=4,000 | B=5,200 |
C=3,000
Step 1 & 2: Decision Variables
& Objective
Decision Variables:
• A = units of Model A
• B = units of Model B
• C = units of Model C
Objective Function:
Maximize Profit:
Z = 4,000A + 5,200B + 3,000C
Step 3: Constraints
Resource Limits:
• A + B + C ≤ 100 (capacity)
• 5A + 7B + 10C ≤ 1,000 (paint)
Marketing Mix:
• A = 20 (exact requirement)
• B ≥ 5 (minimum)
• C ≤ 2B (ratio rule)
Non-Negativity:
• A, B, C ≥ 0
Final LP Model
Maximize: Z = 4,000A + 5,200B + 3,000C
Subject to:
• A + B + C ≤ 100
• 5A + 7B + 10C ≤ 1,000
• A = 20
•B≥5
• C ≤ 2B
• A, B, C ≥ 0
➡ This is the complete LP formulation!
Visualizing LP
Imagine a 3D space where:
• Each axis = A, B, C
• Constraints = planes that form boundaries
• Feasible region = space where all rules are
satisfied
• Optimal solution = point giving highest profit (Z)
➡ Graphical methods work for 2D, Simplex for
many variables.
Self-Review Questions
1. Define Linear Programming.
2. What are the key features of an LP model?
3. Write the steps in LP formulation.
4. Why is A + B + C ≤ 200 a redundant constraint
in the example?
5. How does LP help managers in decision-
making?