7.06a LP formulation: variables, constraints, objective function

3 Ben is packing eggs into boxes, labelled Town Box or Country Box. Each Town Box must contain 10 chicken eggs and 2 duck eggs. Each Country Box must contain 4 chicken eggs and 8 duck eggs. Ben has 253 chicken eggs and 151 duck eggs. Ben wants to pack as many boxes as possible. Formulate Ben's situation as a linear programming problem, defining any variables you introduce.

8 A family business makes and sells two kinds of kitchen table.
Each pine table takes 6 hours to make and the cost of materials is \(\pounds 30\).
Each oak table takes 10 hours to make and the cost of materials is \(\pounds 70\).
Each month, the business has 360 hours available for making the tables and \(\pounds 2100\) available for the materials.
Each month, the business sells all of its tables to a wholesaler.
The wholesaler specifies that it requires at least 10 oak tables per month and at least as many pine tables as oak tables. Each pine table sold gives the business a profit of \(\pounds 40\) and each oak table sold gives the business a profit of \(\pounds 75\). Use a graphical method to find the number of each type of table the business should make each month, in order to maximise its total profit. Show clearly how you obtain your answer.
[0pt] [8 marks]

7 An engineering company makes brake kits and clutch kits to sell to motorsport teams. The table below summarises the time taken and costs involved in making the two different types of kit. The workers at the engineering company have a combined 2500 hours available to make the kits every month. The engineering company has \(\pounds 200000\) available to cover the costs of making the kits every month. To meet the minimum demands of the motorsport teams, the engineering company must make at least 100 of each type of kit every month. 7

1. Using a graphical method on the grid opposite, find the number of each type of kit that the engineering company should make every month, in order to maximise its total monthly profit. Show clearly how you obtain your answer. \includegraphics[max width=\textwidth, alt={}, center]{c297a67f-65fd-47e0-a60c-d38fd86c6081-13_2486_1709_221_153} Do not write outside the box 7
2. Give a reason why the engineering company may not be able to make the number of each kit that you found in part (a). 7
3. During one particular month the engineering company removes the need to make at least 100 of each type of kit. Explain whether or not this has an effect on your answer to part (a).

5. A standard transportation problem is described in the linear programming formulation below. Let \(X _ { i j }\) be the number of units transported from \(i\) to \(j\) where \(i \in \{ \mathrm {~A} , \mathrm {~B} , \mathrm { C } , \mathrm { D } \}\) $$j \in \{ \mathrm { R } , \mathrm {~S} , \mathrm {~T} \} \text { and } x _ { i j } \geqslant 0$$ Minimise \(P = 23 x _ { \mathrm { AR } } + 17 x _ { \mathrm { AS } } + 24 x _ { \mathrm { AT } } + 15 x _ { \mathrm { BR } } + 29 x _ { \mathrm { BS } } + 32 x _ { \mathrm { BT } }\) $$+ 25 x _ { \mathrm { CR } } + 25 x _ { \mathrm { CS } } + 27 x _ { \mathrm { CT } } + 19 x _ { \mathrm { DR } } + 20 x _ { \mathrm { DS } } + 25 x _ { \mathrm { DT } }$$ subject to $$\begin{aligned} & \sum x _ { \mathrm { A } j } \leqslant 34 \\ & \sum x _ { \mathrm { B } j } \leqslant 27 \\ & \sum x _ { \mathrm { C } j } \leqslant 41 \\ & \sum x _ { \mathrm { D } j } \leqslant 18 \\ & \sum x _ { i \mathrm { R } } \geqslant 44 \\ & \sum x _ { i \mathrm {~S} } \geqslant 37 \\ & \sum x _ { i \mathrm {~T} } \geqslant k \end{aligned}$$ Given that the problem is balanced,

1. state the value of \(k\).
2. Explain precisely what the constraint \(\sum x _ { i \mathrm { R } } \geqslant 44\) means in the transportation problem.
3. Use the north-west corner method to obtain the cost of an initial solution to this transportation problem.
4. 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

