When plotting the constraints of a linear programming problem by hand, which side of each line is shaded?

The side that does not satisfy the inequality is shaded, so the feasible region is the area left unshaded . Shading the unwanted side leaves a single blank region, which is much easier to read than a region covered by several overlapping shadings.

Whichever method is used, where in the feasible region does the optimal solution lie?

The optimal solution lies at a vertex of the feasible region. Which vertex it is depends on the gradient of the objective line, and this is why both the objective line method and the vertex method work by examining the vertices.

Describe the vertex method for solving a linear programming problem.

Find the coordinates of every vertex of the feasible region, then substitute each pair of values into the objective function and evaluate it. The vertex giving the largest or the smallest value, as the problem requires, is the optimal solution.

True or False? The origin must be included in the list of vertices even when it is obvious it will not give the maximum.

True. Wherever the origin lies in the feasible region it is still a vertex of that region, so the vertex method requires it to be listed and tested alongside all the others.

True or False? The best of the four integer points around the optimal solution is always the best integer solution to the problem.

False. Depending on the gradient of the objective line there can be an integer point elsewhere in the feasible region giving a better value of the objective function. The point found from the four surrounding integers is the one closest to the optimal solution , which is not the same thing as the best integer solution.

A LevelFurther MathsEdexcelDecision 1FlashcardsLinear programmingGraphical Solution of LP problems

Graphical Solution of LP problems (Edexcel A Level Further Maths: Decision 1): Flashcards

Exam code: 9FM0

1/13

0Still learning

Know0

FrontSolving a Linear Programming Problem Graphically
Define the feasible region of a linear programming problem.

Was this flashcard helpful?

Cards in this collection (13)

Define the feasible region of a linear programming problem.
The feasible region is the set of all values of the decision variables that satisfy every constraint at once, including the non-negativity constraint.
On a graph it is the area satisfying all of the inequalities, and it is usually labelled $R$ .
When plotting the constraints of a linear programming problem by hand, which side of each line is shaded?
The side that does not satisfy the inequality is shaded, so the feasible region is the area left unshaded.
Shading the unwanted side leaves a single blank region, which is much easier to read than a region covered by several overlapping shadings.
In a linear programming graph, when is a constraint drawn as a solid line and when as a dotted line?
A solid line is used for a constraint involving $\leq$ or $\geq$ , because the points on the line itself satisfy the constraint.
A dotted line is used for a strict inequality, which is rare in linear programming problems.
Does the point $(6, 4)$ lie in the feasible region defined by the following three constraints?
$x + y \leq 10$
$3 x + 2 y \leq 24$
$x + 2 y \leq 18$
No. The point $(6, 4)$ satisfies $x + y \leq 10$ and $x + 2 y \leq 18$ , but $3 \times 6 + 2 \times 4 = 26$ , which is greater than 24.
A point lies in the feasible region only if it satisfies every constraint, so failing a single one is enough to rule it out.
Define the objective line.
The objective line is the straight line obtained by fixing the objective function $P = a x + b y$ at one particular value of $P$ .
Rearranging gives a line of the form $y = m x + c$ , and each different value of $P$ gives a different line parallel to it.
Complete the rearrangement that turns the objective function into the equation of the objective line:
$P = a x + b y \Rightarrow y =______x + \frac{P}{b}$
The completed rearrangement is:
$P = a x + b y \Rightarrow y = - \frac{a}{b} x + \frac{P}{b}$
The gradient $- \frac{a}{b}$ does not involve $P$ , which is why every objective line for a given problem is parallel to every other one.
In a maximisation problem, which way does the objective line move as the value of $P$ increases?
The objective line moves away from the origin, towards the upper boundaries of the feasible region.
In a minimisation problem the opposite happens, and decreasing the objective function moves the line towards the origin.
Whichever method is used, where in the feasible region does the optimal solution lie?
The optimal solution lies at a vertex of the feasible region.
Which vertex it is depends on the gradient of the objective line, and this is why both the objective line method and the vertex method work by examining the vertices.
How do you find the coordinates of a vertex of the feasible region that cannot be read off the graph?
Solve the equations of the two constraint boundaries that meet there as a pair of simultaneous equations.
For example, the vertex where the boundaries of $x + y \leq 8$ and $x + 4 y \leq 17$ meet is found by solving $x + y = 8$ together with $x + 4 y = 17$ .
Describe the vertex method for solving a linear programming problem.
Find the coordinates of every vertex of the feasible region, then substitute each pair of values into the objective function and evaluate it.
The vertex giving the largest or the smallest value, as the problem requires, is the optimal solution.
True or False?
The origin must be included in the list of vertices even when it is obvious it will not give the maximum.
True.
Wherever the origin lies in the feasible region it is still a vertex of that region, so the vertex method requires it to be listed and tested alongside all the others.
The optimal solution to a problem is $x = 3.2$ and $y = 4.7$ , but the decision variables must be whole numbers. What do you do?
Test the four integer points surrounding it, which here are $(3, 4)$ and $(3, 5)$ and $(4, 4)$ and $(4, 5)$ .
Check which of them satisfy all of the constraints, then evaluate the objective function at those that do and take the best value.
True or False?
The best of the four integer points around the optimal solution is always the best integer solution to the problem.
False.
Depending on the gradient of the objective line there can be an integer point elsewhere in the feasible region giving a better value of the objective function.
The point found from the four surrounding integers is the one closest to the optimal solution, which is not the same thing as the best integer solution.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:Linear Programming (LP) problemsNext:Simplex Algorithm