# What Is Linear Programming? Definition, Model and Example

What is linear programming? It is a method for finding the best possible value of a linear objective function when your choices are limited by linear constraints. You write the goal as an equation, write each limit as an inequality, and then find the point that satisfies every limit while giving the best objective value.

## Quick Answer

- Linear programming (LP) finds the maximum or minimum of a linear function subject to linear constraints [1].
- The function you optimize is the objective function, such as $z = 40x + 30y$.
- The limits on the variables are constraints, such as $2x + y \le 100$ [2].
- The set of all points satisfying the constraints is the feasible region, and the best value occurs at a corner of it [3].
- Variables are usually required to be non-negative, so $x \ge 0$ and $y \ge 0$ [2].

## What Linear Programming Means

In plain terms, linear programming is a way to make the best decision when resources are limited. You have some quantity to maximize, like profit or output, or to minimize, like cost or time. You also have rules that cap how much you can do, like machine hours, labor hours, or budget. If the goal and every rule can be written as straight-line equations, the problem is a linear program [1].

The precise definition: linear programming, sometimes called linear optimization, is the problem of maximizing or minimizing a linear function over a convex polyhedron specified by linear and non-negativity constraints [2]. A convex polyhedron is the shape you get when you intersect several half-planes. In two variables it is a flat polygon. In more variables it is a higher-dimensional solid with flat faces.

The word "programming" here does not mean writing computer code. It comes from an older use of "program" meaning a plan or schedule. The field grew out of operations research after the Second World War, when planners needed to allocate scarce resources across competing activities [1].

## How It Works

A linear program has three parts: an objective function, a set of constraints, and non-negativity conditions. The standard maximization form is:

$$
\text{maximize } z = c_1 x_1 + c_2 x_2 + \dots + c_n x_n
$$

subject to

$$
a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \le b_1
$$
$$
a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \le b_2
$$
$$
x_1 \ge 0, \; x_2 \ge 0, \; \dots, \; x_n \ge 0
$$

Each symbol has a job:

- $z$ is the objective value you want to make as large as possible.
- $x_1, x_2, \dots, x_n$ are the decision variables, the amounts you choose.
- $c_1, c_2, \dots, c_n$ are the objective coefficients, the value each unit of a variable adds to $z$.
- $a_{ij}$ is how much of resource $i$ one unit of variable $j$ uses.
- $b_i$ is the total amount available of resource $i$.
- The inequalities are the constraints, and the non-negativity lines stop variables from going below zero [1][2].

The feasible region is every point that satisfies all constraints at once. For a linear objective over a convex polyhedron, the best value is always found at a corner (a vertex) of that region, or along an edge connecting two equally good corners [3]. That fact is why you can solve small two-variable problems by testing corners instead of searching the whole area.

## Worked Example

Suppose a small factory makes two products, X and Y. Each unit of X earns \$40 and each unit of Y earns \$30. Machine time is limited to 100 hours per week, and each unit of X uses 2 hours while each unit of Y uses 1 hour. Labor is limited to 80 hours per week, and each unit of either product uses 1 hour. The factory wants the production mix that maximizes weekly profit.

Here is a week of the factory's production log, in illustrative units.

| day | units_x | units_y |
| --- | --- | --- |
| Mon | 10 | 20 |
| Tue | 15 | 18 |
| Wed | 20 | 15 |
| Thu | 25 | 12 |
| Fri | 30 | 10 |
| Sat | 22 | 14 |
| Sun | 18 | 16 |

The model is built from the goal and the two limits.

- Objective function: maximize $z = 40x + 30y$
- Constraint 1 (machine hours): $2x + y \le 100$
- Constraint 2 (labor hours): $x + y \le 80$
- Non-negativity: $x \ge 0, \; y \ge 0$

The feasible region is the polygon bounded by those two lines and the two axes. Its corners are where the boundary lines meet. Testing each corner gives the objective value:

