CAPITOLUL IV

REPARTIZAREA LUCRĂRILOR PE EXECUTANȚI PE BAZA CHELTUIELILOR TOTALE MINIME PRIN METODE ALE CERCETĂRII

OPERAȚIONALE

Această perfecţionare a programării operative se poate realiza prin metodele cercetării operaţionale, care implică alocarea executanţilor direcţi la nivelul sarcinilor de producţie, o sarcină de producţie putând utiliza o combinaţie de executanţi (fig. 3.1).

Fig. 3.1 Repartizare tip distribuire

Într-o problemă de afectare (repartizare) intervin n resurse (R1, R2,.....Rn) care trebuie repartizate la n activităţi (A1, A2,.....An), astfel încât:

- fiecare resursă să fie repartizată la câte o singură activitate;- fiecărei activităţi să i se repartizeze câte o singură resursă,

Aj

Ri

A1 A2 . . . Aj … An

R1 c11 c12 ….. c1j ….. c1n

R2 c21 c22 ….. c2j ….. c2n

.

.

.

.

.

.Ri ci1 ci2 …... cij …... cin

.

.

.

.

.

.Rn cn1 cn2 …... cnj …... cnn

unde cij- “costul” corespunzător repartizării Ri pe activităţile .Observaţie. Termenul de cost ataşat unei perechi (Ri, ) are un sens larg, de valoare ataşată acestei perechi şi poate avea diferite interpretări: consum de timp, cheltuială bănească, beneficiu unitar, procentaj de rebuturi, randament, etc.

Pentru scrierea modelului matematic al problemei fixăm n2 variabile (necunoscutele problemei) astfel:

Aj

Ri

A1 A2 . . . Aj … An

R1 x11 x12 ….. x1j ….. x1n

R2 x21 x22 ….. x2j ….. x2n

.

.

.

.

.

.Ri xi1 xi2 ….. xij …. xin

.

.

.

.

.

.Rn xn1 xn2 ….. xnj ….. xnn

Convenim ca variabilele fixate să poată lua valori egale cu 0 sau cu 1, astfel încât:

, dacă resursa Ri este repartizată activităţii ;

, dacă resursa Ri nu este repartizată activităţii .

Faptul că resursele R1,...,Rn sunt afectate unei singure activităţi, se pot scrie următoarele egalităţi:

Se observă că egalitatea nu poate avea loc decât dacă un termen este egal cu 1 iar toţi ceilalţi sunt egali cu zero.

Aceasta poate fi scrisă condensat astfel:

Restricţiile care impun ca fiecărei activităţi să-i fie repartizată o singură resursă sunt:

Condensat, aceste relaţii se scriu astfel:

Costul total se calculează cu formula:

Observaţie. Această sumă se reduce la suma acelor costuri care corespund la valori .Modelul matematic al problemei de afectare va fi:

În repartizarea sarcinilor pe executanţi se foloseşte algoritmul ungar al lui Egervahry-Kuhn, utilizat îndeosebi pentru determinarea unui cuplaj maxim într-un graf corespunzător unui cost total minim. Aplicat eficientizării repartizării sarcinilor pe muncitori, el foloseşte o matrice de bază, în care coloanele sunt lucrările atribuite iar liniile reprezintă lucrătorii, în ale cărei căsuţe se înscriu timpii necesari executării sarcinilor primite.

În continuare, prezentăm pe scurt noţiunile de bază necesare aplicării algoritmului ungar şi anume:

- cuplajul unui graf G, care reprezintă o mulţime de arce E, astfel încât două arce din E să nu fie adiacente (K);

- suportul matricei A, notat cu S(A), care reprezintă mulţimea de linii şi coloane a căror suprimare duce la dispariţia tuturor zerourilor matricei A. Evident că pentru o matrice dată poate exista o familie de suporturi : notăm mulţimea lor cu  .

Suportul care posedă numărul minim de linii şi coloane se numeşte suportul minimal al matricei A.

Notăm cu (A) numărul de elemente ale suportului minimal, adică (A) = min , S(A) .

Spre exemplu, pentru matricea A = | aij | de mai jos, unde i = 1, ..., 5 şi y = 1, ..., 7 se pot considera suporturile :

Y1 Y2 Y3 Y4 Y5 Y6 Y7

X1 0 0

X2 0

X3 0 0 0

X4

X5 0

Se observă că suportul minimal este S3(A) = şi că (A) = |S3(A)| = 3.Din punct de vedere economic, existenţa unor cheltuieli diferite pentru fiecare repartiţie impune ca odată cu determinarea cuplajului maxim să se obţină şi costul total minim legat

de repartizări.

Fie matricea A asociată unui graf, în care elementele aij, i = 1, ..., 5 şi j = 1, ..., 5, reprezintă costurile corespunzătoare repartiţiilor , adică:

Să considerăm două cuplaje maxime arbitrare, pe care le notăm cu şi :

Notăm cu şi costurile totale ale cuplajelor maxime de mai sus, determinate astfel:

