Linear Programming Formulation

4 The "Cuddly Friends Company" produces soft toys. For one day's production run it has available \(11 \mathrm {~m} ^ { 2 }\) of furry material, \(24 \mathrm {~m} ^ { 2 }\) of woolly material and 30 glass eyes. It has three soft toys which it can produce: The "Cuddly Aardvark", each of which requires \(0.5 \mathrm {~m} ^ { 2 }\) of furry material, \(2 \mathrm {~m} ^ { 2 }\) of woolly material and two eyes. Each sells at a profit of \(\pounds 3\). The "Cuddly Bear", each of which requires \(1 \mathrm {~m} ^ { 2 }\) of furry material, \(1.5 \mathrm {~m} ^ { 2 }\) of woolly material and two eyes. Each sells at a profit of \(\pounds 5\). The "Cuddly Cat", each of which requires \(1 \mathrm {~m} ^ { 2 }\) of furry material, \(1 \mathrm {~m} ^ { 2 }\) of woolly material and two eyes. Each sells at a profit of \(\pounds 2\). An analyst formulates the following LP to find the production plan which maximises profit. $$\begin{array} { l l } \text { Maximise } & 3 a + 5 b + 2 c
\text { subject to } & 0.5 a + b + c \leqslant 11 ,
& 2 a + 1.5 b + c \leqslant 24 ,
& 2 a + 2 b + 2 c \leqslant 30 . \end{array}$$

1. Explain how this formulation models the problem, and say why the analyst has not simplified the last inequality to \(a + b + c \leqslant 15\).
2. The final constraint is different from the others in that the resource is integer valued. Explain why that does not impose an additional difficulty for this problem.
3. Solve this problem using the simplex algorithm. Interpret your solution and say what resources are left over. On a particular day an order is received for two Cuddly Cats, and the extra constraint \(c \geqslant 2\) is added to the formulation.
4. Set up an initial simplex tableau to deal with the modified problem using either the big-M approach or two-phase simplex. Do not perform any iterations on your tableau.
5. Show that the solution given by \(a = 8 , b = 2\) and \(c = 5\) uses all of the resources, but that \(a = 6 , b = 6\) and \(c = 2\) gives more profit. What resources are left over from the latter solution?

4 A publisher is considering producing three books over the next week: a mathematics book, a novel and a biography. The mathematics book will sell at \(\pounds 10\) and costs \(\pounds 4\) to produce. The novel will sell at \(\pounds 5\) and costs \(\pounds 2\) to produce. The biography will sell at \(\pounds 12\) and costs \(\pounds 5\) to produce. The publisher wants to maximise profit, and is confident that all books will be sold. There are constraints on production. Each copy of the mathematics book needs 2 minutes of printing time, 1 minute of packing time, and \(300 \mathrm {~cm} ^ { 3 }\) of temporary storage space. Each copy of the novel needs 1.5 minutes of printing time, 0.5 minutes of packing time, and \(200 \mathrm {~cm} ^ { 3 }\) of temporary storage space. Each copy of the biography needs 2.5 minutes of printing time, 1.5 minutes of packing time, and \(400 \mathrm {~cm} ^ { 3 }\) of temporary storage space. There are 10000 minutes of printing time available on several printing presses, 7500 minutes of packing time, and \(2 \mathrm {~m} ^ { 3 }\) of temporary storage space.

1. Explain how the following initial feasible tableau models this problem.

   P	\(x\)	\(y\)	\(z\)	\(s 1\)	\(s 2\)	\(s 3\)	RHS
   1	- 6	- 3	- 7	0	0	0	0
   0	2	1.5	2.5	1	0	0	10000
   0	1	0.5	1.5	0	1	0	7500
   0	300	200	400	0	0	1	2000000

2. Use the simplex algorithm to solve your LP, and interpret your solution.
3. The optimal solution involves producing just one of the three books. By how much would the price of each of the other books have to be increased to make them worth producing? There is a marketing requirement to provide at least 1000 copies of the novel.
4. Show how to incorporate this constraint into the initial tableau ready for an application of the two-stage simplex method. Briefly describe how to use the modified tableau to solve the problem. You are NOT required to perform the iterations.

1 Hussain wants to travel by train from Edinburgh to Southampton, leaving Edinburgh after 9 am and arriving in Southampton by 4 pm . He wants to leave Edinburgh as late as possible.
Hussain rings the train company to find out about the train times. Write down a question he might ask that leads to
(A) an existence problem,
(B) an optimisation problem.

6 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.

1. 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.
2. Determine how many beads of each colour will be used in each bracelet.
3. 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.
4. Determine the least possible value of Sasha’s maximum total profit.
5. Why might Sasha not achieve this maximum profit?

8. A shop sells three types of pen. These are ballpoint pens, rollerball pens and fountain pens. The shop manager knows that each week she should order

• at least 50 pens in total
• at least twice as many rollerball pens as fountain pens

In addition,

• at most \(60 \%\) of the pens she orders must be ballpoint pens
• at least a third of the pens she orders must be rollerball pens

Each ballpoint pen costs \(\pounds 2\), each rollerball pen costs \(\pounds 3\) and each fountain pen costs \(\pounds 5\)
The shop manager wants to minimise her costs.
Let \(x\) represent the number of ballpoint pens ordered, let \(y\) represent the number of rollerball pens ordered and let \(z\) represent the number of fountain pens ordered.

1. Formulate this information as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients. The shop manager decides to order exactly 10 fountain pens. This reduces the problem to the following $$\begin{array} { l r } \text { Minimise } & P = 2 x + 3 y
   \text { subject to } & x + y \geqslant 40
   & 2 x - 3 y \leqslant 30
   - x + 2 y \geqslant 10
   & y \geqslant 20
   & x \geqslant 0 \end{array}$$
2. Represent these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region R .
3. Use the objective line method to find the optimal vertex, V, of the feasible region. You must make your objective line clear and label the optimal vertex V.
4. Write down the number of each type of pen that the shop manager should order. Calculate the cost of this order.
   (Total \(\mathbf { 1 6 }\) marks)