| Corner $(x, y)$ | Objective value $z = 40x + 30y$ |
| --- | --- |
| $(0, 0)$ | $40(0) + 30(0) = 0.0000$ |
| $(50, 0)$ | $40(50) + 30(0) = 2000.0000$ |
| $(20, 60)$ | $40(20) + 30(60) = 2600.0000$ |
| $(0, 80)$ | $40(0) + 30(80) = 2400.0000$ |

The largest value is $z = 2600.0000$ at the corner $(20, 60)$. So the optimal solution is $x = 20.0000$, $y = 60.0000$, with a maximum profit of $2600.0000$.

Both constraints are tight at this point. Constraint 1 slack is 0 and constraint 2 slack is 0, which means the factory uses all 100 machine hours and all 80 labor hours. Check it: $2(20) + 60 = 100$ and $20 + 60 = 80$.

You can confirm the same answer with a few lines of Python using SciPy.

```python
from scipy.optimize import linprog
import numpy as np
c = [-40, -30]
A = [[2, 1], [1, 1]]
b = [100, 80]
res = linprog(c, A_ub=A, b_ub=b, bounds=[(0, None), (0, None)])
print(f"x = {res.x[0]:.4f}, y = {res.x[1]:.4f}, max profit = {-res.fun:.4f}")
```

Output:

```text
x = 20.0000, y = 60.0000, max profit = 2600.0000
```

The solver minimizes by default, so the objective coefficients are negated. Minimizing $-40x - 30y$ is the same as maximizing $40x + 30y$.

## How to Interpret It

Read the optimal solution as a plan, not a prediction. The value $x = 20$ and $y = 60$ means that if the factory follows this mix, it earns the most profit the constraints allow. It does not promise that profit will appear, because the model assumes the per-unit values and resource limits hold exactly.

The slack values tell you which resources are fully used. A slack of 0 means the constraint is binding, so that resource is exhausted. A positive slack means you have room left. In the example, both constraints are binding, so adding machine hours or labor hours could raise the maximum profit. If a constraint had slack, loosening it would change nothing.

The objective value is the best achievable under the stated rules. If the real world differs from those rules, the number is only as good as the model.

## When to Use It (and when not to)

Use linear programming when your goal and limits are linear, your variables can take fractional values, and you can state the constraints clearly. It fits production planning, transportation and routing, scheduling, and product mix decisions [4]. Airlines use it to schedule flights and staff, delivery services use it to route shipments, and retailers use it to plan orders and deliveries [4].

Do not use it when the goal or a constraint is curved, when a small change in one variable causes a jump in another, or when the answer must be a whole number and rounding a fractional answer would break a constraint. If variables must be integers, the problem becomes an integer linear program, which can be much harder to solve [1]. Also avoid it when the coefficients are guesses with wide error bars, because the optimal corner can shift when the inputs shift.

## Linear Programming vs Linear Regression

These two are easy to confuse because both use linear equations. They answer different questions.

| Feature | Linear programming | Linear regression |
| --- | --- | --- |
| Purpose | Find the best decision under limits | Describe the relationship in data |
| Direction | Optimize an objective | Fit a line to observed points |
| Inputs | Constraints and coefficients you set | Observed data pairs |
| Output | Optimal variable values | Slope, intercept, fit statistics |
| Typical use | Resource allocation, scheduling | Prediction, trend estimation |

Linear programming prescribes what you should do. Linear regression describes what the data shows.

## Common Mistakes

- Forgetting non-negativity. If you leave out $x \ge 0$ and $y \ge 0$, the solver may return negative production, which is meaningless. Add the non-negativity constraints every time.
- Testing only interior points. The optimum sits at a corner of the feasible region, so test the vertices, not random points inside [3].
- Mixing up maximization and minimization. Solvers like SciPy's `linprog` minimize by default, so negate the objective coefficients when you want a maximum.
- Writing a constraint in the wrong direction. A limit on available hours is an upper bound, so it uses $\le$. A requirement to meet a minimum uses $\ge$.
- Ignoring units. Machine hours, labor hours, and dollars must stay consistent, or the coefficients will not mean what you think.
- Assuming the answer is unique. When the objective is parallel to a constraint edge, every point on that edge can be optimal, so more than one plan may tie.

