Extras din curs
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.
Preview document
Conținut arhivă zip
- Probleme de Programare Liniara de Tip Transport.DOC