Skip to content
NumeriveMATH
Make learning comfortable
Changing style, motion, or reading speed keeps your current question, answers, homework, and saved progress. The school band still chooses your task layout. Saved to your learner profile across devices. All lessons and help stay available.
← Linear Optimization levels

Linear Optimization / LEVEL 1 · DIFFICULTY 4/5

Linear Optimization

Read the prerequisite, study a worked example and justify each step in these selected university topics.

2 stages · 16 practice problems · two 4-question assessment forms

STAGE ULP 1.1 · 8 PRACTICE PROBLEMS · 4 NEW-CONTEXT APPLICATIONS

Feasible Regions, Vertices & Dual Bounds

Useful preparation: Graphing Inequalities & Feasible Regions

Open this topic in the university library →

For a long equation, swipe sideways inside its formula box to see every term.

Meaning & notation

A linear program chooses values that satisfy all linear restrictions while making a linear objective as large or small as possible. In two variables, each restriction cuts out a half-plane. Their intersection is the feasible region. Sliding a straight objective-level line explains why corners are useful, while a weighted combination of constraints can prove that no feasible point does better.

Feasible point and objective
A feasible point satisfies every constraint, including sign restrictions. The objective c transpose x assigns a value to each feasible point and must be stated separately from the restrictions.
Vertex
A vertex is an extreme point: it cannot be written as a nontrivial convex combination of two distinct feasible points. In a polygon, vertices are its corners.
Dual bound
For a maximization problem, a valid upper bound follows from constraints by operations that preserve their inequality directions. A feasible point attaining that bound is provably optimal.

Conditions before calculation

  • Linear objectives and constraints contain no products of decision variables, powers above one, or variable-dependent coefficients. Ordinary linear programming allows fractional variable values.
  • For a nonempty bounded polygon, a linear objective attains a maximum and minimum, each at at least one vertex. There can be additional optimal points along an edge or throughout the region.
  • First check feasibility and boundedness of the objective. An unbounded feasible region need not make every objective unbounded, and arbitrary polyhedra may have no vertices.

Why the method works

1. Translate the model

Define each decision variable with units, then express resources and requirements as inequalities. A graph is useful only after the directions and nonnegativity conditions match the application.

2. Enumerate feasible corners

Find boundary intersections, but keep only those satisfying every constraint. Compare objective values at the retained vertices when the bounded-polygon theorem applies.

3. Certify with constraint weights

For max c transpose x with Ax at most b and x nonnegative, choose a nonnegative vector u with A transpose u at least c. Every feasible objective is bounded by b transpose u.

cTx≤uTAx≤uTbc^{\mathsf T}x\le u^{\mathsf T}Ax\le u^{\mathsf T}b

Worked examples

EXAMPLE 1

Maximize 3 x+2 y\displaystyle 3\, x + 2\, y subject to x+y\displaystyle x + y at most 4, 2 x+y\displaystyle 2\, x + y at most 5, and x,y nonnegative.

  1. The two slanted boundaries intersect at (1,3). Together with the axes, the feasible vertices are (0,0), (2.5,0), (1,3), and (0,4).

  2. Evaluate the objective at each vertex.

    0,7.5,9,80,\quad 7.5,\quad 9,\quad 8

  3. Add the two resource inequalities to certify the upper bound; the candidate meets both with equality.

    3x+2y=(x+y)+(2x+y)≤4+5=93x+2y=(x+y)+(2x+y)\le4+5=9

Conclusion: The feasible point (1,3) attains 9 and is therefore optimal; the bound is a proof that covers all feasible points.

EXAMPLE 2

For x,y nonnegative and x−y\displaystyle x - y at most 1, compare maximizing and minimizing x+y\displaystyle x + y.

  1. The origin is feasible. For every nonnegative t, the point (t,t) is also feasible because its coordinate difference is zero.

  2. Along this feasible ray, the objective grows without bound.

    x+y=2t⟶∞x+y=2t\longrightarrow\infty

  3. For minimization, nonnegativity supplies a lower bound that the origin attains.

    x+y≥0,(x,y)=(0,0)x+y\ge0,\qquad (x,y)=(0,0)

Conclusion: The maximum is unbounded, but the minimum is 0. The same unbounded feasible region produces different objective behavior.

Pitfalls & counterexamples

Tempting claim: An optimal solution must be a unique vertex.

Correction: At least one optimal vertex exists under the stated bounded-polygon conditions, but uniqueness is a separate question.

Test the claim: Maximizing x+y\displaystyle x + y over the nonnegative triangle x+y\displaystyle x + y at most 1 makes every point on the edge x+y=1\displaystyle x + y = 1 optimal.

Check your understanding

Can multiplying a less-than-or-equal constraint by a negative weight preserve its direction?

Write a reason before opening the explanation. This reflection is not graded or saved.

