Probleme de Transport Unicriteriale și Multicriteriale

Domeniu: Transporturi

Conține 28 fișiere: doc, rtf

Pagini : 100 în total

Cuvinte : 19211

Mărime: 509.30KB (arhivat)

Publicat de: Melina Cosma

Puncte necesare: 10

Profesor îndrumător / Prezentat Profesorului: Conf. dr. LIANA LUPSA

UNIVERSITATEA “BABEŞ-BOLYAI” CLUJ-NAPOCA FACULTATEA DE MATEMATICĂ ŞI INFORMATICĂ

Descarcă acum

Cuprins Extras Bibliografie Preview

Cuprins

Capitolul I. Probleme de transport
1.1 Formularea problemei de transport dupǎ criteriile cost şi timp 4
1.1.1 Formularea problemei de transport dupǎ criteriul cost 4
1.1.2 Modelul deschis al problemei transportului 7
1.1.3 Formularea problemei de transport dupǎ criteriul timp 9
1.2 Metode de determinare a unui plan de transport 10
1.2.1 Noţiuni introductive 10
1.2.2 Metoda colţului nord-vest 12
1.2.3 Metoda elementului minim 16
1 3 Utilizarea metodei potenţialelor pentru rezolvarea problemei de transport
de tip cost 17
1 3 1 Descrierea algoritmului metodei potenţialelor pentru rezolvarea problemei
de transport de tip cost 19
1.3.2 Fundamentatea teoreticǎ a metodei potenţialelor 27
1.3.3 Degenerarea în problema transportului 33
1.3.4 Convergenţa algoritmului 35
1.3.5 Cazul maximului 36
1.3.6 Restricţii cu inegalitǎţi 37
1.4 Utilizarea metodei potenţialelor pentru rezolvarea problemei de transport
de tip timp 38
1 4 1 Descrierea algoritmului metodei potenţialelor pentru rezolvarea problemei
de transport de tip timp 38
1 4 2 Rezultate legate de studiul problemei de transport de tip timp 41
Capitolul II. Probleme de transport bicriteriale şi multicriteriale de tip cost
2.1 Exemple de probleme de transport bicriteriale şi multicriteriale de tip cost 44
2.2 Utilizarea metodei potenţialelor pentru rezolvarea problemei de transport
bicriteriale de tip cost 46
2.3 Utilizarea metodei potenţialelor pentru rezolvarea problemei de transport multicriteriale de tip cost 51
Capitolul III. Probleme de transport bicriteriale şi multicriteriale de tip mixt.
Probleme de transport bicriteriale de tip timp
3.1 Exemple de probleme de transport bicriteriale şi multicriteriale de tip mixt 59
3.2 Utilizarea metodei potenţialelor pentru rezolvarea problemei de transport
bicriteriale de tip timp-cost 61
3.3 Utilizarea metodei potenţialelor pentru rezolvarea problemei de transport
bicriteriale de tip cost-timp 64
3 4 Utilizarea metodei potenţialelor pentru rezolvarea problemei de transport
bicriteriale de tip timp-timp 67
Capitolul IV. Aplicaţie practicǎ 70
Bibliografie

Extras din proiect

Capitolul I. Probleme de transport

1.1 Formularea problemei de transport după criteriile cost şi timp

1.1.1 Formularea problemei de transport după criteriul cost

Să presupunem că în anumite centre pe care le vom numi baze de desfacere A1,…, Am se găseşte un produs (omogen) respectiv în cantităţiile a1, …, am. Aceste produse urmează să fie transportate în centrele de consum B1, …, Bn respectiv în cantităţiile b1, …, bn. Se cunosc costurile de transport cij pentru o unitate de cantitate, din centrul de desfacere Ai la centru de consum Bj. Se cere cantitatea xij care se transportă de la centrul Ai la centrul Bj.

Condiţiile problemei transportului se pot scrie într-o formă compactă sub forma următorului tabel:

Matricea X = (xij) se va numi matricea planului transportului sau simplu planul transportului, matricea C = (cij) – matricea costurilor, a = (a1, …, am)t – vectorul disponibilului, iar b = (b1, …, bn ) – vectorul necesarului.

Problema transportului: să se întocmească un plan de transport astfel încât cheltuielile totale de transport să fie minime.

Definiţie 1.1.1.1

Un plan X = (xij) se numeşte admisibil dacă numerele xij verifică următoarele condiţii:

(1.1.1.1)

Aici primul grup de condiţii, numite balanţă pe linii, arată că din fiecare centru de desfacere trebuie transportată toată marfa, iar al doilea grup de condiţii, numite balanţă pe coloane, arată că fiecare centru de consum trebuie să fie satisfăcut în întregime.

Modelul matematic al problemei transportului: să se minimizeze funcţia

(1.1.1.2) f(X) = , pentru fiecare X = (xij) ℝmxn .

Funcţia reprezintă costul total al unui plan de transport pe mulţimea planurilor de transport admisibile, adică pe mulţimea soluţiilor admisibile ale sistemului (1.1.1.1).

Convenim ca, în cele ce urmează, problema de transport după criteriul cost (de tip cost) să o notăm prin (TC).

Dacă notăm cu A =

unde I = (1, 1, …, 1) de tip 1xn, iar En este matricea unitate de ordinul n, atunci problema de transport dată în Tabelul 1.1.1.1 se poate formula matricial sub forma:

(1.1.1.3) min {CX | AX = 0, X },

unde s-a pus C = (c11, …, c1n, c21, …, c2n, …, cmn), X = (x11, …, x1n, x21, …, x2n, …, xmn)t.

Teorema 1.1.1.1

Sistemul (1.1.1.1) este compatibil dacă şi numai dacă are loc relaţia

(1.1.1.4)

Demonstraţie

Dacă sistemul (1.1.1.1) este compatibil, atunci avem

deci are loc egalitatea (1.1.1.4).*

Condiţia (1.1.1.4) este şi suficientă pentru compatibilitatea sistemului (1.1.1.1). Într-adevăr, dacă este îndeplinită condiţia (1.1.1.4), atunci numerele

, i {1, …, m}, j {1, …, n}

verifică sistemul (1.1.1.1), căci xij şi avem

şi

Condiţia (1.1.1.4) se numeşte condiţie de echilibru a balanţei.

Teorema 1.1.1.2

Mulţimea soluţiilor admisibile a oricărei probleme de transport în care este verificată condiţia de echilibru a balanţei este o mulţime nevidă şi mărginită.

Demonstraţie

Faptul că mulţimea soluţiilor admisibile este nevidă, în cazul când este verificată condiţia de echilibru (1.1.1.4), rezultă din Teorema 1.1.1.1. Mărginirea rezultă din inegalitatea