## Limitations

Linear programming cannot handle curved relationships, and it assumes every coefficient is known exactly. In real problems, costs, prices, and capacities are estimates. A small change in one coefficient can move the optimal corner to a different vertex, so the answer can look precise while resting on shaky inputs.

It also assumes divisibility. If you must produce whole units, a fractional optimum like $x = 20.5$ is not usable, and simply rounding can violate a constraint. Integer and mixed-integer versions exist, but they are harder to solve and can take far longer [1]. Finally, a linear program has no way to express risk, uncertainty, or fairness. It optimizes one number, so anything you care about but did not put in the objective is ignored.

## Frequently Asked Questions

### What is linear programming in simple words?

It is a method for making the best choice when you have a goal and limited resources. You write the goal as a linear equation, write each limit as a linear inequality, and find the values that give the best result while respecting every limit [1].

### What is the objective function in linear programming?

The objective function is the quantity you want to maximize or minimize, written as a linear combination of the decision variables, such as $z = 40x + 30y$ [1]. Its coefficients say how much each unit of a variable contributes to the goal.

### What is the difference between the objective function and constraints?

The objective function is what you want to improve. Constraints are the rules that restrict your choices, such as $2x + y \le 100$ [2]. You optimize the objective while satisfying all constraints at once.

### Why is the optimal solution always at a corner?

For a linear objective over a convex polyhedron, the best value occurs at a vertex of the feasible region, or along an edge between two equally good vertices [3]. This is why testing corners solves small two-variable problems.

### Can linear programming handle whole-number answers?

Not directly. Standard linear programming allows fractional values. When variables must be integers, the problem becomes an integer linear program, which can be much harder to solve [1].

## References

1. [26](https://math.mit.edu/~djk/18.310/18.310F04/26and27.html)
2. [Linear Programming -- from Wolfram MathWorld](https://mathworld.wolfram.com/LinearProgramming.html)
3. [7.1: Introduction to Linear Programming (Maximization) - Mathematics LibreTexts](https://math.libretexts.org/Courses/Angelo_State_University/Finite_Mathematics/07%3A_Systems_of_Inequalities_and_Linear_Programming/7.01%3A_Introduction_to_Linear_Programming_(Maximization))
4. [6.4.1: Introduction to Linear Programming Applications in Business, Finance, Medicine, and Social Science - Statistics LibreTexts](https://stats.libretexts.org/Sandboxes/JolieGreen/Finite_Mathematics_-_June_2022/06%3A_Linear_Programming_-_A_Geometric_Approach/6.04%3A_Linear_Programming_-_The_Simplex_Method/6.4.01%3A_Introduction_to_Linear_Programming_Applications_in_Business_Finance_Medicine_and_Social_Science)

## Further Reading

- [Wilson G, Bryan J, Cranston K et al. (2017). Good enough practices in scientific computing. PLOS Computational Biology](https://doi.org/10.1371/journal.pcbi.1005510)
- [Wilkinson MD, Dumontier M, Aalbersberg IJ et al. (2016). The FAIR Guiding Principles for scientific data management and stewardship. Scientific Data](https://doi.org/10.1038/sdata.2016.18)

## Related Articles

- [What Is Data Granularity? Definition and Examples](/blog/data-analysis/data-granularity-definition-examples)
- [Accuracy vs Precision: Differences and Examples](/blog/data-analysis/accuracy-vs-precision-differences-examples)
- [Observation Definition in Statistics: What Counts as Data](/blog/data-analysis/observation-definition-statistics)
- [What Is Causation? Definition and Examples](/blog/data-analysis/what-is-causation-definition-examples)
- [Spurious Correlation: Definition, Examples and How to Spot It](/blog/data-analysis/spurious-correlation-definition-examples)