Linear Programming

Hey students! 👋 Welcome to one of the most practical and exciting topics in AS-level Further Mathematics - Linear Programming! This lesson will teach you how to solve real-world optimization problems using mathematical techniques. By the end of this lesson, you'll understand how to formulate linear programming problems, solve them graphically, and interpret the results to make optimal decisions. Whether it's maximizing profits, minimizing costs, or finding the best allocation of resources, linear programming is your mathematical toolkit for making smart choices! 🎯

Understanding Linear Programming Fundamentals

Linear programming (LP) is a mathematical method used to find the best possible outcome in a mathematical model with linear relationships. Think of it as finding the "sweet spot" where you get the maximum benefit or minimum cost while staying within your limits.

The key components of any linear programming problem are:

Objective Function: This is what you want to optimize (maximize or minimize). For example, if you're running a bakery, your objective might be to maximize profit: $P = 5x + 3y$, where $x$ represents the number of chocolate cakes and $y$ represents the number of vanilla cakes you produce.

Decision Variables: These are the quantities you can control and want to find optimal values for. In our bakery example, $x$ and $y$ are decision variables representing the number of each type of cake.

Constraints: These are the limitations or restrictions you must work within. Your bakery might have limited ingredients, oven time, or storage space. For instance:

• Flour constraint: $2x + y \leq 100$ (you only have 100kg of flour)
• Time constraint: $x + 2y \leq 80$ (you have 80 hours available)
• Non-negativity: $x \geq 0, y \geq 0$ (you can't produce negative cakes!)

Real-world applications are everywhere! Airlines use linear programming to optimize flight schedules and crew assignments. Manufacturing companies use it to determine the optimal product mix. Even your favorite streaming service uses similar techniques to recommend content! 📱

Formulating Linear Programming Problems

The art of formulating LP problems lies in translating real-world situations into mathematical language. Let's work through a comprehensive example that you might encounter in your exams.

Example: The Furniture Factory Problem

Imagine you're managing a furniture factory that produces tables and chairs. Each table generates £40 profit, and each chair generates £30 profit. You want to maximize your weekly profit, but you face several constraints:

1. Labor constraint: Each table requires 4 hours to make, each chair requires 2 hours, and you have 120 hours of labor available per week
2. Material constraint: Each table uses 3 units of wood, each chair uses 1 unit, and you have 60 units of wood available
3. Demand constraint: You can sell at most 25 tables per week
4. Non-negativity: You can't produce negative furniture!

Let's define our variables:

• Let $x$ = number of tables produced per week
• Let $y$ = number of chairs produced per week

Objective Function: Maximize $Z = 40x + 30y$ (total profit)

Constraints:

• Labor: $4x + 2y \leq 120$
• Material: $3x + y \leq 60$
• Demand: $x \leq 25$
• Non-negativity: $x \geq 0, y \geq 0$

This systematic approach works for any LP problem: identify what you're optimizing, define your variables clearly, and translate each limitation into a mathematical inequality. Remember, the word "linear" means all relationships are straight lines - no squares, cubes, or other fancy powers! 📐

Graphical Solution Methods

The graphical method is your visual gateway to understanding linear programming! This method works perfectly for problems with two variables and gives you incredible insight into how the solution process works.

Step 1: Plot the Constraints

Start by treating each constraint as an equation and plotting it as a line. For our furniture factory:

• Labor constraint: $4x + 2y = 120$ becomes the line $y = 60 - 2x$
• Material constraint: $3x + y = 60$ becomes the line $y = 60 - 3x$
• Demand constraint: $x = 25$ is a vertical line

Step 2: Identify the Feasible Region

The feasible region is the area where ALL constraints are satisfied simultaneously. It's like finding the overlap of all your limitations. This region is always a polygon (or unbounded area) with straight edges, because linear constraints create straight boundaries.

For our example, you'll shade the area that satisfies:

• Below or on the labor line (because $4x + 2y \leq 120$)
• Below or on the material line (because $3x + y \leq 60$)
• Left of or on the demand line (because $x \leq 25$)
• In the first quadrant (because $x, y \geq 0$)

Step 3: Apply the Corner Point Theorem

Here's the magic! 🎩 The Corner Point Theorem states that the optimal solution to a linear programming problem will always occur at a corner point (vertex) of the feasible region. This means you don't need to check every point in the region - just the corners!

Why does this work? Imagine the objective function as a series of parallel lines moving across the feasible region. The last point these lines touch before leaving the region is always a corner point.

Corner-Point Analysis and Optimization

Now comes the systematic part - finding and evaluating all corner points! This is where your algebraic skills shine. ✨

Finding Corner Points

Corner points occur where constraint lines intersect. For our furniture factory, we need to find intersections of:

1. Labor and Material constraints: Solve $4x + 2y = 120$ and $3x + y = 60$ simultaneously

• From the second equation: $y = 60 - 3x$
• Substitute into first: $4x + 2(60 - 3x) = 120$
• Simplify: $4x + 120 - 6x = 120$, so $-2x = 0$, therefore $x = 0$
• Then $y = 60 - 3(0) = 60$
• Corner point: $(0, 60)$

1. Material and Demand constraints: Solve $3x + y = 60$ and $x = 25$

• Substitute $x = 25$: $3(25) + y = 60$
• So $y = 60 - 75 = -15$
• This gives $(25, -15)$, but since $y \geq 0$, this point is outside our feasible region

Continue this process for all possible intersections, including intersections with the axes.

Evaluating Corner Points

Once you have all feasible corner points, substitute each into your objective function. The point giving the highest value (for maximization) or lowest value (for minimization) is your optimal solution!

Let's say our corner points are $(0, 0)$, $(0, 60)$, $(15, 15)$, and $(20, 0)$:

• At $(0, 0)$: $Z = 40(0) + 30(0) = £0$
• At $(0, 60)$: $Z = 40(0) + 30(60) = £1800$
• At $(15, 15)$: $Z = 40(15) + 30(15) = £1050$
• At $(20, 0)$: $Z = 40(20) + 30(0) = £800$

The optimal solution is $(0, 60)$ with a maximum profit of £1800! 💰

Interpreting Optimal Solutions and Constraints

Understanding what your solution means in the real world is just as important as finding it mathematically! Let's dive deep into interpretation.

Active vs. Inactive Constraints

An active constraint is one where the optimal solution lies exactly on the constraint line - meaning you're using all available resources. An inactive constraint has some slack - you're not fully utilizing that resource.

In our optimal solution $(0, 60)$:

• Labor constraint: $4(0) + 2(60) = 120$ ✓ (Active - using all 120 hours)
• Material constraint: $3(0) + 60 = 60$ ✓ (Active - using all 60 units of wood)
• Demand constraint: $0 \leq 25$ ✓ (Inactive - could produce more tables if other resources allowed)

Sensitivity Analysis

What happens if your constraints change slightly? This is crucial for business planning! If you could get 10 more hours of labor, would it improve your profit? The answer depends on whether labor is currently an active constraint.

Shadow Prices

The shadow price of a constraint tells you how much your objective function would improve if you relaxed that constraint by one unit. For active constraints, shadow prices are positive; for inactive constraints, they're zero.

Practical Interpretation

Our solution $(0, 60)$ means: produce 0 tables and 60 chairs for maximum profit of £1800. But wait - this might not make business sense! You might want to produce some tables for market diversity, customer satisfaction, or long-term strategy. Linear programming gives you the mathematical optimum, but you must consider practical business factors too! 🤔

Conclusion

Linear programming is your mathematical superpower for solving optimization problems! We've learned how to formulate real-world problems by identifying objective functions, decision variables, and constraints. The graphical method provides visual insight, while corner-point analysis gives us the systematic approach to find optimal solutions. Remember that the optimal solution always occurs at a corner point of the feasible region, and interpreting results requires both mathematical understanding and practical business sense. These skills will serve you well not only in your AS-level Further Mathematics exams but also in future studies and career decisions where optimization matters!

Study Notes

• Linear Programming Components: Objective function (what to optimize), decision variables (what to control), constraints (limitations), non-negativity conditions

• Objective Function: Mathematical expression to maximize or minimize, written as $Z = ax + by$ for two variables

• Constraints: Linear inequalities representing limitations, typically in the form $ax + by \leq c$ or $ax + by \geq c$

• Feasible Region: Area on graph where all constraints are satisfied simultaneously; always forms a polygon with straight edges

• Corner Point Theorem: Optimal solution always occurs at a vertex (corner point) of the feasible region

• Graphical Method Steps: (1) Plot constraint lines, (2) Identify feasible region, (3) Find corner points, (4) Evaluate objective function at each corner point

• Finding Corner Points: Solve systems of equations where constraint lines intersect; check that points satisfy all constraints

• Active Constraint: Constraint where optimal solution lies exactly on the constraint line (fully utilized resource)

• Inactive Constraint: Constraint with slack; optimal solution is inside the constraint boundary (underutilized resource)

• Shadow Price: Amount objective function improves per unit increase in a constraint's right-hand side value

• Sensitivity Analysis: Study of how changes in constraints affect the optimal solution

• Standard Form: Maximize/minimize $Z = c_1x_1 + c_2x_2$ subject to linear constraints and $x_1, x_2 \geq 0$