7.06c Working with constraints: algebra and ad hoc methods

5. A carpet manufacturer has two warehouses, \(W _ { 1 }\) and \(W _ { 2 }\), which supply carpets for three sales outlets, \(S _ { 1 } , S _ { 2 }\) and \(S _ { 3 }\). At one point \(S _ { 1 }\) requires 40 rolls of carpet, \(S _ { 2 }\) requires 23 rolls of carpet and \(S _ { 3 }\) requires 37 rolls of carpet. At this point \(W _ { 1 }\) has 45 rolls in stock and \(W _ { 2 }\) has 40 rolls in stock. The following table shows the cost, in pounds, of transporting one roll from each warehouse to each sales outlet: The company's manager wishes to supply the 85 rolls that are in stock such that transportation costs are kept to a minimum.

1. Use the north-west corner rule to obtain an initial solution to the problem.
2. Calculate improvement indices for the unused routes.
3. Use the stepping-stone method to obtain an optimal solution.

5 Greetings cards are sold in luxury, standard and economy packs.
The table shows the cost of each pack and number of cards of each kind in the pack. Alice needs 25 cards, of which at least 8 must be handmade cards, at least 8 must be cards with flowers and at least 4 must be cards with animals.

1. Explain why Alice will need to buy at least two packs of cards. Alice does not want to spend more than \(\pounds 12\) on the cards.
2. (a) List the combinations of packs that satisfy all Alice's requirements.
   (b) Which of these is the cheapest? Ben offers to buy any cards that Alice buys but does not need. He will pay 12 pence for each handmade card and 5 pence for any other card. Alice does not want her net expenditure (the amount she spends minus the amount that Ben pays her) on the cards to be more than \(\pounds 12\).
3. Show that Alice could now buy two luxury packs. Alice decides to buy exactly 2 packs, of which \(x\) are luxury packs, \(y\) are standard packs and the rest are economy packs.
4. Give an expression, in terms of \(x\) and \(y\) only, for the number of cards of each type that Alice buys. Alice wants to minimise her net expenditure.
5. Find, and simplify, an expression for Alice's minimum net expenditure in pence, in terms of \(x\) and \(y\). You may assume that Alice buys enough cards to satisfy her own requirements.
6. Find Alice's minimum net expenditure.

7. Emily is planning to sell three types of milkshake, strawberry, vanilla and chocolate. Emily has completed some market research and has used this to form the following constraints on the number of milkshakes that she will sell each week.

• She will sell fewer than 200 non-vanilla milkshakes in total.
• She will sell at most 2.5 times as many strawberry milkshakes as vanilla milkshakes.
• At most, \(75 \%\) of the milkshakes that she will sell will be vanilla.

The profit on each strawberry milkshake sold is \(\pounds 0.75\), the profit on each vanilla milkshake sold is \(\pounds 1.20\) and the profit on each chocolate milkshake sold is \(\pounds 1.45\) Emily wants to maximise her profit.
Let \(x\) represent the number of strawberry milkshakes sold, let \(y\) represent the number of vanilla milkshakes sold and let \(z\) represent the number of chocolate milkshakes sold.

1. Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. In week 1, Emily sells 100 strawberry milkshakes and 25 chocolate milkshakes.
2. Calculate the maximum possible profit and minimum possible profit, in pounds, for the sale of all milkshakes in week 1. You must show your working.

5. A clothing shop sells a particular brand of shirt, which comes in three different sizes, small, medium and large. Each month the manager of the shop orders \(x\) small shirts, \(y\) medium shirts and \(z\) large shirts.
The manager forms constraints on the number of each size of shirts he will have to order.
One constraint is that for every 3 medium shirts he will order at least 5 large shirts.

1. Write down an inequality, with integer coefficients, to model this constraint. Two further constraints are $$x + y + z \geqslant 250 \text { and } x \leqslant 0.2 ( x + y + z )$$
2. Use these two constraints to write down statements, in context, that describe the number of different sizes of shirt the manager will order. The cost of each small shirt is \(\pounds 6\), the cost of each medium shirt is \(\pounds 10\) and the cost of each large shirt is \(\pounds 15\) The manager must minimise the total cost of all the shirts he will order.
3. Write down the objective function. Initially, the manager decides to order exactly 150 large shirts.
4. 1. Rewrite the constraints, as simplified inequalities with integer coefficients, in terms of \(x\) and \(y\) only.
   2. Represent these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region \(R\).
5. Use the objective line method to find the optimal vertex, \(V\), of the feasible region. You must make your objective line clear and label \(V\).
6. Write down the number of each size of shirt the manager should order. Calculate the total cost of this order. Later, the manager decides to order exactly 50 small shirts and exactly 75 medium shirts instead of 150 large shirts.
7. Find the minimum number of large shirts the manager should order and show that this leads to a lower cost than the cost found in (f).

8. A bakery makes three types of doughnut. These are ring, jam and custard. The bakery has the following constraints on the number of doughnuts it must make each day.

• The total number of doughnuts made must be at least 200
• They must make at least three times as many ring doughnuts as jam doughnuts
• At most \(70 \%\) of the doughnuts the bakery makes must be ring doughnuts
• At least a fifth of the doughnuts the bakery makes must be jam doughnuts

