Formulating Resource Allocation Problems as LPs

Translating a verbal resource-allocation scenario into a linear program: choosing decision variables, writing the linear objective, and writing one capacity constraint per limited resource.

Step 1 of 157%

Tutorial

Introduction

A resource allocation problem asks: given limited resources, how should we divide them among competing activities to maximize total profit (or minimize total cost)?

To model such a problem as a linear program, we follow three steps.

Decision variables. Introduce one variable $x_j$ for each activity, representing the level of that activity (units produced, hours used, acres planted, etc.).
Objective function. If each unit of activity $j$ contributes $c_j$ dollars of profit, the total profit is the linear function

\text{maximize} \quad c_1 x_1 + c_2 x_2 + \cdots + c_n x_n.

Resource constraints. If resource $i$ is available in total amount $b_i$ and each unit of activity $j$ consumes $a_{ij}$ units of resource $i$ , then total usage cannot exceed availability:

a_{i1} x_1 + a_{i2} x_2 + \cdots + a_{in} x_n \le b_i.

Activity levels are also non-negative: $x_j \ge 0$ for every $j$ .

For instance, if making one chair requires $2$ hours of labor, one table requires $5$ hours, and $40$ hours are available, the labor constraint is

2 x_1 + 5 x_2 \le 40.