Master Comunicare managerial i resurse umaneLecia 7

Problema de transport (Transportation problem) Din aceast categorie fac parte: problemele de alocare;problemele de transport;probleme de stabilire a unui traseu optim (problema comisului voiajor). Modelul de transport este aplicat n general acelor cazuri n care se pune problema distribuirii unor obiecte de la deintori la solicitani , fiecare dintre acetia (distribuitori i solicitani) fiind situai n amplasamente diferite.

Problema de alocare (Assignment Problem)Problema alocrii este considerat ca un tip special de problem de transport.

n general este vorba despre un numr de angajai care pot ndeplini n sarcini i un cost nenegativ Cij implicat de atribuirea ctre angajatul i a sarcinii j, cost care se consider cunoscut.

Obiectivul problemei este acela de a asigura fiecrui angajat cte o sarcin, astfel nct s se minimizeze costul total.

Problema de alocare (Assignment Problem)Problemele de alocare se caracterizeaz prin cerina de a mperechea elemente dintr-un grup cu elemente din alt grup (unu la unu).

Se definesc variabilele binare Xij care pot lua valorile 0 sau 1.

Xij = 1, arat c se atribuie sarcina j candidatului i.

Xij = 0 arat c nu se atribuie sarcina j candidatului i.

Problema de alocare (Assignment Problem)Exemplul 1n tabelul urmtor sunt prezentai timpii necesari fiecruia din 3 muncitori pentru executarea fiecreia din 3 operaii. S se minimizeze timpul total de executare a celor trei operaii. Fiecare muncitor execut o singur operaie. Ce operaie va executa fiecare muncitor? S se formuleze modelul de programare liniar al acestei probleme.

Problema de alocare (Assignment Problem)Exemplul 1Xij=1 dac muncitorul i va executa operaia j

Xij=0 dac muncitorul i nu va executa operaia j

Op. 1

Op. 2

Op. 3

Muncitor 1

3

5

6

Muncitor 2

8

9

7

Muncitor 3

9

2

4

Problema de alocare (Assignment Problem)Exemplul 1Tabelul cu variabilele de decizieRezolvare cu NET.EXE, componenta Assignment Problem

Op. 1

Op. 2

Op. 3

Muncitor 1

X11

X12

X13

Muncitor 2

X21

X22

X23

Muncitor 3

X31

X32

X33

Problema de alocare (Assignment Problem)Exemplul 1Funcia obiectivS se minimizeze timpul total de executare a celor trei operaii.Min (3X11 + 5X12 + 6X13 + 8X21 + 9X22 + 7X23 + 9X31 + 2X32 + 4X33)Restriciile sunt:X11+X12+X13=1X21+X22+X23=1 Pe liniiX31+X32+X33=1

X11+X21+X31=1X12+X22+X32=1 Pe coloaneX13+X23+X33=1

Xij=0 sau Xij=1 pentru i,j=1,2,3

Problema de alocare (Assignment Problem)Exemplul 1Muncitorul 1 va executa operaia 1, muncitorul 2 operaia 3 i muncitorul 3 operaia 2.

Dac exist 4 muncitori care pot executa fiecare oricare din cele 3 operaii, s repartizeze optim cei 3 muncitori pe cele 3 operaii i s identifice muncitorul care va fi exclus. n tabelul urmtor sunt prezentai timpii necesari fiecruia din cei 4 muncitori pentru executarea fiecreia din cele 3 operaii.Problema de alocare (Assignment Problem)Exemplul 2 (extensie a problemei precedente)

Operaie 1Operaie 2Operaie 3Muncitor 1356Muncitor 2897Muncitor 3924Muncitor 4324

Problema de alocare (Assignment Problem)Rezolvare

Problema de alocare (Assignment Problem)RezolvareMuncitorul 1 va executa operaia 1, muncitorul 3 operaia 3 i muncitorul 4 operaia 3. Muncitorul 2 va fi exclus.

O companie care asigur service pentru calculatoare are 4 clieni notai C1, C2, C3 i C4. Aceast companie are 4 tehnicieni (T1,T2,T3,T4) pentru a asigura service-ul. Datorit specializrii diferite a acestora, timpul necesar pentru nlturarea defectelor reclamate de fiecare dintre clieni este prezentat n urmtorul tabel.

Managerul acestei companii dorete s afle ce tehnician s repartizeze pentru fiecare client, astfel nct s minimizeze timpul total de remediere a defeciunilor pentru cei 4 clieni.Problema de alocare (Assignment Problem) Exemplul 3

Clieni

Tehnicieni

C1

C2

C3

C4

T1

3

6

7

10

T2

5

6

3

8

T3

2

8

4

16

T4

8

6

5

9

Probleme de stabilire a unui traseu optim Problema comisului voiajorProblema comis-voiajor-ului presupune existena unui numr de noduri (locaii) i arcuri care leag toate nodurile.

Obiectivul este acela de a parcurge toate nodurile (a vizita toate locaiile) o singur dat, minimiznd distana parcurs.

Pentru rezolvarea acestui tip de probleme exist algoritmi implementai n diferite pachete de programe printre care se numr i QSB i care ofer un suport software eficient pentru rezolvarea rapid a acestor probleme. Rezolvare cu NET.EXE, componenta Traveling Salesman Problem

Probleme de stabilire a unui traseu optim Problema comisului voiajor

Problema comisului voiajorExemplul 4Cunoscndu-se distanele n km. dintre 8 orae prezentate n tabelul de mai jos, se cere s se determine traseul optim care s treac o singur dat prin fiecare ora astfel nct distana parcurs s fie minim.

De la

oraul

La oraul

1

2

3

4

5

6

7

8

1

-

150

180

300

200

50

290

350

2

150

-

120

180

250

200

150

250

3

180

120

-

150

150

120

150

200

4

300

180

150

-

300

320

25

60

5

200

250

150

300

-

100

300

350

6

50

200

120

320

100

-

300

350

7

290

150

150

25

300

300

-

90

8

350

250

200

60

350

350

90

-

Problema comisului voiajorExemplu