Problema de transport - DRL.ro

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


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.


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


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.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


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.


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


(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)


Fig. 5.2. Caseta de dialog Solver Parameters


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).


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).


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


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ă


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).


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


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


Î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:


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.


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


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:


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:


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.


C1 C2 C3 Disponibil

D1 20 30 10 100

D2 30 40 25 300

D3 35 15 20 100

Cerere 150 125 225


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


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


C1 C2 C3 D

D1 22 33 11 50

D2 44 55 22 30

N 30 10 40


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:


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



C1 C2 C3 (D)

D1 2 1 2 40

D2 9 4 7 60

D3 1 2 9 10

(N) 40 50 20



C1 C2 C3 (D)

D1 2 1 2 50

D2 9 4 7 70

D3 1 2 9 20

(N) 40 50 20



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



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



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



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


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

Date post:	12-Dec-2021
Category:	Documents
Upload:	others
View:	2 times
Download:	0 times

Problema de transport - DRL.ro

Documents