Probleme de Programare Liniară de Tip Transport

Forma generală a unei probleme de tip transport este dată de tabelul:

B1 B2 ... Bn Disp.

A1 c11 C12 ... c1n D1

A2 c21 C22 ... c2n D2

... ... ... ... ... ...

Am cm1 cm2 ... cmn Dm

Necesar N1 N2 ... Nm

unde A1, A2,...., Am sunt firme producătoare care au disponibile cantităţile D1, respectiv D2, ... , Dm (dintr-un anumit produs), iar B1, B2,...., Bn sunt firme care au nevoie de produsul respectiv în anumite cantităţi: N1, N2, ... , Nm. Costul corespunzător transportului unei unităţi de produs de la firma Ai la beneficiarul Bj este dată de costul cij înscris în tabel. Dacă totalul disponibilului este egal cu totalul necesarului, adică , ne punem problema distribuirii cantităţilor de produse disponibile către beneficiari, în condiţiile unor costuri totale de transport minime.

O soluţie a acestei probleme se scrie sub forma , , , unde reprezintă cantitatea de produs pe care o primeşte beneficiarul Bj de la producătorul Ai.

Pentru a determina costul total de transport, se calculează funcţia obiectiv .

Metode pentru determinarea unei soluţii de bază

Aceste metode duc la găsirea unei soluţii în distribuirea produsului de la producători la beneficiari, fără însă a obţine un cost minim de transport.

1. Metoda minimului pe linie

Se caută costul minim de transport de pe prima linie, . Se compară disponibilul de pe linia 1 cu necesarul de pe coloana j. Dacă disponibilul este mai mic decât necesarul, se atribuie celulei x1j disponibilul existent şi se trece la următoarea linie. Dacă disponibilul este superior necesarului, atunci se atribuie celulei necesarul corespunzător şi se trece la următoarea celulă cu cost minim (dintre cele rămase) de pe linia 1. Se continuă procedeul până se consumă întregul disponibil de pe linia 1, după care se trece la linia următoare. După ce se atribuie întregul disponibil beneficiarilor, se scrie soluţia şi se calculează funcţia obiectiv.

Exemplu

B1 B2 B3 B4 Disp.

A1 4 50 3 4 5 50

A2 100 4 5 6 4 100

A3 3 5 100 4 50 4 150

A4 7 4 5 100 6 100

Necesar 100 50 100 150 400

Solutia va fi: ; functia obiectiv:

2. Metoda minimului pe coloană

Se caută costul minim de transport de pe prima coloană, ci1. Se compară disponibilul de pe linia i cu necesarul de pe coloana 1. Dacă disponibilul este mai mic decât necesarul, se atribuie celulei xi1 acest disponibil şi se trece la următorul cost minim de pe coloana 1. Dacă disponibilul este superior necesarului, atunci se atribuie celulei necesarul corespunzător şi se trece la următoarea coloană. Se continuă procedeul până se atribuie întregul necesar pentru coloana 1, după care se trece la coloana următoare. După ce se atribuie întregul disponibil beneficiarilor, se scrie soluţia şi se calculează funcţia obiectiv.

Exemplu

B1 B2 B3 B4 Disp.

A1 4 50 3 4 5 50

A2 4 5 6 100 4 100

A3 100 3 5 50 4 4 150

A4 7 4 50 5 50 6 100

Necesar 100 50 100 150 400

Solutia va fi: ; functia obiectiv:

3. Metoda minimului pe tabel

Se procedează ca la metodele anterioare, cu deosebirea că se caută costul minim din întreaga matrice a costurilor, . Se compară disponibilul cu necesarul şi după încărcarea celulei cu cost minim, se va trece la următoarea celulă cu cost minim din tabel.