Linear Programming

Linear programming helps you find the best way to allocate limited resources - like deciding how much of each product to make or how to divide your budget to maximize profit while staying within your constraints.

What is Linear Programming?

Linear programming is a method for finding the best solution when you want to maximize or minimize something (like profit or cost) while working within limitations (like budget or capacity).

Why Use Linear Programming?

Business Need: You have limited resources and want to use them in the best possible way to achieve your business goal, whether that's maximizing profit, minimizing costs, or optimizing efficiency.

Example: A bakery wants to decide how many croissants and muffins to bake each day to maximize profit, but they're limited by oven time, ingredients, and staff hours.

How Linear Programming Works

Simple Example: Bakery Production Planning

Your Situation: You own a bakery and want to maximize daily profit

Products You Can Make:

• Croissants: $3 profit each, take 10 minutes to make
• Muffins: $2 profit each, take 5 minutes to make

Your Limitations (Constraints):

• Oven time: 8 hours (480 minutes) per day
• Baker time: 6 hours (360 minutes) per day
• Croissant demand: Maximum 30 per day
• Muffin demand: Maximum 50 per day

Goal: Maximize total profit = ($3 × Croissants) + ($2 × Muffins)

Step 1: Set up the constraints

• Oven time: (10 × Croissants) + (5 × Muffins) ≤ 480 minutes
• Baker time: (8 × Croissants) + (4 × Muffins) ≤ 360 minutes
• Croissant limit: Croissants ≤ 30
• Muffin limit: Muffins ≤ 50

Step 2: Find the optimal solution Using linear programming: Make 20 croissants and 40 muffins

• Total profit: ($3 × 20) + ($2 × 40) = $140 per day
• Uses exactly 400 minutes of oven time and 320 minutes of baker time

When to Use Linear Programming

Use When:

• You want to maximize profit or minimize cost
• You have limited resources (time, money, materials, people)
• Each unit contributes the same amount (linear relationship)
• You can clearly define your constraints

Don't Use When:

• Relationships are not linear (economies of scale, bulk discounts)
• You have very few options to choose from
• Constraints change frequently
• The problem is too complex with too many variables

Practical Business Example: Manufacturing Resource Allocation

Business Problem: Electronics manufacturer wants to maximize monthly profit from two product lines

Products:

• Smartphones: $50 profit per unit
• Tablets: $80 profit per unit

Resource Constraints:

• Assembly time: 4,800 hours available per month
  • Smartphones need 2 hours each
  • Tablets need 4 hours each
• Testing time: 2,400 hours available per month
  • Smartphones need 1 hour each
  • Tablets need 2 hours each
• Market demand: Maximum 800 smartphones, 400 tablets per month

Linear Programming Solution:

Step 1: Set up the problem

• Goal: Maximize profit = ($50 × Smartphones) + ($80 × Tablets)
• Assembly constraint: (2 × Smartphones) + (4 × Tablets) ≤ 4,800
• Testing constraint: (1 × Smartphones) + (2 × Tablets) ≤ 2,400
• Demand constraints: Smartphones ≤ 800, Tablets ≤ 400

Step 2: Solve for optimal production Optimal solution: 800 smartphones and 400 tablets

• Monthly profit: ($50 × 800) + ($80 × 400) = $72,000
• Uses all 4,800 assembly hours and 2,400 testing hours
• Meets maximum market demand for both products

Business Impact:

• Clear production targets for manufacturing team
• Optimal resource utilization (no wasted capacity)
• Maximum profit given current constraints
• Foundation for capacity expansion decisions

3. Risk Constraint: No more than 40% in high-risk assets (real estate and equities)

• (Real Estate + Equities) ≤ 0.40 × Total Investment

4. Liquidity Constraint: Maintain liquid assets for policy payouts

• (Govt Bonds + Corp Bonds) ≥ 200M minimum liquid assets

Simple Tools You Can Use

Excel Solver

