7.06a LP formulation: variables, constraints, objective function

2. A company has three factories, \(\mathrm { A } , \mathrm { B }\) and C . It supplies mattresses to three shops, \(\mathrm { D } , \mathrm { E }\) and F . The table shows the transportation cost, in pounds, of moving one mattress from each factory to each shop. It also shows the number of mattresses available at each factory and the number of mattresses required at each shop. A minimum cost solution is required.

1. Use the north-west corner method to obtain an initial solution.
2. Show how the transportation algorithm is used to solve this problem. You must state, at each appropriate step, the

1. Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S.

Each worker must be assigned to at most one task and each task must be done by just one worker. The amount, in pounds, that each worker would earn while assigned to each task is shown in the table below. The Hungarian algorithm is to be used to find the maximum total amount which may be earned by the four workers.

1. Explain how the table should be modified.
2. Reducing rows first, use the Hungarian algorithm to obtain an allocation which maximises the total earnings, stating how each table was formed.
3. Formulate the problem as a linear programming problem. You must define your decision variables and make your objective function and constraints clear.
   

4. A game uses a standard pack of 52 playing cards. A player gives 5 tokens to play and then picks a card. If they pick a \(2,3,4,5\) or 6 then they gain 15 tokens. If any other card is picked they lose. If they lose, the card is replaced and they can choose to pick again for another 5 tokens. This time if they pick either an ace or a king they gain 40 tokens. If any other card is picked they lose. Daniel is deciding whether to play this game.

1. Draw a decision tree to model Daniel's possible decisions and the possible outcomes.
2. Calculate Daniel's optimal EMV and state the optimal strategy indicated by the decision tree.

2 Rahul is decorating a room. He needs to decorate at least \(30 \mathrm {~m} ^ { 2 }\) of the walls using paint, panelling or wallpaper. The cost ( \(\pounds\) ) and the time required (hours) to decorate \(1 \mathrm {~m} ^ { 2 }\) of wall are shown in the table. Rahul wants to complete decorating the walls in no more than 8 hours and wants to minimise the cost.
Set up an LP formulation for Rahul's problem, defining your variables. You are not required to solve this LP problem.

6 An online magazine consists of an editorial, articles, reviews and advertisements.
The magazine must have a total of at least 12 pages. The editorial always takes up exactly half a page. There must be at least 3 pages of articles and at most 1.5 pages of reviews. At least a quarter but fewer than half of the pages in the magazine must be used for advertisements. Let \(x\) be the number of pages used for articles, \(y\) be the number of pages used for reviews and \(z\) be the number of pages used for advertisements. The constraints on the values of \(x , y\) and \(z\) are: $$\begin{aligned} & x + y + z \geqslant 11.5 \\ & x \geqslant 3 \\ & y \leqslant 1.5 \\ & 2 x + 2 y - 2 z + 1 \geqslant 0 \\ & 2 x + 2 y - 6 z + 1 \leqslant 0 \\ & y \geqslant 0 \end{aligned}$$

1. (a) Explain why \(x + y + z \geqslant 11.5\).
   (b) Explain why only one non-negativity constraint is needed.
   (c) Show that the requirement that at least one quarter of the pages in the magazine must be used for advertisements leads to the constraint \(2 x + 2 y - 6 z + 1 \leqslant 0\). Advertisements bring in money but are not popular with the subscribers. The editor decides to limit the number of pages of advertisements to at most four.
2. Graph the feasible region in the case when \(z = 4\) using the axes in the Printed Answer Booklet. To be successful the magazine needs to maximise the number of subscribers.
   The editor has found that when \(z \leqslant 4\) the expected number of subscribers is given by \(P = 300 x + 400 y\).
3. (a) What is the maximum expected number of subscribers when \(z = 4\) ?
   (b) By first considering the feasible region for \(z = k\), where \(k \leqslant 4\), find an expression for the maximum number of subscribers in terms of \(k\). \section*{END OF QUESTION PAPER} \section*{OCR} \section*{Oxford Cambridge and RSA}

6 Jack is making pizzas for a party. He can make three types of pizza:

