Simplex algorithm

A furniture company makes three types of wardrobes.

Each Type A wardrobe requires 4 hours of machine time, 6 hours of craftsman time and 2 hours of finishing time.

Each Type B wardrobe requires 3 hours of machine time, 5 hours of craftsman time and 11 hours of finishing time.

Each Type C wardrobe requires 5 hours of machine time, 4 hours of craftsman time and 4 hours of finishing time.

Each month, there is a maximum of 200 hours of machine time, 160 hours of craftsman time and 144 hours of finishing time.

The company makes £16 profit on each Type A wardrobe, £20 profit on each Type B wardrobe and £14 profit on each Type C wardrobe. The company wants to make as much profit P as possible.

Let x, y and z denote the number of Type A, Type B and Type C wardrobes made each month.

Write down the objective function for this problem.

Complete the table in the Printed Answer Booklet to represent the problem as an initial

simplex tableau. You should use the first blank row for your objective function.

Show the calculations used to find the pivot element for the first iteration of the simplex

algorithm.

Carry out one iteration of the simplex algorithm. You should give each entry in exact

form.

Determine the value of k.

Complete the table in the Printed Answer Booklet to represent the problem as an initial

simplex tableau.

Carry out one iteration of the simplex algorithm.

State the values of x, y and z that result from your iteration.

An initial simplex tableau is given below.

Carry out two iterations of the simplex algorithm, choosing the first pivot from the x column.

After three iterations the resulting tableau is as follows.

State the values of P, x, y, z, s and t that result from these three iterations.

Explain why no further iterations are possible.

The initial simplex tableau is changed to the following, where k is a positive real value.

After one iteration of the simplex algorithm the value of P is 500.

Deduce the value of k.

Represent this problem as an initial simplex tableau.

Carry out one iteration of the simplex algorithm.

Write down the exact values of the basic feasible solution for x, y and z after two

iterations.

State what you can deduce about the optimal value of the objective for the original

problem.

You are now given that, in addition to the constraints above, x + y + z = 9.

Use the additional constraint to rewrite the original constraints in terms of x and y but not z.

Explain why the simplex algorithm cannot be applied to this new problem without some

modification.

An initial simplex tableau is shown below.

The variables s, t and u are slack variables.

For the LP problem that this tableau represents, write down the following, in terms of x and y only.

• The objective function, P, to be maximised.

• The constraints as inequalities.

The graph below shows the feasible region for the problem (as the unshaded region, and its boundaries), and objective lines P = 10 and P = 20 (shown as dotted lines).

The optimal solution is P = 23, when x = 0 and y = 4.6.

Complete the first three rows of branch-and-bound in the Printed Answer Booklet, branching on y first, to determine an optimal solution when x and y are constrained to take integer values.

In your working, you should show non-integer values to 2 decimal places.

The tableau entry 18.8 is reduced to 0.

Describe carefully what changes, if any, this makes to the following.

• The graph of the feasible region.

• The optimal integer valued solution.

An initial simplex tableau is shown below.

Write down the objective for the problem that is represented by this initial tableau.

Variables s and t are slack variables.

Use the final row of the initial tableau to explain what a slack variable is.

Carry out one iteration of the simplex algorithm and hence:

• give the pivot column used and the value of the pivot element

• write down the value of P after this iteration

• find the values of x, y and z after this iteration

• describe the effect of the iteration geometrically.