Linear Programming: Formulation & Graphical Solution

TAKEAWAYS:

• Linear Programming (LPP) converts word problems into mathematical inequalities to maximize/minimize objectives under constraints.
• Graphical solutions work only for problems with ≤2 decision variables (e.g., two machines, two products).
• The feasible region is the polygon where all constraints overlap; its corner points always contain the optimal solution.
• Non-binding constraints (slack > 0) can be ignored when testing corner points.
• Unbounded problems have no solution if the feasible region extends infinitely in the direction of the objective function.
• Graphical methods fail for >2 variables but are useful for intuition and small-scale problems.

1. What is a Linear Programming Problem (LPP)?

LPP is a mathematical technique to optimize (maximize/minimize) a linear objective function subject to linear constraints. It is used to allocate limited resources efficiently.

Key Components

• Decision Variables (x₁, x₂, …): Quantities to be determined (e.g., units of product P, Q).
• Objective Function: The goal to maximize/minimize (e.g., profit Z = 3x₁ + 4x₂).
• Constraints: Resource limits (e.g., 2x₁ + x₂ ≤ 100 for raw material).
• Non-negativity: x₁, x₂ ≥ 0 (no negative production).

Standard Form

mindmap:
  root((LPP Standard Form))
    Maximize Z = c₁x₁ + c₂x₂ + ... + cₙxₙ
    Subject to:
      a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁ (Constraint 1)
      a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂ (Constraint 2)
      ...
      x₁, x₂, ..., xₙ ≥ 0

Example: Food Production

A company produces two foods, P and Q, with vitamins A, B, and C. Each unit of P has 2A, 2B, 1C; Q has 1A, 3B, 2C. Daily demand: ≥10A, ≥20B, ≥15C. Cost: P = Rs. 5, Q = Rs. 7. Maximize profit Z = 3P + 4Q under constraints.

2. Formulating LPP from Word Problems

Step-by-Step Process

1. Identify Decision Variables: Let P = x, Q = y.
2. Write Objective Function: Maximize Z = 3x + 4y.
3. Translate Constraints:
   • Vitamin A: 2x + y ≥ 10
   • Vitamin B: 2x + 3y ≥ 20
   • Vitamin C: x + 2y ≥ 15
4. Non-negativity: x, y ≥ 0.

Worked Example: Kathmandu Traffic Routes

A city has two routes (A, B) to reduce congestion. Maximize passenger flow Z = 5A + 3B under:

• Route A can handle ≤1000 cars/day.
• Route B ≤800 cars/day.
• Total capacity: A + B ≤ 1500.

mindmap:
  root((Traffic Routes LPP))
    Maximize Z = 5A + 3B
    Constraints:
      A ≤ 1000
      B ≤ 800
      A + B ≤ 1500
      A, B ≥ 0

3. Graphical Solution Method

Works only for 2-variable LPPs (x, y). Steps:

1. Plot constraints as lines.
2. Shade the feasible region (where all constraints overlap).
3. Find corner points of the feasible region.
4. Evaluate Z at each corner to find the optimal solution.

Key Visuals

• Constraint Lines: Plot as y = mx + c.
• Feasible Region: Overlapping shaded area.
• Corner Points: Intersections of boundary lines.

Worked Example: Food Production (Graphical)

Constraints:

1. 2x + y ≥ 10 → y ≥ -2x + 10
2. 2x + 3y ≥ 20 → y ≥ (-2/3)x + 20/3
3. x + 2y ≥ 15 → y ≥ (-1/2)x + 15/2
4. x, y ≥ 0

Graph:

Corner Points:

1. (0, 10) → Z = 40
2. (0, 7.5) → Z = 30
3. (6, 4) → Z = 36
4. (5, 0) → Z = 15

Optimal Solution: (6, 4) with Z = 36.

4. Special Cases in Graphical LPP

Example: Unbounded Problem

Maximize Z = 2x + y Subject to: x + y ≤ 10 x ≥ 0, y ≥ 0

Graph:

Solution: No maximum Z (unbounded).

5. Comparing Graphical vs. Algebraic Methods

