Linear programming

The table below shows the cost, in pounds, of transporting one unit of stock from each of four supply points, A, B, C and D, to three demand points, P, Q and R. It also shows the stock held at each supply point and the number of units required at each demand point.

A minimum cost solution is required.

Use the north-west corner method to obtain an initial solution to this transportation problem.

Perform one iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by showing the route and stating the

• shadow costs

• improvement indices

• entering cell and exiting cell

Formulate the transportation problem as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.

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

A standard transportation problem is described in the linear programming formulation below.

Let x_ij be the number of units transported from i to j

where i i {A, B, C, D}

Minimise P x_AR + 17x_AS + 24x_AT + 15x_BR + 29x_BS + 32x_BT

subject to

Given that the problem is balanced,

state the value of k.

transportation problem.

Use the north‑west corner method to obtain the cost of an initial solution to this transportation problem.

Perform one iteration of the stepping‑stone method to obtain an improved solution. You must make your method clear by showing the route and the

• shadow costs

• improvement indices

• entering cell and exiting cell.

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.

Four workers, A, B, C and D, are to be assigned to three tasks, 1, 2 and 3. Each task must be assigned to just one worker and each worker can do one task only.

Worker A cannot do task 2 and worker D cannot do task 3

The cost of assigning each worker to each task is shown in the table below.

The total cost is to be minimised.

Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.

Alexis and Becky are playing a zero‑sum game.

Alexis has two options, Q and R. Becky has three options, X, Y and Z.

Alexis intends to make a random choice between options Q and R, choosing option Q with probability p₁ and option R with probability p₂ Alexis wants to find the optimal values of p₁ and p₂ and formulates the following linear programme, writing the constraints as inequalities.

Maximise P = V

where V = 3 + the value of the game to Alexis

subject=to=$V 6p₁ + p₂

Complete the pay‑off matrix for Alexis in the answer book.

Use a graphical method to find the best strategy for Alexis.

Calculate the value of the game to Alexis.

Becky intends to make a random choice between options X, Y and Z, choosing option X with probability q₁, option Y with probability q₂ and option Z with probability q₃

Determine the best strategy for Becky, making your method and working clear.

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.

Table 1 shows the cost, in pounds, of transporting one unit of stock from each of four supply points, A, B, C and D, to three sales points, P, Q and R. It also shows the number of units held at each supply point and the number of units required at each sales point. A minimum cost solution is required.

Table 2 shows an initial solution given by the north-west corner method.

Taking AR as the entering cell, use the stepping-stone method to find an improved solution. Make your method clear.

Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by stating ●shadow costs ●improvement indices ●route ●entering cell and exiting cell.

Determine whether the solution obtained from this second iteration is optimal, giving the reason for your answer.

Formulate this situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.

Explain why the Simplex algorithm cannot be used to solve transportation linear programming problems such as that formulated in (d).

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

Explain, with justification, why this matrix may be reduced to a 3 × 3 matrix by removing option S from player A’s choices.

Verify that there is no stable solution to the reduced game.

Player A intends to make a random choice between options Q, R and T, choosing option Q with probability p₁, option R with probability p₂ and option T 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 programme, writing the constraints as inequalities.

Maximise P=V, where V= the value of original game + 3 subject to V ≤4p₁+ 7p₂+ 6p₃ V 8p₁+p₃ V 6p₁+ 4p₂+ 3p₃ p₁+p₂+p₃ 1 p₁ 0, p₂ 0, p₃ 0, V 0

Explain why V cannot exceed any of the following expressions

Explain why it is necessary to use the constraint p₁+p₂+p₃ ≤1

The Simplex algorithm is used to solve the linear programming problem. Given that the optimal value of p = and the optimal value of p = 0

calculate the value of the game to player A.

Player B intends to make a random choice between options X, Y and Z, choosing option X with probability q₁, option Y with probability q₂ and option Z with probability q₃

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

A shop sells two types of watch, analogue watches and digital watches.

The shop manager knows that, each month, she should order at least 60 watches in total. In addition, at most 80% of the watches she orders must be digital.

Let x be the number of analogue watches ordered and let y be the number of digital watches ordered.

Write down inequalities, in terms of x and y, to model these constraints.

Two further constraints are

Represent all these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region, R.

The cost to the shop of ordering an analogue watch is five times the cost of ordering a digital watch. The shop manager wishes to minimise the total cost.

Determine the number of each type of watch the shop manager should order. You must make your method clear.

Given that the minimum total cost of ordering the watches is £4455

determine the cost of ordering one analogue watch and the cost of ordering one digital watch. You must make your method clear.

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.