It costs 8 pence to make each ring doughnut, 10 pence to make each jam doughnut and 14 pence to make each custard doughnut. The bakery wants to minimise the total daily costs of making the required doughnuts. Let \(x\) represent the number of ring doughnuts, let \(y\) represent the number of jam doughnuts and let z represent the number of custard doughnuts the bakery makes each day.

1. Formulate this as a linear programming problem stating the objective and listing the constraints as simplified inequalities with integer coefficients. On a given day, instead of making at least 200 doughnuts, the bakery requires that exactly 200 doughnuts are made. Furthermore, the bakery decides to make the minimum number of jam doughnuts which satisfy all the remaining constraints. Given that the bakery still wants to minimise the total cost of making the required doughnuts, use algebra to
2. 1. calculate the number of each type of doughnut the bakery will make on that day,
   2. calculate the corresponding total cost of making all the doughnuts. \section*{END}

5. \begin{figure}[h] \end{figure} Figure 5 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.

1. Write down the inequalities that form region \(R\).
2. Find the exact coordinates of the vertices of the feasible region. The objective is to maximise \(P\), where \(P = 2 x + 3 y\)
3. Use point testing to find the optimal vertex, V, of the feasible region. The objective is changed to maximise \(Q\), where \(Q = 2 x + \lambda y\) Given that \(\lambda\) is a constant and V is still the only optimal vertex of the feasible region,
4. find the range of possible values of \(\lambda\).

6. \begin{figure}[h] \end{figure} Figure 4 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region. The vertices of the feasible region are \(A ( 4,7 ) , B ( 5,3 ) , C ( - 1,5 )\) and \(D ( - 2,1 )\).

1. Determine the inequality that defines the boundary of \(R\) that passes through vertices \(A\) and \(C\), leaving your answer with integer coefficients only. The objective is to maximise \(P = 5 x + y\)
2. Find the coordinates of the optimal vertex and the corresponding value of \(P\). The objective is changed to maximise \(Q = k x + y\)
3. If \(k\) can take any value, find the range of values of \(k\) for which \(A\) is the only optimal vertex.

2. An outdoor theatre is holding a summer gala performance. The theatre owner must decide whether to take out insurance against rain for this performance. The theatre owner estimates that

• on a fine day, the total profit will be \(\pounds 15000\)
• on a wet day, the total loss will be \(\pounds 20000\)

Insurance against rain costs \(\pounds 2000\). If the performance must be cancelled due to rain, then the theatre owner will receive \(\pounds 16000\) from the insurer. If the performance is not cancelled due to rain, then the theatre owner will receive nothing from the insurer. The probability of rain on the day of the gala performance is 0.2
Draw a decision tree and hence determine whether the theatre owner should take out the insurance against rain for this performance.

3. The table below shows the stock held at each supply point and the stock required at each demand point in a standard transportation problem. The table also shows the cost, in pounds, of transporting the stock from each supply point to each demand point. The problem is partially described by the linear programming formulation below.
Let \(x _ { i j }\) be the number of units transported from i to j $$\begin{aligned} & \text { where } \quad i \in \{ A , B , C , D \} \\ & \quad j \in \{ Q , R , S \} \text { and } x _ { i j } \geqslant 0 \\ & \text { Minimise } P = 23 x _ { A Q } + 18 x _ { A R } + 12 x _ { A S } + 8 x _ { B Q } + 10 x _ { B R } + 14 x _ { B S } \\ & \quad + 11 x _ { C Q } + 14 x _ { C R } + 21 x _ { C S } + 19 x _ { D Q } + 15 x _ { D R } + 11 x _ { D S } \end{aligned}$$

1. Write down, as inequalities, the constraints of the linear program.
2. Use the north-west corner method to obtain an initial solution to this transportation problem.
3. Taking AS as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear.
4. Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by showing the route and the

3. The table below shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { E } , \mathrm { F } , \mathrm { G }\) and H , to three sales points, \(\mathrm { A } , \mathrm { B }\) and C . It also shows the stock held at each supply point and the amount required at each sales point.
A minimum cost solution is required.

1. Explain why it is necessary to add a dummy demand point.
2. On Table 1 in the answer book, insert appropriate values in the dummy demand column, D. After finding an initial feasible solution and applying one iteration of the stepping-stone method, the table becomes

   	\(A\)	\(B\)	\(C\)	\(D\)
   \(E\)	21
   \(F\)	19	13
   \(G\)		6	23
   \(H\)	5			18

3. Starting with GD as the next entering cell, perform two further iterations of the stepping-stone method to obtain an improved solution. You must make your method clear by showing your routes and stating the

5. Sebastien needs to make a journey. He can choose between travelling by plane, by train or by coach. Sebastien knows the exact costs of all three travel options, but he also wants to account for his travel time, including any possible delays. The cost of Sebastien's time is \(\pounds 50\) per hour.
The table below shows the costs, the journey times (without delays), and the corresponding probabilities of delays, for each travel option.

1. By drawing a decision tree, evaluate the EMV of the total cost of Sebastien's journey for each node of your tree.
2. Hence state the travel option that minimises the EMV of the total cost of Sebastien's journey.
3. A cube root utility function is applied to the total costs of each option. Determine the travel option with the best expected utility and state the corresponding value.

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

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.

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.

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

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]