7.06f Integer programming: branch-and-bound method

5. A travel company offers a touring holiday which stops at four locations, \(A , B , C\) and \(D\). The tour may be taken with the locations appearing in any order, but the number of days spent in each location is dependent on its position in the tour, as shown in the table below. Showing the state of the table at each stage, use the Hungarian algorithm to find the order in which to complete the tour so as to maximise the total number of days. State the maximum total number of days that can be spent in the four locations.
(11 marks)

3. Whilst Clive is in hospital, four of his friends decide to redecorate his lounge as a welcomehome surprise. They divide the work to be done into four jobs which must be completed in the following order:

• strip the wallpaper,
• paint the woodwork and ceiling,
• hang the new wallpaper,
• replace the fittings and tidy up.

The table below shows the time, in hours, that each of the friends is likely to take to complete each job. As they do not know how long Clive will be in hospital his friends wish to complete the redecoration in the shortest possible total time.

1. Use the Hungarian method to obtain the optimal allocation of the jobs, showing the state of the table after each stage in the algorithm.
   (6 marks)
2. Hence, find the minimum time in which the friends can redecorate the lounge.
   (1 mark)

3. Four people are contributing to the entertainment section of an email magazine. For one issue reviews are required for a film, a musical, a ballet and a concert such that each person reviews one show. The people in charge of the magazine will pay each person's expenses and the cost, in pounds, for each reviewer to attend each show are given below. Use the Hungarian algorithm to find an optimal assignment which minimises the total cost. State the total cost of this allocation.
(10 marks)

6 An initial simplex tableau is shown below. The variables \(s , t\) and \(u\) are slack variables.

1. For the LP problem that this tableau represents, write down the following, in terms of \(x\) and \(y\) only.
   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). \includegraphics[max width=\textwidth, alt={}, center]{133395d2-5020-4054-a229-70168f1d0f95-7_883_1043_1272_244} The optimal solution is \(P = 23\), when \(x = 0\) and \(y = 4.6\).
2. 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 \(\mathbf { 2 }\) decimal places. The tableau entry 18.8 is reduced to 0 .
3. Describe carefully what changes, if any, this makes to the following.

4. A linear programming problem in \(x , y\) and \(z\) is described as follows. Maximise \(\quad P = - x + y\) subject to $$\begin{gathered} x + 2 y + z \leqslant 15 \\ 3 x - 4 y + 2 z \geqslant 1 \\ 2 x + y + z = 14 \\ x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{gathered}$$

1. 1. Eliminate \(z\) from the first two inequality constraints, simplifying your answers.
   2. Hence state the maximum possible value of \(P\) Given that \(P\) takes the maximum possible value found in (a)(ii),
2. 1. determine the maximum possible value of \(x\)
   2. Hence find a solution to the linear programming problem.

5. A linear programming problem in \(x\) and \(y\) is described as follows. Maximise \(\quad P = 2 x + 3 y\) subject to $$\begin{aligned} x & \geqslant 25 \\ y & \geqslant 25 \\ 7 x + 8 y & \leqslant 840 \\ 4 y & \leqslant 5 x \\ 5 y & \geqslant 3 x \\ x , y & \geqslant 0 \end{aligned}$$

1. Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence determine the feasible region and label it R .
2. Use the objective line method to find the optimal vertex, V, of the feasible region. You must clearly draw and label your objective line and the vertex V.
3. Calculate the exact coordinates of vertex V. Given that an integer solution is required,
4. determine the optimal solution with integer coordinates. You must make your method clear.

5. Two friends, Anaira and Tommi, play a game involving two positive numbers \(x\) and \(y\) Anaira gives Tommi the following clues to see if he can correctly determine the value of \(x\) and the value of \(y\)

• \(x\) is greater than \(y\) and the difference between the two is at least 100
• \(x\) is at most 5 times as large as \(y\)
• the sum of \(2 x\) and \(3 y\) is at least 350
• the sum of \(x\) and \(y\) is as small as possible

Tommi decides to solve this problem by using the big-M method.

1. Set up an initial tableau for solving this problem using the big-M method. As part of your solution, you must show
   • how the constraints were made into equations using one slack variable, exactly two surplus variables and exactly two artificial variables
   • how the objective function was formed
   The big-M method is applied until the tableau containing the optimal solution to the problem is found. One row of this final tableau is as follows.

   b.v.	\(x\)	\(y\)	\(s _ { 1 }\)	\(S _ { 2 }\)	\(\mathrm { S } _ { 3 }\)	\(a _ { 1 }\)	\(a _ { 2 }\)	Value
   \(x\)	1	0	\(- \frac { 3 } { 5 }\)	0	\(- \frac { 1 } { 5 }\)	\(\frac { 3 } { 5 }\)	\(\frac { 1 } { 5 }\)	130

2. 1. State the value of \(x\)
   2. Hence deduce the value of \(y\), making your reasoning clear.

