Simplex algorithm

A two person zero-sum game is represented by the pay-off matrix for player A shown above.

Verify that there is no stable solution to this game.

Let player A play option X with probability p

Use a graphical method to find the optimal value of p and hence find the best strategy for player A in this game.

A third option, Z, is added to player A’s options. Option Z has the pay-offs shown in the matrix below.

Player A now intends to make a random choice between options X, Y and Z, choosing option X with probability x, option Y with probability y and option Z with probability z

Player A decides to use the Simplex algorithm to find the optimal values of x, y and z

Determine an initial Simplex tableau to solve this 33 game, making your variables clear.

In the optimal Simplex tableau for this 3×3 game, x = 0 and y =

By considering the values of the two games, determine how much better the 33 game (with option Z) is for player A compared with the 2×3 game (without option Z). You must make your reasoning clear.

Two friends, Anaira and Tommi, play a game involving two positive numbers x and y

Anaira gives Tommi the following clues to see if he can correctly determine the value of x and the value of y

• x is greater than y and the difference between the two is at least 100

• x is at most 5 times as large as y

• the sum of 2 x and 3 y is at least 350

• the sum of x and y is as small as possible

Tommi decides to solve this problem by using the big-M method.

Set up an initial tableau for solving this problem using the big-M method.

As part of your solution, you must show

• how the constraints were made into equations using one slack variable, exactly two surplus variables and exactly two artificial variables

• how the objective function was formed

The big-M method is applied until the tableau containing the optimal solution to the problem is found. One row of this final tableau is as follows.

b.v.	x	y	s1	s2	s3	a1	a2	Value
x	1	0	53	0	15	3 5	1 5	130

State the value of x

Hence deduce the value of y, making your reasoning clear.

A maximisation linear programming problem in x, y and z is to be solved using the Simplex method.

The tableau after the 1st iteration is shown below.

b.v.	x	y	z	s1	s2	s3	Value
s1	0	12	3 2	1	12	0	30
x	1	1 4	14	0	1 4	0	10
s3	0	1	1	0	0	1	26
P	0	14	114	0	3 4	0	30

State the column that contains the pivot value for the 1st iteration. You must give a reason for your answer.

By considering the equations represented in the above tableau, formulate the linear programming problem in x, y and z only. State the objective and list the constraints as inequalities with integer coefficients.

Taking the most negative number in the profit row to indicate the pivot column, perform the 2nd iteration of the Simplex algorithm, to obtain a new tableau, T. Make your method clear by stating the row operations you use.

Explain, using T, how you know that an optimal solution to the original linear programming problem has not been found after the 2nd iteration.

State the values of the basic variables after the 2nd iteration.

A student attempts the 3rd iteration of the Simplex algorithm and obtains the tableau below.

b.v.	x	y	z	s1	s2	s3	Value
z	0	0	1	1 2	14	1 4	43 2
x	1	0	0	1 4	1 8	18	57 4
y	0	1	0	12	1 4	3 4	9 2
P	0	1	0	5 4	1 8	7 8	361 4

Explain how you know that the student’s attempt at the 3rd iteration is not correct.

A linear programming problem in x, y and z is to be solved using the big‑M method. The initial tableau is shown below.

Using the information in the above tableau, formulate the linear programming problem. You should

• list each of the constraints as an inequality

• state the two possible objectives

Obtain the most efficient pivot for a first iteration of the big‑M method. You must give reasons for your answer.

Please turn over for Question 5

Figure 5 shows the constraints of a linear programming problem in x and y where R is the feasible region.

The objective is to maximise P = x + ky, where k is a positive constant.

The optimal vertex of R is to be found using the Simplex algorithm.

Set up an initial tableau for solving this linear programming problem using the Simplex algorithm.

After two iterations of the Simplex algorithm a possible tableau T is

b.v.	x	y	s1	s2	s3	s4	Value
s1	0	0	1	53	0	1 5	1
x	1	0	0	1 5	0	52	2
s3	0	0	0	115	1	12 5	22
y	0	1	0	2 5	0	1 5	5
P	0	0	0	15 52 k	0	52 15 k	5k + 2

State the value of each variable after the second iteration.

It is given that T does not give an optimal solution to the linear programming problem.

After a third iteration of the Simplex algorithm the resulting tableau does give an optimal solution to the problem.

Perform the third iteration of the Simplex algorithm and hence determine the range of possible values for P. You should state the row operations you use and make your method and working clear.

A two person zero‑sum game is represented by the pay‑off matrix for player A shown above. It is given that k is an integer.

Show that Q is the play‑safe option for player A regardless of the value of k.

Given that Z is the play‑safe option for player B,

determine the range of possible values of k. You must make your working clear.