• There is enough dough to make 30 pizzas.
• Type Z pizzas use vegan cheese. Jack only has enough vegan cheese to make 2 type Z pizzas.
• At least half the pizzas made must be suitable for vegetarians.
• Jack has enough onions to make 50 type X pizzas or 20 type Y pizzas or 20 type Z pizzas or some mixture of the three types.

Suppose that Jack makes \(x\) type X pizzas, \(y\) type Y pizzas and \(z\) type Z pizzas.

1. Formulate the constraints above in terms of the non-negative, integer valued variables \(x , y\) and \(z\), together with non-negative slack variables \(s , t , u\) and \(v\). Jack wants to find out the maximum total number of pizzas that he can make.
2. 1. Set up an initial simplex tableau for Jack's problem.
   2. Carry out one iteration of the simplex algorithm, choosing your pivot so that \(x\) becomes a basic variable. When Jack carries out the simplex algorithm his final tableau is:

      \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
      1	0	0	0	0	0	\(\frac { 3 } { 7 }\)	\(\frac { 2 } { 7 }\)	\(28 \frac { 4 } { 7 }\)
      0	0	0	0	1	0	\(- \frac { 3 } { 7 }\)	\(- \frac { 2 } { 7 }\)	\(1 \frac { 3 } { 7 }\)
      0	0	0	1	0	1	0	0	2
      0	1	0	0	0	0	\(\frac { 5 } { 7 }\)	\(\frac { 1 } { 7 }\)	\(14 \frac { 2 } { 7 }\)
      0	0	1	1	0	0	\(- \frac { 2 } { 7 }\)	\(\frac { 1 } { 7 }\)	\(14 \frac { 2 } { 7 }\)

3. Use this final tableau to deduce how many pizzas of each type Jack should make. Jack knows that some of the guests are vegans. He decides to make 2 pizzas of type \(Z\).
4. 1. Plot the feasible region for \(x\) and \(y\).
   2. Complete the branch-and-bound formulation in the Printed Answer Booklet to find the number of pizzas of each type that Jack should make.
      You should branch on \(x\) first. \section*{END OF QUESTION PAPER}

7. A tailor makes two types of garment, \(A\) and \(B\). He has available \(70 \mathrm {~m} ^ { 2 }\) of cotton fabric and \(90 \mathrm {~m} ^ { 2 }\) of woollen fabric. Garment \(A\) requires \(1 \mathrm {~m} ^ { 2 }\) of cotton fabric and \(3 \mathrm {~m} ^ { 2 }\) of woollen fabric. Garment \(B\) requires \(2 \mathrm {~m} ^ { 2 }\) of each fabric. The tailor makes \(x\) garments of type \(A\) and \(y\) garments of type \(B\).

1. Explain why this can be modelled by the inequalities $$\begin{aligned} & x + 2 y \leq 70 \\ & 3 x + 2 y \leq 90 \\ & x \geq 0 , y \geq 0 \end{aligned}$$ (2 marks)
   The tailor sells type \(A\) for \(\pounds 30\) and type \(B\) for \(\pounds 40\). All garments made are sold. The tailor wishes to maximise his total income.
2. Set up an initial Simplex tableau for this problem.
   (3 marks)
3. Solve the problem using the Simplex algorithm.
   (8 marks) Figure 4 shows a graphical representation of the feasible region for this problem. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{3147dad8-2d3c-42fd-b288-7017ff1fce16-004_452_828_995_356} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure}
4. Obtain the coordinates of the points A, \(C\) and \(D\).
5. Relate each stage of the Simplex algorithm to the corresponding point in Fig. 4.
   (3 marks) Answer Book (AB12)
   Graph Paper (ASG2) Items included with question papers Answer booklet

7. A tailor makes two types of garment, \(A\) and \(B\). He has available \(70 \mathrm {~m} ^ { 2 }\) of cotton fabric and \(90 \mathrm {~m} ^ { 2 }\) of woollen fabric. Garment \(A\) requires \(1 \mathrm {~m} ^ { 2 }\) of cotton fabric and \(3 \mathrm {~m} ^ { 2 }\) of woollen fabric. Garment \(B\) requires \(2 \mathrm {~m} ^ { 2 }\) of each fabric. The tailor makes \(x\) garments of type \(A\) and \(y\) garments of type \(B\).

