Further Mathematics | Linear programming

Welcome to Linear Programming: Making Optimal Decisions!

Hello there! Linear Programming (LP) is one of the most practical and exciting areas of Decision Mathematics. It’s all about finding the best possible outcome—usually maximizing profit or minimizing cost—given a set of limitations (constraints).

In this chapter, we will learn how to translate real-world problems into mathematical models and solve them graphically. Don't worry if the term "programming" sounds intimidating; here, it just means planning or scheduling. We are essentially using geometry to solve optimization problems!

SECTION CONTEXT: This topic forms a core part of Unit D1: Decision Mathematics 1.

---

1. Foundations of Linear Programming

What is Optimization?

In D1, optimization means finding the maximum or minimum value of something. Linear Programming provides a systematic way to do this when all relationships involved are linear (straight lines).

The Three Essential Components of an LP Problem

Every Linear Programming problem must have three things:

1. Decision Variables: These are the quantities we are trying to determine. They are usually represented by \(x\) and \(y\).
   Example: The number of Type A chairs (\(x\)) and Type B tables (\(y\)) a factory should produce.
2. Objective Function: This is the formula we want to maximize (e.g., Profit, Revenue) or minimize (e.g., Cost, Time). It must be a linear equation in terms of the decision variables.
3. Constraints: These are the limitations or restrictions on the resources available. They are expressed as linear inequalities.
   Example: The total time available for assembly cannot exceed 100 hours: \(2x + 5y \le 100\).

---

2. Formulating the Linear Programming Problem

The first step in solving any LP problem is translating the words into mathematical language. This is often the trickiest part, so follow these steps carefully.

Step-by-Step Formulation Guide

1. Define the Decision Variables

Clearly state what \(x\) and \(y\) represent. Be specific, including units if necessary.

Example: Let \(x\) be the number of large bags produced, and \(y\) be the number of small bags produced.

2. State the Objective Function

Identify whether the goal is Maximization (Max) or Minimization (Min). Write the formula for the quantity being optimized, often called \(P\) (for Profit) or \(C\) (for Cost).

Example: If profit is $5 per large bag (\(x\)) and $3 per small bag (\(y\)), the objective function is:

$$\text{Maximize } P = 5x + 3y$$

3. Establish the Constraints (Inequalities)

Identify every restriction imposed by the problem (time, materials, capacity, etc.).

• Inequality Direction Check:
  • "Cannot exceed," "at most," "maximum," or "limited to" means \(\le\) (Less than or Equal to).
  • "At least," "must be greater than," or "minimum" means \(\ge\) (Greater than or Equal to).
  • If something must be exactly a certain value, use \(=\) (though these are rare in D1 graphical problems).
• Non-Negativity Constraints: Since you cannot produce a negative number of items, always include: $$\mathbf{x \ge 0 \quad \text{and} \quad y \ge 0}$$

  (These constraints are crucial and define the first quadrant of your graph.)

Key Takeaway from Formulation

Breathe and translate: Read the problem carefully, assign variables, write the goal (Objective), and list the limitations (Constraints). If you get the formulation right, the graphical part is easier!

---

3. The Graphical Solution: Finding the Feasible Region

Once formulated, the problem must be solved using a graph. Since we are dealing with two variables (\(x\) and \(y\)), we can use a 2D coordinate plane.

Step 1: Plotting the Constraint Lines

To plot an inequality (e.g., \(2x + y \le 10\)), we first treat it as an equation to draw the boundary line:

$$\mathbf{2x + y = 10}$$

• Find the intercepts:
  • Set \(x=0\) to find the y-intercept. (Here: \(y=10\). Point \((0, 10)\))
  • Set \(y=0\) to find the x-intercept. (Here: \(2x=10\), so \(x=5\). Point \((5, 0)\))
• Draw a straight line connecting these intercepts.

Step 2: Identifying the Feasible Region (R)

The Feasible Region (R) is the area on the graph where ALL constraints are simultaneously satisfied. We need to determine which side of the line represents the inequality.

The Test Point Method:

1. Choose a test point, usually the origin \((0, 0)\), unless the line passes through it.
2. Substitute \((0, 0)\) into the original inequality.
3. If the inequality is True (e.g., \(0 \le 10\)), then the feasible region lies on the side containing \((0, 0)\).
4. If the inequality is False (e.g., \(0 \ge 10\) is False), then the feasible region lies on the opposite side.

Shading Convention: In Decision Mathematics, it is standard practice to shade the region you DO NOT want (the infeasible region). This leaves the feasible region (R) clear and unshaded, often a polygon defined by the intersecting lines.

