REZOLVAREA PROBLEMELOR DE ALOCARE

REZOLVAREA PROBLEMELOR DE ALOCARE

Probleme de alocare

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. In 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 incat 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 II.3.1.

Tabelul II.3.1 - Timpii estimati pentru terminarea fiecarui proiect

Figura II.3.1 prezinta graful de retea pentru problema analizata.

Figura II.3.1 - Graful de retea atasat problemei

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.

Problema poate fi rezolvata folosind metoda programarii liniare. Avem nevoie de o variabila pentru fiecare arc si o restrictie pentru fiecare nod. Vom utiliza variabile de decizie cu doi indici x_ij - repartizarea liderului i la proiectul j.

Deci vom avea 9 variabile de decizie:

unde i=1,2,3 si j=1,2,3.

Utilizand aceste notatii:

Timpul necesar pentru finalizarea proiectelor de catre Ionescu este 10x₁₁+15x₁₂+9x₁₃ (doar una din variabilele de decizie poate lua valoarea 0).

Timpul necesar pentru finalizarea proiectelor de catre Popescu este 9x₂₁+18x₂₂+5x₂₃ (doar una din variabilele de decizie poate lua valoarea 0).

Timpul necesar pentru finalizarea proiectelor de catre Georgescu este 6x₃₁+14x₃₂+3x₃₃ (doar una din variabilele de decizie poate lua valoarea 0).

Suma acestor timpi furnizeaza numarul total de zile pentru a finaliza cele trei studii de piata. Astfel, functia obiectiv este:

Min (10x₁₁+15x₁₂+9x₁₃+9x₂₁+18x₂₂+5x₂₃+6x₃₁+14x₃₂+3x₃₃)

Restrictiile reflecta faptul ca fiecare lider poate fi repartizat cel mult unui client si fiecare client trebuie sa aiba repartizat un lider. Aceste restrictii sunt:

Combinand functia obiectiv cu restrictiile obtinem urmatorul model:

Min (10x₁₁+15x₁₂+9x₁₃+9x₂₁+18x₂₂+5x₂₃+6x₃₁+14x₃₂+3x₃₃)

Foaia de calcul folosita pentru rezolvarea problemei este prezentata in figura II.3.2.

Figura II.3.2 - Foaia de calcul atasata problemei

Datele problemei sunt introduse in domeniul A1:D7.

Se rezolva problema utilizand Solver-ul. Caseta de dialog Solver Parameters se completeaza ca in figura II.3.3. Optiunile selectate sunt Assume Linear Model si Assume

Non-Negative.

Figura II.3.3 - Caseta Solver Parameters

Solutia optima a problemei este: Ionescu este repartizat clientului 2, Popescu clientului 3 si Georgescu clientului 1. Timpul de finalizare a celor trei proiecte este de 26 de zile.

Variatii ale problemei

Deoarece problemele de alocare pot fi tratate ca fiind cazuri speciale de probleme de transport, variatiile care pot aparea la problemele de alocare sunt aceleasi ca si la problemele de transport.

Numarul total de agenti (oferta) este diferit de numarul total de activitati (cererea)

Daca numarul de agenti depaseste numarul de activitati, agentii suplimentari vor ramane nealocati in modelul de programare liniara. Daca numarul de activitati este mai mare decat numarul de agenti, modelul de programare liniara nu va avea o solutie fezabila. In aceasta situatie este suficient sa adaugam un numar suficient de "agenti falsi" pentru ca numarul de agenti sa fie egal cu numarul de activitati. In functia obiectiv coeficientii pentru agentii falsi vor fi zero.

Daca problemele de alocare sunt evaluate in termeni de venit sau profit vom avea de rezolvat o problema de maximizare in loc de una de minimizare.

In plus, daca una sau mai multe alocari nu pot fi acceptate, variabilele de decizie corespunzatoare vor fi eliminate din modelul de programare liniara. Pentru exemplul prezentat acest lucru poate aparea daca la un agent nu are experienta necesara sa lucreze la un proiect. Pentru a nu face modificari in foaia de calcul, cea mai simpla solutie ar fi atasarea unor costuri foarte mari pentru variabilele de decizie ce corespund alocarilor ce nu pot fi acceptate.

Modelul general pentru problemele de alocare este: