Linear Programming

Linear programming is a mathematical optimization technique for finding the best outcome in a model with linear relationships. It's widely used in financial services for portfolio optimization and in retail for resource allocation and supply chain management.

Business Foundation

Linear programming finds optimal solutions when both objectives and constraints can be expressed as linear relationships:

Core Components:

Objective Function: What you want to maximize (profit, efficiency) or minimize (cost, risk)
Decision Variables: The quantities you control (investments, production, allocations)
Constraints: Limitations and requirements (budgets, capacity, regulations)
Linear Relationships: Each decision variable contributes proportionally to objectives and constraints

Business Applications:

Maximize profit subject to resource limitations
Minimize cost while meeting service requirements
Optimize allocation across competing priorities
Balance multiple objectives with regulatory constraints

Standard Form Components

Objective Function

The business goal expressed as a mathematical function:

Maximization Problems: Profit maximization, return optimization, efficiency improvement

Example: Maximize Total Profit = (Unit Profit 1 × Quantity 1) + (Unit Profit 2 × Quantity 2) + ...

Minimization Problems: Cost minimization, risk reduction, resource conservation

Example: Minimize Total Cost = (Unit Cost 1 × Quantity 1) + (Unit Cost 2 × Quantity 2) + ...

Key Elements:

Objective Value: Total result we want to optimize
Coefficients: Per-unit contribution to the objective
Decision Variables: Quantities under our control
Linearity: Each variable contributes proportionally

Constraint Set

Business limitations and requirements:

Constraint Types:

Resource Constraints: Limited budgets, capacity, materials, or time
Demand Requirements: Minimum service levels, quota fulfillment
Regulatory Limits: Compliance requirements, safety standards
Operational Rules: Business policies, strategic requirements

Mathematical Structure: Each constraint expresses how decision variables consume or generate resources

Simplex Method

The simplex algorithm systematically searches for the optimal solution by moving between feasible corner points:

Solution Strategy

Linear programming optimal solutions occur at vertices (corner points) of the feasible region:

Algorithm Steps:

Start: Begin at any feasible corner point
Evaluate: Check if current point can be improved
Move: If possible, move to an adjacent corner point with better objective value
Repeat: Continue until no improvement is possible
Optimal: Current point is the optimal solution

Business Interpretation

At each corner point, some activities are at their limits (active constraints) while others may have unused capacity:

Basic Variables: Activities running at positive levels

Example: Products being produced, investments being made

Non-basic Variables: Activities not being used in current solution

Example: Unused production capacity, unselected investment options

Optimality Check: Determine if switching to unused activities could improve the objective

Financial Services Example: Life Insurance Portfolio Optimization

Business Context: A life insurance company optimizes its investment portfolio to maximize returns while managing risk and meeting regulatory requirements.

Decision Variables:

Government Bonds: Amount invested in low-risk government securities (millions)
Corporate Bonds: Amount invested in medium-risk corporate debt (millions)
Real Estate: Amount invested in property and REITs (millions)
Equities: Amount invested in stocks and equity funds (millions)

Objective Function: Maximize expected annual return

Expected Returns:

Government Bonds: 4% annual return (lowest risk)
Corporate Bonds: 6% annual return (medium-low risk)
Real Estate: 8% annual return (medium risk)
Equities: 12% annual return (highest risk, highest return)

Maximize: Total Annual Return = (0.04 × Govt Bonds) + (0.06 × Corp Bonds) + (0.08 × Real Estate) + (0.12 × Equities)

Business Constraints:

1. Budget Constraint: Total investment cannot exceed 500M available capital

Govt Bonds + Corp Bonds + Real Estate + Equities ≤ 500M

2. Regulatory Constraint: At least 50% must be in bonds for regulatory compliance

(Govt Bonds + Corp Bonds) ≥ 0.50 × Total Investment

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

Optimal Solution (using simplex method):

Government Bonds: 150M (30% of portfolio)
Corporate Bonds: 100M (20% of portfolio)
Real Estate: 100M (20% of portfolio)
Equities: 150M (30% of portfolio)
Total Investment: 500M

Optimal Annual Return: (0.04 × [mathematical expression]100M) + (0.08 × [mathematical expression]150M) = 32M = 6.4%

Business Impact: 6.4% annual portfolio return while meeting all regulatory and risk constraints.

Retail Example: Supply Chain Optimization

Business Context: A retail chain optimizes product distribution from warehouses to stores to minimize transportation costs while meeting demand.

Decision Variables:

Shipping Quantities: Units shipped from each warehouse to each store
Example: Warehouse 1 to Store 2, Warehouse 2 to Store 3, etc.

Objective Function: Minimize total shipping cost

Formula: Sum of (Shipping Cost per Unit × Units Shipped) for all warehouse-store combinations

Cost Matrix ([mathematical expression]) - Cost per unit shipped:

        Store 1  Store 2  Store 3  Store 4
Warehouse 1:  8      6       10      9
Warehouse 2:  9      12      13      7  
Warehouse 3:  14     9       16      5

Constraints:

Supply Constraints: Each warehouse has limited inventory

Warehouse 1: Can ship maximum 300 units total
Warehouse 2: Can ship maximum 300 units total
Warehouse 3: Can ship maximum 200 units total

Demand Constraints: Each store has specific requirements

Store 1: Needs exactly 200 units
Store 2: Needs exactly 250 units
Store 3: Needs exactly 200 units
Store 4: Needs exactly 150 units

Complete Problem Formulation: Minimize total shipping cost subject to supply and demand constraints

Optimal Solution:

Warehouse 1 → Store 2: 250 units, Store 4: 50 units
Warehouse 2 → Store 1: 200 units, Store 4: 100 units
Warehouse 3 → Store 3: 200 units

Total Cost: 7,200

Business Value: 15% reduction in shipping costs compared to ad-hoc allocation.

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 × [mathematical expression]400M

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

(Index Funds + Growth Stocks) ≥ 0.30 × [mathematical expression]300M

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

Growth Stocks ≤ 0.20 × [mathematical expression]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 [mathematical expression]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 ≥ [mathematical expression]50K, Personalized Discounts ≥ [mathematical expression]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.

Overview Optimization Methods