Why is the simplex algorithm used instead of the graphical method?

The graphical method needs the problem drawn on a set of axes, so it only works with two decision variables. The simplex algorithm works with any number of decision variables, because it is carried out on a table rather than on a graph.

What has to be true of a linear programming problem before the simplex algorithm can be applied directly?

The problem must have a basic feasible solution to start from, and where the feasible region contains the origin that solution is the origin itself. Where the feasible region does not contain the origin, the algorithm has to be adapted so that a basic feasible solution is found first.

How do you decide which variable to write in the basic variable column of a tableau row?

The basic variable for a row is the variable whose column holds a 1 in that row and 0 in every other row . The basic variable column is filled in last , once the rest of the tableau is complete, and the bottom row is always the objective row.

Once the pivot element has been found, what two things must the row operations achieve?

The pivot row is scaled so that the pivot element becomes 1 . A multiple of that new pivot row is then added to or subtracted from every other row, the objective row included, so that every other entry in the pivot column becomes 0 .

How do you know that the simplex algorithm is complete?

The algorithm is complete once there are no negative entries in the objective row, ignoring the Value column. That tableau is called the final tableau , and the optimal solution is read from it.

How is the optimal solution read from the final tableau?

Each variable listed in the basic variable column takes the number in the Value column of its own row, and the objective function takes the Value in its row. Every other variable is non-basic and takes the value zero .

True or False? A variable that is not in the basic variable column still takes a value from its own column in the final tableau.

False. A non-basic variable is always zero , and the numbers standing in its column are part of the tableau's working rather than a value for that variable.

In an iteration of the simplex algorithm, what do you do if two columns tie for the most negative entry?

Either of the tied columns may be chosen as the pivot column, and it is usual to take the first of them. The choice changes the intermediate tableaux but not the final answer, since the method allows it to be made freely.

A LevelFurther MathsEdexcelDecision 1FlashcardsLinear programmingSimplex Algorithm

Simplex Algorithm (Edexcel A Level Further Maths: Decision 1): Flashcards

Exam code: 9FM0

1/28

0Still learning

Know0

FrontSimplex Algorithm - Slack Variables & Initial Tableau
Why is the simplex algorithm used instead of the graphical method?

Was this flashcard helpful?

Cards in this collection (28)