Two fertilizers are available, a liquid \(X\) and a powder \(Y\). A bottle of \(X\) contains 5 units of chemical \(A\), 2 units of chemical \(B\) and \(\frac{1}{2}\) unit of chemical \(C\). A packet of \(Y\) contains 1 unit of \(A\), 2 units of \(B\) and 2 units of \(C\). A professional gardener makes her own fertilizer. She requires at least 10 units of \(A\), at least 12 units of \(B\) and at least 6 units of \(C\). She buys \(x\) bottles of \(X\) and \(y\) packets of \(Y\).

1. Write down the inequalities which model this situation. [4]
2. On the grid provided construct and label the feasible region. [3]

A bottle of \(X\) costs £2 and a packet of \(Y\) costs £3.

1. Write down an expression, in terms of \(x\) and \(y\), for the total cost \(£T\). [1]
2. Using your graph, obtain the values of \(x\) and \(y\) that give the minimum value of \(T\). Make your method clear and calculate the minimum value of \(T\). [4]
3. Suggest how the situation might be changed so that it could no longer be represented graphically. [2]

A manager wishes to purchase seats for a new cinema. He wishes to buy three types of seat; standard, deluxe and majestic. Let the number of standard, deluxe and majestic seats to be bought be \(x\), \(y\) and \(z\) respectively. He decides that the total number of deluxe and majestic seats should be at most half of the number of standard seats. The number of deluxe seats should be at least 10\% and at most 20\% of the total number of seats. The number of majestic seats should be at least half of the number of deluxe seats. The total number of seats should be at least 250. Standard, deluxe and majestic seats each cost £20, £26 and £36, respectively. The manager wishes to minimize the total cost, £\(C\), of the seats. Formulate this situation as a linear programming problem, simplifying your inequalities so that all the coefficients are integers. [9]

Becky's bird food company makes two types of bird food. One type is for bird feeders and the other for bird tables. Let \(x\) represent the quantity of food made for bird feeders and \(y\) represent the quantity of food made for bird tables. Due to restrictions in the production process, and known demand, the following constraints apply. $$x + y \leq 12,$$ $$y < 2x,$$ $$2y \geq 7,$$ $$y + 3x \geq 15.$$

1. On the axes provided, show these constraints and label the feasible region \(R\). [5]

The objective is to minimise \(C = 2x + 5y\).

1. Solve this problem, making your method clear. Give, as fractions, the value of \(C\) and the amount of each type of food that should be produced. [4]

Another objective (for the same constraints given above) is to maximise \(P = 3x + 2y\), where the variables must take integer values.

1. Solve this problem, making your method clear. State the value of \(P\) and the amount of each type of food that should be produced. [4]

Flatland UK Ltd makes three types of carpet, the Lincoln, the Norfolk and the Suffolk. The carpets all require units of black, green and red wool. For each roll of carpet, the Lincoln requires 1 unit of black, 1 of green and 3 of red, the Norfolk requires 1 unit of black, 2 of green and 2 of red, and the Suffolk requires 2 units of black, 1 of green and 1 of red. There are up to 30 units of black, 40 units of green and 50 units of red available each day. Profits of £50, £80 and £60 are made on each roll of Lincoln, Norfolk and Suffolk respectively. Flatland UK Ltd wishes to maximise its profit. Let the number of rolls of the Lincoln, Norfolk and Suffolk made daily be \(x\), \(y\) and \(z\) respectively.

1. Formulate the above situation as a linear programming problem, listing clearly the constraints as inequalities in their simplest form, and stating the objective function. [4]

This problem is to be solved using the Simplex algorithm. The most negative number in the profit row is taken to indicate the pivot column at each stage.

1. Stating your row operations, show that after one complete iteration the tableau becomes

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	\(\frac{1}{2}\)	0	\(1\frac{1}{2}\)	1	\(-\frac{1}{2}\)	0	10
   \(y\)	\(\frac{1}{2}\)	1	\(\frac{1}{2}\)	0	\(\frac{1}{2}\)	0	20
   \(t\)	2	0	0	0	\(-1\)	1	10
   \(P\)	\(-10\)	0	\(-20\)	0	40	0	1600

   [4]
2. Explain the practical meaning of the value 10 in the top row. [2]
3. 1. Perform one further complete iteration of the Simplex algorithm.
   2. State whether your current answer to part (d)(i) is optimal. Give a reason for your answer.
   3. Interpret your current tableau, giving the value of each variable. [8]

