Allocation of Resources (Leaving Cert Applied Maths): Revision Notes
Allocation of Resources
What is allocation of resources?
In resource allocation problems, you need to distribute a limited amount of resources among several different possible uses. These problems have a special characteristic: the amount you allocate to one use directly affects how much is available for other uses. This creates a chain of interconnected decisions that must be optimised together.
The key principle is that you work from sink to source - meaning you start from the final destination and work backwards to the beginning. This approach helps you make the best decisions at each stage because you know the optimal outcomes from future stages.
This backwards approach might seem counterintuitive at first, but it's essential for dynamic programming. By knowing the optimal solutions for future stages, you can make better decisions at earlier stages.
Key features of resource allocation problems
Resource allocation problems using dynamic programming have several important characteristics:
Essential Characteristics of Resource Allocation Problems:
- Finite resources: You have a limited total amount to distribute
- Multiple uses: There are several different ways to use the resources
- Interdependent decisions: What you allocate to one use affects what's available for others
- Sequential decision making: Decisions are made in stages, working backwards
- Optimisation goal: You want to maximise total value or profit
The order of allocation doesn't matter for the final result, but the systematic backwards approach ensures you find the optimal solution.
The apple orchard example
Understanding the problem
Sarah runs an apple orchard and has 5 tonnes of surplus apples after fulfilling her supermarket contracts. She can use these apples to make three different products, but she must allocate at least 1 tonne to apple sauce (due to an existing order). This means she has at most 4 tonnes available for the other two products.
The profit she earns depends on how many tonnes she allocates to each product:
Simple comparison approach
Before using dynamic programming, you might try comparing two specific options:
Simple Comparison Analysis:
Option 1: 2 tonnes pig feed + 2 tonnes cider + 1 tonne apple sauce = €165 + €185 + €125 = €475
Option 2: 0 tonnes pig feed + 2 tonnes cider + 3 tonnes apple sauce = €0 + €185 + €335 = €520
Option 2 gives more profit, but this simple comparison doesn't guarantee the optimal solution.
Dynamic programming solution
The systematic approach uses a table to work through all possibilities stage by stage. The key insight is working in reverse order - starting with apple sauce (Stage 3), then cider (Stage 2), and finally pig feed (Stage 1).
Working backwards approach
The dynamic programming table works as follows:
Understanding the Three Stages:
Stage 3 (Apple Sauce): Since Sarah must use at least 1 tonne for apple sauce, she allocates whatever tonnes are available at this stage. The value is simply the profit from apple sauce production.
Stage 2 (Cider): For each possible number of tonnes available, calculate the profit from different cider allocations plus the Optimal Value to Destination (OVD) from the remaining tonnes. The OVD represents the best possible profit from future stages (in this case, just apple sauce).
Stage 1 (Pig Feed): Similarly, calculate the profit from pig feed plus the OVD from the remaining resources going to stages 2 and 3.
The asterisks (*) in the table mark the optimal decisions at each stage for each possible resource level.
The optimal solution
Working through the complete analysis reveals:
Optimal Resource Allocation Solution:
- 2 tonnes should be allocated to pig feed
- 1 tonne should be allocated to cider
- 2 tonnes should be allocated to apple sauce
- Maximum profit: €605
This systematic approach guarantees the optimal solution by considering all possible allocations and their consequences for future decisions.
Key Points to Remember:
- Work backwards: Start from the final stage and work towards the beginning (sink to source approach)
- Consider constraints: Some allocations might be impossible due to minimum requirements or other restrictions
- Calculate total value: At each stage, consider both immediate profit and the optimal value from remaining resources (OVD)
- Mark optimal choices: Identify the best decision at each stage for each possible resource level
- Verify the solution: The final answer should specify exactly how to allocate resources for maximum benefit