Linear programming formulation for assignment

4. A group of students and teachers from a performing arts college are attending the Glasenburgh drama festival. All of the group want to see an innovative modern production of the play 'The Decision is Final'. Unfortunately there are not enough seats left for them all to see the same performance. There are three performances of the play, 1,2 , and 3 . There are two types of ticket, Adult and Student. Student tickets will be purchased for the students and Adult tickets for the teachers. The table below shows the price of tickets for each performance of the play. There are 18 teachers and 200 students requiring tickets. There are 94,65 and 80 seats available for performances 1,2 , and 3 espectively.

1. Complete the table below.

   	Adult	Student	Dummy	Seats available
   Performance 1	£5.00	£4.50
   Performance 2	£4.20	£3.80
   Performance 3	£4.60	£4.00
   Tickets needed

2. Explain why a dummy column was added to the table above.
3. Use the north-west corner method to obtain a possible solution.
4. Taking the most negative improvement index to indicate the entering square, use the stepping stone method once to obtain an improved solution. You must make your shadow costs and improvement indices clear. After a further iteration the table becomes:

   	Adult	Student	Dummy
   Performance 1		73	21
   Performance 2	18	47
   Performance 3		80

5. Demonstrate that this solution gives the minimum cost, and find its value.
   (Total 16 marks)

6. Three workers, \(\mathrm { P } , \mathrm { 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. \begin{table}[h] \end{table}

1. 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. \begin{table}[h]

   	Task A	Task B	Task C
   Worker P	33	37	31
   Worker Q	32	36	40
   Worker R	41	35	38

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table}
2. 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.
   (2)
   (Total 9 marks)

7. Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S. Each worker is to be assigned to exactly one task and each task must be assigned to just one worker. The cost, in pounds, of using each worker for each task is given 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.
(Total 7 marks)

6. 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 below. The total income is to be maximised.

1. Modify the table so it can be used to find the maximum income.
2. Formulate the above situation as a linear programming problem. You must define your decision variables and make your objective function and constraints clear.

6. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker. Worker C cannot do task 4 and worker D cannot do task 1. The cost 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.

6. Three warehouses, \(\mathrm { P } , \mathrm { Q }\) and R , supply washing machines to four retailers, \(\mathrm { A } , \mathrm { B } , \mathrm { 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.
(Total 7 marks)

2. A supplier has three warehouses, \(A , B\) and \(C\), at which there are 42,26 and 32 crates of a particular cereal respectively. Three supermarkets, \(D , E\) and \(F\), require 29, 47 and 24 crates of the cereal respectively. The supplier wishes to minimise the cost in meeting the requirements of the supermarkets. The cost, in pounds, of supplying one crate of the cereal from each warehouse to each supermarket is given in the table below. Formulate this information as a linear programming problem.

1. State your decision variables.
2. Write down the objective function in terms of your decision variables.
3. Write down the constraints, explaining what each one represents.

2. A school entrance examination consists of three papers - Mathematics, English and Verbal Reasoning. Three teams of markers are to mark one style of paper each. The table below shows the average time, in minutes, taken by each team to mark one script for each style of paper. It is desired that the scripts are marked as quickly as possible.
Formulate this information as a linear programming problem.

1. State your decision variables.
2. Write down the objective function in terms of your decision variables.
3. Write down the constraints, explaining what each one represents.

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.

Three workers, \(P\), \(Q\) and \(R\), are to be assigned to three tasks, 1, 2 and 3. Each worker is to be assigned to one task and each task must be assigned to one worker. The cost, in hundreds of pounds, of using each worker for each task is given in the table below. The cost is to be minimised.

Cost (in £100s)	Task 1	Task 2	Task 3
Worker \(P\)	8	7	3
Worker \(Q\)	9	5	6
Worker \(R\)	10	4	4

Formulate the above situation as a linear programming problem, defining the decision variables and making the objective and constraints clear. (Total 7 marks)