7. A linear programming problem in \(x , y\) and \(z\) is described as follows. Maximise \(P = 3 x + 2 y + 2 z\) subject to $$\begin{aligned} & 2 x + 2 y + z \leqslant 25 \\ & x + 4 y \leqslant 15 \\ & x \geqslant 3 \end{aligned}$$

1. Explain why the Simplex algorithm cannot be used to solve this linear programming problem. The big-M method is to be used to solve this linear programming problem.
2. Define, in this context, what M represents. You must use correct mathematical language in your answer. The initial tableau for a big-M solution to the problem is shown below.

   b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(s _ { 2 }\)	\(s _ { 3 }\)	\(t _ { 1 }\)	Value
   \(s _ { 1 }\)	2	2	1	1	0	0	0	25
   \(s _ { 2 }\)	1	4	0	0	1	0	0	15
   \(t _ { 1 }\)	1	0	0	0	0	-1	1	3
   \(P\)	\(- ( 3 + M )\)	-2	-2	0	0	M	0	\(- 3 M\)

3. Explain clearly how the equation represented in the b.v. \(t _ { 1 }\) row was derived.
4. Show how the equation represented in the b.v. \(P\) row was derived. The tableau obtained from the first iteration of the big-M method is shown below.

   b.v.	\(x\)	\(y\)	\(z\)	\(s _ { 1 }\)	\(s _ { 2 }\)	\(s _ { 3 }\)	\(t _ { 1 }\)	Value
   \(s _ { 1 }\)	0	2	1	1	0	2	-2	19
   \(s _ { 2 }\)	0	4	0	0	1	1	-1	12
   \(x\)	1	0	0	0	0	-1	1	3
   P	0	-2	-2	0	0	-3	\(3 +\) M	9

5. Solve the linear programming problem, starting from this second tableau. You must

2. The table shows the cost, in pounds, of transporting one unit of stock from each of three supply points, \(\mathrm { A } , \mathrm { B }\) and C , to each of four demand points, \(1,2,3\) and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.

1. Use the north-west corner method to obtain an initial solution.
   (1)
2. Taking A4 as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear.
   (2)
3. Taking the most negative improvement index to indicate the entering cell, use the stepping-stone method once to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
4. Determine whether your current solution is optimal, giving a reason for your answer.

1. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to each of four demand points, \(1,2,3\) and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution to this transportation problem is required.

\begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h] \end{table}

1. Explain why a zero has been placed in cell C 2 in Table 2. State the other cell in Table 2 in which the zero could have been placed.
2. State the shadow costs clearly and enter the improvement indices into Table 3 in your answer book. Taking the most negative improvement index to indicate the entering cell,
   [0pt]
3. list the stepping-stone route that should be used to obtain the next solution. You should make clear the cells that are included in your route and state your entering and exiting cells. [You do not need to state the next solution. You do not need to solve this problem.]

2. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of three supply points, \(\mathrm { A } , \mathrm { B }\) and C , to each of four demand points, 1, 2, 3 and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required. \begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h] \end{table}

1. Taking A4 as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear.
2. Taking the most negative improvement index to indicate the entering cell, use the stepping-stone method once to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
3. Determine whether your current solution is optimal, giving a reason for your answer.
4. State the cost of your current solution.

A three-variable linear programming problem in \(x\), \(y\) and \(z\) is to be solved. The objective is to maximise the profit P. The following tableau was obtained.

1. State, giving your reason, whether this tableau represents the optimal solution. [1]
2. State the values of every variable. [3]
3. Calculate the profit made on each unit of \(y\). [2]

(Total 6 marks)

A two person zero-sum game is represented by the following pay-off matrix for player \(A\).

	\(B\) plays 1	\(B\) plays 2	\(B\) plays 3
\(A\) plays 1	5	7	2
\(A\) plays 2	3	8	4
\(A\) plays 3	6	4	9

1. Formulate the game as a linear programming problem for player \(A\), writing the constraints as equalities and clearly defining your variables. [5]
2. Explain why it is necessary to use the simplex algorithm to solve this game theory problem. [1]
3. Write down an initial simplex tableau making your variables clear. [2]
4. Perform two complete iterations of the simplex algorithm, indicating your pivots and stating the row operations that you use. [8]

(Total 16 marks)

A linear programming problem is \begin{align} \text{Maximise } P &= 4x - y - 2z
\text{subject to } x + 5y + 3z &\leq 60
2x - 5y &\leq 80
2y + z &\leq 10
x \geq 0, y &\geq 0, z \geq 0 \end{align}

1. Use the simplex algorithm to solve the problem. [7]

In the case when \(z = 0\) the feasible region can be represented graphically. \includegraphics{figure_1} The vertices of the feasible region are \((0, 0)\), \((40, 0)\), \((46.67, 2.67)\), \((35, 5)\) and \((0, 5)\), where non-integer values are given to 2 decimal places. The linear programming problem is given the additional constraint that \(x\) and \(y\) are integers.

1. Use branch-and-bound, branching on \(x\) first, to show that the optimum solution with this additional constraint is \(x = 45, y = 2\). [7]