1. Explain why this can be modelled by the inequalities $$\begin{aligned} & x + 2 y \leq 70 \\ & 3 x + 2 y \leq 90 \\ & x \geq 0 , y \geq 0 \end{aligned}$$ The tailor sells type \(A\) for \(\pounds 30\) and type \(B\) for \(\pounds 40\). All garments made are sold. The tailor wishes to maximise his total income.
2. Set up an initial Simplex tableau for this problem.
3. Solve the problem using the Simplex algorithm. Figure 4 shows a graphical representation of the feasible region for this problem. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-008_686_1277_1319_453} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure}
4. Obtain the coordinates of the points A, \(C\) and \(D\).
5. Relate each stage of the Simplex algorithm to the corresponding point in Fig. 4. 6689 Decision Mathematics 1 (New Syllabus) Order of selecting edges
   Final tree
   (b) Minimum total length of cable
   Question 4 to be answered on this page
   (a) \(A\)
   • Monday (M) \(B\) ◯
   • Tuesday (Tu) \(C \odot\)
   • Wednesday (W) \(D\) ◯
   • Thursday (Th) \(E\) -
   • Friday (F)
     (b)
     (c)
   Question 5 to be answered on this page
   Key
   (a) Early
   Time
   Late
   Time \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_433_227_534_201} \(F ( 3 )\) \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_117_222_1016_992}
   H(4) K(6)
   (b) Critical activities
   Length of critical path \(\_\_\_\_\) (c) \includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-011_492_1604_1925_266} Question 6 to be answered on pages 4 and 5
   (a)
   1. SAET \(\_\_\_\_\)
   2. SBDT \(\_\_\_\_\)
   3. SCFT \(\_\_\_\_\)
   
   (b) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-012_691_1307_893_384} \captionsetup{labelformat=empty} \caption{Diagram 1}
   \end{figure} (c) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-013_699_1314_167_382} \captionsetup{labelformat=empty} \caption{Diagram 2}
   \end{figure} Flow augmenting routes
   (d) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-013_693_1314_1368_382} \captionsetup{labelformat=empty} \caption{Diagram 3}
   \end{figure} (e) \(\_\_\_\_\)

7. Rose makes hanging baskets which she sells at her local market. She makes two types, large and small. Rose makes \(x\) large baskets and \(y\) small baskets. Each large basket costs \(\pounds 7\) to make and each small basket costs \(\pounds 5\) to make. Rose has \(\pounds 350\) she can spend on making the baskets.

1. Write down an inequality, in terms of \(x\) and \(y\), to model this constraint.
   (2) Two further constraints are $$\begin{aligned} & y \leqslant 20 \text { and } \\ & y \leqslant 4 x \end{aligned}$$
2. Use these two constraints to write down statements that describe the numbers of large and small baskets that Rose can make.
3. On the grid provided, show these three constraints and \(x \geqslant 0 , y \geqslant 0\). Hence label the feasible region, R. Rose makes a profit of \(\pounds 2\) on each large basket and \(\pounds 3\) on each small basket. Rose wishes to maximise her profit, £P.
4. Write down the objective function.
5. Use your graph to determine the optimal numbers of large and small baskets Rose should make, and state the optimal profit.

9 A factory makes three different types of widget: plain, bland and ordinary. Each widget is made using three different machines: \(A , B\) and \(C\). Each plain widget needs 5 minutes on machine \(A , 12\) minutes on machine \(B\) and 24 minutes on machine \(C\). Each bland widget needs 4 minutes on machine \(A , 8\) minutes on machine \(B\) and 12 minutes on machine \(C\). Each ordinary widget needs 3 minutes on machine \(A\), 10 minutes on machine \(B\) and 18 minutes on machine \(C\). Machine \(A\) is available for 3 hours a day, machine \(B\) for 4 hours a day and machine \(C\) for 9 hours a day. The factory must make:
more plain widgets than bland widgets;
more bland widgets than ordinary widgets.
At least \(40 \%\) of the total production must be plain widgets.
Each day, the factory makes \(x\) plain, \(y\) bland and \(z\) ordinary widgets.
Formulate the above situation as 6 inequalities, in addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), writing your answers with simplified integer coefficients.
(8 marks)