Remember to include the constraints \(x \ge 0\) (shading left of the y-axis) and \(y \ge 0\) (shading below the x-axis).

Key Takeaway from Feasible Region

The feasible region (R) is the only area on the graph where a valid solution can exist. The boundaries of R are the constraint lines.

---

4. Finding the Optimal Solution

The Fundamental Theorem of Linear Programming states that the optimal solution (Maximum or Minimum) will always occur at one of the vertices (corner points) of the feasible region R.

We have two main methods to find this optimum:

Method A: The Objective Line Method (Search Line)

This method involves plotting the objective function and moving it across the feasible region.

Step 1: Determine the Gradient of the Objective Function

Let the objective function be \(P = ax + by\). To plot this as a line, we set \(P\) to a convenient constant value, \(k\):

$$ax + by = k$$

Rearrange this into the form \(y = mx + c\) to find the gradient (\(m\)).

$$by = -ax + k \quad \implies \quad y = -\frac{a}{b}x + \frac{k}{b}$$

The gradient of the objective line is \(m = -\frac{a}{b}\).

Step 2: Draw the Objective Line

Choose a value for \(k\) that makes the intercepts easy to plot (e.g., if \(P = 3x + 2y\), choose \(k=6\), giving \(3x + 2y = 6\)). Draw this line. This is your Search Line.

Step 3: Slide the Line

• Use a ruler parallel to your search line.
• If you are Maximizing, slide the ruler as far as possible away from the origin while still touching the feasible region R.
• If you are Minimizing, slide the ruler as close as possible to the origin while still touching the feasible region R.

Step 4: Identify the Optimal Vertex

The last point the ruler touches (either a single corner point or an entire edge) is the optimum.

💭 Memory Aid: When Maximizing, you want the largest possible value of \(P\), so you are maximizing the distance from the origin (where \(P=0\)).

Method B: The Vertex Testing Method (Corner Point Method)

This method is straightforward but requires algebraic accuracy to find the exact coordinates of every vertex.

Step 1: Identify All Vertices (Corner Points)

List the coordinates of every corner point of the feasible region R. Use simultaneous equations to find the exact coordinates of vertices formed by the intersection of two constraint lines.

Example: If vertex V is formed by \(x + 2y = 10\) and \(x + y = 7\), solve these simultaneously to find \((4, 3)\).

Step 2: Substitute into the Objective Function

Test the coordinates of every vertex in the objective function (\(P\) or \(C\)).

Example: If \(P = 5x + 3y\):

• Vertex A \((0, 0)\): \(P = 5(0) + 3(0) = 0\)
• Vertex B \((5, 0)\): \(P = 5(5) + 3(0) = 25\)
• Vertex C \((4, 3)\): \(P = 5(4) + 3(3) = 29\)

Step 3: State the Optimal Solution

Identify the vertex that yields the required Max or Min value.

Example: If maximizing, the optimum is 29, occurring at \((4, 3)\).

---

5. Advanced Interpretation and Special Cases

Case 1: Non-Integer Solutions vs. Integer Solutions

Often, the variables \(x\) and \(y\) must represent discrete items (like cars, people, or packets) and therefore must be integers (whole numbers).

If your mathematically optimal solution (found by Method A or B) is non-integer—for example, Maximum Profit at \((4.2, 3.8)\)—you must check nearby integer points within or on the boundary of the feasible region R.

How to Find the Integer Optimum:

1. Identify the optimal non-integer vertex, \(V\).
2. Look at the surrounding integer coordinates that are closest to \(V\) and are still inside or on the boundary of R.
3. Test these nearby integer points in the objective function.
4. The point yielding the best result is the integer optimal solution.

Important Tip: When moving from a non-integer optimum to an integer point, ensure you move in the direction that decreases the value of the objective function the least (if maximizing), or increases it the least (if minimizing).

Case 2: Multiple Optimal Solutions

If the gradient of the objective function is exactly the same as the gradient of one of the constraint boundaries, then the optimum solution does not occur at a single point, but along that entire edge segment.

In this case, any point on the boundary segment that connects Vertex A and Vertex B will yield the same optimal value.

To answer this in an exam: State the maximum/minimum value, and specify that it occurs at all points on the line segment joining Vertex A to Vertex B (inclusive).

Interpretation and Final Answer

The final step is always to put your mathematical answer back into the context of the original problem.

If your solution is \(x=10, y=5\) and the maximum profit is $120:

Final Answer: The company should produce 10 units of X and 5 units of Y to achieve a maximum profit of $120.