Linear Programming Basics

Every day, businesses, governments, and even individuals face the challenge of making the best possible decisions with limited resources. Whether it's a factory manager scheduling machines, a logistics coordinator planning delivery routes, or a farmer allocating land to crops, the core problem is the same: how to achieve the most favorable outcome given a set of constraints. Linear programming (LP) is the fundamental mathematical framework for solving these types of optimization problems. It provides a systematic way to find the optimal allocation of resources when both the goal and the restrictions can be expressed as linear relationships.

What is Linear Programming?

Linear programming is a mathematical method for determining the best possible outcome—such as maximum profit or lowest cost—in a model whose requirements are represented by linear relationships. More formally, it is a technique for the optimization of a linear objective function, subject to linear equality and inequality constraints. The power of LP lies in its ability to handle complex, multi-variable decision-making problems by translating them into a precise algebraic model that can be solved algorithmically.

Every linear programming model is built from three core components:

1. Decision Variables: These are the unknown quantities you are trying to solve for, typically representing levels of activity (e.g., number of units to produce, acres to plant, hours to schedule). They are usually denoted as $x_1,x_2,...,x_n$.
2. Objective Function: This is a linear equation that defines the goal of the problem, which you aim to either maximize (e.g., profit, revenue) or minimize (e.g., cost, waste). It is expressed as a function of the decision variables, such as $Z=c_1{x}_1+c_2{x}_2$.
3. Constraints: These are a set of linear equations or inequalities that limit the values the decision variables can take. They represent the scarce resources or other restrictions in the problem, like available labor hours, raw materials, or budget caps. Constraints are typically written as $a_1{x}_1+a_2{x}_2\le b$, where $b$ is the resource limit.

Setting Up a Simple Linear Programming Problem

The first and most critical step is translating a word problem into a mathematical model. Let's walk through a classic production planning example.

Scenario: A furniture workshop produces chairs and tables. Each chair yields a profit of \$20 and requires 2 hours of carpentry and 1 hour of finishing. Each table yields a profit of \$30, requiring 1 hour of carpentry and 2 hours of finishing. The workshop has only 100 carpentry hours and 80 finishing hours available per week. How many chairs and tables should be made to maximize profit?

1. Define Decision Variables:

Let $x_1$ = number of chairs to produce per week. Let $x_2$ = number of tables to produce per week.

1. Formulate the Objective Function:

The goal is to maximize total profit. Profit from chairs is $20x_1$ and from tables is $30x_2$. Therefore, Maximize: $Z=20x_1+30x_2$.

1. List the Constraints:

• Carpentry hours constraint: Each chair uses 2 hours, each table uses 1 hour. Total used cannot exceed 100.

$2x_1+1x_2\le 100$

• Finishing hours constraint: Each chair uses 1 hour, each table uses 2 hours. Total used cannot exceed 80.

$1x_1+2x_2\le 80$

• Non-negativity constraints: You cannot produce a negative number of items.

$x_1\ge 0$, $x_2\ge 0$

The complete LP model is: Maximize $Z=20x_1+30x_2$ Subject to: $$\begin{array}{rl}2x_1+x_2& \le 100\\ x_1+2x_2& \le 80\\ x_1,x_2& \ge 0\end{array}$$

The Graphical Solution and Corner Point Principle

For problems with two decision variables, we can find the solution graphically. This method beautifully illustrates the core concepts that underpin how all linear programming solvers work.

1. Plot the Feasible Region: Graph each inequality constraint on the $x_1$-$x_2$ plane. The area where all constraints overlap, including the non-negativity quadrants, is called the feasible region. This region contains every possible combination of chairs and tables ($x_1,x_2$) that satisfies all workshop limitations.

1. Identify Corner Points: The feasible region will be a polygon. The vertices of this polygon are the corner point solutions (or extreme points).

1. Apply the Fundamental Theorem: A key theorem of linear programming states that if an optimal solution exists, it will occur at one of the corner points of the feasible region. If two corner points are both optimal, then every point on the line segment between them is also optimal.

1. Evaluate the Objective Function: To find the optimal solution, calculate the profit $Z$ at each corner point. The corner point that yields the highest value for $Z$ (in a maximization problem) is the optimal solution.

In our furniture example, the corner points might be (0,0), (50,0), (0,40), and the intersection of the two constraint lines. Solving $2x_1+x_2=100$ and $x_1+2x_2=80$ simultaneously gives $x_1=40$, $x_2=20$. Evaluating profit:

• At (0,0): $Z=0$
• At (50,0): $Z=1000$
• At (0,40): $Z=1200$
• At (40,20): $Z=(20\ast 40)+(30\ast 20)=1400$

The maximum profit of \$1400 occurs at the corner point (40, 20). Therefore, the optimal production plan is 40 chairs and 20 tables.

Common Business Applications

Linear programming is not an abstract mathematical exercise; it is a vital tool for operational efficiency.

• Production Planning: As demonstrated, optimizing the product mix to maximize profit or minimize cost given material, labor, and machine time constraints.
• Scheduling: Assigning employees to shifts to meet demand while minimizing labor costs and respecting union rules or worker preferences.
• Resource Allocation: Distributing limited resources (like advertising budget, raw materials, or investment capital) across different projects or departments to achieve the best overall return.
• Transportation & Logistics: Determining the most cost-effective way to transport goods from multiple suppliers to multiple destinations, minimizing total shipping cost.

Common Pitfalls

1. Misidentifying the Objective: Confusing what to maximize with what to constrain. For example, trying to "maximize available hours" is incorrect; you maximize profit subject to the hour constraints. Always ask: "What is the single numeric measure of success?"
2. Ignoring Non-Negativity: Forgetting the $x_1,x_2\ge 0$ constraints is a common oversight. In most real-world contexts, decision variables (like units produced) cannot be negative.
3. Incorrect Inequality Direction: Writing a "greater than" ($\ge$) constraint when you mean "less than" ($\le$). Always re-read the constraint in plain language: "Total hours used must not exceed 100" directly translates to $\le 100$.
4. Assuming Linearity Applies Everywhere: LP requires proportionality and additivity. If producing 10 chairs takes 20 hours, producing 20 must take 40 hours (proportionality). The total profit must be the sum of individual profits (additivity). If these assumptions are violated (e.g., due to volume discounts or interaction effects), a nonlinear model may be needed.

Summary

• Linear programming is a powerful optimization method for problems where the objective and all constraints can be expressed as linear equations or inequalities.
• Every LP model consists of three parts: decision variables, a linear objective function to maximize or minimize, and a set of linear constraints.
• The set of all points satisfying all constraints is the feasible region. The optimal solution, if it exists, is always found at a corner point of this region.
• The graphical solution method provides an intuitive understanding of these principles, which scale to complex, multi-variable problems solved by software algorithms.
• LP has extensive real-world applications in scheduling, production planning, and resource allocation, helping organizations make optimal, data-driven decisions.