Linear Programming & Optimization: Models, Graphs & Applications

Core Concepts & Definitions

1. What is Linear Programming (LP)?

Linear Programming is a mathematical optimization technique used to find the best possible outcome (maximum profit or minimum cost) in a linear mathematical model subject to constraints.

Key Features of LP Problems:

• Objective Function: A linear equation to be maximized (e.g., profit) or minimized (e.g., cost).
• Decision Variables: Variables under the control of the decision-maker (e.g., number of products to produce).
• Constraints: Limitations or restrictions (e.g., machine hours, raw material availability).
• Non-negativity: Decision variables cannot be negative (e.g., you can’t produce -10 units).

Example in Real Life:

• Nepal Food Corporation (NFC) must decide how much wheat and maize to produce given limited land and labor.
• Daraz optimizes delivery routes to minimize fuel costs while meeting delivery deadlines.

Formulating an LP Problem

Step-by-Step Formulation

1. Identify Decision Variables (e.g., $x$ = units of Product A, $y$ = units of Product B).
2. Write the Objective Function (e.g., maximize $Z=50x+40y$).
3. List Constraints (e.g., $2x+y\le 100$ [labor hours], $x+3y\le 120$ [material]).
4. Add Non-negativity Constraints ($x\ge 0,y\ge 0$).

Example: A Small Manufacturing Firm

A company produces two products:

• Product X: Requires 2 hours of labor, 1 kg of material, and yields ₹50 profit.
• Product Y: Requires 1 hour of labor, 3 kg of material, and yields ₹40 profit. Constraints:
• Maximum 100 labor hours.
• Maximum 120 kg of material.

Formulation:

Maximize \( Z = 50x + 40y \)
Subject to:
\( 2x + y \leq 100 \) (Labor)
\( x + 3y \leq 120 \) (Material)
\( x, y \geq 0 \)

Graphical Method of Solving LP Problems

How It Works

1. Plot Constraints: Convert inequalities into equations and draw lines.
2. Identify Feasible Region: The area satisfying all constraints.
3. Find Corner Points: The optimal solution lies at one of the corner points.
4. Evaluate Objective Function: Calculate $Z$ at each corner point.

Visual: Graphical Solution for the Manufacturing Example

pie
    title Feasible Region for Product X & Y
    "Labor Constraint (2x + y ≤ 100)"
    "Material Constraint (x + 3y ≤ 120)"
    "Non-negativity (x ≥ 0, y ≥ 0)"
    "Feasible Region (Shaded Area)"
    "Corner Points: (0,0), (0,40), (50,0), (30,20)"

Corner Points & Profit Calculation:

Optimal Solution: Produce 50 units of X and 0 units of Y for maximum profit of ₹2500.

The Simplex Method (Algebraic Approach)

When to Use Simplex?

• When problems have more than 2 variables (graphical method fails).
• For large-scale optimization in industries.

Steps of Simplex Method

1. Convert Inequalities to Equations: Introduce slack variables (e.g., $s_1,s_2$).
2. Write Initial Simplex Tableau.
3. Identify Pivot Column & Row.
4. Perform Row Operations to get a new tableau.
5. Check for Optimality: If no negative coefficients in the objective row, stop.

Example: Simplex Tableau for the Manufacturing Problem

After converting constraints:

Maximize \( Z = 50x + 40y + 0s_1 + 0s_2 \)
Subject to:
\( 2x + y + s_1 = 100 \)
\( x + 3y + s_2 = 120 \)
\( x, y, s_1, s_2 \geq 0 \)

Initial Simplex Tableau:

   Basis | x | y | s1 | s2 | RHS
   ----------------------------
   s1    | 2 | 1 | 1 | 0 | 100
   s2    | 1 | 3 | 0 | 1 | 120
   Z-row |-50|-40|0 | 0 | 0

Iteration 1:

• Pivot Column: $y$ (most negative in Z-row).
• Pivot Row: $s_2$ (minimum ratio test: $120/3=40$).
• Perform Row Operations → New tableau.

Final Solution:

• $x=50$, $y=0$, $Z=2500$.

Special Cases in LP

1. Unbounded Solution

• Occurs when the feasible region extends infinitely in the direction of improvement.
• Example: If a constraint is missing (e.g., no upper limit on resources).

2. Infeasible Solution

• No feasible region exists (constraints conflict).
• Example: A factory needs more labor than available.

3. Alternative Optimal Solutions

• Multiple corner points yield the same optimal value.
• Example: Two different production mixes give the same profit.

4. Degeneracy

• A corner point has one or more variables equal to zero.
• Can cause cycling in simplex iterations.

Sensitivity Analysis in LP

What It Does

• Examines how changes in objective coefficients or constraints affect the optimal solution.
• Helps in "what-if" scenarios.

Key Questions Answered by Sensitivity Analysis

1. How much can the profit coefficient change before the optimal solution changes?
2. What if a new constraint is added?
3. What if resource availability changes?

Example: Changing Profit of Product Y

• Current profit for $Y$ is ₹40.
• Range of Optimality: $33.\overline{3}\le \text{Profit of Y}\le 50$.
  • If profit of $Y$ increases beyond ₹50, the optimal solution shifts to producing only $Y$.

Integer Programming (IP)

When to Use IP?

• When decision variables must be whole numbers (e.g., number of machines, workers).
• Example: A factory cannot produce a fraction of a product.

Difference from LP

Solving IP: Branch and Bound Method

1. Solve as LP to get an initial solution.
2. Branch into sub-problems where variables are forced to be integers.
3. Bound the solutions to eliminate non-optimal branches.

Example: Nepali Bakery Problem

A bakery produces bread (x) and cakes (y):