= C14 + C22 + C31 + C43 + C55 = 6 + 3 + 7 + 3 + 9 = 28, = C11 + C25 + C34 + C42 + C53 = 2 + 5 + 3 + 5 + 5 = 20.

Diferenţa dintre cele două costuri este:

= 28 – 20 = 8.

Se demonstrează că diferenţa costurilor totale nu se schimbă dacă din fiecare element al unei linii din A scădem minorantul elementelor liniei respective şi apoi din matricea A1, astfel obţinută, scădem din elementele coloanelor un alt minorant .

Pe baza celor precizate, să urmărim în continuare etapele aplicării algoritmului ungar:Etapa 1: Se scade minorantul fiecărei linii din toate elementele liniei respective, obţinându-

se astfel câte un zero pe fiecare linie a matricei A. Dacă în urma acestei operaţii există coloane care nu conţin zerouri, se scade minorantul fiecărei coloane din toate elementele coloanei respective.

Etapa 2: Fie matricea obţinută în urma operaţiilor din etapa 1. Determinăm un cuplaj maxim în prin procedeul de încadrare şi tăiere a zerourilor. Dacă se obţine câte un zero încadrat pe fiecare linie şi pe fiecare coloană, atunci (A) este egal cu n, dimensiunea matricei A şi cuplajul este maxim, obţinându-se soluţia optimă. În caz contrar, se trece la etapa următoare.

Etapa 3: Căutăm suportul minim printr-un procedeu de marcare a liniilor şi coloanelor astfel :

- marcăm liniile care nu conţin zerouri încadrate şi coloanele care au zerouri tăiate pe liniile marcate;

- marcăm liniile cu zero încadrat pe coloanele marcate;Etapa 4: În matricea tăiem toate liniile nemarcate şi coloanele marcate. Minorantul

elementelor netăiate îl adunăm elementelor dublu tăiate, îl scădem din elementele netăiate, lăsând neschimbate elementele simplu tăiate, obţinând matricea .În matricea repetăm operaţia de

Y1 Y2 Y3 Y4 Y5

X1 2 3 1 6 4

X2 4 3 2 1 5

X3 7 1 1 3 2

X4 4 5 3 1 4

X5 3 4 5 7 9

încadrare şi tăiere a zerourilor. Dacă după această operaţie obţinem (A) = n, algoritmul ia sfârşit obţinându-se soluţia optimă. În caz contrar, se reiau operaţiile corespunzătoare etapelor 3 şi 4.Dacă există mai multe lucrări decât executanţi, trebuie precizat ce lucrare nu va fi îndeplinită sau

ce resurse suplimentare se achiziţionează.

Să considerăm următorul exemplu pentru a înţelege modul de aplicare al algoritmului ungar. Într-un sector dintr-o întreprindere de prelucrare a lemnului șase muncitori execută șase lucrări la diferite componente ale unei garnituri de mobilă. În matricea de mai jos se indică timpul în minute de executare a unei lucrări Li la muncitorul Mj:

Am indicat prin faptul că o anume lucrare nu se poate atribui unui muncitor.. În condiţiile în care timpii de lucru pe fiecare lucrare sunt indicaţi în matricea A de mai sus, se cere

să facă o repartizare a lucrărilor pe muncitori astfel ca suma timpilor cheltuiți pentru prelucrare să fie minimă.

Etapa 1: Scăzând din elementele fiecărei linii minorantul al liniei respective, obţinem matricea A1. Minoranţii sunt trecuţi în prelungirea matricei A.

Deoarece nu s-a obţinut câte un zero şi pe fiecare coloană, scădem din elementele fiecărei coloane a matricei A1 minoranţii şi obţinem matricea . Minoranţii sunt trecuţi în prelungirea matricei A1.

Y1 Y2 Y3 Y4 Y5 Y6 αi

A =

X1 2 3 1 2 4 1X2 1 2 1 3 1 1X3 3 4 2 1 1

X4 2 1 3 3 4 1X5 3 2 3 2 2X6 3 2 4 3 3 2 2

Y1 Y2 Y3 Y4 Y5 Y6

A =

X1 1 2 0 1 3X2 0 1 0 2 0X3 2 3 1 0X4 1 0 2 2 3X5 1 0 1 0X6 1 0 2 1 1 0βj 0 0 0 0 1 0

Etapa 2: Se încadrează un zero de pe o linie cu cele mai puţine zerouri, tăind celelalte zerouri de pe linia şi coloana zeroului încadrat. Pe liniile rămase repetăm operaţia pînă ce toate zerourile au fost sau încadrate sau tăiate.

Astfel procedând, în matricea se obţine:

Deoarece s-a obţinut suportul minim σ(A) = 6, algoritmul ia sfîrşit. Lui σ(A) astfel determinarea îi corespunde cuplajul maxim

şi suma minimă a timpilor de prelucrare va fi : 2+1+1+1+2+2 = 9 min