A company produces two types of party bag, Infant and Junior. Both types of bag contain a balloon, a toy and a whistle. In addition the Infant bag contains 3 sweets and 3 stickers and the Junior bag contains 10 sweets and 2 stickers. The sweets and stickers are produced in the company's factory. The factory can produce up to 3000 sweets per hour and 1200 stickers per hour. The company buys a large supply of balloons, toys and whistles. Market research indicates that at least twice as many Infant bags as Junior bags should be produced. Both types of party bag are sold at a profit of 15p per bag. All the bags are sold. The company wishes to maximise its profit. Let \(x\) be the number of Infant bags produced and \(y\) be the number of Junior bags produced per hour.

1. Formulate the above situation as a linear programming problem. [5]
2. Represent your inequalities graphically, indicating clearly the feasible region. [6]
3. Find the number of Infant bags and Junior bags that should be produced each hour and the maximum hourly profit. Make your method clear. [3]

In order to increase the profit further, the company decides to buy additional equipment. It can buy equipment to increase the production of either sweets or stickers, but not both.

1. Using your graph, explain which equipment should be bought, giving your reasoning. [2]

The manager of the company does not understand why the balloons, toys and whistles have not been considered in the above calculations.

1. Explain briefly why they do not need to be considered. [2]

\includegraphics{figure_6} The captain of the Malde Mare takes passengers on trips across the lake in her boat. The number of children is represented by \(x\) and the number of adults by \(y\). Two of the constraints limiting the number of people she can take on each trip are $$x < 10$$ and $$2 \leq y \leq 10$$ These are shown on the graph in Figure 6, where the rejected regions are shaded out.

1. Explain why the line \(x = 10\) is shown as a dotted line. (1)
2. Use the constraints to write down statements that describe the number of children and the number of adults that can be taken on each trip. (3)

For each trip she charges £2 per child and £3 per adult. She must take at least £24 per trip to cover costs. The number of children must not exceed twice the number of adults.

1. Use this information to write down two inequalities. (2)
2. Add two lines and shading to Diagram 1 in your answer book to represent these inequalities. Hence determine the feasible region and label it R. (4)
3. Use your graph to determine how many children and adults would be on the trip if the captain takes:
   1. the minimum number of passengers,
   2. the maximum number of passengers.
   (4)

(Total 14 marks)

A company produces two types of self-assembly wooden bedroom suites, the 'Oxford' and the 'York'. After the pieces of wood have been cut and finished, all the materials have to be packaged. The table below shows the time, in hours, needed to complete each stage of the process and the profit made, in pounds, on each type of suite.

	Oxford	York
Cutting	4	6
Finishing	3.5	4
Packaging	2	4
Profit (£)	300	500

The times available each week for cutting, finishing and packaging are 66, 56 and 40 hours respectively. The company wishes to maximise its profit. Let \(x\) be the number of Oxford, and \(y\) be the number of York suites made each week.

1. Write down the objective function. [1]
2. In addition to $$2x + 3y \leq 33,$$ $$x \geq 0,$$ $$y \geq 0,$$ find two further inequalities to model the company's situation. [2]
3. On the grid in the answer booklet, illustrate all the inequalities, indicating clearly the feasible region. [4]
4. Explain how you would locate the optimal point. [2]
5. Determine the number of Oxford and York suites that should be made each week and the maximum profit gained. [3]

It is noticed that when the optimal solution is adopted, the time needed for one of the three stages of the process is less than that available.

1. Identify this stage and state by how many hours the time may be reduced. [3]

The Young Enterprise Company "Decide", is going to produce badges to sell to decision maths students. It will produce two types of badges. Badge 1 reads "I made the decision to do maths" and Badge 2 reads "Maths is the right decision". "Decide" must produce at least 200 badges and has enough material for 500 badges. Market research suggests that the number produced of Badge 1 should be between 20% and 40% of the total number of badges made. The company makes a profit of 30p on each Badge 1 sold and 40p on each Badge 2. It will sell all that it produced, and wishes to maximise its profit. Let \(x\) be the number produced of Badge 1 and \(y\) be the number of Badge 2.