• Built-in optimization tool in Excel
• Set up your objective and constraints in spreadsheet
• Click "Solver" and let it find the optimal solution
• Good for: Small to medium problems (up to 200 variables)

Google Sheets Solver

• Similar to Excel but free
• Add-on available in Google Workspace Marketplace
• Good for: Basic optimization problems, team collaboration

Online Linear Programming Tools

• Many free web-based solvers available
• Just enter your constraints and objective
• Good for: Learning, simple problems, quick analysis

Business Software with Built-in Optimization

• Many ERP and supply chain systems include optimization
• Inventory management software often has allocation optimization
• Good for: Specific business processes, integrated with existing systems

Common Business Applications

Production Planning

Problem: Decide how much of each product to make to maximize profit Constraints: Machine capacity, labor hours, material availability Example: Furniture company deciding chairs vs. tables production

Budget Allocation

Problem: Divide marketing budget across channels to maximize return Constraints: Minimum spend requirements, channel capacity limits
Example: Allocate $100K across digital, print, radio, and events

Staff Scheduling

Problem: Assign employees to shifts to minimize cost while meeting coverage needs Constraints: Employee availability, union rules, skill requirements Example: Hospital scheduling nurses across different departments

Supply Chain Distribution

Problem: Ship products from warehouses to stores at minimum cost Constraints: Warehouse capacity, store demand, transportation limits Example: Retail chain distributing inventory to optimize shipping costs

Investment Allocation

Problem: Allocate investment funds to maximize return within risk limits Constraints: Budget limits, diversification requirements, regulatory rules Example: Pension fund allocating across stocks, bonds, and real estate

Quick Decision Guide

For Production Planning: Use when you have multiple products competing for the same resources For Budget Allocation: Use when you need to divide limited funds across multiple options optimally For Scheduling: Use when you have flexibility in assignments and want to minimize costs For Distribution: Use when you have multiple sources serving multiple destinations For Investment: Use when you want to optimize returns while staying within risk constraints

Linear programming turns complex resource allocation decisions into systematic optimization problems, helping you make mathematically optimal choices that maximize profit or minimize costs while respecting all your business constraints.

Duality Theory

Every linear programming problem has a "dual" companion problem that provides valuable business insights:

Primal-Dual Relationship

Primal Problem: Original optimization problem

• Focus: How to best use available resources
• Variables: Decision quantities (production levels, investment amounts)
• Example: "How much should we produce of each product?"

Dual Problem: Mirror problem with different perspective

• Focus: What are resources worth to the organization?
• Variables: Shadow prices (marginal resource values)
• Example: "What is the value of one additional hour of machine time?"

Business Connection: Dual variables represent the economic value of relaxing constraints

Strong Duality Principle

At optimality, both problems yield the same objective value:

Economic Interpretation:

• Primal Value: Total profit from optimal production plan
• Dual Value: Total worth of all resources at shadow prices
• Equality: Resources are valued exactly at their contribution to profit

Financial Services Example: Retirement Fund Allocation

Business Context: A pension fund manager allocates contributions across investment options to maximize long-term value while maintaining required security levels.

Investment Options:

• Treasury Bills: 3% annual return (highest security, lowest risk)
• High-grade Bonds: 5% annual return (high security, low risk)
• Index Funds: 8% annual return (moderate risk, diversified)
• Growth Stocks: 11% annual return (highest risk, highest potential return)

Objective: Maximize 20-year portfolio value while meeting fiduciary requirements

Business Constraints:

1. Full Allocation: All 1B in contributions must be invested

• Treasury Bills + Bonds + Index Funds + Growth Stocks = 1B

2. Security Requirement: At least 40% in secure fixed-income investments

• (Treasury Bills + High-grade Bonds) ≥ 0.40 × 400M

3. Growth Requirement: At least 30% in growth-oriented investments

• (Index Funds + Growth Stocks) ≥ 0.30 × 300M

