The Central Idea
A linear program optimizes a linear objective subject to linear constraints.
A two-variable example is
\[ \boxed{ \begin{aligned} \text{maximize}\quad &40x+60y\\ \text{subject to}\quad &2x+y\le100,\\ &x+3y\le120,\\ &x\ge0,\\ &y\ge0. \end{aligned} } \]The objective assigns value to each feasible decision, while the constraints define the region in which decisions are allowed.
What Makes a Program Linear?
A linear programming model requires linear relationships.
Terms such as
\[ 3x,\qquad 5y,\qquad 2x+7y \]are linear, while terms such as
\[ x^2,\qquad xy,\qquad \sqrt{x},\qquad e^x \]are nonlinear and therefore fall outside ordinary linear programming.
The Linear Objective Function
A linear objective has the form
\[ \boxed{ f(x_1,\ldots,x_n)=c_1x_1+\cdots+c_nx_n }. \]The coefficients \(c_1,\ldots,c_n\) represent the contribution of each decision variable to the objective.
Example: Profit Objective
Suppose product \(x\) contributes \(50\) dollars of profit per unit and product \(y\) contributes \(80\) dollars per unit.
\[ \boxed{P(x,y)=50x+80y}. \]If the goal is maximum profit, then
\[ \boxed{\text{maximize }P(x,y)}. \]Linear Constraints
A linear constraint has the form
\[ a_1x_1+\cdots+a_nx_n\le b, \]or a corresponding equality or greater-than inequality.
For example,
\[ 2x+3y\le120 \]might represent a limited resource.
Resource Interpretation
Suppose product \(x\) requires \(2\) labor hours and product \(y\) requires \(3\) labor hours. If \(120\) labor hours are available, then
\[ \boxed{2x+3y\le120}. \]The left side represents resource use. The right side represents resource availability.
Nonnegativity Constraints
Production quantities, shipment amounts, workforce assignments, and many other decisions cannot be negative.
\[ x_i\ge0. \]In two variables,
\[ x\ge0,\qquad y\ge0. \]The Feasible Region
Every linear constraint defines a half-plane in two dimensions or a half-space in higher dimensions. The feasible region is the intersection of all these sets.
In two variables, the result is often a polygon.
Why the Feasible Region Is Convex
Linear inequalities define convex sets, and the intersection of convex sets is also convex.
Therefore, the feasible region of a linear program is convex. This geometric property is one reason linear programming has such strong global optimality results.
Vertices and Extreme Points
A corner of a polygonal feasible region is called a vertex or extreme point.
In two dimensions, vertices occur where boundary lines intersect. In higher dimensions, extreme points arise where enough independent constraints become active to pin down a point.
The Corner-Point Principle
If a linear objective attains a maximum or minimum over a nonempty polyhedral feasible region, then an optimal solution exists at an extreme point.
Therefore, for small two-variable problems, we can often solve the model by evaluating the objective at the vertices.
Why Vertices Matter
A linear objective changes at a constant rate in a fixed direction. As an objective contour moves across a convex polygon, the final point of contact before leaving the feasible region occurs at a vertex or along an entire edge.
Objective Contours
For a linear objective
\[ f(x,y)=c_1x+c_2y, \]a level set satisfies
\[ c_1x+c_2y=k. \]Solving for \(y\),
\[ y=-\frac{c_1}{c_2}x+\frac{k}{c_2}. \]Every objective contour has the same slope.
Graphical Optimization
In two variables, a linear program can often be solved graphically.
- Graph each constraint boundary.
- Identify the feasible side of each inequality.
- Find the feasible region.
- Determine its vertices.
- Evaluate the objective at each vertex.
- Choose the largest or smallest objective value.
Example: A Small Linear Program
Maximize
\[ P(x,y)=30x+50y \]subject to
\[ x+y\le8, \] \[ x\le6, \] \[ x\ge0, \qquad y\ge0. \]The feasible region has vertices
\[ (0,0),\qquad(6,0),\qquad(6,2),\qquad(0,8). \]Evaluating the Vertices
\[ P(0,0)=0, \] \[ P(6,0)=180, \] \[ P(6,2)=280, \] \[ P(0,8)=400. \]Therefore,
\[ \boxed{\text{maximum profit }=400} \]at
\[ \boxed{(x,y)=(0,8)}. \]Finding Vertices Algebraically
Suppose
\[ x+y=10 \]and
\[ 2x+y=14. \]Subtract the first equation from the second:
\[ x=4. \]Then
\[ y=6. \]So the intersection is
\[ \boxed{(4,6)}. \]Not Every Boundary Intersection Is Feasible
A point may lie at the intersection of two constraint boundaries and still violate another constraint. Every candidate vertex must therefore be checked against the full system.
Binding Constraints
A constraint is binding at a feasible point when it holds with equality.
For
\[ 2x+3y\le120, \]the constraint is binding when
\[ 2x+3y=120. \]Slack
For
\[ 2x+3y\le120, \]the slack is
\[ \boxed{120-(2x+3y)}. \]A binding constraint has zero slack.
Slack Variables
An inequality can be converted into an equality by introducing a nonnegative slack variable.
\[ 2x+3y\le120 \]becomes
\[ \boxed{2x+3y+s=120}, \qquad s\ge0. \]The variable \(s\) measures unused capacity.
Surplus Variables
A lower-bound constraint such as
\[ 2x+y\ge50 \]can be written
\[ 2x+y-s=50, \qquad s\ge0. \]Here \(s\) measures how far the requirement is exceeded.
Standard Form
Linear programs are often rewritten into a standardized algebraic form. One common maximization convention is
\[ \boxed{ \begin{aligned} \text{maximize}\quad &\mathbf{c}^T\mathbf{x}\\ \text{subject to}\quad &A\mathbf{x}\le\mathbf{b},\\ &\mathbf{x}\ge\mathbf{0}. \end{aligned} } \]Other equivalent standard forms are also widely used.
Matrix Form
A large linear program can be written compactly as
\[ A\mathbf{x}\le\mathbf{b}, \]where:
- \(\mathbf{x}\) is the decision vector;
- \(\mathbf{c}\) contains objective coefficients;
- \(A\) contains resource coefficients;
- \(\mathbf{b}\) contains capacity or requirement values.
The objective is
\[ \mathbf{c}^T\mathbf{x}. \]Example: Matrix Representation
The constraints
\[ 2x+3y\le120, \] \[ x+2y\le80 \]can be written
\[ \begin{bmatrix} 2 & 3\\ 1 & 2 \end{bmatrix} \begin{bmatrix} x\\ y \end{bmatrix} \le \begin{bmatrix} 120\\ 80 \end{bmatrix}. \]Bounded Feasible Regions
If the feasible region is bounded and nonempty, every linear objective attains a maximum and minimum on it.
In two dimensions, such a feasible region is often a closed polygon.
Unbounded Feasible Regions
A feasible region may extend indefinitely. This does not automatically mean the linear program has an unbounded objective.
The objective direction must also allow indefinite improvement.
Example: Unbounded Objective
Maximize
\[ f(x,y)=x+y \]subject only to
\[ x\ge0, \qquad y\ge0. \]The objective can increase without limit. Therefore,
\[ \boxed{\text{the linear program is unbounded above}}. \]Infeasible Linear Programs
A system of linear constraints may have no common solution.
For example,
\[ x\ge8 \]and
\[ x\le5 \]cannot both hold. The feasible set is empty.
Multiple Optimal Solutions
Sometimes an objective contour is parallel to a boundary edge. If the best contour touches the feasible region along that entire edge, every point on the edge is optimal.
A linear program can therefore have infinitely many optimal solutions.
Unique Optimal Solutions
If the best objective contour touches the feasible region at exactly one vertex, then the linear program has a unique optimizer.
Degeneracy Preview
In higher-dimensional linear programming, several constraints may meet at one extreme point in a way that creates degeneracy. Degeneracy affects algorithmic behavior but does not change the underlying feasible point.
The Simplex Method
Graphical methods work only for a small number of variables. The simplex method solves larger linear programs by moving systematically from one extreme point to another while improving or preserving the objective.
Why Simplex Uses Vertices
Linear programming's corner-point structure means the search can focus on extreme points rather than every feasible point. The simplex method exploits exactly this geometry.
Interior-Point Methods
Modern linear programming can also be solved using interior-point methods. Instead of traveling along the boundary from vertex to vertex, these methods move through the interior of the feasible region.
Duality Preview
Every linear program has an associated dual problem. The dual assigns values to constraints and resources rather than directly choosing the original activity levels.
Duality provides deep connections among optimal values, resource scarcity, sensitivity, and shadow prices.
Shadow Prices
A binding resource constraint can have a marginal value. In linear programming, this value is often called a shadow price.
It measures how the optimal objective changes when the corresponding resource limit is relaxed slightly, within an appropriate sensitivity range.
Reduced Costs Preview
Linear programming also assigns marginal information to decision variables. A reduced cost can indicate how much an objective coefficient would need to improve before a currently unused variable becomes attractive in the optimal solution.
Sensitivity Analysis
Linear programming is valuable not only because it identifies an optimal solution, but also because it helps answer questions such as:
- How much is an additional unit of a resource worth?
- How far can a profit coefficient change before the solution changes?
- Which constraints are binding?
- Which resources have unused capacity?
- How robust is the current solution?
Modeling Assumption: Proportionality
Linear programming assumes contributions scale proportionally. If one unit of a product uses \(2\) hours, then \(10\) units are modeled as using
\[ 20 \]hours.
There are no nonlinear economies or diseconomies of scale inside the linear model.
Modeling Assumption: Additivity
Total resource use and objective contribution are modeled as sums. Interaction terms such as
\[ xy \]do not appear in an ordinary linear program.
Modeling Assumption: Divisibility
Standard linear programming treats decision variables as continuously divisible unless integer restrictions are added. Thus a model might allow
\[ x=3.7. \]If the real decision requires whole units, integer programming is needed.
Modeling Assumption: Certainty
Basic linear programming assumes the coefficients in the model are known and fixed during optimization. When costs, demand, processing times, or capacities are uncertain, more advanced stochastic or robust methods may be appropriate.
Linear Programming and Integer Programming
If we add
\[ x_i\in\mathbb{Z}, \]the problem becomes an integer linear program. Its objective and algebraic constraints remain linear, but the feasible set becomes discrete.
Binary Decisions
A decision variable restricted by
\[ x\in\{0,1\} \]can represent a yes-or-no choice.
- open or do not open a facility;
- select or reject a project;
- activate or deactivate a route;
- assign or do not assign a resource.
Example: Production Planning Model
A company makes two products. Profit per unit is \(40\) dollars for product \(x\) and \(55\) dollars for product \(y\).
Labor requirements produce
\[ 2x+3y\le180. \]Machine capacity produces
\[ 4x+2y\le200. \]The model is
\[ \boxed{ \begin{aligned} \text{maximize}\quad &40x+55y\\ \text{subject to}\quad &2x+3y\le180,\\ &4x+2y\le200,\\ &x\ge0,\\ &y\ge0. \end{aligned} } \]Example: Diet or Blending Model
Linear programming can also minimize cost while satisfying minimum requirements.
Suppose ingredients \(x\) and \(y\) have cost
\[ 3x+5y \]and must satisfy nutrient requirements such as
\[ 2x+y\ge20, \] \[ x+3y\ge30. \]The model seeks the lowest-cost feasible combination.
Example: Transportation Model
Let
\[ x_{ij} \]represent the quantity shipped from source \(i\) to destination \(j\).
Transportation cost may be
\[ \sum_i\sum_j c_{ij}x_{ij}. \]Supply constraints limit outgoing shipments, while demand constraints require sufficient incoming shipments. This produces a large but highly structured linear program.
Example: Workforce Allocation
Decision variables may represent the number of workers assigned to different shifts or tasks. Constraints can enforce staffing requirements, availability, and workload limits. The objective may minimize labor cost or maximize coverage.
Example: Portfolio Allocation
A simplified investment model may allocate fractions \(x_1,\ldots,x_n\) across assets. A linear objective might maximize expected return subject to budget, category, or allocation constraints.
More realistic risk models often become nonlinear, but the linear version remains useful as a foundational model.
Common Error: Using a Nonlinear Objective
An objective such as
\[ xy \]or
\[ x^2+y \]is not linear. The problem may still be optimizable, but it is not an ordinary linear program.
Common Error: Using Nonlinear Constraints
A constraint such as
\[ x^2+y^2\le25 \]creates a curved boundary. This produces a nonlinear constrained optimization problem rather than a linear program.
Common Error: Testing Only One Vertex
A feasible vertex is only a candidate. Every relevant vertex must be evaluated unless another theorem or algorithm has already established the optimum.
Common Error: Forgetting Feasibility
An intersection of two boundary lines is not automatically a vertex of the feasible region. It must satisfy every constraint.
Common Error: Forgetting Nonnegativity
If activity levels cannot be negative, include
\[ x_i\ge0. \]Omitting these restrictions can create mathematically feasible but practically meaningless solutions.
Common Error: Assuming an Unbounded Region Means No Optimum
The region may be unbounded while the objective still has a finite optimum. The objective direction and feasible directions must be analyzed together.
Common Error: Assuming the Optimum Is Unique
If the objective is parallel to a binding edge, multiple feasible points may produce the same optimal value.
A Reliable Linear Programming Workflow
- Define the decision variables and their units.
- Write the linear objective function.
- Translate every resource or requirement into a linear constraint.
- Include nonnegativity, sign, or bound restrictions.
- Check that the model is genuinely linear.
- Identify the feasible region.
- Check whether the model is feasible and bounded in the objective direction.
- Find all feasible vertices when solving graphically.
- Evaluate the objective at each candidate vertex.
- Identify binding constraints and slack.
- Check for multiple optimal solutions.
- Interpret the optimal decision in the original context.
- Use sensitivity information when available.
Practice 1: Identify Linearity
Which of the following expressions are linear?
\[ 3x+5y, \] \[ x^2+y, \] \[ 7x-2y+4, \] \[ xy. \]Practice 2: Write the Objective
Product \(x\) earns \(25\) dollars per unit and product \(y\) earns \(40\) dollars per unit. Write the profit objective.
Practice 3: Write a Resource Constraint
Product \(x\) uses \(3\) machine hours per unit and product \(y\) uses \(2\) hours per unit. At most \(150\) hours are available.
Write the constraint.
Practice 4: Find a Vertex
Find the intersection of
\[ x+y=9 \]and
\[ 2x+y=13. \]Practice 5: Evaluate Candidate Vertices
Evaluate
\[ P(x,y)=20x+30y \]at
\[ (0,0),\qquad(5,0),\qquad(3,4),\qquad(0,6). \]Which gives the largest value?
Practice 6: Compute Slack
For
\[ 2x+3y\le100, \]compute the slack at
\[ (20,10). \]Practice 7: Binding or Nonbinding?
Determine whether
\[ x+2y\le12 \]is binding at
\[ (4,4). \]Practice 8: Unbounded Model
Consider
\[ \text{maximize }x+y \]subject to
\[ x\ge0,\qquad y\ge0. \]Does a finite maximum exist?
Practice 9: Multiple Optima
Explain how a linear program can have more than one optimal solution.
Practice 10: Build the Model
A company produces products \(x\) and \(y\). Profit per unit is \(35\) dollars for \(x\) and \(50\) dollars for \(y\).
Labor use is \(2\) hours for \(x\) and \(4\) hours for \(y\), with \(160\) hours available.
Material use is \(3\) units for \(x\) and \(2\) units for \(y\), with \(150\) units available.
Write the complete linear program.
Practice Answers
Practice 1
The linear expressions are
\[ \boxed{3x+5y} \]and
\[ \boxed{7x-2y+4}. \]The expressions \(x^2+y\) and \(xy\) are nonlinear.
Practice 2
\[ \boxed{P(x,y)=25x+40y}. \]The objective is to maximize \(P\).
Practice 3
\[ \boxed{3x+2y\le150}. \]Practice 4
Subtract the first equation from the second:
\[ x=4. \]Then
\[ y=5. \]The intersection is
\[ \boxed{(4,5)}. \]Practice 5
\[ P(0,0)=0, \] \[ P(5,0)=100, \] \[ P(3,4)=180, \] \[ P(0,6)=180. \]The largest value is
\[ \boxed{180} \]at both
\[ \boxed{(3,4)\text{ and }(0,6)}. \]Practice 6
Resource use is
\[ 2(20)+3(10)=70. \]Slack is
\[ 100-70=\boxed{30}. \]Practice 7
At \((4,4)\),
\[ 4+2(4)=12. \]Therefore,
\[ \boxed{\text{the constraint is binding}}. \]Practice 8
Both variables can increase indefinitely while remaining feasible. Therefore,
\[ \boxed{\text{no finite maximum exists}}. \]Practice 9
Multiple optima occur when the best objective contour coincides with a feasible edge or face. Every point on that optimal edge or face produces the same objective value.
Practice 10
\[ \boxed{ \begin{aligned} \text{maximize}\quad &35x+50y\\ \text{subject to}\quad &2x+4y\le160,\\ &3x+2y\le150,\\ &x\ge0,\\ &y\ge0. \end{aligned} } \]What to Remember
Linear programming optimizes a linear objective over a region defined by linear constraints.
- the objective must be linear;
- the constraints must be linear;
- the feasible region is convex;
- vertices are central candidate solutions;
- a linear optimum, when attained, can be found at an extreme point;
- binding constraints have zero slack;
- a model may be infeasible, bounded, or unbounded;
- multiple optimal solutions can occur along an edge or face;
- simplex and interior-point methods solve larger models;
- duality and sensitivity analysis reveal the marginal value of resources.
The geometric principle is
\[ \boxed{ \text{a linear objective over a polyhedral feasible region can be optimized at an extreme point} }. \]Where We Go Next
Linear programming works so cleanly because both its objective and its feasible region have a special geometry. More generally, optimization becomes much easier when an objective has no misleading local valleys and the feasible set contains every line segment joining its points.
The next lesson, Convexity, develops the geometric structure behind these global guarantees and explains why convex optimization occupies such a central position in modern mathematics, engineering, economics, and computation.