Post on 12-Dec-2021
transcript
87
5
Problema de transport
5.1. Noţiuni teoretice
Fiind date m centre de aprovizionare cu bunuri, notate Di, (i=1,m), şi n centre
de desfacere, notate Cj, (j=1,n), problema de transport este problema care
caută să minimizeze costul total al transportului bunurilor de la centrele de
aprovizionare Di la centrele de desfacere Cj. Transportul se poate efectua de la
oricare centru Di către oricare centru Cj, existând un cost unitar cij, al
transportului unui bun de la centrul Di către centrul Cj. Astfel, costul total al
transportului este proporţional cu cantitatea de bunuri transportate între sursă
şi destinaţie. Acest model este însă inadecvat dacă dorim să transportăm de
exemplu două pachete cu biscuiţi de la Sibiu la Braşov, deoarece costul
transportului celor două pachete cu camionul nu este în mod sigur dublul
costului transportului unui singur pachet. Dar dacă discutăm de unul sau două
camioane pline cu biscuiţi, situaţia este cu totul alta.
Ĩntr-o problemă de transport, datele problemei sunt furnizate de obicei sub
forma tabelului de mai jos:
Tabelul 5.1
Di \ Cj C1 C2 … Cn Disponibil
D1 c11 c12 … c1n a1
D2 c21 c22 … c2n a2
.
.
.
.
.
.
.
.
.
Dm Cm1 cm2 … cmn am
Necesar b1 b2 … bn
88 Cercetări operaţionale
Modelul matematic al problemei de transport se poate scrie:
x11+x12+…+x1n=a1
… ai0, i=1,m
xm1+xm2+…+xmn=am
şi
x11+x21+…xm1=b1
… bi0, i=1,n (5.1)
x1n+x2n+…+xmn=bn
xij0 (i=1,m; j=1,n)
f x c x MINij ijj
n
i
m
( ) = ===
11
Pentru a rezolva problema de transport, cantitatea de bunuri de bunuri
disponibile trebuie să fie egală cu cantitatea de bunuri necesare, altfel spus
problema de transport trebuie să fie echilibrată. Acest lucru se exprimă
matematic prin relaţia:
a bii
m
ij
n
= =
=1 1
(5.2)
Dacă problema nu este echilibrată, aceasta se poate echilibra prin introducerea
unor centre fictive care să conducă la realizarea relaţiei (5.2), prin adăugarea
unor depozite sau centre fictive şi considerarea costurilor unitare de transport
de la sau către acestea ca fiind nule. De exemplu, dacă:
a bii
m
ij
n
= =
1 1
atunci se adaugă un depozit fictiv, Dm+1 care are un disponibil
astfel încât:
a a bii
m
m ij
n
=+
=
+ =1
11
(5.3)
iar costurile de transport de la Dm+1 la Cj sunt nule:
cm+1,j = 0 (j=1,n)
Problema de transport fiind o problemă de programare liniară se poate rezolva
cu ajutorul algoritmului Simplex. Dar datorită structurii ei speciale, o astfel de
problemă se poate rezolva mai rapid şi mai simplu prin algoritmi specifici.
Algoritmul de determinare a soluţiei optime presupune parcurgerea a două
etape:
1. determinarea unei soluţii admisibile de pornire, folosind una din
metodele:
5. Probleme de transport 89
a. metoda colţului de Nord-Vest;
b. metoda costului minim din tabel;
c. metoda costului minim pe linie
d. metoda costului minim pe coloană.
2. determinarea soluţiei optime pornind de la soluţia admisibilă găsită
anterior folosind:
a. metoda simplex primară (Stepping stone)
b. metoda distribuţiei modificate (MODI).
Metoda colţului de nord-vest presupune parcurgerea următoarelor etape:
1. Se porneşte din colţul cel mai de nord-vest, respectiv din celula [(i,j) i=1
şi j=1].
2. Se atribuie acestei celule valoarea cea mai mică între disponibilul şi
necesarul corespunzătoare centrelor Di şi Cj, respectiv valoarea xij =
min(ai,bj).
3. Se reduce disponibilul (oferta) şi necesarul (cererea) de pe această linie
şi coloană cu valoarea alocată celulei (i,j). Dacă xij = ai atunci se suprimă
linia i. Dacă xij=bj, se suprimă coloana j. Va rezulta un tabel cu o linie
sau o coloană mai puţin. Se alege în continuare următoarea celulă aflată
în colţul cel mai de nord-vest, şi se repetă procedeul de la pasul 2, până
când au fost satisfăcute toate cerinţele (restricţiile).
Algoritmul simplex primar presupune parcurgerea următoarelor etape:
1. Pentru fiecare celulă neocupată cu valori se formează un ciclu închis
pornind de la această celulă şi celulele deja ocupate, prin trasarea unor
linii de conectare. Aceste linii pot fi numai linii orizontale şi verticale şi
pot traversa celule care să aibă deja valori. Tabelul 5.2 exemplifică un
astfel de ciclu pentru celula (1,3), al cărei ciclu este:
1,3: (1,3) → (1,1) → (2,1) → (2,2) → (3,2) → (3,3) → (1,3)
Tabelul 5.2
C1 C2 C3 Disponibil
D1 5 - 4 3 +
100 100
D2 8 + 4 - 3
200 100 300
D3 9 7 + 5 -
100 200 300
Cerere 300 200 200
90 Cercetări operaţionale
2. Începând de la celula neocupată, se calculează costul redus al celulei i,j,
adăugând şi extrăgând valorile aflate la colţurile ciclului, fără a lua în
calcul celulele care sunt pur şi simplu doar traversate. Pentru exemplul
de mai sus, costul redus este:
1,3=(1,3) - (1,1) + (2,1) - (2,2) + (3,2) - (3,3) = 3 – 5 + 8 – 4 + 7 – 5 = 4
5.2. Problemă rezolvată
Fie problema de transport având datele prezentate în tabelul 5.2 , unde sunt
indicate costurile transportului unei unităţi de produs. Să se determine
cantităţile xij care trebuie transportate de la depozitul Di la centrul de desfacere
Cj astfel încât costul total al transportului să fie minim.
Tabelul 5.2
C1 C2 C3 Disponibil
D1 20 30 10 100
D2 30 40 25 300
D3 35 15 20 100
Cerere 150 125 225
Se observă că problema este echilibrată: cantitatea cerută totală
(150+125+225=500) este egală cu cantitatea disponibilă totală
(100+300+100=500).
Din modelul matematic general, m=3 şi n=3, deci soluţia admisibilă de bază va
avea cel mult m+n-1=3+3-1=5 componente nenegative sau celule utilizate.
M
5.2.1. Rezolvarea manuală
5.2.1.1. Determinarea soluţiei admisibile
Se introduc variabilele xij în tabel, rezultând tabelul 5.3.
5. Probleme de transport 91
Tabelul 5.3
C1 C2 C3 Disponibil
D1 20 30 10
x11 x12 x13 100
D2 30 40 25
x21 x22 x23 300
D3 35 15 20
x31 x32 x33 100
Cerere 150 125 225
x11 = min(a1, b1) = min(100, 150) = 100 = a1
Se înlocuieşte a1 = 100 cu 100 - 100 = 0 şi b1 = 150 cu 150 - 100 = 50. Deoarece
x11 = a1, se suprimă linia 1 (această linie nu se va mai lua în considerare în
calculele următoare).
Astfel, vor rezulta datele din tabelul 5.4.
Tabelul 5.4
C1 C2 C3 Disponibil
D1 20 30 10
100 100 0
D2 30 40 25
300 300
D3 35 15 20
100 100
Cerere 150 125 225
50 125 225
Se continuă cu elementul din nord-vest al tabelului din linia a doua:
x21 = min(a2, b1) = min(300, 50) = 50 = b1
Se înlocuieşte a2 = 300 cu 300 - 50 = 250 şi b1 = 50 cu 50 - 50 = 0. Deoarece
x12 = b1, se suprimă prima coloană a tabelului rămas (prima coloană a tabelului
iniţial). Va rezulta tabelul 5.5. Tabelul 5.5
C1 C2 C3 Disponibil
D1 20 30 10
100 100 0 0
D2 30 40 25
50 300 300 250
D3 35 15 20
100 100 100
Cerere 150 125 225
50 125 225
0 125 225
92 Cercetări operaţionale
Elementul din colţul de nord-vest al tabelului rămas este:
x22 = min(a2, b2) = min(250, 125) = 125 = b2
şi se înlocuieşte a2 = 250 cu 250 - 125 = 125 şi b2 = 125 cu 125 - 125 = 0.
Deoarece x22 = b2, se suprimă prima coloană a tabelului rămas (a doua coloană
a tabelului iniţial). Va rezulta tabelul 5.6.
Tabelul 5.6
C1 C2 C3 Disponibil
D1 20 30 10
100 100 0 0 0
D2 30 40 25
50 125 300 300 250 125
D3 35 15 20
100 100 100 100
Cerere 150 125 225
50 125 225
0 125 225
0 0 225
Tabelul rămas va fi format din celulele variabilelor x23 şi x33.
x23 = min(a2, b3) = min(125, 225) = 125 = a2
Se înlocuieşte a2 = 125 cu 125 - 125 = 0 şi b3 = 225 cu 225 - 125 = 100.
Deoarece x23 = a2, se suprimă prima linie a tabelului rămas (a doua linie a
tabelului iniţial).
Va rămâne doar o singură celulă în tabel:
x33 = min(a3, b3) = min(100, 100) = 100 = a3 = b3
şi se înlocuieşte a3 = 100 cu 100 - 100 = 0 şi b3 = 100 cu 100 - 100 = 0. S-a
completat astfel tabelul, rezultând datele din tabelul 5.7. Tabelul 5.7
C1 C2 C3 Disponibil
D1 20 30 10
100 100 0 0 0 0
D2 30 40 25
50 125 125 300 300 250 125 0
D3 35 15 20
100 100 100 100 100 0
Cerere 150 125 225
50 125 225
0 125 225
0 0 225
0 0 0
5. Probleme de transport 93
5.2.1.2. Determinarea soluţiei optime
Soluţia de pornire determinată cu metoda colţului de nord-vest este:
X = (100 0 0; 50 125 125; 0 0 100)T
Ciclul celulei (1,2) şi al celulei (1,3) sunt respectiv:
(1,1) --------
-
(1,2) (1,1) ---------
-
(1,3)
|
|
|
|
|
|
|
|
(2,1) --------
-
(2,2) (2,1) ---------
-
(2,3)
Calculăm i,j :
1,2 = 30 – 40 + 30 – 20 = 0 3,1 = 35 – 30 + 25 –20 = 10
1,3 = 10 – 25 + 30 – 20 = -5 3,2 = 15 – 40 + 25 –20 = -20
Soluţia X nu este optimă deoarece dacă repartizăm o unitate de produs în celula
(1,3) costul transportului scade cu 5 unităţi, în timp ce dacă repartizăm o unitate
de produs în celula (3,2), costul transportului scade cu 20 de unităţi. Calculăm
min (0, 10, -5, -20) = -20 ce corespunde celulei (3,2), căreia îi atribuim valoarea
= min (100, 125) =100.
(2,2)
125-
--------
-
(2,3)
125+
|
|
|
|
(3,2)
--------
-
(3,3)
100-
Noua soluţie se obţine modificând numai valorile variabilelor din ciclu, tabelul
5.8. Noua soluţie a problemei va fi:
X* = (100 0 0; 50 25 225; 0 100 0)T
94 Cercetări operaţionale
Tabelul 5.8
C1 C2 C3
D1 20 30 10
100 . .
D2 30 40 25
50 25 225
D3 35 15 20
. 100 .
Verificăm dacă X* este soluţia optimă:
1,2 = 30 – 40 + 30 – 20 = 0 3,1 = 35 – 30 + 40 –15 = 30
1,3 = 10 –25 + 30 –20 = -5 3,3 = 20 – 25 + 40 – 15 = 20
Soluţia X* nu este optimă, deoarece 1,3 < 0.
= min(100,225) =100
Formăm ciclul celulei (1,3) căreia îi atribuim valoarea . Rezultă tabelul 5.9.
Tabelul 5.9
C1 C2 C3
D1 20 30 10
. . 100
D2 30 40 25
150 25 125
D3 35 15 20
. 100 .
1,1 = 20 – 10 + 25 – 30 = 5 3,1 = 35 – 30 + 40 –15 = 30
1,2 = 30 – 10 + 25 – 40 = 5 3,3 = 20 – 15 + 40 – 25 = 20
Noul X* devine: X* = (0 0 100; 150 25 125; 0 100 0)T care este soluţia
optimă, deoarece orice altă repartiţie s-ar face ar conduce la creşterea costului
transportului şi nu la scăderea acestuia.
Astfel costul minim este:
CT = 30 150 + 40 25 + 25 125 + 15 100 = 11.125 unităţi monetare.
5. Probleme de transport 95
X
5.2.2. Rezolvarea cu Microsoft Excel
Foaia de calcul folosită pentru rezolvarea problemei de transport cu Microsoft
Excel, este prezentată în figura 5.1.
Fig. 5.1. Foaia de calcul ataşată problemei de transport
Datele problemei sunt introduse în domeniul A6:E10. Costurile de transport
sunt introduse de la tastatură în domeniul B7:D9, cantităţile de produse
disponibile in fiecare depozit (oferta) sunt introduse în celulele E7:E9, iar
cererea din centrele de desfacere în celulele B10:D10.
Elementele cheie care trebuie introduse in Excel sunt variabilele de decizie,
funcţia obiectiv, partea stângă şi partea dreaptă a restricţiilor.
Variabilele de decizie, (celulele cu valori schimbabile) sunt celulele B17:D19.
Iniţial, toate variabilele de decizie au valoarea 0. Pentru a calcula costul total
96 Cercetări operaţionale
(funcţia obiectiv), în celula C13 a fost introdusă formula
=SUMPRODUCT(B7:D9,B17:D19).
Celulele E17:E19 conţin formulele pentru partea stângă a restricţiilor asociate
depozitelor (D1, D2, D3), iar celulele B20:D20 conţin formulele pentru partea
stângă a restricţiilor asociate cererii din centrele de desfacere. Formulele
utilizate sunt:
Celula E17: =SUM(B17:D17). Se copiază E17 în E18:E19.
Celula B20: =SUM(B17:B19). Se copiază B20 în C20:D20.
Celulele G17:G19 conţin partea dreaptă a restricţiilor asociate depozitelor, iar
celulele B22:D22 conţin partea dreaptă a restricţiilor asociate cererii din
centrele de desfacere. Aceste valori sunt introduse de la tastatură, fiind datele
iniţiale ale problemei.Se vor utiliza formulele:
Celula G17: =E7. Se copiază G17 în G18:G19.
Celula B22: =B10. Se copiază B22 în C22:D22.
Se rezolvă problema utilizând Solver-ul. Caseta de dialog Solver Parameters
se completează ca în figura 5.2. Opţiunea selectată pentru Select a Solving
Method este Simplex LP pentru. (Fig. 5.3)
5. Probleme de transport 97
Fig. 5.2. Caseta de dialog Solver Parameters
98 Cercetări operaţionale
Fig. 5.3. Opţiunile selectate pentru rularea Solver-ului
Soluţia optimă arată costul minim de transport ca fiind egal cu 11.125 u.m., iar
în domeniul B17:D19 sunt afişate cantităţile care trebuie transportate pe fiecare
rută. Valoarea 0 indică faptul că pe ruta respectivă nu se transportă nimic (Fig.
5.4).
5. Probleme de transport 99
Fig. 5.4 Soluţia optimă
Q
5.2.3. Rezolvarea cu WinQSB
Pentru rezolvarea problemelor de transport, se alege modulul Network
Modeling (Fig. 5.5).
100 Cercetări operaţionale
Fig. 5.5 Alegerea modulului Network Modeling
Din meniul File, se selectează New Problem. Pe ecran va apărea căsuţa de
dialog din figura 5.6, în care se completează datele generale ale problemei. Se
bifează tipul problemei de transport – Transportation Problem – obiectivul
problemei (de minimizare), modul de introducere a datelor (forma matriceală),
titlul problemei, precum şi numărul de surse şi destinaţii (în cazul de faţă: 3
depozite şi 3 centre de desfacere).
Fig. 5.6 Datele generale ale problemei
5. Probleme de transport 101
După ce datele problemei au fost introduse, ca in figura 5.7, din meniul Solve
and Analyze, se selectează opţiunea Solve the Problem.
Fig. 5.7. Datele detaliate ale problemei
Soluţia problemei va fi afişată ca în figura 5.8. Se observă că modul de
prezentare este diferit de Excel. În prima coloană (From) sunt trecute
depozitele, iar în coloana To, sunt trecute destinaţiile sau centrele de desfacere.
Coloana a treia, (Shipment) conţine cantitatea transportată pe ruta respectivă,
iar coloana a patra (Unit Cost) arată costul unitar de transport pe ruta respectivă.
Costul total de transport este afişat la baza coloanei a cincea – Total Cost. Din
meniul Results, se poate selecta afişarea grafică a soluţiei problemei (Fig. 5.9).
Fig. 5.8. Soluţia optimă
Fig. 5.9. Prezentarea soluţiei sub forma grafică
102 Cercetări operaţionale
S
5.2.4. Rezolvarea cu QM for Windows
Din arborele modulelor (sau din meniul MODULE) se alege opţiunea
Transportation, (Fig. 5.10), care va deschide automat fereastra – Create data
set for Transportation (Fig. 5.11).
Fig. 5.10. Selectarea modulului pentru probleme de transport
În pasul următor se introduc date generale despre problemă: titlul, numărul de
centre de desfacere (Number of Sources), numărul de depozite (Number of
Destinations), tipul problemei – de minimizare. De asemenea, programul ne
permite să rebotezăm liniile şi coloanele sau să ne informăm la modul general
asupra modulului (Overview). Introducem în această fereastră datele generale
ale problemei (Fig.5.11).
În următorul pas se introduc datele detaliate ale problemei (Fig.5.12). Totodată
se poate alege metoda de start a algoritmului, putând astfel alege între Metoda
colţului de Nord-Vest, metoda costului minim sau metoda aproximării Vogel.
Noi vom selecta metoda colţului de Nord-Vest (Northwest Corner Method).
5. Probleme de transport 103
Fig. 5.11. Crearea unei probleme noi cu datele generale
Fig. 5.12 Introducerea datelor de detaliu
După ce datele au fost introduse, se dă clic pe SOLVE, iar programul ne va
afişa soluţia problemei (Fig. 5.13).
Fig. 5.13. Rezolvarea problemei
104 Cercetări operaţionale
Utilizând meniul SOLUTIONS (Fig.5.14) putem afişa şi alte informaţii
interesante despre problemă, cum este, de exemplu fereastra Marginal Costs
care ne oferă costurile reduse. Costul redus reprezintă valoarea cu care creşte
costul dacă o unitate de produs este transportată pe această cale, bineînţeles prin
aplicarea modificărilor de compensare necesare.
Fig. 5.14 Meniul SOLUTIONS
Se poate observa că au fost găsite aceleaşi rezultate ca şi prin celelalte metode
de rezolvare. Costul total al transportului este de 11.125 um. (Fig 5.13).
5.3 Aplicaţii
1. Compania CCC are trei fabrici de asamblare a microprocesoarelor. Cea din
San Francisco are o producţie lunară de 1700 de unităţi. Fabrica din Los
Angeles produce 2000 unităţi pe lună, iar cea din Phoenix 1700 unităţi.
Microprocesoarele sunt vândute în patru magazine. Magazinul din San
Diego a emis o comandă de 1700 de unităţi pentru luna următoare, cel din
Barstow are o cerere de 1000 unităţi, cel din Tucson 1500 de unităţi, iar
pentru magazinul din Dallas cererea este de 1200 unităţi. Costul de transport
al unui microprocesor de la fiecare fabrică până la fiecare magazin este
prezentat în tabelul următor:
Fabrici
Magazine
San Diego Barstow Tucson Dallas
San Francisco 5 3 2 6
Los Angeles 4 7 8 10
Phoenix 6 5 3 8
5. Probleme de transport 105
În calitate de manager de distribuţie, formulaţi un model matematic pentru
a găsi cel mai ieftin mod de distribuţie.
2. În fiecare lună sunt tipărite câte 5000 de exemplare din revista AutoMagazin
la 2 tipografii: una la Bucureşti şi una la Cluj-Napoca. De aici revistele sunt
transportate la centrele regionale de distribuţie. Luna aceasta centrul din
Braşov a comandat 4000 de exemplare, centrul de la Piteşti a cerut 2000 de
reviste, iar centrul de distribuţie de la Timişoara a cerut 2500 de copii.
Costurile de transport de la fiecare tipografie la centrele de distribuţie sunt
date în tabelul de mai jos:
Tipografii
Centre regionale de distribuţie
Braşov Piteşti Timişoara
Bucureşti 0,07 0,05 0,10
Cluj-Napoca 0,03 0,11 0,04
În calitate de manager de distribuţie, formulaţi un model matematic pentru
a găsi cel mai ieftin mod de distribuţie.
3. O companie petrolieră are rafinării de benzină în New Orleans, cu o
capacitate de producţie de 300.000 de barili săptămânal şi în Newark, cu
capacitate de 500.000 de barili pe săptămână. Benzina din aceste rafinării
este transportată în patru centre regionale de depozitare. Centrul din
Washington D.C. are nevoie de 200.000 barili pentru săptămâna următoare,
cel din Tampa 100.000 barili, cel din Atlanta 400.000 barili, iar cel din
Cincinnati 300.000 barili. Costul de transport pentru fiecare baril de la
fiecare rafinărie la centrele de depozitare sunt date în tabelul de mai jos:
Rafinării
Centre regionale de depozitare
Washington D.C. Tampa Atlanta Cincinnati
New Orleans 0,10 0,05 0,07 0,09
Newark 0,05 0,11 0,08 0,07
În calitate de manager de distribuţie determinaţi planul de distribuţie cel
mai ieftin.
4. Compania „American Motors” poate trimite un total de 200 automobile cu
camionul şi 600 cu trenul de la fabirca din Detroit la dealerii săi din Chicago,
Cleveland, Washington D.C. şi Philadelphia. Costul (în dolari) pentru
trimiterea unei masini la fiecare dintre dealeri cu camionul sau cu trenul,
precum si cererea dealerilor sunt date in tabelul următor:
106 Cercetări operaţionale
Mijloc de
transport
Costul de transport ($/maşină)
Chicago Cleveland Washington D.C. Philadelphia
Camion 30 20 50 60
Tren 45 30 75 90
Cererea 300 100 250 150
În calitate de manager de al departamentului logistic, formulaţi un model
matematic pentru determinarea modului în care vor fi trimise maşinile la
dealeri, pentru a minimiza costurile de transport
5. Un reprezentant al Ministerului de Interne este responsabil cu distribuţia
ofiţerilor proaspăt absolvenţi la unităţi militare. Sarcina sa curentă este
distribuirea a 120 de noi ofiţeri care au absolvit trei academii militare:
Şcoala Număr de
absolvenţi
Bucureşti 30
Sibiu 75
Craiova 15
Aceşti ofiţeri vor fi distribuiţi în unul din următoarele centre militare, a
căror nevoi de personal calificat sunt prezentate în tabelul de mai jos:
Centrul Posturi
disponibile
Cluj-Napoca 22
Arad 31
Constanţa 37
Feteşti 30
În prima fază reprezentantul ministerului doreşte să determine o distribuţie
iniţială care să minimizeze costurile de transport ale militarilor şi ale
familiilor lor. Această distribuire va fi ulterior modificată în funcţie de
preferinţele ofiţerilor. Costurile medii de transfer (în sute de u.m.) sunt
prezentate in tabelul de mai jos:
Cluj-Napoca Arad Constanţa Feteşti
Bucureşti 15 22 38 40
Sibiu 29 27 33 35
Craiova 39 41 16 19
Găsiţi distribuţia iniţială folosind metoda colţului de nord-vest.
5. Probleme de transport 107
6. Să se rezolve următoarea problemă de transport:
M1 M2 M3 M4 Disponibil
S1 11,0 12,9 13,1 14,1 200
S2 11,8 13,4 12,1 13,6 240
S3 14,7 12,6 14,2 12,2 160
Necesar 150 140 60 250 600
7. O companie deţine 4 termocentrale şi produce energie pentru o mare parte
din sudul României. Compania deţine şi 3 mine de cărbune, necesar pentru
funcţionarea termocentralelor, precum şi reţeaua de distribuţie necesară
transportării cărbunelui de la mine la termocentrale. Costurile de transport
sunt date în tabelul de mai jos:
Mine
Termocentrale
1 2 3 4
A 4 7 9 8
B 5 4 6 7
C 10 3 6 8
Capacitatea zilnică a minelor, şi cererea de cărbune a fiecărei termocentrale,
în mii de tone pe zi au fost estimate la:
Mina Capacitatea Termocentrala Cererea de cărbune
A 40 1 30
B 30 2 25
C 50 3 35
4 40
Găsiţi cel mai ieftin algoritm de transport al cărbunilor de la mine la
termocentrale
8. O companie care produce îngrăşăminte chimice doreşte să aloce producţia
de la 3 fabrici în 3 depozite regionale. Capacitatea de producţie, cererea şi
costurile de transport sunt date în tabelul de mai jos. Găsiţi modul optim de
alocare a îngrăşămintelor de la fabrici la depozitele regionale.
Fabrici
Depozite regionale Capacitatea de
producţie (tone) Brăila Timişoara Craiova
Iaşi 7 5 10 12
Rm. Vâlcea 8 6 10 18
Câmpina 6 8 5 15
Cerea (tone) 15 20 10
108 Cercetări operaţionale
9. O companie are două fabrici A şi B şi trei depozite R, S şi T în care
transportă marfa fabricată. Costurile de transport pentru o tonă, cantitatea
disponibilă şi capacitatea depozitelor este dată în tabelul de mai jos. Să se
organizeze transportul astfel încât costul total să fie minim.
R S T Disponibil
A 3 1 5 100
B 2 4 6 200
Capacitate 70 60 50
10. O companie petrolieră are comenzi de 80 de unităţi/zi dintr-un anumit tip de
benzină de la trei terminale care fiecare necesită 25, 45 şi 10 unităţi/zi.
Compania are două rafinării, fiecare cu o capacitate de 50 de unităţi/zi. Cum
ar trebui făcut transportul petrolului astfel încât să fie cât mai economicos,
ştiind costurile ca fiind cele din tabelul de mai jos? Numerele de mai jos
reprezintă unităţi valorice.
Terminal
1 2 3 Oferta
Rafinăria 1 2,0 2,8 3,8 50
Rafinăria 2 3,0 4,0 4,2 50
Cererea 25 45 10
11. Rezolvaţi problema de transport dată mai jos:
Destinaţia Oferta
1 2 3 4 5
Sursa
10 15 17 14 26 31
30 32 41 39 50 31
52 56 49 48 61 37
Cererea 18 12 9 30 30 99
12. Firma METROS deţine trei depozite în localităţile Braşov (1), Timişoara (2)
şi Iaşi (3) de la care face aprovizionarea cu produse clienţilor din patru
localităţi (Sibiu (1), Oradea (2), Râmnicu-Vâlcea (3), Piatra-Neamţ (4)) în
care această firmă are filiale. Cele trei depozite au o capacitate de 500, 400
şi respectiv 325 de unităţi. Cererea în cele patru localităti este de 300, 115,
275 şi respectiv 190 de unităţi. Costul de transport de la depozite în cele
patru localităţi este dat în tabelul de mai jos:
5. Probleme de transport 109
Localitatea Oferta
1 2 3 4
Depozit
1 1.20 0.65 0.25 0.60 500
2 1.10 0.90 1.05 0.75 400
3 0.80 0.75 0.87 0.65 325
Cererea 300 115 275 190
13. Rezolvaţi următoarea problemă de transport:
Localitatea Oferta
1 2 3 4
Fabrica
1 11 22 6 5 75
2 16 31 14 15 60
3 5 21 4 9 40
Cererea 30 65 55 25
14. Rezolvaţi următoarea problemă de transport:
Destinaţia Oferta
1 2 3 4
Sursa
1 15 22 38 40 30
2 29 27 33 35 75
3 39 41 16 19 15
Cererea 22 31 37 30
15. Un centru de creştere a animalelor de carne deţine trei locuri de îngrăşare a
animalelor la Predeal, Stâna de Vale şi Păltiniş. Animalele sunt îngrăşate
aici şi apoi sunt transportate la unul din cele trei abatoare moderne situate
în trei localităti diferite, Braşov, Sibiu şi Oradea. Costurile de transport sunt
date în tabelul de mai jos (la sute de capete):
Abator
1 2 3
Centrul de
creştere
1 42 45 38
2 25 20 30
3 33 26 28
Numărul de animale disponibile în cele trei locuri de îngrăşare, în sute de
capete, sunt:
110 Cercetări operaţionale
Locul de creştere Număr disponibil
1 30
2 40
3 30
Capacităţile, în sute de capete, ale abatoarelor sunt:
Abatorul Capacitate
1 30
2 30
3 40
Determinaţi graficul de transport al animalelor către abatoare astfel încât
costul total să fie minim.
16. O companie care realizează case prefabricate din lemn are cinci clienţi care
doresc locuinţele livrate la timp. Compania are un stoc de case în cinci zone
diferite, şi în fiecare zonă se află două sau trei case. Costurile de livrare a
caselor sunt date în tabelul de mai jos:
Sursă Clienţi
Stoc 1 2 3 4 5
1 93 70 48 68 81 2
2 45 89 97 85 96 3
3 92 93 58 37 99 2
4 55 103 55 57 38 3
5 74 60 78 54 52 2
Cererea 1 1 1 1 1
Datele din tabel se interpretează astfel: sursa 3 are 2 case disponibile; Costul
de transport al unei case de la sursa 3 la clientul 4 este de 37 u.m. ş.a.m.d.
Problema companiei este de a determina planul de livrare al caselor către
cei cinci clienţi astfel încât costul să fie minim.
17. O firmă asigură transportul produselor pij de la depozitele Di la centrele de
desfacere Cj, conform tabelului de mai jos. Determinaţi cantităţile xij ce
trebuie transportate de la fiecare depozit la centre astfel încât costul total al
transportului să fie minim.
5. Probleme de transport 111
C1 C2 C3 Disponibil
D1 20 30 10 100
D2 30 40 25 300
D3 35 15 20 100
Cerere 150 125 225
18. Să se rezolve următoarea problemă de transport:
C1 C2 C3 C4 (D)
D1 5 6 2 5 15
D2 1 3 4 2 25
D3 7 1 3 4 20
(N) 10 30 5 15
19. Să se rezolve următoarea problemă de transport:
D1 D2 D3 D4 N
C1 10 30 20 50 50
C2 60 20 30 20 20
C3 40 50 10 10 60
D 30 10 10 80
20. Să se rezolve următoarea problemă de transport:
C1 C2 C3 D
D1 22 33 11 50
D2 44 55 22 30
N 30 10 40
21. Să se rezolve următoarea problemă de transport:
C1 C2 C3 D
D1 10 4 2 20
D2 6 8 4 40
D3 10 8 6 40
(N) 40 10 30
22. O companie are 3 fabrici şi 5 depozite. Conducerea companiei doreste să
găsească cea mai ieftină modalitate de a repartiza produsele de la fabrici la
fiecare dintre depozite. Costurile de transport şi capacităţile de producţie ale
fabricilor şi, respectiv, de depozitare sunt date în tabelul de mai jos:
112 Cercetări operaţionale
Depozite
Fabrici Capacitatea
de
depozitare 1 2 3
A 5 4 8 800
B 3 5 4 400
C 8 7 4 500
D 6 6 6 400
E 6 7 6 600 Capacitate de
producţie 1100 900 700
Care este sugestia dumneavoastră pentru conducerea firmei?
23. Să se rezolve următoarea
problemă de transport:
C1 C2 C3 (D)
D1 2 1 2 40
D2 9 4 7 60
D3 1 2 9 10
(N) 40 50 20
24. Să se rezolve următoarea
problemă de transport:
C1 C2 C3 (D)
D1 2 1 2 40
D2 9 4 7 60
D3 1 2 9 10
(N) 40 50 20
25. Să se rezolve următoarea
problemă de transport:
C1 C2 C3 (D)
D1 2 1 2 50
D2 9 4 7 70
D3 1 2 9 20
(N) 40 50 20
26. Să se rezolve următoarea
problemă de transport:
C1 C2 C3 (D)
D1 3 8 5 5
D2 2 7 3 14
D3 4 4 2 8
D4 6 5 8 7
(N) 8 10 18
27. Să se rezolve următoarea
problemă de transport:
C1 C2 C3 (D)
D1 6 5 4 10
D2 3 7 2 16
D3 5 10 8 10
D4 4 6 3 12
(N) 10 7 6
28. Să se rezolve următoarea
problemă de transport:
D1 D2 D3 D4 N
C1 5 9 10 6 4
C2 10 7 5 4 5
C3 4 5 5 4 2
C4 6 5 7 5 3
D 3 4 4 3
5. Probleme de transport 113
29. Să se rezolve următoarea problemă de transport:
D1 D2 D3 D4 D5 N
C1 10 20 15 6 0 15
C2 26 30 30 20 16 10
C3 28 29 25 13 8 15
C4 15 20 25 5 5 16
D 9 15 9 15 8
30. Să se rezolve următoarea problemă de transport, unde M reprezintă un cost
prohibitiv:
C1 C2 C3 (D)
D1 6 9 0 20
D2 3 9 11 15
D3 9 1 M 20
D4 M 6 7 15
(N) 20 20 30
31. Să se rezolve următoarea problemă de transport:
C1 C2 C3 C4 (D)
D1 8 6 9 10 35
D2 9 12 13 7 50
D3 14 9 16 5 40
(N) 45 20 30 30