4. Risk Limitation: No more than 20% in high-risk growth stocks

• Growth Stocks ≤ 0.20 × 200M

Optimal Allocation:

• Treasury bills: 400M (40%)
• High-grade bonds: 100M (10%)
• Index funds: 300M (30%)
• Growth stocks: 200M (20%)

Expected Annual Return: 6.5%

Business Impact: Balanced portfolio meeting fiduciary requirements while maximizing participant returns.

Sensitivity Analysis

Analyzing how optimal solutions change when business conditions change:

Shadow Prices

Shadow prices reveal the value of additional resources:

Business Interpretation:

• Shadow Price: Additional profit from one more unit of a constrained resource
• Example: If budget shadow price is 1M additional budget increases profit by 150K
• Zero Shadow Price: Resource has excess capacity, additional units have no value
• High Shadow Price: Resource is a critical bottleneck

Management Applications:

• Resource Allocation: Identify which constraints to relax first
• Investment Decisions: Calculate ROI of capacity expansion
• Negotiation: Understand the value of contract modifications

Allowable Ranges

Parameters can change within specific ranges without changing the optimal solution structure:

Stability Analysis: Determine how much conditions can change before reconsidering the current strategy

Retail Example: Customer Retention Campaign Optimization

Business Context: A retail chain optimizes marketing budget allocation across different customer retention campaigns to maximize customer lifetime value improvement.

Campaign Types:

• Email Marketing: Direct communication campaigns (thousands)
• Loyalty Programs: Points, rewards, and membership enhancements (thousands)
• Personalized Discounts: Targeted offers based on customer behavior (thousands)
• Premium Service: Enhanced customer support and concierge services (thousands)

Objective: Maximize customer lifetime value improvement across all campaigns

Effectiveness Rates (CLV increase per 1,000 invested):

• Email Marketing: 2,500 CLV increase (2.5x return)
• Loyalty Programs: 4,200 CLV increase (4.2x return)
• Personalized Discounts: 3,800 CLV increase (3.8x return)
• Premium Service: 5,100 CLV increase (5.1x return - highest effectiveness)

Business Constraints:

1. Budget Constraint: Total marketing budget of 500,000

• Email + Loyalty + Discounts + Premium Service = 500K

2. Technology Constraint: Limited IT infrastructure and platform capacity

• Technology-intensive campaigns (Email + Loyalty) ≤ 300K

3. Staff Constraint: Limited personnel for program management

• Labor-intensive campaigns (Loyalty + Premium Service) ≤ 400K

4. Minimum Investment Requirements: Each campaign needs minimum investment for effectiveness

• Email Marketing ≥ 50K, Personalized Discounts ≥ 40K

Optimal Solution:

• Email marketing: 50K
• Loyalty programs: 200K
• Personalized discounts: 100K
• Premium service: 150K

Maximum CLV Improvement: 2,015K

Business Impact: 22% improvement in customer retention rates and 18% increase in average customer lifetime value.

Applications Summary

Financial Services Applications

• Portfolio Optimization: Asset allocation for maximum risk-adjusted returns
• Capital Allocation: Optimal distribution of funds across business units
• Regulatory Compliance: Meeting capital requirements at minimum cost
• Risk Management: Hedging strategies and diversification optimization

Retail Applications

• Supply Chain: Optimal distribution and inventory placement
• Marketing Mix: Budget allocation across advertising channels
• Staffing: Workforce scheduling and resource allocation
• Pricing Strategy: Dynamic pricing for profit maximization

Key Benefits

• Optimal Decisions: Mathematical guarantee of best solution
• Resource Efficiency: Maximum output from limited resources
• Sensitivity Analysis: Understanding of solution robustness
• Scalability: Handles large-scale problems efficiently

Linear programming provides a rigorous mathematical framework for optimization in both financial services and retail sectors, enabling data-driven decision making that maximizes value while respecting operational and regulatory constraints.