Explain why player B should never play option X. You must make your reasoning clear.

Player A intends to make a random choice between options Q, R and S, choosing option Q with probability p₁, option R with probability p₂ and option S with probability p₃

Player A wants to find the optimal values of p₁, p₂ and p₃ using the Simplex algorithm.

Given that k –4, player A formulates the following objective function for the corresponding linear program.

Maximise P = V, where V = the value of the original game + 4

Formulate the constraints of the linear programming problem for player A. You should write the constraints as equations.

Write down an initial Simplex tableau, making your variables clear.

The Simplex algorithm is used to solve the linear programming problem. It is given that in the final Simplex tableau the optimal value of p = , the optimal value of p = and all the slack variables are zero.

Determine the value of k, making your method clear.

Susie is preparing for a triathlon event that is taking place next month. A triathlon involves three activities: swimming, cycling and running.

Susie decides that in her training next week she should

• maximise the total time spent cycling and running

• train for at most 39 hours

• spend at least 40% of her time swimming

• spend a total of at least 28 hours of her time swimming and running

Susie needs to determine how long she should spend next week training for each activity. Let

• x represent the number of hours swimming

• y represent the number of hours cycling

• z represent the number of hours running

Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients.

Susie decides to solve this linear programming problem by using the two-stage Simplex method.

Set up an initial tableau for solving this problem using the two-stage Simplex method.

As part of your solution you must show how

• the constraints have been made into equations using slack variables, exactly one surplus variable and exactly one artificial variable

• the rows for the two objective functions are formed

The following tableau T is obtained after one iteration of the second stage of the two‑stage Simplex method.

Obtain a suitable pivot for a second iteration. You must give reasons for your answer.

Starting from tableau T, solve the linear programming problem by performing one further iteration of the second stage of the two-stage Simplex method. You should make your method clear by stating the row operations you use.

A maximisation linear programming problem in x, y and z is to be solved using the two-stage simplex method.

The partially completed initial tableau is shown below.

Using the information in the above tableau, formulate the linear programming problem. State the objective and list the constraints as inequalities.

Complete the bottom row of Table 1 in the answer book. You should make your method and working clear.

The following tableau is obtained after two iterations of the first stage of the two-stage simplex method.

Basic variable	x	y	z	s1	s2	s3	a1	a2	Value
s1	0	5 6	0	1	7 12	3 4	127	34	147 4
x	1	2 3	0	0	13	0	1 3	0	3
z	0	1 6	1	0	121	14	1 12	1 4	7 4
P	0	5 6	0	0	1211	34	11 12	3 4	45 4
A	0	0	0	0	0	0	1	1	0

Explain how the above tableau shows that a basic feasible solution has been found for the original linear programming problem.

Write down the basic feasible solution for the second stage.

Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the second stage of the two-stage simplex method, to obtain a new tableau, T. Make your method clear by stating the row operations you use.

Explain, using T, whether or not an optimal solution to the original linear programming problem has been found.

Write down the value of the objective function.

State the values of the basic variables.

A linear programming problem in x, y and z is described as follows.

Maximise P = 2x + 2yz

subject to 3x + y + 2z 30

Explain why the Simplex algorithm cannot be used to solve this linear programming problem.

Set up the initial tableau for solving this linear programming problem using the big-M method.

After a first iteration of the big-M method, the tableau is

b.v.	x	y	z	s1	s2	s3	a1	a2	Value
s1	3	0	1.5	1	0	0.25	0		26.25
a1	1	0	1.5	0			1	0.25	11.75
y	0	1	0.5	0	0		0	0.25	3.75
P	M)	0	M	0	M	M	0	0.5 + 0.75M	M

State the value of each variable after the first iteration.

Explain why the solution given by the first iteration is not feasible.

Taking the most negative entry in the profit row to indicate the pivot column,

obtain the most efficient pivot for a second iteration. You must give reasons for your answer.

A two person zero-sum game is represented by the pay-off matrix for player A shown above.

Verify that there is no stable solution to this game.

Player A intends to make a random choice between options P, Q and R, choosing option P with probability p₁, option Q with probability p₂ and option R with probability p₃

Player A wants to find the optimal values of p₁, p₂ and p₃ using the Simplex algorithm. Player A formulates the following linear programming problem for the game, writing the constraints as inequalities.

Maximise P = V

Correct the errors made by player A in the linear programming formulation of the game, giving reasons for your answer.

Write down an initial Simplex tableau for the corrected linear programming problem.

The Simplex algorithm is used to solve the corrected linear programming problem.

The optimal values are p₁ = 0.6, p₂ = 0 and p₃= 0.4

Calculate the value of the game to player A.

Determine the optimal strategy for player B, making your reasoning clear.