Întrucât la încadrarea zerourilor am avut posibilitatea alegerii, acest lucru ne arată că soluţia nu este unică, existând şi alte modalități cu suma minimă a timpilor de prelucrare tot cu valoarea 9, astfel:

Y1 Y2 Y3 Y4 Y5 Y6

X1 1 2 0 0 3

X2 0 1 0 1 0

X3 2 3 1 0

X4 1 0 2 1 3

X5 1 0 0 0

X6 1 0 2 1 0 0

Y1 Y2 Y3 Y4 Y5 Y6X1 1 2 0 3

X2 1 0 1 0

X3 2 3 1

X4 1 2 1 3

X5 1 0 0

X6 1 0 2 1 0

Y1 Y2 Y3 Y4 Y5 Y6

X1 1 2 ∞ 0 3

X2 ∞ 1 0 1 0

X3 2 3 1 ∞ ∞

X4 ∞ 1 2 1 3

X5 1 0 ∞ ∞ 0

X6 1 2 1 0 0

Se observă că încadrarea zerourilor de pe poziţiile este unică. În consecinţă, se poate încadra un zero de pe linia lui sau obţinând o altă variantă a suportului U(A) la care îi corespunde cuplajul maxim :

Suma minimă a timpilor de prelucrare va fi tot 2 + 1 + 1 + 1 + 2 + 2 = 9

Să supunem atenţiei, în continuare, un alt exemplu referitor la executarea a cinci lucrări de către cinci executanți, de această dată cu parcurgerea integrală a algoritmului ungar. În condiţiile în care timpii de lucru pe fiecare lucrare sunt indicaţi în matricea A de mai jos, se cere să facă o repartizare a lucrărilor pe muncitori astfel ca suma timpilor cheltuiți pentru prelucrare să fie minimă.

Etapa 1. Dacă scădem din elementele fiecărei linii minorantul αi al liniei respective, obţinem matricea A1.

Minoranţii αi sunt trecuţi în prelungirea matricei A.

Se observă că s-a obţinut câte un zero pe fiecare

linie a matricei, însă coloana a doua nu conţine zero. Scădem minorantul al fiecărei coloane din toate elementele respective, obţinându-se matricea .

Y1 Y2 Y3 Y4 Y5 αi

A=

X1 20 10 25 5 5

X2 10 15 0 0

X3 6 10 15 6

X4 20 5 5 5

X5 25 20 0 0

Y1 Y2 Y3 Y4 Y5

A1=

X1 15 5 20 0

X2 10 15 0

X3 0 4 9

X4 15 0 0

X5 25 20 0

βj 0 4 0 0 0

Etapa 2. Determinăm un cuplaj maxim în prin procedeul de încadrare şi tăiere a zerourilor.

Deoarece (A) = 4 ≠ n = 5, se trece la etapa următoare.Etapa 3. Se caută suportul minim prin procedeul de marcare a liniilor şi coloanelor.

Am marcat linia care nu conţine zerouri încadrate şi coloana care are zerouri tăiate pe linia

marcată . Totodată, marcăm şi linia care conţine zero încadrat pe coloana marcată .Etapa 4. În matricea tăiem toate liniile nemarcate şi coloanele marcate, adică linile şi

coloana .

Y1 Y2 Y3 Y4 Y5

X1 15 1 20 0

X2 10 15 0

X3 0 0 9

X4 15 0 0

X5 21 20 0

Y1 Y2 Y3 Y4 Y5

X1 15 1 20

X2 10 15

X3 0 9

X4 15 0

X5 21 20 0

Y1 Y2 Y3 Y4 Y5

X1 15 1 20

X2 10 15 *

X3 0 9

X4 15 0

X5 21 20 0 *

*

Y1 Y2 Y3 Y4 Y5

X1 15 1 20

X2 10 15 *

X3 0 9

X4 15 0

X5 21 20 0 *

*

În matricea minorantul elementelor netăiate (este 10) îl adunăm elementelor dublu-tăiate (prin tăiere de linii şi coloane) şi îl scădem din elementele netăiate, iar elementele simplu tăiate rămân neschimbate. Obţinem astfel matricea :

În matricea repetăm operaţia de încadrare şi tăiere a zerourilor.

Suportul minim σ(A) fiind egal cu 5, îi corespunde cupajul maxim:K(A) =

Valoarea minimă a timpilor de prelucrare va fi : 5 + 10 + 10 + 5 + 0 = 30

Cuplajul maxim, corespunzător suportului minim, respectiv valorii minime a timpilor de prelucrare, este redat de graful din fig. 3.2.

X1 Y1X2 Y2X3 Y3X4 Y4X5 Y5

Y1 Y2 Y3 Y4 Y5

=

X1 15 1 30 0

X2 0 5 0

X3 0 0 9

X4 15 0 0

X5 11 10 0

Y1 Y2 Y3 Y4 Y5

=

X1 15 1 30

X2 5 0

X3 0 9

X4 15 0

X5 11 10

Fig. 3.2. Graful corespunzător suportului minim (A) = 5