Chapter I: Introduction to Operations Research

Welcome to Operations Research!

Discover how mathematics and computational methods help solve real-world decision-making problems across industries, governments, and daily life.

Definition

Operations Research (OR) is a scientific approach to decision-making that seeks to determine how best to design and operate systems, usually under conditions requiring the allocation of scarce resources.

"The set of rational methods and techniques oriented toward finding the best choice in how to operate in order to achieve the desired result or the best possible result."

💡 Think About It:

When you plan your daily schedule, allocate your study time, or choose the fastest route to university; you're already doing informal operations research!

The Challenge: British military needed to optimize radar placement to defend against German air attacks.

The Innovation: Physicist Patrick Blackett assembled a multidisciplinary team; the first "Operational Research" group, to apply scientific methods to military operations.

The Success: Mathematical analysis dramatically improved resource allocation, aircraft deployment, and defense strategies.

Key Insight: Complex operational problems could be solved using quantitative analysis, not just intuition.

✅ Fun Fact:

The famous meeting between George Dantzig and mathematician John von Neumann on October 3, 1947, led to the development of duality theory, one of the most important concepts in optimization!

Type 1: Combinatorial Problems

Characteristic: Large (often enormous) number of possible solutions

Challenge: Finding the best solution among billions of possibilities

Example: Choosing 5 warehouse locations from 30 potential sites

• Number of combinations: C(30,5) = 142,506 possible selections!
• Must evaluate which combination minimizes total transportation cost

Solution Methods: Branch and bound, dynamic programming, heuristics

Type 2: Stochastic (Probabilistic) Problems

Characteristic: Involve uncertainty and randomness

Challenge: Must account for variability in data

Example: Inventory management with uncertain demand

• Customer demand varies randomly each day
• Must balance inventory costs vs. stockout risk

Solution Methods: Probability theory, simulation, stochastic programming

Type 3: Competitive Problems

Characteristic: Multiple decision-makers with conflicting objectives

Challenge: Each player's decision affects others

Example: Pricing strategies in competitive markets

• Two companies compete for same customers
• Each must anticipate competitor's actions

Solution Methods: Game theory, Nash equilibrium analysis

What is Linear Programming?

Linear Programming is a mathematical method for determining the optimal allocation of limited resources among competing activities, where both the objective and constraints are expressed as linear functions.

Standard Form of a Linear Program

Optimize (Maximize or Minimize):

z = c₁x₁ + c₂x₂ + ... + cₙxₙ

Subject to:

a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁
a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂
...
aₘ₁x₁ + aₘ₂x₂ + ... + aₘₙxₙ ≤ bₘ

Non-negativity:

x₁, x₂, ..., xₙ ≥ 0

Optimize: z = cᵀx

Subject to: Ax ≤ b, x ≥ 0

Where:

• x = (x₁, x₂, ..., xₙ)ᵀ is the decision variable vector (n × 1)
• c = (c₁, c₂, ..., cₙ)ᵀ is the objective coefficient vector (n × 1)
• A = [aᵢⱼ] is the constraint matrix (m × n)
• b = (b₁, b₂, ..., bₘ)ᵀ is the right-hand side vector (m × 1)

💡 Why Matrix Notation? Cleaner, more compact, easier for computer implementation, and essential for theoretical analysis!

The Three-Step Modeling Process

Problem Statement

A furniture company produces two products: chairs (Product A) and tables (Product B).

Resource Requirements:

🎯 Management Question: How many chairs and tables should the company produce to maximize total profit?

Solution: Step-by-Step Formulation

When Can We Use the Graphical Method?

• Only works for problems with two decision variables (x₁ and x₂)
• Provides excellent visual understanding of LP concepts
• Shows feasible region, constraints, and optimization graphically
• Great for learning, but impractical for larger problems

Step 1: Set Up Coordinate System

• Horizontal axis (x-axis) represents x₁
• Vertical axis (y-axis) represents x₂
• Only plot the first quadrant (both variables ≥ 0)

Step 2: Plot Each Constraint

For each constraint:

1. Convert inequality to equality (replace ≤ with =)
2. Find two points on the line (usually intercepts)
3. Draw the line
4. Determine which side satisfies the inequality (shade feasible region)

Example for 2x₁ + x₂ ≤ 400:

• When x₁ = 0: x₂ = 400 → Point (0, 400)
• When x₂ = 0: x₁ = 200 → Point (200, 0)
• Draw line through these points
• Test point (0,0): 2(0) + (0) = 0 ≤ 400 ✓ → Shade toward origin

Step 3: Identify Feasible Region

