Linear Programming: Models, Graphs & Optimization

What is Linear Programming?

Linear programming (LP) is a mathematical technique used to optimize (maximize or minimize) a linear objective function subject to linear constraints. It is widely used in business, economics, and engineering to make optimal decisions under limited resources.

Key Components of LP

1. Objective Function: The function to be maximized or minimized (e.g., profit, cost, time).
2. Decision Variables: Variables representing the quantities to be determined (e.g., number of products to produce).
3. Constraints: Limitations or restrictions on the decision variables (e.g., resource availability, demand).
4. Non-negativity Constraints: Decision variables cannot be negative (e.g., you cannot produce a negative number of products).

---

Why Use Linear Programming?

LP is useful because:

• It provides an optimal solution to complex decision-making problems.
• It is computationally efficient for linear problems.
• It can handle multiple constraints and objectives simultaneously.

---

Formulating LP Problems

Formulating an LP problem involves translating a real-world problem into mathematical terms.

Steps to Formulate an LP Problem

1. Identify the Objective: What do you want to maximize or minimize?
2. Define Decision Variables: What quantities will you decide?
3. Formulate Constraints: What are the limitations?
4. Write the Non-negativity Constraints: Ensure variables are non-negative.

---

Example: Production Planning for a Factory

Problem Statement: A factory produces two products, A and B. Each unit of A requires 2 hours of labor and 1 kg of material, while each unit of B requires 1 hour of labor and 3 kg of material. The factory has 100 hours of labor and 90 kg of material available per week. The profit per unit of A is Rs. 50, and for B, it is Rs. 40. How many units of A and B should be produced to maximize profit?

Step 1: Define Decision Variables

Let:

• $x$ = number of units of product A to produce.
• $y$ = number of units of product B to produce.

Step 2: Formulate the Objective Function

Maximize profit: $$\text{Profit}=50x+40y$$

Step 3: Formulate Constraints

1. Labor constraint: $$2x+y\le 100$$
2. Material constraint: $$x+3y\le 90$$
3. Non-negativity constraints: $$x\ge 0,y\ge 0$$

Step 4: Write the Complete LP Model

$$\text{Maximize }Z=50x+40y$$ Subject to: $$\begin{gathered} 2x+y\le 100 \\ x+3y\le 90 \\ x,y\ge 0 \end{gathered}$$

---

Solving LP Problems Graphically

Graphical methods are used for problems with two decision variables. Here’s how to solve the above problem graphically.

Step 1: Plot the Constraints

1. Labor Constraint: $2x+y=100$
   • When $x=0$, $y=100$.
   • When $y=0$, $x=50$.
2. Material Constraint: $x+3y=90$
   • When $x=0$, $y=30$.
   • When $y=0$, $x=90$.

Step 2: Identify the Feasible Region

The feasible region is the area that satisfies all constraints. It is the shaded area in the graph above.

Step 3: Find the Corner Points

The optimal solution lies at one of the corner points of the feasible region. The corner points are:

1. (0, 0)
2. (0, 30)
3. (30, 20)
4. (50, 0)

Step 4: Evaluate the Objective Function at Each Corner Point

• At (0, 0): $Z=50(0)+40(0)=0$
• At (0, 30): $Z=50(0)+40(30)=1200$
• At (30, 20): $Z=50(30)+40(20)=1500+800=2300$
• At (50, 0): $Z=50(50)+40(0)=2500$

However, (50, 0) does not satisfy the material constraint $x+3y\le 90$. So, the feasible corner points are (0, 0), (0, 30), and (30, 20). The optimal solution is at (30, 20) with a maximum profit of Rs. 2300.

---

The Simplex Method

For problems with more than two variables, the graphical method is not feasible. The simplex method is an algorithmic approach to solve LP problems.

Steps of the Simplex Method

1. Convert Inequalities to Equations: Add slack or surplus variables to convert inequalities into equalities.
2. Set Up the Initial Simplex Tableau: Create a table to represent the constraints and objective function.
3. Identify the Pivot Column: Choose the column with the most negative coefficient in the objective row (for maximization).
4. Identify the Pivot Row: Calculate the ratio of the right-hand side to the pivot column for each positive entry in the constraint rows. Choose the smallest ratio.
5. Perform Row Operations: Use the pivot row and column to update the tableau.
6. Check for Optimality: If there are no negative coefficients in the objective row, the current solution is optimal. Otherwise, repeat steps 3-5.

---

Example: Solving Using Simplex Method

Let’s solve the same problem using the simplex method.