1. Formulate this situation as a linear programming problem, simplifying your inequalities so that all the coefficients are integers. [6]
2. On the grid provided in the answer book, construct and clearly label the feasible region. [5]
3. Using your graph, advise the company on the number of each badge it should produce. State the maximum profit "Decide" will make. [3]

\includegraphics{figure_6} Keith organises two types of children's activity, 'Sports Mad' and 'Circus Fun'. He needs to determine the number of times each type of activity is to be offered. Let \(x\) be the number of times he offers the 'Sports Mad' activity. Let \(y\) be the number of times he offers the 'Circus Fun' activity. Two constraints are $$x \leq 15$$ and $$y > 6$$ These constraints are shown on the graph in Figure 6, where the rejected regions are shaded out.

1. Explain why \(y = 6\) is shown as a dotted line. [1] Two further constraints are $$3x \geq 2y$$ and $$5x + 4y \geq 80$$
2. Add two lines and shading to Diagram 1 in the answer book to represent these inequalities. Hence determine the feasible region and label it R. [3] Each 'Sports Mad' activity costs £500. Each 'Circus Fun' activity costs £800. Keith wishes to minimise the total cost.
3. Write down the objective function, C, in terms of \(x\) and \(y\). [2]
4. Use your graph to determine the number of times each type of activity should be offered and the total cost. You must show sufficient working to make your method clear. [5]

(Total 11 marks)

Herman is packing some hampers. Each day, he packs three types of hamper: basic, standard and luxury. Each basic hamper has 6 tins, 9 packets and 6 bottles. Each standard hamper has 9 tins, 6 packets and 12 bottles. Each luxury hamper has 9 tins, 9 packets and 18 bottles. Each day, Herman has 600 tins and 600 packets available, and he must use at least 480 bottles. Each day, Herman packs \(x\) basic hampers, \(y\) standard hampers and \(z\) luxury hampers.

1. In addition to \(x \geqslant 0\), \(y \geqslant 0\) and \(z \geqslant 0\), find three inequalities in \(x\), \(y\) and \(z\) that model the above constraints, simplifying each inequality. [4]
2. On a particular day, Herman packs the same number of standard hampers as luxury hampers.
   1. Show that your answers in part (a) become \(x + 3y \leqslant 100\) \(3x + 5y \leqslant 200\) \(x + 5y \geqslant 80\) [2]
   2. On the grid opposite, draw a suitable diagram to represent Herman's situation, indicating the feasible region. [4]
   3. Use your diagram to find the maximum total number of hampers that Herman can pack on that day. [2]
   4. Find the number of each type of hamper that Herman packs that corresponds to your answer to part (b)(iii). [1]

Phil is to buy some squash balls for his club. There are three different types of ball that he can buy: slow, medium and fast. He must buy at least 190 slow balls, at least 50 medium balls and at least 50 fast balls. He must buy at least 300 balls in total. Each slow ball costs £2.50, each medium ball costs £2.00 and each fast ball costs £2.00. He must spend no more than £1000 in total. At least 60% of the balls that he buys must be slow balls. Phil buys \(x\) slow balls, \(y\) medium balls and \(z\) fast balls.

1. Find six inequalities that model Phil's situation. [4 marks]
2. Phil decides to buy the same number of medium balls as fast balls.
   1. Show that the inequalities found in part (a) simplify to give $$x \geq 190, \quad y \geq 50, \quad x + 2y \geq 300, \quad 5x + 8y \leq 2000, \quad y \leq \frac{1}{3}x$$ [2 marks]
   2. Phil sells all the balls that he buys to members of the club. He sells each slow ball for £3.00, each medium ball for £2.25 and each fast ball for £2.25. He wishes to maximise his profit. On Figure 1 on page 14, draw a diagram to enable this problem to be solved graphically, indicating the feasible region and the direction of an objective line. [7 marks]
   3. Find Phil's maximum possible profit and state the number of each type of ball that he must buy to obtain this maximum profit. [4 marks]

