Resource allocation problems
Resource Allocation Problems
Resource allocation problems decide how limited resources should be assigned to activities.
Many LP models are resource allocation problems.
Basic Structure
A resource allocation problem has:
- limited resources
- activities or decisions
- resource consumption per activity
- benefit or cost per activity
- requirements or policy rules
Decision Variables
Let:
\[x_j=\text{level of activity }j\]for:
\[j=1,\ldots,n\]Activities can mean:
- producing a product
- hiring a worker type
- operating a mine
- cultivating a crop
- assigning land
- investing money
- shipping goods
Resource Constraints
If activity $j$ uses $a_{ij}$ units of resource $i$, and only $b_i$ units are available, then:
\[\sum_{j=1}^n a_{ij}x_j\le b_i\]for each resource $i$.
This is the most common resource allocation constraint.
Requirement Constraints
If activities must produce at least $d_i$ units of requirement $i$, then:
\[\sum_{j=1}^n a_{ij}x_j\ge d_i\]This appears in diet, production-demand, and mining problems.
Objective Function
If activity $j$ gives benefit $p_j$, use:
\[\max \sum_{j=1}^n p_jx_j\]If activity $j$ has cost $c_j$, use:
\[\min \sum_{j=1}^n c_jx_j\]General Resource Allocation LP
A common form is:
\[\max p^Tx\]subject to:
\[Ax\le b\] \[x\ge 0\]For minimum-cost requirement problems:
\[\min c^Tx\]subject to:
\[Ax\ge d\] \[x\ge 0\]Example: Two Mines
A company operates two mines.
Let:
\[x_1=\text{days per week operating mine X}\] \[x_2=\text{days per week operating mine Y}\]Suppose the weekly contract requires:
- $12$ tons high-grade ore
- $8$ tons medium-grade ore
- $24$ tons low-grade ore
Mine outputs per day are:
| Mine | High | Medium | Low | Cost/day |
|---|---|---|---|---|
| X | 6 | 3 | 4 | 180 |
| Y | 1 | 1 | 6 | 160 |
The LP is:
\[\min 180x_1+160x_2\]subject to:
\[6x_1+x_2\ge 12\] \[3x_1+x_2\ge 8\] \[4x_1+6x_2\ge 24\] \[x_1,x_2\ge 0\]If mines can operate at most seven days per week, add:
\[x_1\le 7,\qquad x_2\le 7\]Example: Hiring Researchers
Let:
\[x_1=\text{first-level researchers}\] \[x_2=\text{second-level researchers}\] \[x_3=\text{third-level researchers}\]If the goal is to maximize the total number hired:
\[\max x_1+x_2+x_3\]Salary budget of three million euros:
\[40000x_1+30000x_2+25000x_3\le 3000000\]Second-level salary expenditure cannot exceed $80\%$ of first-level salary expenditure:
\[30000x_2\le 0.8(40000x_1)\]The number of second-level researchers must be at least double the number of third-level researchers:
\[x_2\ge 2x_3\]At least six positions for each level:
\[x_1\ge 6,\qquad x_2\ge 6,\qquad x_3\ge 6\]If hires must be whole people, add:
\[x_1,x_2,x_3\in\mathbb{Z}\]Without integer restrictions, it is an LP relaxation.
Example: Land Allocation
Let:
\[x_1=\text{hectares allocated to lettuce}\] \[x_2=\text{hectares allocated to tomatoes}\]If lettuce and tomatoes require $18$ and $24$ labor hours per hectare, and $100$ hours are available:
\[18x_1+24x_2\le 100\]If marketing requires at least $45$ quintals lettuce and $50$ quintals tomatoes, and yields are $20$ and $30$ quintals per hectare:
\[20x_1\ge 45\] \[30x_2\ge 50\]Revenue can be maximized using selling prices and yields.
Ratio and Policy Constraints
Many resource allocation problems include policy rules.
Example:
activity A must be at least double activity B
Write:
\[x_A\ge 2x_B\]Example:
expenditure on B cannot exceed $80\%$ of expenditure on A
Write:
\[c_Bx_B\le 0.8c_Ax_A\]These are linear because variables are not multiplied together.
Common Mistakes
Avoid these mistakes:
- putting requirements as $\le$ instead of $\ge$
- forgetting maximum resource capacities
- ignoring time period differences
- using counts when the problem asks for expenditure
- forgetting policy constraints
- forgetting integrality when variables count people or vehicles
- writing ratios as fractions with variables in the denominator
Key Takeaway
Resource allocation LPs choose activity levels so limited resources are used in the best possible way while satisfying all requirements and policy rules.
Exam checkpoint
For formulation questions, show variables, objective, constraints, sign restrictions, and units. Do not solve unless the question asks for a solution.