Linear programming

A caterer can make three different sizes of salad; small, medium and large. The caterer will make a total of at least 280 salads. The caterer wants at least 35% of the salads to be small and no more than 20% of the salads to be large. The caterer has enough ingredients to make 400 small salads or 300 medium salads or 200 large salads. The profit on each small, medium and large salad is 40p, 60p and 85p respectively. The caterer wants to maximise his total profit. Let x represent the number of small salads, y represent the number of medium salads and z represent the number of large salads. Formulate this information as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem.

1. (a)

2.

3. 42 21 15 16 35 10 31 11 27 39

4.

Length of shortest path: ________________________________________________

5.

6 (a) Key:

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28

7.

Charlie needs to buy storage containers. There are two different types of storage container available, standard and deluxe. Standard containers cost £20 and deluxe containers cost £65. Let x be the number of standard containers and y be the number of deluxe containers. The maximum budget available is £520

Write down an inequality, in terms of x and y, to model this constraint.

Three further constraints are:

Add lines and shading to Diagram 1 in the answer book to represent all four constraints. Hence determine the feasible region and label it R.

The capacity of a deluxe container is 50% greater than the capacity of a standard container. Charlie wishes to maximise the total capacity.

State an objective function, in terms of x and y.

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.

Calculate the exact coordinates of vertex V.

Determine the number of each type of container that Charlie should buy. You must make your method clear and calculate the cost of purchasing the storage containers.

The table shows the cost, in pounds, of transporting one unit of stock from each of four supply points, A, B, C and D, to each of three sales points, P, Q and R. It also shows the stock held at each supply point and the amount required at each sales point. A minimum cost solution is required.

The north-west corner method gives the following initial solution.

Taking AQ as the entering cell, use the stepping stone method to find an improved solution. Make your route clear.

Perform one further iteration of the stepping stone method to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.

Determine whether your current solution is optimal. Justify your answer.

State the cost of the solution you found in (b).

Formulate this problem as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.

Three warehouses, P, Q and R, supply washing machines to four retailers, A, B, C and D. The table gives the cost, in pounds, of transporting a washing machine from each warehouse to each retailer. It also shows the number of washing machines held at each warehouse and the number of washing machines required by each retailer. The total cost of transportation is to be minimised.

Formulate this transportation problem 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.

Harry wants to rent out boats at his local park. He can use linear programming to determine the number of each type of boat he should buy. Let x be the number of 2-seater boats and y be the number of 4-seater boats. One of the constraints is

Explain what this constraint means in the context of the question.

Another constraint is

Explain what this constraint means in the context of the question.

A third constraint is

Represent these three constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region R.

Each 2-seater boat costs £100 and each 4-seater boat costs £300 to buy. Harry wishes to minimise the total cost of buying the boats.

Write down the objective function, C, in terms of x and y.

Determine the number of each type of boat that Harry should buy. You must make your method clear and state the minimum cost.

A company makes two types of garden bench, the ‘Rustic’ and the ‘Contemporary’. The company wishes to maximise its profit and decides to use linear programming. Let x be the number of ‘Rustic’ benches made each week and y be the number of ‘Contemporary’ benches made each week. The graph in Figure 6 is being used to solve this linear programming problem. Two of the constraints have been drawn on the graph and the rejected region shaded out.

Write down the constraints shown on the graph giving your answers as inequalities in terms of x and y.

It takes 4 working hours to make one ‘Rustic’ bench and 3 working hours to make one ‘Contemporary’ bench. There are 120 working hours available in each week.

Write down an inequality to represent this information. Market research shows that ‘Rustic’ benches should be at most of the total benches made each week.

Write down, and simplify, an inequality to represent this information. Your inequality must have integer coefficients.

Add two lines and shading to Diagram 1 in your answer book to represent the inequalities of (b) and (c). Hence determine and label the feasible region, R.

The profit on each ‘Rustic’ bench and each ‘Contemporary’ bench is £45 and £30 respectively.

Write down the objective function, P, in terms of x and y.

Determine the coordinates of each of the vertices of the feasible region and hence use the vertex method to determine the optimal point.

