Home / Courses / Optimization / Linear Programming

Optimization · Module 7 of 10

Linear Programming

When the objective and every constraint are linear, the feasible region is a polygon and the optimum sits at a corner. That single fact turns a search over infinitely many points into a check of a few vertices.

01

Readiness check

This module optimises linear problems. Tick only what you can do closed-notes.

  • Graph a line and shade an inequality.
  • Find where two lines intersect.
  • Evaluate a linear function at a point.
  • Recall a feasible region as an intersection of half-planes.
  • Recall that an optimum can lie on a constraint boundary.
0 or 1 weak itemsContinue with this module.
2 weak itemsRevisit feasible regions in Module 1.
3 or more weak itemsRefresh solving linear systems in Mathematics, Module 8.
02

The core idea

A linear program has a linear objective and linear constraints. Its feasible region is a convex polygon, and the optimum always lies at a vertex, so the solution is found by evaluating the objective at the corners.

minimise (or maximise) cTxsubject to Ax ≤ b, x ≥ 0optimum is at a vertex of the feasible polygon

A linear program (LP) optimises a linear objective cTx over a feasible region defined by linear inequalities Ax ≤ b and bounds x ≥ 0. Because every constraint is linear, the feasible region is a convex polytope, a polygon in two variables, and because the objective is linear, its contours are straight lines. Sliding a contour as far as it will go in the improving direction, it last touches the region at a corner. This is the fundamental theorem of linear programming: an optimum, if one exists, is attained at a vertex. In two variables you can therefore solve an LP graphically, by finding the feasible polygon's corners and evaluating the objective at each. The simplex method generalises this to many variables: it walks from vertex to adjacent vertex, always improving, until no neighbour is better. Every LP also has a dual problem whose optimal values are the shadow prices of the constraints, linking back to the multipliers of the previous module.

The skill works when: you find the feasible vertices and evaluate the objective at each.
The skill breaks down when: the region is unbounded in the improving direction, or a corner is read as feasible when a constraint is violated.
The concept. The feasible region is a polygon; the objective's parallel contours sweep across it. The optimum is the vertex a contour reaches last, so only the corners need checking.
03

The skills, taught in order

Five skills build the LP, its feasible polygon, the vertex principle, and the simplex idea.

7.1 The linear program

An LP minimises or maximises a linear objective subject to linear equalities and inequalities. Writing it in a standard form, minimise cTx subject to Ax ≤ b and x ≥ 0, makes it ready for a solver and clarifies the structure.

7.2 The feasible region

Each linear inequality cuts the plane into a half-plane; their intersection is the feasible region, a convex polygon (or polytope). It may be bounded, unbounded, or empty, and its shape is entirely determined by the constraints.

7.3 Vertices and the fundamental theorem

The corners of the feasible polygon are its vertices, each the intersection of two active constraints. The fundamental theorem of LP guarantees that an optimum, when it exists, occurs at a vertex, so evaluating the objective at every corner solves the problem.

FeatureLinear program
Objectivelinear, cTx
Feasible regionconvex polygon
Optimum locationat a vertex
Solution methodsimplex or interior point

The structure of an LP. Linearity makes the region convex and forces the optimum to a corner.

7.4 The simplex method

The simplex method starts at a feasible vertex and moves along an edge to an adjacent vertex that improves the objective, repeating until no neighbour is better. It visits only corners, and in practice reaches the optimum in a modest number of steps.

7.5 Duality and shadow prices

Every LP has a dual LP; at the optimum their objectives are equal, and the dual variables are the shadow prices of the primal constraints. A binding constraint's shadow price says how much the optimum would improve per unit of relaxation, the LP form of a Lagrange multiplier.

Engineering connection: allocating limited material, machine time, or power to maximise output is a linear program, and the shadow prices tell you which resource to buy more of.

04

Worked example 1: a graphical linear program

Maximise P = 3x + 4y subject to x + y ≤ 4, x + 3y ≤ 6, and x, y ≥ 0. Find the optimal vertex and value.

Figure 1. The feasible polygon has four corners. Evaluating 3x + 4y at each, the maximum occurs at the intersection vertex (3, 1), where both slanted constraints are active.
  1. ProblemMaximise P over the feasible region in Figure 1.
  2. Given / findMaximise P = 3x + 4y subject to x + y ≤ 4, x + 3y ≤ 6, x, y ≥ 0. Find the optimal vertex.
  3. AssumptionsBounded feasible region; the optimum is at a vertex.
  4. ModelFind every corner, then evaluate P at each and take the largest.
  5. Equationscorners: (0,0), (4,0), (0,2), and x+y=4 ∩ x+3y=6intersection: 2y = 2 ⇒ (3, 1)
  6. SolveP(0,0) = 0; P(4,0) = 12; P(0,2) = 8; P(3,1) = 9 + 4 = 13. The maximum is 13 at (3, 1).
  7. Check(3, 1) is feasible: x + y = 4 ≤ 4 and x + 3y = 6 ≤ 6, both active. No corner gives a higher P, so it is optimal.
  8. ConclusionThe optimum is x = 3, y = 1 with P = 13, where both slanted constraints bind. Only the vertices needed checking.
