Linear Programming Examples: 47 Problems with Answers

Worked examples of Linear Programming to try before you open each solution, then practice problems with answers.

Worked Examples

Example 1

medium
Maximize z=3x+2y subject to x+y≤4, x≥0, y≥0.
Show solution

Answer

z=12 at (4,0)

First step

1.
Step 1: Identify the feasible region: the triangle with vertices (0,0), (4,0), (0,4).

See the full worked solution + why-it-works coaching

SetupKey insightWhy it worksCommon pitfallConnection

Free: full solutions on 3 topics a day. No card.

Every topic, every day: the Family plan

Example 2

hard
Minimize z=2x+5y subject to x+2y≥6, x+y≥4, x≥0, y≥0.

Example 3

medium
Maximize P=5x+6y subject to x+y≤8, 2x+y≤12, x,y≥0.

Example 4

medium
Find the feasible vertex of x+y≤6 and 2x+y≤8 in the first quadrant where the two lines meet.

Example 5

hard
A farmer plants wheat (x acres, $200 profit/acre) and corn (y acres, $300 profit/acre). Wheat needs 1 hour labor/acre; corn needs 2 hours. Total land ≤50 acres; labor ≤80 hours. Find the best mix.

Example 6

hard
Show that if the objective is parallel to a binding constraint, there can be infinitely many optimal solutions.

Practice Problems

Try each one, then open the solution to compare your method.

Example 1

easy
A feasible region has vertices at (0,0), (5,0), (3,4), (0,6). Maximize z=x+2y.

Example 2

medium
A company makes chairs ($40 profit) and tables ($70 profit). Each chair takes 2 hours, each table takes 5 hours. With 40 hours available, maximize profit.

Example 3

easy
Evaluate the objective P=3x+2y at the corner point (2,1).

Example 4

easy
Does the point (1,1) satisfy the constraint x+y≤5?

Example 5

easy
Is (6,0) feasible under x+y≤5 with x,y≥0?

Example 6

easy
At which of (0,0) and (3,3) is P=x+y larger?

Example 7

easy
State the non-negativity constraints for a problem producing x chairs and y tables.

Example 8

easy
Write a constraint: a worker has at most 8 hours, using 2 hours per unit of x.

Example 9

easy
A constraint says production must be at least 10 units of x. Write it.

Example 10

easy
How many corner points does a triangular feasible region have to check?

Example 11

medium
Maximize P=2x+3y over corners (0,0), (4,0), (0,3), (2,2).

Example 12

medium
Minimize C=x+2y over corners (1,4), (3,1), (5,2).

Example 13

medium
Find the intersection of x+y=4 and x−y=2 (a corner point).

Example 14

medium
A shop profits $4 per x and $5 per y. Write the objective to maximize.

Example 15

medium
Region: x≥0, y≥0, x+y≤6. Maximize P=x+y.

Example 16

medium
Is the feasible region for x≥0, y≥0, x+y≥2 bounded or unbounded?

Example 17

medium
Maximize P=5x+4y subject to x≤4, y≤3, x,y≥0.

Example 18

medium
A constraint 2x+3y≤12 meets the x-axis where?

Example 19

challenge
Maximize P=3x+4y over x+y≤4, x+3y≤6, x,y≥0. Find the optimum.

Example 20

challenge
A factory makes x,y with profit P=40x+30y, limits x+y≤8 (labor), 2x+y≤10 (material), x,y≥0. Maximize.

Example 21

challenge
Why must the optimum of a linear objective on a bounded polygon occur at a vertex?

Example 22

medium
Maximize P=x+2y over corners (0,0), (0,5), (4,3), (6,0).

Example 23

easy
Evaluate P=4x+3y at the corner (2,5).

Example 24

easy
Is (3,4) feasible for x+2y≤12, x,y≥0?

Example 25

easy
Find the corner of the region x≥0, y≥0, x+y≤10 that maximizes P=2x+5y.

Example 26

easy
Find where 3x+4y=24 crosses the y-axis.

Example 27

easy
Minimize C=x+y over corners (0,2), (3,0), (2,1).

Example 28

medium
Find the intersection of 2x+y=10 and x+y=6.

Example 29

medium
A bakery makes muffins ($2 profit each) and scones ($3 profit each). Each muffin uses 1 oz of butter; each scone uses 2 oz. They have 20 oz of butter and want at most 15 items total. Write the LP.

Example 30

medium
Maximize P=2x+3y subject to x+2y≤20, x+y≤15, x,y≥0.

Example 31

medium
Minimize C=3x+2y subject to x+y≥5, 2x+y≥8, x,y≥0.

Example 32

medium
Maximize P=6x+4y subject to x+y≤10, 2x+3y≤24, x,y≥0.

Example 33

medium
Maximize P=x+y over the region x+y≤4, x,y≥0.

Example 34

medium
Find where 4x+3y=24 meets the x-axis.

Example 35

medium
Is (5,4) feasible for 3x+2y≤25, x+4y≤20, x,y≥0?

Example 36

medium
At which corner is P=4x+y maximized over (0,0), (5,0), (3,4), (0,6)?

Example 37

hard
Maximize P=7x+9y subject to x+y≤6, 3x+y≤12, x+2y≤10, x,y≥0.

Example 38

hard
A diet problem: each unit of food A costs $3 and provides 4 g of protein and 1 g of fat; each unit of food B costs $2 and provides 2 g of protein and 1 g of fat. Need at least 20 g protein and at most 8 g fat. Minimize cost.

Example 39

hard
Maximize P=3x+5y on the region x+y≤4, 2x+y≤6, x,y≥0.

Example 40

challenge
A factory produces three products with profits $10,$12,$15 per unit and machine-hour costs 1,2,3 hours per unit. With 24 machine-hours available and a demand cap of 10 units per product, but no constraint linking products, what is the best single-product plan?

Example 41

challenge
Minimize C=4x+5y subject to x+y≥6, x+3y≥9, x,y≥0.

What to focus on

Core idea: Linear programming maximizes or minimizes a linear objective over a region cut out by linear constraints, and the optimum always sits at a corner of that region.

Common stuck point: The procedure for linear programming is the easy part; the trap is searching the interior for the best value. Asking "Am I optimizing a linear objective over a region bounded by linear inequalities, with the answer expected at a corner?" first is what keeps a correct-looking calculation from being attached to the wrong concept.

Ask yourself: Am I optimizing a linear objective over a region bounded by linear inequalities, with the answer expected at a corner?

Concept recap

Linear programming optimizes a linear objective subject to linear inequality or equality constraints.

Finding the optimum is like pushing a ruler across a polygon cut from paper, keeping it parallel to the profit line. The last bit of paper the ruler touches before it leaves is a corner, because the ruler and the polygon's edges are all straight. If the profit rule were curved, the last point touched could be in the middle of a side.

Read the full lesson on Linear Programming

Background knowledge

These ideas may be useful before you work through the harder examples.

inequalitiessystems of equationsconstraint system