Does linear programming mean computer programming?

No. It names a mathematical optimization framework, although software is commonly used to solve it.

Can an LP return fractional quantities?

Yes. Standard LP variables are continuous unless additional integrality requirements are imposed.

Does a solver always find a usable plan?

No. The model may be infeasible, unbounded, numerically problematic, or missing requirements needed in practice.

AI Glossary / Mathematics and optimization / Intermediate

Linear programming

Definition

Linear programming is optimization of a linear objective subject to linear equality and inequality constraints. The decision variables are ordinarily continuous, allowing fractional values within their bounds. It provides a mathematical way to choose among feasible plans, such as allocating limited resources while maximizing a specified benefit or minimizing cost.

What it means

Programming here means planning or optimization, not simply writing software. A linear program, or LP, combines decision variables, an objective, and constraints into one model. The coefficients describe how each decision contributes to the objective and uses constrained resources.
Linearity means contributions add and scale proportionally within the model. If one unit uses two hours, three units use six hours, with no modeled setup effect or quantity-dependent rate. Whether that approximation is reasonable depends on the setting.
An LP finds the best feasible solution to the stated model. It does not discover missing constraints, establish that input estimates are accurate, or decide which business objective ought to matter. Those choices remain part of modeling and review.

How it works

Define a vector x of decision variables. A common form minimizes cᵀx subject to Ax≤b, Ex=d, and lower and upper variable bounds. Maximization can be expressed by negating the objective. Linear constraints define a convex feasible region.
Algorithms such as simplex and interior-point methods exploit this structure. A problem can have an optimum, be infeasible because no decision satisfies all constraints, or be unbounded in the improving objective direction. These outcomes mean different things and require different interpretations.
Dual variables can provide bounds and sensitivity information. Their economic interpretation depends on the formulation and on the range over which the relevant solution structure remains valid. Requiring some variables to be integers produces a mixed-integer or integer optimization problem, even when its objective and constraints remain linear.

Three practical examples

A production model can allocate divisible material across products while respecting capacity constraints.
A transport model can distribute flows across routes to meet supply and demand at minimum modeled cost.
A blending model can choose ingredient quantities that satisfy linear composition requirements and quantity limits.

Think of it this way

Think of choosing a combination from a region of allowed plans while moving a straight scoring rule as far as possible in the preferred direction. The analogy helps visualize two variables, but real models can have thousands of dimensions. The allowed region also depends entirely on the constraints included in the model.

Worked example

Consider an original planning example with nonnegative quantities x and y. Maximize the benefit 3x+2y subject to x+y≤4 and 2x+y≤6. The first constraint represents one resource and the second another, in explicitly chosen compatible units.
The feasible corner points are (0,0), (0,4), (3,0), and (2,2). Their objective values are 0, 8, 9, and 10. The point (2,2) uses both resources fully and gives benefit 10.
We can verify global optimality without relying only on the corner list. Add the two resource inequalities: (x+y)+(2x+y)≤4+6, which gives 3x+2y≤10 for every feasible plan. Since (2,2) achieves this upper bound, it is optimal. The two unit multipliers form a simple dual bound certificate.
Now increase the first resource limit to 4+δ while leaving the second at 6. If both constraints remain binding, their intersection is x=2−δ and y=2+2δ. For −1≤δ≤2, these quantities remain nonnegative and attain the summed upper bound 10+δ. Outside that interval, this same intersection is not feasible, so the formula must not be extended without re-solving the problem.
Finally, if x and y must represent whole indivisible items, that requirement must be stated. This example happens to have an integer optimum at the original limits, but ordinary LP does not generally guarantee integer decisions. Rounding a fractional answer can violate constraints or lose optimality.

Illustrative case study

In a fictional food-production company, a planner develops a linear blending model using ingredient costs and composition limits. The initial solution meets the numerical specifications but proposes a batch smaller than the equipment can practically process.
The team adds the missing operational requirement and checks whether it can be represented linearly or requires discrete decisions. It then reviews the revised plan against real operating procedures. The scenario illustrates model refinement, not a reported cost saving or proof that every production requirement fits an LP.

Common misconceptions and mistakes

Do not confuse a feasible plan with an optimal plan. Do not assume every LP has a unique optimum or that every bounded feasible region contains exactly one best point. Multiple plans can share the same objective value.
An unbounded objective often points to a missing practical limit, but it can also be a legitimate mathematical property of the model. Infeasibility can reflect conflicting requirements or data errors. Also, an LP solver's numerical tolerances matter: verify important constraints in the original units rather than interpreting every tiny displayed violation as either harmless or catastrophic without context.

Business use

LP is useful when decisions, costs, and resource relationships admit a credible linear formulation. A reviewable model links each variable and constraint to a business meaning, records units, and separates measured quantities from assumptions. Scenario analysis can show how conclusions change when uncertain coefficients vary.
Treat dual sensitivity values as local model information rather than unrestricted prices for buying resources. Check whether the predicted marginal benefit still applies over the proposed change. If reality includes fixed charges, logical choices, or nonlinear physical relationships, consider an appropriate extension instead of forcing those effects into an unjustified linear approximation.

Check your understanding

Two valid constraints imply an objective is at most 12, and a feasible plan achieves 12. What does that establish?

Answer: The plan is globally optimal for that objective and feasible set, because no feasible plan can exceed the bound.

Related terms

Objective function
Linear constraints
Interior-point method
decision variable
feasible region
linear constraint
simplex method
duality
shadow price
mixed-integer programming

Learn next

Next, formulate a two-variable resource-allocation problem and verify its best plan with a bound formed from the constraints. Then study duality and sensitivity analysis, paying attention to where a marginal-value interpretation stops applying.

Sensitivity analysis

Sources

Primary software reference: SciPy, linprog, official formulation and solver-status documentation: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html . The allocation model, dual bound, and parameter-change interval are original algebraic illustrations.

Previous: Linear probing Next: Linear-quadratic regulator rapidly exploring random tree