Why is the simplex algorithm used instead of the graphical method?
The graphical method needs the problem drawn on a set of axes, so it only works with two decision variables.
The simplex algorithm works with any number of decision variables, because it is carried out on a table rather than on a graph.
What has to be true of a linear programming problem before the simplex algorithm can be applied directly?
The problem must have a basic feasible solution to start from, and where the feasible region contains the origin that solution is the origin itself.
Where the feasible region does not contain the origin, the algorithm has to be adapted so that a basic feasible solution is found first.
Define a slack variable.
A slack variable is a non-negative variable added to the left-hand side of a constraint involving $\leq$ in order to turn that inequality into an equation.
It takes up the spare capacity, or slack, that the constraint has not used.
Complete the equation formed by introducing a slack variable into the constraint $2 x + 3 y \leq 10$ :
$2 x + 3 y______s_{1} = 10$
The completed equation is:
$2 x + 3 y + s_{1} = 10$
A slack variable is always added, because it makes up the difference between the left-hand side and the limit of 10.
True or False?
A problem with four constraints involving $\leq$ needs four slack variables.
True.
One slack variable is needed for each constraint involving $\leq$ , because each inequality has to be turned into an equation separately.
The non-negativity constraints are not counted, since they are not turned into equations.
How is the objective function written before it goes into the initial tableau?
The objective function is rearranged so that all the variables sit on the same side as $P$ and zero is on the other, so $P = 8 x + 5 y + 7 z$ becomes $P - 8 x - 5 y - 7 z = 0$ .
This is why the objective row of an initial tableau holds negative coefficients.
How do you decide which variable to write in the basic variable column of a tableau row?
The basic variable for a row is the variable whose column holds a 1 in that row and 0 in every other row.
The basic variable column is filled in last, once the rest of the tableau is complete, and the bottom row is always the objective row.
How is the pivot column chosen in an iteration of the simplex algorithm?
The pivot column is the column holding the most negative entry in the objective row, ignoring the Value column.
For example, where the objective row reads $- 8$ , $- 5$ and $- 7$ across the $x$ , $y$ and $z$ columns, the pivot column is the $x$ column.
How are the $θ$ -values found, and what are they used for?
For every row except the objective row, divide the entry in the Value column by the entry in the pivot column.
The row with the least positive $θ$ -value is the pivot row, and a row whose pivot column entry is zero has no $θ$ -value at all, since the division is undefined.
Once the pivot element has been found, what two things must the row operations achieve?
The pivot row is scaled so that the pivot element becomes 1.
A multiple of that new pivot row is then added to or subtracted from every other row, the objective row included, so that every other entry in the pivot column becomes 0.
How do you know that the simplex algorithm is complete?
The algorithm is complete once there are no negative entries in the objective row, ignoring the Value column.
That tableau is called the final tableau, and the optimal solution is read from it.
How is the optimal solution read from the final tableau?
Each variable listed in the basic variable column takes the number in the Value column of its own row, and the objective function takes the Value in its row.
Every other variable is non-basic and takes the value zero.
True or False?
A variable that is not in the basic variable column still takes a value from its own column in the final tableau.
False.
A non-basic variable is always zero, and the numbers standing in its column are part of the tableau's working rather than a value for that variable.
Which two features of a linear programming problem stop the simplex algorithm being used directly?
The simplex algorithm cannot be used directly where a constraint involves $\geq$ , or where the objective function has to be minimised rather than maximised.
In both cases the two-stage simplex method is used instead.
Define a surplus variable.
A surplus variable is a non-negative variable subtracted from the left-hand side of a constraint involving $\geq$ in order to turn that inequality into an equation.
It takes up the excess that the constraint has over its lower limit.
Why must an artificial variable be introduced whenever a surplus variable is used?
A surplus variable is subtracted, so its coefficient is $- 1$ , whereas a basic variable must have a coefficient of $+ 1$ .
An artificial variable always enters with a coefficient of 1, so it supplies the basic variable that the constraint would otherwise lack.
Complete the equation formed from the constraint $2 x - y \geq 2$ using a surplus variable and an artificial variable:
$2 x - y______s_{1}______a_{1} = 2$
The completed equation is:
$2 x - y - s_{1} + a_{1} = 2$
The surplus variable is subtracted and the artificial variable is added, and that difference in sign is the thing to watch for.
What is the new objective function used in the first stage of the two-stage simplex method?
The new objective function is $I$ , defined as the negative sum of the artificial variables, so $I = - (a_{1} + a_{2} + . . . + a_{n})$ for $n$ artificial variables.
Before it goes into the tableau, each artificial variable is rewritten in terms of the decision and surplus variables and substituted in.
What is the first stage of the two-stage simplex method for, and what value should $I$ reach?
The first stage maximises $I$ in order to find a basic feasible solution to start from.
The largest value $I$ can take is 0, which happens exactly when every artificial variable has been driven to zero, since artificial variables cannot be negative.
True or False?
If $I$ is still negative at the end of the first stage, the second stage should be carried out anyway.
False.
A value of $I$ other than zero means that no basic feasible solution exists, so the problem cannot be solved and there is nothing to be gained by going on.
Only where $I = 0$ does the method continue to the second stage.
What is done to the tableau between the first and second stages?
The $I$ objective row and every artificial variable column are removed from the tableau.
The second stage is then the ordinary simplex algorithm applied to what is left, in order to maximise $P$ .
How is the two-stage simplex method used when the objective function has to be minimised?
Minimising an objective function is the same as maximising its negative, so to minimise $C = 4 x + 2 y$ you maximise $P = - 4 x - 2 y$ instead.
The method then runs exactly as it does for a maximisation problem, and at the end the answer is converted back using $C = - P$ .
In an iteration of the simplex algorithm, what do you do if two columns tie for the most negative entry?
Either of the tied columns may be chosen as the pivot column, and it is usual to take the first of them.
The choice changes the intermediate tableaux but not the final answer, since the method allows it to be made freely.
In the Big-M method, what is $M$ ?
$M$ is an arbitrarily large positive number.
It is never given a value and never needs to be calculated, because it is there only to make the sign of each objective row entry certain.
How is the objective function rewritten for the Big-M method?
Subtract $M A$ from it, where $A$ is the sum of the artificial variables.
Each artificial variable is first made the subject of its own constraint, so that $A$ can be written in terms of the decision and surplus variables before it is substituted in.
For $P = 3 x + 2 y$ with $A = 20 - 4 x - 2 y + s_{3} + s_{4}$ , complete the objective row for the Big-M method:
$P - (4 M + 3) x - (______M + 2) y + M s_{3} + M s_{4} =______M$
The completed objective row is:
$P - (4 M + 3) x - (2 M + 2) y + M s_{3} + M s_{4} = - 20 M$
Each coefficient combines the term from $P$ with the matching term from $- M A$ , so the $y$ coefficient pairs the 2 with the $2 M$ .
What is the main advantage of the Big-M method over the two-stage simplex method, and its main drawback?
The advantage is that it needs only one stage, so each tableau carries a single objective row rather than two.
The drawback is that the algebra in terms of $M$ becomes awkward to track through the row operations.
True or False?
A Big-M tableau whose objective row contains the entry $M - 7$ is not yet optimal.
False.
Since $M$ is arbitrarily large, $M - 7$ is positive, so it does not stop the tableau being optimal.
A Big-M tableau is optimal when no entry in the objective row is negative, and it is entries of the form $7 - M$ that are.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:Graphical Solution of LP problems