Compare your reasoning

No.

A negative multiplier reverses the inequality. Nonnegative dual weights prevent this error for the displayed upper-bound construction.

Connect this idea

Duality interprets constraints as certificates and resource values. Integer programming adds discrete restrictions; sensitivity analysis asks how the optimal value changes when resource limits change.

Practise this topic →Review concept flashcards

Reference reading

Use these texts to study the underlying definitions and theorems in greater depth. The explanations and examples above are written for Numerive.

Preview the eight practice prompts
  1. Problem 1

    Maximize 3 x+2 y\displaystyle 3\, x + 2\, y subject to x≥0\displaystyle x \ge 0, y≥0\displaystyle y \ge 0 and x+y≤4\displaystyle x + y \le 4. Find the maximum value.

    Practise this exact problem →
  2. Problem 2

    Maximize x+y\displaystyle x + y subject to 0≤x≤2\displaystyle 0 \le x \le 2, 0≤y≤5\displaystyle 0 \le y \le 5. Find the maximum.

    Practise this exact problem →
  3. Problem 3

    For a linear program x+y≤3\displaystyle x + y \le 3 and 2 x+y≤7\displaystyle 2\, x + y \le 7. Adding these constraints gives an upper bound on 3 x+2 y\displaystyle 3\, x + 2\, y. What is that bound?

    Practise this exact problem →
  4. Problem 4

    Consider maximizing x subject only to x≥2\displaystyle x \ge 2. Does it have a finite maximum? Enter 1 for yes, 0 for no.

    Practise this exact problem →
  5. Problem 5New context

    A resource allocation maximizes 3 x+2 y\displaystyle 3\, x + 2\, y subject to x≥0\displaystyle x \ge 0, y≥0\displaystyle y \ge 0 and x+y≤5\displaystyle x + y \le 5. Find the maximum value.

    Practise this exact problem →
  6. Problem 6New context

    A bounded production model maximizes x+y\displaystyle x + y subject to 0≤x≤3\displaystyle 0 \le x \le 3, 0≤y≤6\displaystyle 0 \le y \le 6. Find the maximum.

    Practise this exact problem →
  7. Problem 7New context

    A planner has constraints x+y≤4\displaystyle x + y \le 4 and 2 x+y≤9\displaystyle 2\, x + y \le 9. Adding these constraints gives an upper bound on 3 x+2 y\displaystyle 3\, x + 2\, y. What is that bound?

    Practise this exact problem →
  8. Problem 8New context

    A proposed allocation maximizes x subject only to x≥3\displaystyle x \ge 3. Does it have a finite maximum? Enter 1 for yes, 0 for no.

    Practise this exact problem →
Open stage ULP 1.1 in the student workspace →

STAGE ULP 1.2 · 8 PRACTICE PROBLEMS · 4 NEW-CONTEXT APPLICATIONS

Integer Decisions, Assignment & Transport

Useful preparation: Feasible Regions, Vertices & Dual Bounds

Open this topic in the university library →

For a long equation, swipe sideways inside its formula box to see every term.

Meaning & notation

A fractional answer may be mathematically feasible for an LP yet impossible when decisions count indivisible objects. Integer programming keeps the same linear expressions but restricts selected variables to integers. Transportation and assignment problems have special network structure: under integer supply and demand data, their standard LPs have integral vertices, so an integral optimum can be found without generic integer search.

Integer program and relaxation
An integer program restricts some or all variables to integer values. Its LP relaxation removes those restrictions, enlarging the feasible set and providing an objective bound.
Transportation model
Variable xij is the quantity sent from source i to destination j. Row sums match supplies, column sums match demands, and nonnegative shipments incur a sum of unit costs times quantities.
Assignment model
A standard assignment problem pairs each agent with one task and each task with one agent. Binary variables indicate pairs; it is a transportation model with each supply and demand equal to one.

Conditions before calculation

  • Relaxation gives an upper bound for maximization and a lower bound for minimization. A fractional relaxed optimizer is not automatically a valid integer solution.
  • The balanced transportation formulation requires total supply to equal total demand. A dummy source or destination can model a genuine shortage or surplus only with appropriate costs and meaning.
  • The integrality guarantee applies to the standard network formulation with integer supplies, demands, and any integral capacities. Extra coupling constraints or fixed-charge decisions can destroy that structure; arbitrary feasible or optimal convex combinations can still be fractional.

Why the method works

1. Separate bounds from decisions

Solve or analyze the relaxation to learn what is theoretically possible. Check an integer candidate against every original constraint and compute its objective directly.

2. Use structure when available

The network constraint matrix is totally unimodular: every square subdeterminant is zero, one, or minus one. With integer right sides, this makes its feasible vertices integral.

3. Certify completeness