6. Real-World Applications

## In the real world

1. eSewa/Khalti (Digital Payments)

   • Idea: Resource allocation (e.g., optimizing server resources to handle peak transaction volumes).
   • How: LPP models how many servers (x) and load balancers (y) to deploy to minimize cost while meeting transaction limits.
   • Worked Example: eSewa’s server team uses LPP to allocate 100 servers (x) and 50 load balancers (y) to handle 500,000 transactions/day, minimizing cost Z = 200x + 150y under constraints like:
     • 3x + 2y ≥ 500 (transactions/hr)
     • x ≤ 120 (server limit)
     • y ≤ 60 (load balancer limit).

2. Daraz (E-commerce Logistics)

   • Idea: Inventory management (balancing stock levels for products).
   • How: LPP helps Daraz decide how many units of Product A (x) and Product B (y) to stock in warehouses to maximize profit Z = 50x + 30y while meeting demand constraints (e.g., 2x + y ≥ 1000 units/week).

3. NTC/Ncell (Network Optimization)

   • Idea: Bandwidth allocation (assigning data speeds to users).
   • How: LPP optimizes how much bandwidth (x) to allocate to voice calls and (y) to data, maximizing user satisfaction Z = 4x + 6y under constraints like:
     • x + y ≤ 1000 (total bandwidth)
     • 2x + y ≥ 800 (voice priority).

7. Worked Example: Daraz Order Fulfillment

Problem: Daraz has two warehouses (W1, W2) to fulfill orders for Product X and Y. Each order for X requires 1 unit of W1 and 2 units of W2; Y requires 2 units of W1 and 1 unit of W2. Maximize profit Z = 10X + 15Y under:

• W1 ≤ 100 units/day.
• W2 ≤ 120 units/day.

Formulation: Maximize Z = 10X + 15Y Subject to: X + 2Y ≤ 100 (W1 constraint) 2X + Y ≤ 120 (W2 constraint) X, Y ≥ 0

Graphical Solution:

Solution: Order 40X and 30Y for maximum profit Rs. 900/day.

8. Exam Tips

1. Always check for feasibility: If no feasible region exists, state "No solution."
2. Plot constraints carefully: Use dashed lines for "≤" and solid for "≥"; shade correctly.
3. Test corner points systematically: Start with intercepts (x=0, y=0) then move to intersections.
4. Label axes clearly: Include units (e.g., "Units of Product P").
5. For unbounded problems: Show the feasible region extends infinitely in the direction of the objective function.
6. Interpret results: State the optimal values of variables and the objective function’s value.

9. Common Mistakes to Avoid

• Ignoring non-negativity: Forgetting x, y ≥ 0 can lead to invalid solutions.
• Misplotting inequalities: Shading the wrong side of a constraint line.
• Incorrect corner points: Missing intersections or miscalculating them.
• Assuming non-corner points are optimal: Only corner points yield optimal solutions in LPP.

10. Practice Problems (From Past Exams)

1. Food Company Problem: Solve graphically for a company producing foods P, Q, R with vitamins A, B, C. Constraints:

   • P: 2A, 2B, 1C
   • Q: 1A, 3B, 2C
   • R: 3A, 1B, 1C
   • Daily demand: ≥10A, ≥20B, ≥15C
   • Maximize profit Z = 5P + 4Q + 3R.

2. Motorcycle Bidding (Dominance Rule): A company bids on 4 motorbikes. Use dominance to eliminate suboptimal bids.

3. Hungarian Assignment Method: Assign 3 jobs to 3 machines with cost matrix:

   Jobs\Machines | A   | B   | C
   --------------|-----|-----|----
   X             | 4   | 6   | 8
   Y             | 2   | 3   | 4
   Z             | 4   | 8   | 5
   

   Find the optimal assignment.

Final Note

Graphical LPP is a foundation for more complex methods like the Simplex algorithm. Mastering it helps visualize optimization problems and build intuition for real-world applications like resource allocation, logistics, and financial planning. Always plot constraints accurately and test corner points—this is the key to solving graphical LPPs correctly.