Problemă tip transport

Un produs trebuie transportat de la furnizorii F1,F2 catre beneficiarii Bl, B2, B3. Cantitatile de care dispun cei trei furnizori, necesarul fiecarui beneflciar si costurile unitare de transport sunt date in tabelul urmator:

B1 B2 B3 Disponibil

F1 3 2 2 60

F2 4 5 6 70

Necesar 40 50 40

a) Sa se scrie modelul matematic al problemei.

b) Sa se determine planul optim de transport astfel incat costul total de transport sa fie minim, pornind de la o solutie de baza obtinuta prin metoda coltului de nord-vest.

Rezolvare :

Modelul matematic este:

x11 + x12 + x13 = 60

x21 + x22 + x23 = 70

x11 + x21 = 40

x12 + x22 = 50

x13 + x23 = 40

xijc 0

Etapa 1 Se verifică dacă problema este echilibrată (N = D); deoarece N = D = 130, rezultă că această condiţie este îndeplinită.

Se determina solutia de baza prin metoda coltului de nord-vest.

In aceasta metoda se tine cont de pozitia celuluei in tabel.. La fiecare pas se va alege celula din colţul de nord-vest (stânga sus) din dreptunghiul rămas. Pornim de la celula x11

Dacă disponibilul este mai mare decât necesarul, se atriubuie celulei acest necesar şi se trece la celula din colţul de nord-vest a dreptunghiului rămas

Dacă disponibilul este mai mic decât necesarul, se atribuie celulei acest disponibil şi se trece la celula din colţul de nord-vest a dreptunghiului rămas

Etapa 2 Se determină o soluţie de bază, notată Xo.

Folosind metoda coltului de nord-vest se obtine urmatoarea solutie:

B1 B2 B3 Disponibil

F1 3 40 2 20 2 60

F2 4 5 30 6 40 70

Necesar 40 50 40

Etapa 3 Se verifica daca solutia este nedegenerata adica daca are m + n – 1 componente nenule (2+3-1=4). Solutia are 4 componente nenule deci este nedegenerata.