For a small bounded integer model, enumerate all possible values systematically. For transportation, use balance equations to reduce variables, then optimize over the resulting feasible interval or use a network algorithm.

Worked examples

EXAMPLE 1

Maximize 5 x+4 y\displaystyle 5\, x + 4\, y with 3 x+2 y\displaystyle 3\, x + 2\, y at most 7 and nonnegative integer x,y.

  1. Because 3x cannot exceed 7, only x=0\displaystyle x = 0,1,2 need examination. For each x, a positive coefficient on y makes the largest feasible integer y best.

  2. Enumerate these three best possibilities and their objective values.

    (x,y)=(0,3),(1,2),(2,0)⇒12,13,10(x,y)=(0,3),(1,2),(2,0)\quad\Rightarrow\quad 12,13,10

  3. The relaxation prefers y because it earns 2 per resource unit rather than 53\displaystyle \frac{5}{3}. Its point (0,3.5) has value 14, an upper bound.

Conclusion: The integer optimum is (1,2) with value 13. Rounding the relaxed y down gives only 12; rounding it up violates the resource limit.

EXAMPLE 2

Sources A,B supply 3,2 units; destinations 1,2 demand 2,3 units. Unit costs are A 1=1\displaystyle A\, 1 = 1, A 2=4\displaystyle A\, 2 = 4, B 1=3\displaystyle B\, 1 = 3, B 2=1\displaystyle B\, 2 = 1. Find a minimum-cost shipment.

  1. Let t be the A-to-1 shipment. Balance determines all other shipments.

    xA1=t,xA2=3−t,xB1=2−t,xB2=tx_{A1}=t,\quad x_{A2}=3-t,\quad x_{B1}=2-t,\quad x_{B2}=t

  2. Nonnegativity gives 0 at most t at most 2; express total cost.

    C(t)=t+4(3−t)+3(2−t)+t=18−5tC(t)=t+4(3-t)+3(2-t)+t=18-5t

  3. The cost decreases as t grows, so take t=2\displaystyle t = 2. Check row totals 3,2 and column totals 2,3.

    X=(2102),C=2+4+0+2=8X=\begin{pmatrix}2&1\\0&2\end{pmatrix},\qquad C=2+4+0+2=8

Conclusion: The balanced, nonnegative shipment has minimum cost 8 and is integral.

Pitfalls & counterexamples

Tempting claim: Rounding any LP optimum solves its integer program.

Correction: Rounding may violate constraints or miss a better feasible integer point.

Test the claim: The first example rounds down to value 12 even though the feasible integer point (1,2) earns 13.

Check your understanding

Does an integral transportation optimum imply every feasible shipment is integral?

Write a reason before opening the explanation. This reflection is not graded or saved.

Compare your reasoning

No.

In the second example t=12\displaystyle t = \frac{1}{2} gives a feasible fractional shipment. Integrality describes vertices and the existence of an integral optimum.

Connect this idea

Assignment is a bipartite matching problem. Branch-and-bound combines relaxation bounds with discrete search for general integer models; network structure can make specialized problems much easier.

Practise this topic →Review concept flashcards

Reference reading

Use these texts to study the underlying definitions and theorems in greater depth. The explanations and examples above are written for Numerive.

Preview the eight practice prompts
  1. Problem 1

    Maximize the integer x 2 x≤7\displaystyle x\, 2\, x \le 7, x≥0\displaystyle x \ge 0. Find the largest feasible integer x.

    Practise this exact problem →
  2. Problem 2

    An assignment has costs [[1,6],[5,2]]. Find the minimum total cost assigning one task per worker and one worker per task.

    Practise this exact problem →
  3. Problem 3

    A transport plan sends 2 units on a route costing 3 per unit and 4 units on a route costing 2 per unit. Find the total transport cost.

    Practise this exact problem →
  4. Problem 4

    Two sources supply 3 and 5. One destination demands 2; all supply must be shipped. What demand must the second destination have for balance?

    Practise this exact problem →
  5. Problem 5New context

    Whole units x must satisfy 2 x≤9\displaystyle 2\, x \le 9, x≥0\displaystyle x \ge 0. Find the largest feasible integer x.

    Practise this exact problem →
  6. Problem 6New context

    Two workers and two tasks have cost matrix [[2,7],[6,3]]. Find the minimum total cost assigning one task per worker and one worker per task.

    Practise this exact problem →
  7. Problem 7New context

    A delivery plan sends 3 units on a route costing 3 per unit and 5 units on a route costing 2 per unit. Find the total transport cost.

    Practise this exact problem →
  8. Problem 8New context

    A balanced transport network has supplies 4 and 6. One destination demands 3; all supply must be shipped. What demand must the second destination have for balance?

    Practise this exact problem →
Open stage ULP 1.2 in the student workspace →
Browse another level →
Numerive