Result. Maximum P = 13 at the vertex (3, 1).
05

Worked example 2: a minimisation linear program

Minimise the cost C = 2x + 3y subject to x + y ≥ 4 and x ≥ 1 (with y ≥ 0). Find the optimal vertex and value.

Figure 2. The feasible region is unbounded above, but the cost is minimised at a corner. Checking the vertices, (4, 0) gives the lowest cost.
  1. ProblemMinimise C over the feasible region in Figure 2.
  2. Given / findMinimise C = 2x + 3y subject to x + y ≥ 4, x ≥ 1, y ≥ 0. Find the optimal vertex.
  3. AssumptionsThe minimum is attained at a vertex of the feasible region.
  4. ModelIdentify the corners where the active constraints meet, then evaluate C at each.
  5. Equationscorner (1, 3): x = 1 ∩ x + y = 4corner (4, 0): y = 0 ∩ x + y = 4
  6. SolveC(1, 3) = 2 + 9 = 11. C(4, 0) = 8 + 0 = 8. The minimum is 8 at (4, 0).
  7. Check(4, 0) is feasible: x + y = 4 ≥ 4 and x = 4 ≥ 1. Moving along the boundary away from it only raises C, so it is optimal.
  8. ConclusionThe cheapest feasible plan is x = 4, y = 0 with C = 8. Even for an unbounded region, the optimum sits at a corner.
Result. Minimum C = 8 at the vertex (4, 0).
06

Misconceptions and diagnostics

MistakeSymptomDiagnostic questionCorrection
Searching the interiorChecking points inside the region"Where must the LP optimum be?"An LP optimum is at a vertex; check the corners.
Infeasible corner usedA vertex violates a constraint"Does this point satisfy all constraints?"Only feasible vertices are candidates.
Missing unboundednessObjective improves without limit"Is the region bounded in this direction?"An LP can be unbounded; check the improving direction.
Ignoring shadow pricesNo sense of which constraint binds"What is each constraint's dual value?"Read shadow prices to see what to relax.
07

Practice ladder

Level 1 · Direct skill

Find where x + y = 4 and x = 1 intersect.

Show answer

x = 1, so y = 3: the point (1, 3).

Level 2 · Mixed concept

Maximise P = x + y over x + y ≤ 4, x, y ≥ 0. What is the optimum?

Show answer

Any point on x + y = 4 gives P = 4; the whole edge is optimal, so the maximum is 4 (attained at vertices like (4, 0) and (0, 4)).

Level 3 · Independent problem

Maximise P = 5x + 4y over x + y ≤ 5, x ≤ 3, x, y ≥ 0. Find the optimal vertex.

Show answer

Corners: (0,0)=0, (3,0)=15, (3,2)=23, (0,5)=20. Maximum is 23 at (3, 2), where x = 3 and x + y = 5 are both active.

Transfer task | Real engineering

You allocate limited machine hours and material to two products to maximise profit. Explain how the shadow prices guide which resource to expand.

What good work looks like

Solve the LP, then read the dual value on each binding resource constraint: the resource with the highest shadow price yields the most extra profit per added unit, so it is the one to expand first.

08

Working with AI, and proving it yourself

Use AI as an examiner, not a solver

"Check that each vertex I found is feasible."
"Give me three LPs; I will find the feasible corners of each."
"Solve the LP for me." Finding and testing the vertices is the skill.
"Which constraint matters most?" Reading the shadow prices is the point.

Portfolio task

Model a real allocation problem as an LP, solve it graphically or with a solver, identify the binding constraints, and interpret their shadow prices.

Must include: the LP in standard form, the optimal vertex, the active constraints, and a shadow-price reading.
09

Retrieval and spaced review

Closed notes. Answer out loud, then reveal.

1. What shape is an LP feasible region?

A convex polygon (polytope), the intersection of half-planes.

2. Where does the LP optimum occur?

At a vertex of the feasible region, by the fundamental theorem.

3. How does the simplex method work?

It walks from vertex to improving adjacent vertex until none is better.

4. What are the dual variables?

The shadow prices of the constraints, equal at optimum to the primal value.

5. When does an LP have no optimum?

When it is infeasible, or unbounded in the improving direction.

TodayFinish this quiz and Levels 1 and 2 of the ladder.
+1 dayRe-solve both LPs from a blank page.
+3 daysSolve three new LPs at their vertices.
+7 daysAdd a quadratic objective and penalties, Module 8.
+30 daysReuse LP and shadow prices for a real allocation.
10

Textbook mapping

This module follows Nocedal and Wright, Numerical Optimization, 2nd edition. Use these references to read further.

Topic in this moduleWhere to read more
Linear programming and the feasible regionNocedal & Wright, Chapter 13
The simplex methodNocedal & Wright, Chapter 13
Duality and shadow pricesNocedal & Wright, Chapter 13

Chapter numbers refer to the 2nd edition. The linear-programming theory is standard, so any recent edition will align closely.