Problemă de transport

Problema de transport este un model din categoria celor de programare liniară, având modelul matematic asemănător acestui tip de problemă, dar cu unele particularităţi care au dus la apariţia unor metode specifice de rezolvare.

1. Modelul matematic

Fie m centre de expediţie ale aceluiaşi produs notate Ai, i=1, …, m şi n centre de primire notate Bj, j=1, …, n. Cantitatea expediată dintr-un centru Ai este egală cu ai, iar cea solicitată în centrul Bj este egală cu bj . Notăm cu cij, i=1, …, m, j=1, …, n costul de transport pe unitatea de produs din Ai în Bj şi cu xij cantitatea transportată din Ai în Bj.

Se pune problema determinării cantităţilor transportate xij , i=1,…, m, j=1,…,n astfel încât costul total de transport să fie minim (sau maxim în unele probleme). Acest costul total de transport este reprezentat de o funcţie de forma:

f=c11x11+ c12x12+ …+ c1nx1n+ c21x21+…+ c2nx2n+…+ cmnxmn

care trebuie minimizată (maximizată). Noi vom considera în continuare doar problemă de minim.

Ca şi în unele probleme obişnuite de programare liniară, există un sistem de restricţii care în acest caz sunt de forma:

În cazul în care are loc = =S atunci problema de transport se va numi echilibrată, iar dacă =S1 S2= se va numi neechilibrată. Vom aborda pentru început problemele de transport echilibrate, modelul matematic al unei astfel de probleme fiind de forma:

min f= (1.8)

în condiţiile:

Pentru rezolvarea problemei se poate utiliza un tabel de forma:

Tabelul (1.3)

Se numeşte celulă (căsuţă) a tabelului (1.3) o pereche de elemente

notată ( i, j), i=1,…, m, j=1,…, n.

O problemă de transport conţine m + n ecuaţii liniare cu mn necunoscute, dintre acestea m + n- 1 fiind liniar independente deci numărul ecuaţiilor liniar independente este mai mic sau egal cu cel al necunoscutelor, sistemul fiind deci nedeterminat.

Definiţie: Se numeşte soluţie admisibilă a problemei de transport , o soluţie care satisface relaţiile (1.9-1.11).

Definiţie: Se numeşte soluţie de bază a problemei de transport, acea soluţie

admisibilă, care conţine cel mult m + n- 1 valori xij>0, restul fiind nule.

Definiţie: Se numeşte soluţie de bază nedegenerată a problemei de transport,

acea soluţie de bază care conţine exact m + n- 1 valori xij>0, restul fiind nule; dacă numărul soluţiilor xij>0 este strict mai mic decât m + n- 1 se numeşte degenerată.

Definiţie: Se numeşte soluţie optimă a problemei de transport, acea soluţie de

bază pentru care se obţine optimul (minimul sau maximul) funcţiei obiectiv.

Definiţie: Se numeşte bază a problemei de transport, notată cu B mulţimea celulelor (i, j) i=1,…, m, j=1,…, n care conţine valori xij > 0 şi este formată din cel mult m + n- 1 celule şi cel puţin n. Celulele care fac parte din bază le numim bazice şi le vom nota (i, j)B, iar celelalte le numim nebazice şi le notăm (i, j)R.

Definiţie: Se numeşte ciclu corespunzător unei celule nebazice , o succesiune de celule bazice (cu excepţia celei iniţiale şi finale) , , …, , , obţinută în felul următor:

- se pleacă din celula şi se trece într-o celulă situată pe orizontala sau verticala celulei , chiar ,,sărind” peste alte celule bazice şi nebazice, astfel încât să existe posibilitatea ca din să se poată trece pe o direcţie perpendiculară, într-o altă celulă bazică .