8 Each day, a factory makes three types of hinge: basic, standard and luxury. The hinges produced need three different components: type \(A\), type \(B\) and type \(C\). Basic hinges need 2 components of type \(A , 3\) components of type \(B\) and 1 component of type \(C\). Standard hinges need 4 components of type \(A , 2\) components of type \(B\) and 3 components of type \(C\). Luxury hinges need 3 components of type \(A\), 4 components of type \(B\) and 5 components of type \(C\). Each day, there are 360 components of type \(A\) available, 270 of type \(B\) and 450 of type \(C\). Each day, the factory must use at least 720 components in total.
Each day, the factory must use at least \(40 \%\) of the total components as type \(A\).
Each day, the factory makes \(x\) basic hinges, \(y\) standard hinges and \(z\) luxury hinges.
In addition to \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\), find five inequalities, each involving \(x , y\) and \(z\), which must be satisfied. Simplify each inequality where possible.

4 [Figure 2, printed on the insert, is provided for use in this question.]
Each year, farmer Giles buys some goats, pigs and sheep.
He must buy at least 110 animals.
He must buy at least as many pigs as goats.
The total of the number of pigs and the number of sheep that he buys must not be greater than 150 .
Each goat costs \(\pounds 16\), each pig costs \(\pounds 8\) and each sheep costs \(\pounds 24\).
He has \(\pounds 3120\) to spend on the animals.
At the end of the year, Giles sells all of the animals. He makes a profit of \(\pounds 70\) on each goat, \(\pounds 30\) on each pig and \(\pounds 50\) on each sheep. Giles wishes to maximize his total profit, \(\pounds P\). Each year, Giles buys \(x\) goats, \(y\) pigs and \(z\) sheep.

1. Formulate Giles's situation as a linear programming problem.
2. One year, Giles buys 30 sheep.
   1. Show that the constraints for Giles's situation for this year can be modelled by $$y \geqslant x , \quad 2 x + y \leqslant 300 , \quad x + y \geqslant 80 , \quad y \leqslant 120$$ (2 marks)
   2. On Figure 2, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and the direction of the objective line.
      (8 marks)
   3. Find Giles's maximum profit for this year and the number of each animal that he must buy to obtain this maximum profit.
      (3 marks)

8 A factory packs three different kinds of novelty box: red, blue and green. Each box contains three different types of toy: \(\mathrm { A } , \mathrm { B }\) and C . Each red box has 2 type A toys, 3 type B toys and 4 type C toys.
Each blue box has 3 type A toys, 1 type B toy and 3 type C toys.
Each green box has 4 type A toys, 5 type B toys and 2 type C toys.
Each day, the maximum number of each type of toy available to be packed is 360 type A, 300 type B and 400 type C. Each day, the factory must pack more type A toys than type B toys.
Each day, the total number of type A and type B toys that are packed must together be at least as many as the number of type C toys that are packed. Each day, at least \(40 \%\) of the total toys that are packed must be type C toys.
Each day, the factory packs \(x\) red boxes, \(y\) blue boxes and \(z\) green boxes.
Formulate the above situation as 6 inequalities, in addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), simplifying your answers.

8 [Figure 2, printed on the insert, is provided for use in this question.]
A company makes two types of boxes of chocolates, executive and luxury.
Every hour the company must make at least 15 of each type and at least 35 in total.
Each executive box contains 20 dark chocolates and 12 milky chocolates.
Each luxury box contains 10 dark chocolates and 18 milky chocolates.
Every hour the company has 600 dark chocolates and 600 milky chocolates available.
The company makes a profit of \(\pounds 1.50\) on each executive box and \(\pounds 1\) on each luxury box.
The company makes and sells \(x\) executive boxes and \(y\) luxury boxes every hour.
The company wishes to maximise its hourly profit, \(\pounds P\).

1. Show that one of the constraints leads to the inequality \(2 x + 3 y \leqslant 100\).
2. Formulate the company's situation as a linear programming problem.
3. On Figure 2, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and an objective line.
4. Use your diagram to find the maximum hourly profit.