State the maximum weekly profit the company could make.

Three workers, Harriet, Jason and Katherine, are to be assigned to three tasks, 1, 2 and 3. Each worker must be assigned to just one task and each task must be done by just one worker. The amount each person would earn, in pounds, while assigned to each task is shown in the table

The total income is to be maximised.

Modify the table so it can be used to find the maximum income.

Formulate the above situation as a linear programming problem. You must define your decision variables and make your objective function and constraints clear.

Lethna is producing floral arrangements for an awards ceremony. She will produce two types of arrangement, Celebration and Party. Let x be the number of Celebration arrangements made. Let y be the number of Party arrangements made. Figure 6 shows three constraints, other than x, y 0 The rejected region has been shaded. Given that two of the three constraints are y 30 and x 60,

write down, as an inequality, the third constraint shown in Figure 6.

Each Celebration arrangement includes 2 white roses and 4 red roses. Each Party arrangement includes 1 white rose and 5 red roses. Lethna wishes to use at least 70 white roses and at least 200 red roses.

Write down two further inequalities to represent this information.

Add two lines and shading to Diagram 1 in the answer book to represent these two inequalities.

Hence determine the feasible region and label it R.

The times taken to produce each Celebration arrangement and each Party arrangement are 10 minutes and 4 minutes respectively. Lethna wishes to minimise the total time taken to produce the arrangements.

Write down the objective function, T, in terms of x and y.

Use point testing to find the optimal number of each type of arrangement Lethna should produce, and find the total time she will take.

60

Figure 6

A company is going to hire out two types of car, standard and luxury. Let x be the number of standard cars it should buy. Let y be the number of luxury cars it should buy. Figure 6 shows three constraints, other than x, y 0 Two of these are x 20 and y 8

Write, as an inequality, the third constraint shown in Figure 6. The company decides that at least of the cars must be luxury cars.

Express this information as an inequality and show that it simplifies to

You must make the steps in your working clear.

Each time the cars are hired they need to be prepared. It takes 5 hours to prepare a standard car and it takes 6 hours to prepare a luxury car. There are 300 hours available each week to prepare the cars.

Express this information as an inequality.

Add two lines and shading to Diagram 1 in the answer book to illustrate the constraints found in parts (b) and (c).

Hence determine the feasible region and label it R.

The company expects to make £80 profit per week on each car. It therefore wishes to maximise P = 80 x + 80 y, where P is the profit per week.

Use the objective line (ruler) method to find the optimal vertex, V, of the feasible region. You must clearly draw and label your objective line and the vertex V.

Given that P is the expected profit, in pounds, per week, find the number of each type of car that the company should buy and the maximum expected profit.

A firm is planning to produce two types of radio, type A and type B. Market research suggests that, each week:

• At least 50 type A radios should be produced.

• The number of type A radios should be between 20% and 40% of the total number of radios produced.

Each type A radio requires 3 switches and each type B radio requires 2 switches. The firm can only buy 200 switches each week. The profit on each type A radio is £15. The profit on each type B radio is £12. The firm wishes to maximise its weekly profit. Formulate this situation as a linear programming problem, defining your variables.

4.

Three workers, P, Q and R, are to be assigned to three tasks, A, B and C. Each worker must be assigned to just one task and each task must be assigned to just one worker. Table 1 shows the cost of using each worker for each task. 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 and constraints clear. You are not required to solve the problem.

Table 2 shows the profit gained by using each worker for each task. The total profit is to be maximised.

Modify Table 2 in the answer book so that the Hungarian Algorithm could be used to find the maximum total profit. You are not required to solve the problem.

The graph in Figure 6 is being used to solve a linear programming problem. Two of the constraints have been drawn on the graph and the rejected regions shaded out.

Write down the constraints shown on the graph.

Two further constraints are

Add two lines and shading to Graph 1 in your answer book to represent these constraints. Hence determine the feasible region and label it R.

The objective is to

Draw a profit line on Graph 1 and use it to find the optimal solution. You must label your profit line clearly.