Mark wants to decorate the walls of his study. The total wall area is 24 m\(^2\). Mark can cover the walls using any combination of three materials: panelling, paint and pinboard. He wants at least 2 m\(^2\) of pinboard and at least 10 m\(^2\) of panelling. Panelling costs £8 per m\(^2\) and it will take Mark 15 minutes to put up 1 m\(^2\) of panelling. Paint costs £4 per m\(^2\) and it will take Mark 30 minutes to paint 1 m\(^2\). Pinboard costs £10 per m\(^2\) and it will take Mark 20 minutes to put up 1 m\(^2\) of pinboard. He has all the equipment that he will need for the decorating jobs. Mark is able to spend up to £150 on the materials for the decorating. He wants to know what area should be covered with each material to enable him to complete the whole job in the shortest time possible. Mark models the problem as an LP with five constraints. His constraints are: $$x + y + z = 24,$$ $$4x + 2y + 5z \leqslant 75,$$ $$x \geqslant 10,$$ $$y \geqslant 0,$$ $$z \geqslant 2.$$

1. Identify the meaning of each of the variables \(x\), \(y\) and \(z\). [2]
2. Show how the constraint \(4x + 2y + 5z \leqslant 75\) was formed. [2]
3. Write down an objective function, to be minimised. [1]

Mark rewrites the first constraint as \(z = 24 - x - y\) and uses this to eliminate \(z\) from the problem.

1. Rewrite and simplify the objective and the remaining four constraints as functions of \(x\) and \(y\) only. [3]
2. Represent your constraints from part (iv) graphically and identify the feasible region. Your graph should show \(x\) and \(y\) values from 0 to 15 only. [4]

Badgers is a small company that makes badges to customers' designs. Each badge must pass through four stages in its production: printing, stamping out, fixing pin and checking. The badges can be laminated, metallic or plastic. The times taken for 100 badges of each type to pass through each of the stages and the profits that Badgers makes on every 100 badges are shown in the table below. The table also shows the total time available for each of the production stages. Suppose that the company makes \(x\) hundred laminated badges, \(y\) hundred metallic badges and \(z\) hundred plastic badges.

1. Show that the printing time leads to the constraint \(x + y + 2z \leq 600\). Write down and simplify constraints for the time spent on each of the other production stages. [4]
2. What other constraint is there on the values of \(x\), \(y\) and \(z\)? [1]

The company wants to maximise the profit from the sale of badges.

1. Write down an appropriate objective function, to be maximised. [1]
2. Represent Badgers' problem as an initial Simplex tableau. [4]
3. Use the Simplex algorithm, pivoting first on a value chosen from the \(x\)-column and then on a value chosen from the \(y\)-column. Interpret your solution and the values of the slack variables in the context of the original problem. [9]

Leone is designing her new garden. She wants to have at least 1000 m\(^2\), split between lawn and flower beds. Initial costs are £0.80 per m\(^2\) for lawn and £0.40 per m\(^2\) for flowerbeds. Leone's budget is £500. Leone prefers flower beds to lawn, and she wants the area for flower beds to be at least twice the area for lawn. However, she wants to have at least 200 m\(^2\) of lawn. Maintenance costs each year are £0.15 per m\(^2\) for lawn and £0.25 per m\(^2\) for flower beds. Leone wants to minimize the maintenance costs of her garden.

1. Formulate Leone's problem as a linear programming problem. [7]
2. Produce a graph to illustrate the inequalities. [6]
3. Solve Leone's problem. [2]
4. If Leone had more than £500 available initially, how much extra could she spend to minimize maintenance costs? [1]

An engineer makes three components \(X\), \(Y\) and \(Z\). Relevant details are as follows: Component \(X\) requires 6 minutes turning, 3 minutes machining and 1 minute finishing. Component \(Y\) requires 15 minutes turning, 3 minutes machining and 4 minutes finishing. Component \(Z\) requires 12 minutes turning, 1 minute machining and 4 minutes finishing. The engineer gets access to 185 minutes turning, 30 minutes machining and 60 minutes finishing each day. The profits from selling components \(X\), \(Y\) and \(Z\) are £40, £90 and £60 respectively and the engineer wishes to maximise the profit from her work each day. Let the number of components \(X\), \(Y\) and \(Z\) the engineer makes each day be \(x\), \(y\) and \(z\) respectively.