6 [Figure 3, printed on the insert, is provided for use in this question.]
Ernesto is to plant a garden with two types of tree: palms and conifers.
He is to plant at least 10, but not more than 80 palms.
He is to plant at least 5 , but not more than 40 conifers.
He cannot plant more than 100 trees in total. Each palm needs 20 litres of water each day and each conifer needs 60 litres of water each day. There are 3000 litres of water available each day. Ernesto makes a profit of \(\pounds 2\) on each palm and \(\pounds 1\) on each conifer that he plants and he wishes to maximise his profit. Ernesto plants \(x\) palms and \(y\) conifers.

1. Formulate Ernesto's situation as a linear programming problem.
2. On Figure 3, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and the direction of the objective line.
3. Find the maximum profit for Ernesto.
4. Ernesto introduces a new pricing structure in which he makes a profit of \(\pounds 1\) on each palm and \(\pounds 4\) on each conifer. Find Ernesto's new maximum profit and the number of each type of tree that he should plant to obtain this maximum profit.

5 [Figure 2, printed on the insert, is provided for use in this question.]
The Jolly Company sells two types of party pack: excellent and luxury.
Each excellent pack has five balloons and each luxury pack has ten balloons.
Each excellent pack has 32 sweets and each luxury pack has 8 sweets.
The company has 1500 balloons and 4000 sweets available.
The company sells at least 50 of each type of pack and at least 140 packs in total.
The company sells \(x\) excellent packs and \(y\) luxury packs.

1. Show that the above information can be modelled by the following inequalities. $$x + 2 y \leqslant 300 , \quad 4 x + y \leqslant 500 , \quad x \geqslant 50 , \quad y \geqslant 50 , \quad x + y \geqslant 140$$ (4 marks)
2. The company sells each excellent pack for 80 p and each luxury pack for \(\pounds 1.20\). The company needs to find its minimum and maximum total income.
   1. On Figure 2, draw a suitable diagram to enable this linear programming problem to be solved graphically, indicating the feasible region and an objective line.
   2. Find the company's maximum total income and state the corresponding number of each type of pack that needs to be sold.
   3. Find the company's minimum total income and state the corresponding number of each type of pack that needs to be sold.

7 A factory makes batches of three different types of battery: basic, long-life and super.
Each basic batch needs 4 minutes on machine \(A\), 7 minutes on machine \(B\) and 14 minutes on machine \(C\). Each long-life batch needs 10 minutes on machine \(A\), 14 minutes on machine \(B\) and 21 minutes on machine \(C\). Each super batch needs 10 minutes on machine \(A\), 14 minutes on machine \(B\) and 28 minutes on machine \(C\). Machine \(A\) is available for 4 hours a day, machine \(B\) for 3.5 hours a day and machine \(C\) for 7 hours a day. Each day the factory must make:
more basic batches than the total number of long-life and super batches; at least as many long-life batches as super batches. At least 15\% of the production must be long-life batches.
Each day, the factory makes \(x\) basic, \(y\) long-life and \(z\) super batches.
Formulate the above situation as 6 inequalities, in addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), writing your answers with simplified integer coefficients.

9 A company producing chicken food makes three products, Basic, Premium and Supreme, from wheat, maize and barley. A tonne \(( 1000 \mathrm {~kg} )\) of Basic uses 400 kg of wheat, 200 kg of maize and 400 kg of barley.
A tonne of Premium uses 400 kg of wheat, 500 kg of maize and 100 kg of barley.
A tonne of Supreme uses 600 kg of wheat, 200 kg of maize and 200 kg of barley.
The company has 130 tonnes of wheat, 70 tonnes of maize and 72 tonnes of barley available. The company must make at least 75 tonnes of Supreme.
The company makes \(\pounds 50\) profit per tonne of Basic, \(\pounds 100\) per tonne of Premium and \(\pounds 150\) per tonne of Supreme. They plan to make \(x\) tonnes of Basic, \(y\) tonnes of Premium and \(z\) tonnes of Supreme.

1. Write down four inequalities representing the constraints (in addition to \(x , y \geqslant 0\) ).
   [0pt] [4 marks]