Step 1: Convert Inequalities to Equations

Add slack variables $s_1$ and $s_2$: $$\begin{gathered} 2x+y+s_1=100 \\ x+3y+s_2=90 \end{gathered}$$

Step 2: Set Up the Initial Tableau

The objective function becomes: $$Z-50x-40y=0$$

Initial tableau:

       x    y    s1    s2    RHS
Z-row  -50  -40   0     0     0
s1-row  2    1    1     0    100
s2-row  1    3    0     1     90

Step 3: Identify the Pivot Column and Row

• Pivot column: $y$ (most negative in Z-row).
• Ratios: $100/1=100$, $90/3=30$. Pivot row is the second row.

Step 4: Perform Row Operations

Update the tableau:

       x    y    s1    s2    RHS
Z-row  -50  0    40    0    1200
s1-row  2    0   -1    0    70
s2-row  1    0   -3    1    0

Step 5: Check for Optimality

The Z-row has a negative coefficient for $x$. Repeat the process.

• Pivot column: $x$.
• Ratios: $70/2=35$, $0/1=0$ (ignore). Pivot row is the first row.

Update the tableau:

       x    y    s1    s2    RHS
Z-row  0    0    10    0    1750
s1-row  1    0   -0.5  0    35
s2-row  0    0   -2.5  1   -35

The solution is not feasible (negative RHS for $s_2$). Re-evaluate the pivot row selection.

---

Shadow Prices and Sensitivity Analysis

Shadow prices indicate how much the objective function value would change if the right-hand side of a constraint were increased by one unit. Sensitivity analysis helps understand how changes in the coefficients of the objective function or constraints affect the optimal solution.

Shadow Prices in the Example

From the final tableau, the shadow prices for the constraints are derived from the coefficients of the slack variables in the Z-row. For example, if the labor constraint increases by 1 hour, the profit increases by Rs. 10 (shadow price of $s_1$).

---

Applications of Linear Programming

In the Real World

1. Supply Chain Optimization (Daraz, Amazon)

   • What it uses: LP models to optimize inventory levels, transportation routes, and warehouse locations.
   • How it works: Daraz uses LP to minimize delivery costs while ensuring products are available in all regions. For example, if Daraz has warehouses in Kathmandu, Pokhara, and Biratnagar, LP helps determine how many products to stock in each warehouse to meet demand at the lowest cost.

2. Bank Loan Portfolio (NMB Bank, Global IME)

   • What it uses: LP to maximize profit from loans while managing risk.
   • How it works: Banks allocate funds to different loan types (e.g., personal loans, business loans, mortgages) to maximize interest income. LP ensures the bank stays within regulatory limits (e.g., maximum exposure to a single sector) while optimizing returns. For example, if NMB Bank has Rs. 10 billion to lend, LP helps decide how much to lend to individuals vs. businesses to maximize profit while keeping default risk below 5%.

3. Traffic Management (Kathmandu Metropolitan City)

   • What it uses: LP to optimize traffic signal timings and route planning.
   • How it works: Traffic engineers use LP to minimize congestion by adjusting signal timings or suggesting alternative routes. For instance, during Dashain, when traffic in Kathmandu increases, LP models can suggest rerouting buses and taxis to avoid bottlenecks at Thapathali or Kalanki intersections, reducing travel time by up to 20%.

---

Worked Example: Traffic Light Optimization in Kathmandu

Problem Statement: Kathmandu Metropolitan City wants to optimize traffic light timings at a busy intersection (e.g., Thapathali) to minimize wait times. There are two roads:

• Road 1: Traffic arrives at a rate of 300 vehicles per hour.
• Road 2: Traffic arrives at a rate of 400 vehicles per hour. Each traffic light cycle lasts 60 seconds. The goal is to determine the optimal green light duration for each road to minimize total wait time.

Step 1: Define Decision Variables

Let:

• $x$ = green light duration for Road 1 (in seconds).
• $y$ = green light duration for Road 2 (in seconds).

Step 2: Formulate Constraints

1. Total cycle time: $$x+y\le 60$$
2. Non-negativity: $$x\ge 0,y\ge 0$$

Step 3: Formulate the Objective Function

Minimize total wait time. Assume wait time is proportional to the square of the difference between arrival rate and service rate (a common assumption in queueing theory). The objective function can be approximated as: $$\text{Minimize }Z={\left(\frac{300}{3600}\cdot (60-x)\right)}^2+{\left(\frac{400}{3600}\cdot (60-y)\right)}^2$$ Simplify: $$Z={\left(\frac{1}{12}(60-x)\right)}^2+{\left(\frac{1}{9}(60-y)\right)}^2$$