1. Write down the 3 inequalities that apply in addition to \(x \geq 0\), \(y \geq 0\) and \(z \geq 0\). [3 marks]
2. Explain why it is not appropriate to use a graphical method to solve the problem. [1 mark]

It is decided to use the simplex algorithm to solve the problem.

1. Show that a possible initial tableau is:

   Basic Variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	6	15	12	1	0	0	185
   \(s\)	3	3	1	0	1	0	30
   \(t\)	1	4	4	0	0	1	60
   \(P\)	\(-4\)	\(-9\)	\(-6\)	0	0	0	0

   [2 marks]

It is decided to increase \(y\) first.

1. Perform sufficient complete iterations to obtain a final tableau and explain how you know that your solution is optimal. You may assume that work in progress is allowed. [9 marks]
2. State the number of each component that should be made per day and the total daily profit that this gives, assuming that all items can be sold. [1 mark]
3. If work in progress is not practicable, explain how you would obtain an integer solution to this problem. You are not expected to find this solution. [2 marks]

T42 Co. Ltd produces three different blends of tea, Morning, Afternoon and Evening. The teas must be processed, blended and then packed for distribution. The table below shows the time taken, in hours, for each stage of the production of a tonne of tea. It also shows the profit, in hundreds of pounds, on each tonne.

	Processing	Blending	Packing	Profit (£100)
Morning blend	3	1	3	4
Afternoon blend	2	3	4	5
Evening blend	4	2	3	3

The total times available each week for processing, blending and packing are 35, 20 and 24 hours respectively. T42 Co. Ltd wishes to maximise the weekly profit. Let \(x\), \(y\) and \(z\) be the number of tonnes of Morning, Afternoon and Evening blend produced each week.

1. Formulate the above situation as a linear programming problem, listing clearly the objective function, and the constraints as inequalities. [4]

An initial Simplex tableau for the above situation is

Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	3	2	4	1	0	0	35
\(s\)	1	3	2	0	1	0	20
\(t\)	2	4	3	0	0	1	24
\(P\)	\(-4\)	\(-5\)	\(-3\)	0	0	0	0

1. Solve this linear programming problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column at each stage. [11]

T42 Co. Ltd wishes to increase its profit further and is prepared to increase the time available for processing or blending or packing or any two of these three.

1. Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available. [2]

Flatland UK Ltd makes three types of carpet, the Lincoln, the Norfolk and the Suffolk. The carpets all require units of black, green and red wool. For each roll of carpet, the Lincoln requires 1 unit of black, 1 of green and 3 of red, the Norfolk requires 1 unit of black, 2 of green and 2 of red, and the Suffolk requires 2 units of black, 1 of green and 1 of red. There are up to 30 units of black, 40 units of green and 50 units of red available each day. Profits of £50, £80 and £60 are made on each roll of Lincoln, Norfolk and Suffolk respectively. Flatland UK Ltd wishes to maximise its profit. Let the number of rolls of the Lincoln, Norfolk and Suffolk made daily be \(x\), \(y\) and \(z\) respectively.

1. Formulate the above situation as a linear programming problem, listing clearly the constraints as inequalities in their simplest form, and stating the objective function. [4]

This problem is to be solved using the Simplex algorithm. The most negative number in the profit row is taken to indicate the pivot column at each stage.

1. Stating your row operations, show that after one complete iteration the tableau becomes

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	\(\frac{1}{2}\)	0	\(1\frac{1}{2}\)	1	\(-\frac{1}{2}\)	0	10
   \(y\)	\(\frac{1}{2}\)	1	\(\frac{1}{2}\)	0	\(\frac{1}{2}\)	0	20
   \(t\)	2	0	0	0	\(-1\)	1	10
   P	\(-10\)	0	\(-20\)	0	40	0	1600

   [4]

You may not need to use all of the tableaux.

1. Explain the practical meaning of the value 10 in the top row. [2]
2. 1. Perform one further complete iteration of the Simplex algorithm.

      Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations

      Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations

   2. State whether your current answer to part (d)(i) is optimal. Give a reason for your answer.
   3. Interpret your current tableau, giving the value of each variable. [8]