2. The company want exactly half the production to be Supreme. Show that the constraints in part (a) become $$\begin{aligned} x + y & \leqslant 130 \\ 4 x + 7 y & \leqslant 700 \\ 2 x + y & \leqslant 240 \\ x + y & \geqslant 75 \\ x & \geqslant 0 \\ y & \geqslant 0 \end{aligned}$$
3. On the grid opposite, illustrate all the constraints and label the feasible region.
4. Write an expression for \(P\), the profit for the whole production, in terms of \(x\) and \(y\) only.
   [0pt] [2 marks]
5. 1. By drawing an objective line on your graph, or otherwise, find the values of \(x\) and \(y\) which give the maximum profit.
      [0pt] [2 marks]
   2. State the maximum profit and the amount of each product that must be made.
      [0pt] [2 marks] \section*{Answer space for question 9}
      \includegraphics[max width=\textwidth, alt={}]{f5890e58-38c3-413c-8762-6f80ce6dcec7-21_1349_1728_310_148}
      QUESTION
      PART
      REFERENCE \includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-24_2488_1728_219_141}

8 Nerys runs a cake shop. In November and December she sells Christmas hampers. She makes up the hampers herself, in two sizes: Luxury and Special. Each day, Nerys prepares \(x\) Luxury hampers and \(y\) Special hampers.
It takes Nerys 10 minutes to prepare a Luxury hamper and 15 minutes to prepare a Special hamper. She has 6 hours available, each day, for preparing hampers. From past experience, Nerys knows that each day:

• she will need to prepare at least 5 hampers of each size
• she will prepare at most a total of 32 hampers
• she will prepare at least twice as many Luxury hampers as Special hampers.

Each Luxury hamper that Nerys prepares makes her a profit of \(\pounds 15\); each Special hamper makes a profit of \(\pounds 20\). Nerys wishes to maximise her daily profit, \(\pounds P\).

1. Show that \(x\) and \(y\) must satisfy the inequality \(2 x + 3 y \leqslant 72\).
2. In addition to \(x \geqslant 5\) and \(y \geqslant 5\), write down two more inequalities that model the constraints above.
3. On the grid opposite draw a suitable diagram to enable this problem to be solved graphically. Indicate a feasible region and the direction of an objective line.
4. 1. Use your diagram to find the number of each type of hamper that Nerys should prepare each day to achieve a maximum profit.
   2. Calculate this profit.
      \includegraphics[max width=\textwidth, alt={}]{fb95068f-f76d-492a-b385-bce17b26ae30-27_2490_1719_217_150}
      \section*{DO NOT WRITE ON THIS PAGE ANSWER IN THE SPACES PROVIDED}

4. Four workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , are to be assigned to four tasks, \(1,2,3\) and 4 . Each worker must be assigned to only one task and each task must be done by only one worker. Worker A cannot do task 3 and worker D cannot do task 2
The cost, in pounds, 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. You do not need to solve this problem.

7. A clothing manufacturer can export a maximum of five batches of shirts each year. Each exported batch contains just one type of shirt, the types being T-shirts, Rugby shirts and Polo shirts. The table below shows the profit, in £ 1000 s, for the number of each exported batch type. 2.

1. 	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   3.

   	B plays 1	B plays 2	B plays 3
   A plays 1	0	- 2	6
   A plays 2	3	4	1
   A plays 3	- 1	1	- 3

   4.

   	1	2	3	4
   A	53	84	-	20
   B	87	72	41	38
   C	70	51	52	25
   D	45	-	81	70

   5. (a)
2. You may not need to use all of these tableaux

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	15	- 2	3	1	0	0	180
   \(s\)	10	1	1	0	1	0	80
   \(t\)	1	6	- 2	0	0	1	100
   \(P\)	- 1	- 2	- 5	0	0	0	0

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

3. 
   6. (a) Value of initial flow
   (b) Capacity of cut \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{d5798c81-290a-4e4b-aa46-497b62ca899b-20_1931_1099_507_408} \captionsetup{labelformat=empty} \caption{Diagram 1}
   \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{d5798c81-290a-4e4b-aa46-497b62ca899b-21_1874_953_653_589}
   7. You may not need to use all the rows of this table

   Stage	State	Action	Dest.	Value
   T-shirt

   Stage	State	Action	Dest.	Value

   Maximum annual profit £ \(\_\_\_\_\)