Step 4: Solve Graphically or Using Simplex

For simplicity, let’s assume we test values of $x$ and $y$ that satisfy $x+y=60$. For example:

• If $x=20$, $y=40$: $$Z={\left(\frac{40}{12}\right)}^2+{\left(\frac{20}{9}\right)}^2\approx 11.11+4.94=16.05$$
• If $x=24$, $y=36$: $$Z={\left(\frac{36}{12}\right)}^2+{\left(\frac{24}{9}\right)}^2=9+7.11=16.11$$

The optimal solution is closer to $x=20$, $y=40$, meaning Road 1 gets 20 seconds of green light, and Road 2 gets 40 seconds. This reduces total wait time by balancing the higher traffic volume on Road 2.

---

Advantages and Disadvantages of LP

Advantages

• Optimal Solutions: Provides the best possible solution given the constraints.
• Flexibility: Can handle a wide range of problems with linear relationships.
• Efficiency: Computationally efficient for large problems.
• Interpretability: Results are easy to understand and implement.

Disadvantages

• Linearity Assumption: Assumes relationships between variables are linear, which may not always be true.
• Complexity: Formulating real-world problems as LP models can be challenging.
• Limited to Linear Problems: Cannot handle non-linear relationships or integer constraints without extensions (e.g., integer programming).

---

Extensions of Linear Programming

1. Integer Programming: Used when decision variables must be integers (e.g., number of machines or workers).
2. Non-linear Programming: Used when the objective function or constraints are non-linear.
3. Stochastic Programming: Used when some parameters are uncertain or probabilistic.

---

Exam Tip

For the exam, focus on the following:

1. Formulation: Be able to translate a word problem into an LP model. Practice with at least 3-4 examples.
2. Graphical Solution: Know how to plot constraints and identify the feasible region. Understand why the optimal solution lies at a corner point.
3. Simplex Method: Understand the steps and be able to set up and solve a tableau. Practice with problems having 2-3 constraints.
4. Shadow Prices: Know how to interpret shadow prices and their significance in decision-making.
5. Applications: Be ready to discuss real-world applications like supply chain optimization, traffic management, or financial planning. Use examples from Nepalese companies (e.g., Daraz, NMB Bank) or global firms (e.g., Amazon, Google).
6. Limitations: Understand the limitations of LP and when other techniques (e.g., non-linear programming) might be more appropriate.

---

Common Mistakes to Avoid

• Incorrect Formulation: Misinterpreting the objective or constraints. Always double-check the signs (≤ or ≥) and units.
• Graphical Errors: Plotting constraints incorrectly. Ensure intercepts are calculated accurately.
• Simplex Errors: Forgetting to update the tableau correctly or misidentifying the pivot row/column.
• Ignoring Non-negativity: Forgetting to include $x,y\ge 0$ constraints.
• Overcomplicating: Stick to the basics. The exam may test your ability to solve standard problems efficiently.

---

Practice Problem

Problem: A company produces two products, P and Q. Each unit of P requires 3 hours of labor and 2 kg of material, while each unit of Q requires 2 hours of labor and 4 kg of material. The company has 120 hours of labor and 160 kg of material available. The profit per unit of P is Rs. 40, and for Q, it is Rs. 60. Formulate the LP model and solve it graphically to find the optimal production quantities.

Solution Steps:

1. Define decision variables: $x$ = units of P, $y$ = units of Q.
2. Formulate the objective function: Maximize $Z=40x+60y$.
3. Formulate constraints:
   • Labor: $3x+2y\le 120$
   • Material: $2x+4y\le 160$
   • Non-negativity: $x,y\ge 0$
4. Plot the constraints and identify the feasible region.
5. Find the corner points and evaluate the objective function at each point.
6. Determine the optimal solution.

---

Visual Summary of LP Process

---

Real-World Picture: LP in Action

---

TAKEAWAYS:

• Linear programming models real-world problems as linear equations and inequalities to find optimal solutions under constraints.
• Graphical methods work for two-variable problems, while the simplex method handles larger problems algorithmically.
• Shadow prices reveal how much the objective value changes with small changes in constraints, aiding sensitivity analysis.
• Applications range from supply chain optimization (Daraz) to traffic management (Kathmandu Metropolitan City) and financial planning (NMB Bank).
• Always verify formulations, plot constraints accurately, and interpret results in the context of the problem.
• Practice is key: master formulation, graphical solutions, and simplex steps to excel in exams.