Problemele de alocare pot aparea in diverse situatii de luare a deciziilor. Problemele tipice sunt: alocarea lucrarilor pe masini, repartizarea personalului in diverse centre teritoriale, repartizarea agentilor care sa efectueze anumite activitati. O caracteristica distincta este ca unui agent ii este asignata o singura activitate si se incearca optimizarea unui obiectiv, cum ar fi minimizarea costurilor, minimizarea timpului, maximizarea profitului, etc.
Pentru a ilustra modul de rezolvare a problemelor de alocare vom considera urmatorul exemplu: Firma ABC, specializata in studii de marketing are trei clienti noi. Fiecarui proiect ii trebuie alocat un lider de proiect. Timpul necesar pentru realizarea proiectului depinde de experienta si abilitatea liderului de proiect. }n prezent sunt disponibile doar trei persoane, proiectele au aproximativ aceeasi prioritate si nu pot fi realizate in acelasi timp.
Conducerea firmei trebuie sa stabileasca ce lider de proiect va coordona fiecare studiu astfel inc`t cele trei studii sa se termine in timpul total cel mai scurt. Unui lider i se poate aloca doar un proiect. Cu trei clienti si trei studii sunt posibile 9 alternative. Timpii estimati pentru finalizarea fiecarui proiect sunt prezentati in tabelul 15.1. Nodurile corespund liderilor de proiect si clientilor, iar arcurile reprezinta repartizarile posibile ale liderilor de proiect clientilor.
Oferta in fiecare nod origine este 1 si cererea in fiecare nod destinatie este 1. Costul repartizarii unui lider de proiect la un client este timpul necesar pentru realizarea studiului.
Observati asemanarea dintre problemele de alocare si cele de transport, problemele de alocare fiind un caz special de probleme de transport in care toate ofertele si cererile au valoarea 1, iar cantitatea transportata pe fiecare arc este 0 sau 1.
