Formulating linear programs

Formulating linear programs Flashcards

Spec 5.1 · Edexcel A-Level Further Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

13 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 13 cards
What are the three parts of a linear program?
Decision variables, an objective function to maximise or minimise, and linear constraints (with non-negativity).
What does 'at most' translate to?
≤\le
What does 'at least' translate to?
≥\ge
How is a ≤\le constraint made into an equation?
Add a slack variable: 3x+2y≤20→3x+2y+s1=203x+2y\le20\to3x+2y+s_1=20.
What does a slack variable represent?
The unused amount of a resource.
What does a slack variable of 0 mean?
The constraint is binding: the resource is fully used.
How is a ≥\ge constraint made into an equation?
Subtract a surplus variable: x+y≥5→x+y−s=5x+y\ge5\to x+y-s=5.
What does a surplus variable represent?
The amount by which the requirement is exceeded.
Why is an artificial variable needed?
A surplus variable alone gives −s=5-s=5 at the origin, so there is no starting basic feasible solution; t1t_1 provides one.
Write x+y≥5x+y\ge5 with surplus s3s_3 and artificial t1t_1.
x+y−s3+t1=5x+y-s_3+t_1=5
Which constraint types get an artificial variable?
≥\ge and == constraints.
What must an artificial variable equal in a genuine solution?
Zero.
Rewrite the objective P=3x+5yP=3x+5y for a Simplex tableau.
P−3x−5y=0P-3x-5y=0

Flashcards