Linear programming flashcards

Test yourself one card at a time: say the answer, flip, then mark it. Cards you know drop out; the rest come back until you know them. Your progress stays in this browser.

Decision variables
The quantities you choose in a linear programming problem, e.g. x = the number of vases made each week. Define them precisely, with units and time period.
Constraint
A linear inequality that a feasible solution must satisfy, coming from a limited resource, a minimum requirement or a ratio.
Non-negativity constraints
x ≥ 0 and y ≥ 0: the decision variables cannot be negative.
Objective function
The linear expression to be maximised or minimised, e.g. maximise P = 15x + 12y.
Feasible region
The set of all points that satisfy every constraint; usually labelled R on the graph.
Optimal solution
A feasible solution that gives the best (largest or smallest) value of the objective function.
Unbounded feasible region
A region that extends without limit in some direction; a positive objective then has no maximum but may have a minimum.
Gradient of the objective line P = ax + by
−a/b (all objective lines are parallel). (No — derive it)
Intercepts of the boundary line ax + by = c
(c/a, 0) and (0, c/b). (No — derive it)
“At least p% of the total is x” as an inequality
x ≥ (p/100)(x + y), then clear fractions, e.g. 25%: 3x ≥ y. (No — learn it)
“At least m of y for every n of x” as an inequality
ny ≥ mx. (No — learn it)
Condition for a vertex to be optimal
The objective gradient −a/b lies between the gradients of the two boundary lines meeting at that vertex. (No — derive it)
Standard layout of a formulation
Maximise (or minimise) P = ax + by subject to the constraints, x ≥ 0, y ≥ 0. (No — learn it)
Deciding which side of 3x + 2y = 60 satisfies 3x + 2y ≤ 60
Test O: 0 ≤ 60 is true, so the side containing O is allowed.
Drawing a ratio constraint such as y ≤ 3x
The boundary y = 3x passes through O; plot a second point, e.g. (10, 30), and test a point not on the line such as (1, 0).
Objective line method for a maximum
Draw one objective line, slide a ruler parallel to it away from O; the last point of R it touches is optimal.
Objective line method for a minimum
Slide the objective line parallel to itself towards O; the last point of R it touches is optimal.
Objective line parallel to an edge of R
Every point on that edge is optimal — the optimum is not unique.
Why is the optimum always at a vertex?
Objective lines are parallel; sliding one across a convex region, the last contact is at a corner (or along a whole edge containing two corners).
Why can rounding an optimal vertex give the wrong integer answer?
The rounded point may break a constraint, or a different nearby integer point may give a better value. Test the nearby integer points.
When is y ≥ 0 not needed in a formulation?
When a stronger constraint such as y ≥ 3 already implies it (writing it anyway is not wrong).
Vertex method
Find the exact coordinates of every vertex of R, evaluate the objective at each, and pick the best value.
Why must the vertices be found by algebra?
Vertices are often fractions, e.g. (105/19, 110/19), which cannot be read accurately from a graph.
Maximise P = 15x + 12y subject to 3x + 2y ≤ 60, x + 2y ≤ 32, y ≥ 3, x ≥ 0
Vertices (0, 3), (18, 3), (14, 9), (0, 16); P = 36, 306, 318, 192. Maximum 318 at (14, 9).
Minimise C = 400x + 250y subject to x + y ≥ 60, y ≤ 3x, y ≥ 20
Vertices (15, 45) and (40, 20); C = 17 250 and 21 000. Minimum £17 250 at (15, 45); the region is unbounded, so there is no maximum.
Write “at most 30% of the total is y” as an inequality with integer coefficients
y ≤ 0.3(x + y) → 10y ≤ 3x + 3y → 7y ≤ 3x.
Best integer point for P = 40x + 30y with 5x + 3y ≤ 45, 2x + 5y ≤ 40 (vertex ≈ (5.53, 5.79))
Test nearby points: (5, 5) £350, (5, 6) £380, (6, 5) £390, (6, 6) not feasible. Best (6, 5), £390.
(15, 10) is where 2x + 3y = 60 and 4x + 3y = 90 meet. For which k is it optimal for P = 30x + ky?
Need −30/k between −4/3 and −2/3: 2/3 ≤ 30/k ≤ 4/3, so 22.5 ≤ k ≤ 45.
Solve 3x + 2y = 60 and x + 2y = 32
Subtract: 2x = 28, x = 14, y = 9 — the vertex (14, 9).
Simplify 400x + 250y ≤ 20 000
Divide by 50: 8x + 5y ≤ 400.
Defining variables as “x = vases”
Too vague: write “x = the number of vases made each week”.
“x is at most three times y” written as 3x ≤ y
Reversed: it is x ≤ 3y. Test with numbers, e.g. x = 30, y = 10 must be allowed.
Mixed units in a constraint
Convert first: 6 hours = 360 minutes, 4.8 kg = 4800 g, then simplify.
Finding the optimum without showing a method
Draw and label an objective line on the graph, or tabulate the objective at every vertex.
Integer answer required, vertex not integer
Do not just round: test nearby integer points against every constraint and compare objective values; state the answer in context.
Labelling the feasible region
Label it R and say whether you shaded the region you want or the regions you do not want.

Practise this topicNotes Questions (28)Test builder