Linear Programming Problem

Introduction to Linear Programming: Graphical Method and Decision Optimization

Linear Programming (LP) is a powerful mathematical modeling technique used to allocate limited resources in an optimal way. The goal of linear programming is to find the maximum or minimum value of a linear function, called the objective function, subject to a set of linear inequalities called constraints. These constraints represent the limitations of real-world scenarios, such as budget caps, labor hour availability, material shortages, or production capacity. Linear programming is widely taught in economics, business management, and operations research because it provides a scientific approach to decision-making.

Real-World Applications of Linear Programming

Linear programming is utilized daily by large corporations, logistics networks, and agricultural farms. For instance, a manufacturing company uses LP to determine how many units of two different products they should produce to maximize total profit while operating under limited machine hours and raw materials. Shipping companies like FedEx use LP to solve transportation problems, finding the most cost-effective routes to distribute packages from multiple warehouses to different destination cities. Farms use it to create optimal feed mixes for livestock, ensuring animals get required nutrients at the lowest possible cost.

Core Prerequisites

To solve linear programming problems, you should be comfortable with graphing linear equations, finding the intersection point of two lines using simultaneous equations, and shading regions on a graph representing linear inequalities (defining the feasible region).

Solving a Linear Programming Problem (Graphical Method)

The graphical method is used to solve LP problems involving only two variables. Let us solve a maximization problem step-by-step.

Objective Function: Maximize Profit $$P = 3x + 4y$$

Subject to the constraints:

1. \(x + y \le 4\)
2. \(2x + y \le 6\)
3. \(x \ge 0, \quad y \ge 0\) (Non-negativity constraints)

Step 1: Graph the Constraint Inequalities
Treat the inequalities as equations to draw the boundary lines:
Line 1: \(x + y = 4\). Intercepts are \((4,0)\) and \((0,4)\).
Line 2: \(2x + y = 6\). Intercepts are \((3,0)\) and \((0,6)\).

Step 2: Identify the Feasible Region
The feasible region is the area on the graph that satisfies all inequalities simultaneously. Since the inequalities are "less than or equal to" (\(\le\)), we shade the region towards the origin \((0,0)\). The boundaries of this shaded area are constrained by the axes (\(x \ge 0\), \(y \ge 0\)).

Step 3: Find the Corner Points (Vertices) of the Feasible Region
According to the Corner Point Theorem, the optimal solution (maximum or minimum) always occurs at one of the corner points of the feasible region. Let us list the vertices of our shaded region:
A: \((0,0)\) (the origin)
B: \((3,0)\) (\(x\)-intercept of Line 2)
C: \((0,4)\) (\(y\)-intercept of Line 1)
D: The intersection of Line 1 and Line 2. Solve the simultaneous equations: subtract the equations \((2x + y = 6) - (x + y = 4) \Rightarrow x = 2\). Substitute \(x\) into Line 1: \(2 + y = 4 \Rightarrow y = 2\). So the intersection point is \((2,2)\).

Step 4: Evaluate the Objective Function at Each Corner Point
We plug the coordinates of each vertex into our profit equation \(P = 3x + 4y\):

• At A\((0,0)\): \(P = 3(0) + 4(0) = 0\)
• At B\((3,0)\): \(P = 3(3) + 4(0) = 9\)
• At C\((0,4)\): \(P = 3(0) + 4(4) = 16\)
• At D\((2,2)\): \(P = 3(2) + 4(2) = 6 + 8 = 14\)

Step 5: Identify the Optimal Solution
The maximum value of \(P\) is 16, which occurs at the corner point C\((0,4)\). Therefore, to maximize profit under these constraints, we should set \(x = 0\) and \(y = 4\).

Common Student Errors

A frequent mistake is shading the wrong side of the constraint boundary lines. Always use a test point, like \((0,0)\), to check which side of the line to shade. Another error is miscalculating the coordinates of the intersection point due to simple arithmetic mistakes when solving the simultaneous equations.

Study Hack & Mnemonic: The Bound Polygon Rule

Think of the feasible region as a walled-in garden (a polygon). The corner points are the fence posts. The objective function is a sweeping line that moves across the garden. The maximum or minimum value will always occur as the line hits the very last fence post before leaving the garden. Therefore, you don't need to check the infinite points inside the garden; you only need to evaluate the coordinates of the corner fence posts!

Conclusion

Linear programming provides a systematic way to make optimal choices under resource limitations. By graphing linear inequalities, finding the feasible region, and testing its corner points, you can solve basic business optimization problems with mathematical certainty.