Fundamentals of Operational Research
Assignment
School of Mathematics
Year 2024/2025
INSTRUCTIONS:
1. This assignment is individual and it is worth 20% of the mark of the course.
2. You must consider this as an exam that you do at home. The same policy than in an exam will be applied for assignments with signs of plagiarism. This is a serious academic offence.
3. The submission deadline is Monday 11 November at 11:00 on Gradescope.
4. Provide clear answers and justify every argument that you use. This does not mean to explain in twenty lines what can be said in two. Neither to explain in two words what requires two or three lines. There is no minimum or maximum number of pages that you can submit, but take into account these guidelines.
An agricultural company, Your Grain, has 5 machines that can be sent to 2 different areas of a field to collect wheat grain. If dj machines are sent to area j , j ∈ {1, 2}, then rj (dj ) tonnes can be collected on one single day as follows:
● r1 (d1 ) = 2d1 + 7, d1 > 0.
● r2 (d2 ) = 7d2 + 3, d2 > 0.
● r1 (0) = r2 (0) = 0.
The goal is to determine how to allocate the machines to the areas of the field to maximize the total number of grain tonnes collected per day. Any machine sent to an area must work there for the full day. Thus, it is not possible to have fractional allocations of machines. In addition, no machine can be left unallocated.
1. (20 marks) Formulate the problem as an integer programming problem. That is, define the necessary decision variables, write the objective function, and write all the necessary constraints, explaining all of them briefly.
2. (10 marks) From now on we will focus exclusively on backwards dynamic programming. First, define the states and stages for this problem.
3. (30 marks) Now define a backwards dynamic programming recursive expression to max- imize the number of wheat tonnes that can be collected each day. But do not solve the problem yet (you will do it in the next part of this question). What value of this recursive expression do you need to compute to solve the problem?
4. (40 marks) Finally, solve the problem using the recursive expression that you have defined on the previous question to compute the value that you indicated. You are not allowed to compute any shortest or longest path on a graph. You must solve this problem by using a recursive expression.