• Profit: ₹20 per bread, ₹30 per cake.
• Constraints:
  • $2x+y\le 100$ (oven hours)
  • $x+2y\le 120$ (labor hours)
• LP Solution: $x=40,y=20$ (but $y$ must be integer).

IP Solution:

• Try $y=20$ → Check feasibility.
• If infeasible, try $y=19$ or $y=21$.
• Final optimal integer solution: $x=42,y=16$ (profit = ₹1200).

Applications of LP in Nepal

1. Agriculture (Nepal Food Corporation - NFC)

• Problem: Allocate land between wheat and maize to maximize profit.
• Constraints: Irrigation water, labor, and market demand.
• Solution: LP helps decide optimal crop mix.

2. Transportation (NTC & Ncell Logistics)

• Problem: Deliver goods from warehouses to retail stores at minimum cost.
• Constraints: Truck capacity, road conditions, fuel costs.
• Solution: Transportation LP models optimize routes.

3. Banking (Nabil Bank, Global IME)

• Problem: Allocate loans to different sectors (agriculture, business) for maximum return.
• Constraints: Total loanable funds, risk limits.
• Solution: LP ensures optimal portfolio diversification.

4. E-Commerce (Daraz, Pathao)

• Problem: Optimize inventory levels to minimize holding costs while meeting demand.
• Constraints: Storage space, supplier lead times.
• Solution: Inventory LP models reduce waste.

5. Healthcare (Patan Hospital)

• Problem: Allocate nurses and doctors to shifts to minimize overtime costs.
• Constraints: Staff availability, patient needs.
• Solution: LP ensures efficient workforce scheduling.

Real-World Case Study: Toyota’s Production Optimization

Problem

Toyota produces multiple car models (e.g., Corolla, Fortuner) with limited assembly line capacity and raw materials.

LP Model Used

1. Decision Variables:
   • $x$ = Number of Corolla units.
   • $y$ = Number of Fortuner units.
2. Objective: Maximize profit $Z=500x+800y$.
3. Constraints:
   • Assembly line hours: $10x+20y\le 10,000$.
   • Steel availability: $5x+15y\le 15,000$.

Solution

• Optimal Production: 500 Corolla and 300 Fortuner units.
• Result: ₹690 million profit with constrained resources.

Exam Tip: How to Score Full Marks in TU Exams

1. Problem Formulation (30% Weightage)

• Do:
  • Clearly define decision variables.
  • Write the objective function correctly.
  • List all constraints (including non-negativity).
• Avoid:
  • Missing constraints.
  • Incorrect signs in inequalities.

2. Graphical Solution (20% Weightage)

• Do:
  • Plot all constraints accurately.
  • Shade the feasible region correctly.
  • Identify all corner points.
  • Calculate $Z$ at each corner.
• Avoid:
  • Skipping the feasible region.
  • Misidentifying corner points.

3. Simplex Method (25% Weightage)

• Do:
  • Show initial tableau clearly.
  • Perform row operations step-by-step.
  • Explain pivot selection.
  • State the final optimal solution.
• Avoid:
  • Arithmetic errors.
  • Skipping iterations.

4. Sensitivity Analysis (15% Weightage)

• Do:
  • Explain range of optimality.
  • Discuss shadow prices (dual values).
  • Interpret changes in constraints.
• Avoid:
  • Assuming all coefficients are equally sensitive.

5. Integer Programming (10% Weightage)

• Do:
  • Solve the LP relaxation first.
  • Use branching rules (e.g., round up/down).
  • Verify integer constraints.
• Avoid:
  • Forgetting to check feasibility after branching.

Common Mistakes to Avoid

❌ Ignoring Non-negativity Constraints → Leads to unrealistic solutions. ❌ Incorrect Feasible Region in Graphical Method → Wrong optimal solution. ❌ Arithmetic Errors in Simplex → Wrong final answer. ❌ Assuming LP Always Gives Integer Solutions → Must check for IP. ❌ Not Interpreting Sensitivity Results → Partial credit lost.

Practice Questions for TU Exam

1. Formulate an LP model for a company producing two products with given constraints.
2. Solve graphically and find the optimal solution.
3. Apply the simplex method to a 3-variable problem.
4. Perform sensitivity analysis for a given LP problem.
5. Solve an integer programming problem using branching.

In the Real World

1. eSewa & Khalti (Digital Payments Optimization)

• LP Idea Used: Resource Allocation
• How?
  • eSewa must allocate servers, bandwidth, and customer support agents to handle transactions efficiently.
  • Objective: Minimize server costs while ensuring no downtime.
  • Constraints:
    • Maximum transactions per server.
    • Peak hour demand (e.g., during Dashain/Tihar).
  • Result: LP models help reduce costs by 20% while maintaining service quality.

2. Daraz (Inventory & Delivery Optimization)

• LP Idea Used: Transportation & Inventory Models
• How?
  • Daraz uses LP to decide:
    • How many products to stock in each warehouse (minimizing holding costs).
    • Optimal delivery routes for last-mile delivery (minimizing fuel costs).
  • Example:
    • If Daraz has 3 warehouses and 5 delivery zones, LP finds the cheapest way to distribute orders.
    • Real Impact: Faster deliveries and 15% cost savings.

3. NTC (Telecom Network Optimization)

• LP Idea Used: Network Design & Capacity Planning
• How?
  • NTC must decide:
    • Where to place cell towers to cover maximum users.
    • How to allocate spectrum to avoid interference.
  • Example:
    • If NTC has limited spectrum bands, LP helps assign them to high-demand areas (e.g., Kathmandu, Pokhara).
    • Result: Better network coverage with minimal infrastructure cost.

Final Summary Table: LP vs. IP vs. Transportation Models