(Total 18 marks)

Three workers, \(P\), \(Q\) and \(R\), are to be assigned to three tasks, 1, 2 and 3. Each worker is to be assigned to one task and each task must be assigned to one worker. The cost, in hundreds of pounds, of using each worker for each task is given in the table below. The cost is to be minimised.

Cost (in £100s)	Task 1	Task 2	Task 3
Worker \(P\)	8	7	3
Worker \(Q\)	9	5	6
Worker \(R\)	10	4	4

Formulate the above situation as a linear programming problem, defining the decision variables and making the objective and constraints clear. (Total 7 marks)

Kassi and Theo are discussing how much oil and how much vinegar to use to dress their salad. They agree to use between 5 and 10ml of oil and between 3 and 6ml of vinegar and that the amount of oil should not exceed twice the amount of vinegar. Theo prefers to have more oil than vinegar. He formulates the following problem to maximise the proportion of oil: Maximise \(\frac{x}{x + y}\) subject to \(0 \leq x \leq 10\), \(0 \leq y \leq 6\), \(x - 2y \leq 0\).

1. Explain why this problem is not an LP. [1]
2. Use the simplex method to solve the following LP. Maximise \(x - y\) subject to \(0 \leq x \leq 10\), \(0 \leq y \leq 6\), \(x - 2y \leq 0\). [7]
3. Kassi prefers to have more vinegar than oil. She formulates the following LP. Maximise \(y - x\) subject to \(5 \leq x \leq 10\), \(3 \leq y \leq 6\), \(x - 2y \leq 0\). Draw separate graphs to show the feasible regions for this problem and for the problem in part (ii). [5]
4. Explain why the formulation in part (ii) produced a solution for Theo's problem, and why it is more difficult to use the simplex method to solve Kassi's problem in part (iii). [2]
5. Produce an initial tableau for using the two-stage simplex method to solve Kassi's problem. Explain briefly how to proceed. [5]

A Young Enterprise Company decides to sell two types of cakes at a breakfast club. The two types of cakes are blueberry and chocolate. From its initial market research, the company knows that it will: • sell at most 200 cakes in total • sell at least twice as many blueberry cakes as they will chocolate cakes • make 20p profit on each blueberry cake they sell • make 15p profit on each chocolate cake they sell. The company's objective is to maximise its profit. Formulate the Young Enterprise Company's situation as a linear programming problem. [4 marks]

Kira and Julian play a zero-sum game that does not have a stable solution. Kira has three strategies to choose from: \(\mathbf{K_1}\), \(\mathbf{K_2}\) and \(\mathbf{K_3}\) To determine her optimal mixed strategy, Kira begins by defining the following variables: \(v =\) value of the game for Kira \(p_1 =\) probability of Kira playing strategy \(\mathbf{K_1}\) \(p_2 =\) probability of Kira playing strategy \(\mathbf{K_2}\) \(p_3 =\) probability of Kira playing strategy \(\mathbf{K_3}\) Kira then formulates the following linear programming problem. Maximise \(v\) subject to \(7p_1 + p_2 + 8p_3 \geq v\) \(3p_1 + 7p_2 + 2p_3 \geq v\) \(9p_1 + 2p_2 + 4p_3 \geq v\) and \(p_1 + p_2 + p_3 \leq 1\) \(p_1, p_2, p_3 \geq 0\)

1. 1. Explain why the condition \(p_1 + p_2 + p_3 \leq 1\) is necessary in Kira's linear programming problem. [1 mark]
   2. Explain why the condition \(p_1, p_2, p_3 \geq 0\) is necessary in Kira's linear programming problem. [1 mark]
2. Julian has three strategies to choose from: \(\mathbf{J_1}\), \(\mathbf{J_2}\) and \(\mathbf{J_3}\) Complete the following pay-off matrix which represents the game for Kira. [3 marks]

   	Julian
   Strategy	\(\mathbf{J_1}\)	\(\mathbf{J_2}\)	\(\mathbf{J_3}\)
   \(\mathbf{K_1}\)	7
   Kira \(\mathbf{K_2}\)
   \(\mathbf{K_3}\)