• The feasible region is where ALL constraints are satisfied simultaneously
• It's the intersection (overlap) of all individual constraint regions
• For LP problems, this is always a convex polygon

Step 4: Find Corner Points (Vertices)

• The optimal solution is always at a corner point (vertex) of the feasible region
• Find coordinates of all corner points by solving systems of equations
• Include intersection points and axis intercepts

Step 5: Evaluate Objective Function

• Calculate the objective function value at each corner point
• The corner point with the best objective value is the optimal solution

🔑 Fundamental Theorem of Linear Programming

If an optimal solution exists, it occurs at a vertex (corner point) of the feasible region.

This is why we only need to check corner points—we don't need to test every point inside the region!

Problem Statement

A company produces two products: Product A and Product B. The company uses three raw materials (M1, M2, M3) with limited availability.

Resource Requirements and Profit:

🎯 Question: How many units of Product A and Product B should the company produce to maximize total profit?

Mathematical Formulation

Graphical Solution Process

Step 1: Plot the Constraint Lines

Step 2: Identify Corner Points

The feasible region is bounded by the constraints and the axes. We need to find all corner points:

Step 3: Evaluate Objective Function at Each Corner Point

🎉 Optimal Solution

Optimal Production Plan:
• Produce 100 units of Product A
• Produce 200 units of Product B

Maximum Profit: $35,000

Resource Utilization:

• Material M1: 100 + 200 = 300 units (fully utilized ✓)
• Material M2: 2(100) + 200 = 400 units (fully utilized ✓)
• Material M3: 200 units used out of 250 available (50 units slack)

💡 Interpretation: Materials M1 and M2 are the binding constraints (fully used), while M3 has excess capacity. If we could obtain more M1 or M2, we could increase profit!

🔍 Key Insights from This Example

• Corner point optimality: The optimal solution occurred at vertex C, confirming the fundamental theorem
• Binding constraints: M1 and M2 are tight (no slack), meaning they limit production
• Non-binding constraint: M3 has 50 units of slack—not fully utilized
• Sensitivity: Additional units of M1 or M2 would increase profit (shadow prices > 0)
• Trade-offs: Product A has higher unit profit ($150 vs $100), but requires more M2

✅ Verification

Let's verify that our solution (100, 200) satisfies all constraints:

• M1: 100 + 200 = 300 ≤ 300 ✓
• M2: 2(100) + 200 = 400 ≤ 400 ✓
• M3: 200 ≤ 250 ✓
• Non-negativity: x₁ = 100 ≥ 0, x₂ = 200 ≥ 0 ✓

All constraints satisfied! ✓

Step 1: Initialization

Convert problem to standard form

Add slack variables to convert inequalities to equalities

Find an initial basic feasible solution (usually origin)

Step 2: Optimality Test

Check if current solution is optimal

Examine reduced costs (or relative cost coefficients)

If all ≤ 0 for maximization: STOP, optimal found!

Step 3: Select Entering Variable

Choose variable to enter the basis

Select variable with most positive reduced cost

This variable will increase from 0 to some positive value

Step 4: Unboundedness Test

Check if problem is unbounded

If entering variable can increase indefinitely: problem is unbounded

Otherwise, proceed to next step

Step 5: Select Leaving Variable

Determine which variable will leave the basis

Use minimum ratio test

Ensures feasibility is maintained

Step 6: Pivot Operation

Perform pivoting (row operations)

Update the simplex tableau

Move to new corner point

1. Bounds on Optimal Value

Use dual to quickly find upper/lower bounds without fully solving the primal

2. Sensitivity Analysis

Shadow prices show how objective changes with resource availability

3. Computational Efficiency

Sometimes the dual is easier to solve than the primal (fewer constraints or variables)

4. Economic Insights

Shadow prices reveal resource valuations for strategic decision-making

✈️ Aviation: American Airlines

Application: Crew scheduling, route optimization, fleet assignment

Impact: Saves over $500 million annually

Methods: Large-scale LP, integer programming, network optimization

📦 Logistics: UPS ORION System

Application: Route optimization for delivery drivers

Impact: Saves 100+ million miles per year, reduces fuel costs and emissions

Methods: Vehicle routing algorithms, real-time optimization

🏭 Manufacturing: Toyota Production System

Application: Just-in-time production, inventory minimization

Impact: Revolutionary lean manufacturing principles

Methods: Scheduling algorithms, inventory theory, quality control

💰 Finance: Portfolio Optimization

Application: Asset allocation, risk management

Impact: Foundation of modern investment theory (Nobel Prize: Markowitz, 1990)

Methods: Quadratic programming, stochastic optimization