6. Jonathan is an author who is planning his next book tour. He will visit four countries over a period of four weeks. He will visit just one country each week. He will leave from his home, S , and will only return there after visiting the four countries. He will travel directly from one country to the next. He wishes to determine a schedule of four countries to visit. Table 1 shows the countries he could visit each week. \begin{table}[h] 2. 3.

1. You may not need to use all of these tables

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   4. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{4abb2325-b9df-4849-b08c-7db465fe85e0-18_1056_1572_1450_185} \captionsetup{labelformat=empty} \caption{Diagram 1}
   \end{figure} Maximum flow along SBET: \(\_\_\_\_\) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{4abb2325-b9df-4849-b08c-7db465fe85e0-19_1043_1572_1505_187} \captionsetup{labelformat=empty} \caption{Diagram 2}
   \end{figure} 5.

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	- 2	- 6	1	1	0	0	40
   \(s\)	2	3	2	0	1	0	80
   \(t\)	1	2	2	0	0	1	50
   \(P\)	- 4	- 2	\(- k\)	0	0	0	0

   You may not need to use all of these tableaux

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   6.

   Stage	State	Action	Destination	Value
   0	I	IS	S	\(30 - 5 = 25 ^ { * }\)

   Stage	State	Action	Destination	Value

   END

7. A company has purchased a plot of land and has decided to build four holiday homes, A, B, C and D, on the land at the rate of one home per year. The company expects that the construction costs each year will vary, depending on which houses have already been constructed and which house is currently under construction. The expected construction costs, in thousands of pounds, are shown in the table below. \begin{table}[h] \end{table} 2. You may not need to use all of these tables \begin{table}[h] \end{table} 3. You may not need to use all of these tables 4. 5. (a) You may not need to use all of these tableaux 6.

1. Value of initial flow
2. and (c) \includegraphics[max width=\textwidth, alt={}, center]{e0c66144-9e34-42fc-9f40-a87a49331483-20_725_1251_404_349} \section*{Diagram 1}
   \includegraphics[max width=\textwidth, alt={}]{e0c66144-9e34-42fc-9f40-a87a49331483-20_1070_1264_1322_349}
   \section*{Diagram 2}

(d)
(e) \includegraphics[max width=\textwidth, alt={}, center]{e0c66144-9e34-42fc-9f40-a87a49331483-21_714_1385_1306_283} \section*{Diagram 3} (f)
7. (a)

5. A leisure company owns boats of each of the following types: 2-person boats which are 4 metres long and weigh 50 kg .
4-person boats which are 3 metres long and weigh 20 kg .
8-person boats which are 14 metres long and weigh 100 kg .
The leisure company is willing to donate boats to a local sports club to accommodate up to 40 people at any one time. However, storage facilities mean that the combined length of the boats must not be more than 75 metres. Also, it must be possible to transport all the boats on a single trailer which has a maximum load capacity of 600 kg . The club intends to hire the boats out to help with the cost of maintaining them. It plans to charge \(\pounds 10 , \pounds 12\) and \(\pounds 8\) per day, for the 2 -, 4 - and 8 -person boats respectively and wishes to maximise its daily revenue ( \(\pounds R\) ). Let \(x , y\) and \(z\) represent the number of 2-, 4- and 8-person boats respectively given to the club.

1. Model this as a linear programming problem. Using the Simplex algorithm the following initial tableau is obtained:

   \(R\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)
   1	\({ } ^ { - } 10\)	\({ } ^ { - } 12\)	\({ } ^ { - } 8\)	0	0	0	0
   0	1	2	4	1	0	0	20
   0	4	3	14	0	1	0	75
   0	5	2	10	0	0	1	60

2. Explain the purpose of the variables \(s , t\) and \(u\).
3. By increasing the value of \(y\) first, work out the next two complete tableaus.
4. Explain how you know that your final tableau gives an optimal solution and state this solution in practical terms.

3 Manon makes apple cakes and banana cakes. Each apple cake is made with 3 eggs and 100 grams of flour. Each banana cake is made with 2 eggs and 150 grams of flour. Manon has 36 eggs and 1500 grams of flour.
Manon wants to make as many cakes as possible.
Formulate Manon's situation as a linear programming problem, clearly defining any variables you introduce.