1. **Stating the problem:** We want to allocate the number of groups $L$, $C$, and $P$ (lectures, classes, practicals) to maximize appreciation while not exceeding a budget of 95 million. 2. **Formulating the integer linear programming (ILP) problem:** Let: - $L$ = number of lecture groups - $C$ = number of class groups - $P$ = number of practical groups Given: - Cost per unit: $20, 25, 50$ million for $L, C, P$ respectively - Appreciation per unit: $1, 2, 4$ for $L, C, P$ respectively - Budget constraint: $20L + 25C + 50P \leq 95$ Objective: maximize total appreciation $$ \max_{L, C, P \in \mathbb{Z}_{\geq 0}} \, Z = 1 \cdot L + 2 \cdot C + 4 \cdot P $$ Subject to: $$ 20L + 25C + 50P \leq 95 $$ $$ L, C, P \geq 0 \, \text{and integers} $$ 3. **Drawing a convenient network (conceptual):** - We can see the problem as stages of decision making in dynamic programming, where each stage corresponds to one work form. - Stage 1: Decide $L$ (lectures), possible values given budget constraints - Stage 2: Decide $C$ (classes) given remaining budget - Stage 3: Decide $P$ (practicals) given remaining budget Each transition consumes part of the budget and adds appreciation. 4. **Solving using dynamic programming:** Define the value function $V_i(b)$ as the maximum appreciation achievable from stage $i$ onward with budget $b$ remaining. - Stage 3 (practicals): $$ V_3(b) = \max_{0 \leq p \leq \lfloor b/50 \rfloor} 4p $$ - Stage 2 (classes): $$ V_2(b) = \max_{0 \leq c \leq \lfloor b/25 \rfloor} \left[ 2c + V_3(b - 25c) \right] $$ - Stage 1 (lectures): $$ V_1(b) = \max_{0 \leq l \leq \lfloor b/20 \rfloor} \left[ l + V_2(b - 20l) \right] $$ With initial budget $b=95$, the solution is: $$ Z^* = V_1(95) $$ 5. **General Bellman equation for this problem:** For stage $i = 1,2,3$ with decision variable $x_i$ costing $c_i$ per unit and appreciation $a_i$ per unit, and budget $b$ remaining, $$ V_i(b) = \max_{0 \leq x_i \leq \lfloor b/c_i \rfloor} \left[ a_i x_i + V_{i+1}(b - c_i x_i) \right] $$ with terminal condition: $$ V_{4}(b) = 0 $$ because after the last stage there is no further appreciation. **Final answer:** The ILP formulation is: $$\max_{L,C,P \in \mathbb{Z}_{\geq 0}} L + 2C + 4P$$ subject to $$20L + 25C + 50P \leq 95$$ and using dynamic programming as above optimizes the allocation maximizing appreciation without exceeding the budget.