Linear programming

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.

Sasha is making three identical bead bracelets using amber, brown and red coloured beads. Sasha has 20 amber beads, 12 brown beads and 10 red beads.

Each bracelet must use exactly 12 beads.

The profit from selling a bracelet is 6 pence for each amber bead used plus 2 pence for each brown bead used plus 3 pence for each red bead used.

Sasha wants to maximise the total profit from selling the three bracelets.

Express Sasha’s problem as a linear programming formulation in two variables a and b, where a represents the number of amber beads in each bracelet and b represents the number

of brown beads in each bracelet.

Determine how many beads of each colour will be used in each bracelet.

By listing all the feasible solutions, identify an aspect of the optimal solution, other than the

profit, that is different from all the other feasible solutions.

The beads that are not used in making the bracelets can be sold.

The profit from selling each amber bead is k pence, where k is an integer, but nothing for each brown or red bead sold.

All the previous constraints still apply.

Instead of maximising the profit from the bracelets, Sasha wants to maximise the total profit from selling the bracelets and any left over beads.

You are given that the optimal solution to the earlier problem does not maximise the total profit from selling the bracelets and any left over beads.

Determine the least possible value of Sasha’s maximum total profit.

Why might Sasha not achieve this maximum profit?

Player 1 and player 2 are playing a two-person zero-sum game.

In each round of the game the players each choose a strategy and simultaneously reveal their choice.

The number of points won in each round by player 1 for each combination of strategies is shown in the table below.

Each player is trying to maximise the number of points that they win.

Determine play-safe strategies for each player.

Show that the game is not stable.

Show that the number of strategies available to player 1 cannot be reduced by dominance.

You must make it clear which values are being compared.

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.

Alex and Beth play a zero-sum game. Alex chooses a strategy P, Q or R and Beth chooses a strategy X, Y or Z. The table shows the number of points won by Alex for each combination of strategies. The entry for cell (P, X) is x, where x is an integer.

Suppose that P is a play-safe strategy.

Determine the values of x for which the game is stable.

Determine the values of x for which the game is unstable.

The game can be reduced to a 2 × 3 game using dominance.

Write down the pay-off matrix for the reduced game.

When the game is unstable, Alex plays strategy P with probability p.

Determine, as a function of x, the value of p for the optimal mixed strategy for Alex.

Suppose, instead, that P is not a play-safe strategy and the value of x is - 5.

Show how to set up a linear programming formulation that could be used to find the optimal

mixed strategy for Alex.

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.