Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Idei bun pentru succesul afacerii tale. producerea de hrana, vegetala si animala, fibre, cultivarea plantelor, cresterea animalelor


Afaceri Agricultura Economie Management Marketing Protectia muncii
Transporturi

Transporturi


Index » business » Transporturi
Minimizarea cheltuielilor de transport. Problema clasica


Minimizarea cheltuielilor de transport. Problema clasica




Minimizarea cheltuielilor de transport. Problema clasica

1. Activitatea de transport. Generalitati

La baza activitatii de transport stau urmatoarele principii:

   reducerea la maxim posibil a operatiilor de transport;




   mecanizarea operatiilor de transport si asigurarea cerintelor de eficienta economica a acestora;

   deplasarea materialelor prin gravitatie, ori de cate ori este posibil;

   asigurarea unui flux simplu si rectiliniu al materialelor cu deplasari cat mai scurte, rapide si fara incrucisari sau blocarea circulatiei;

   alegerea sistemelor de transport usor adaptabile (elastice).

In sistemele de productie organizate pentru productia de masa sau de serie mare, cu flux de transport stabil, transportul se face, de regula, pe baza de grafic, de itinerariu si marsruturi constante. In celelalte situatii (productie de serie mica sau individuala, caz in care fluxurile de transport sunt variabile) transportul se face pe baza de programe zilnice sau la cerere.

Cresterea coeficientului de folosire a cursei determina reducerea necesarului de material rulant, cresterea productivitatii activitatii de transport si reducerea costurilor in activitatea de transport. Analiza costurilor trebuie sa arate abaterile de la costul normat si, eventual, marimea pierderilor.

Caile de imbunatatire a activitatii de transport intern sunt:

   mecanizarea lucrarilor de incarcare-descarcare;

   centralizarea lucrarilor de transport;

   crearea bazei de reparatii si intretinere a mijloacelor de transport;

   sporirea volumului transporturilor care se repeta (aplicarea sistemului pendular si mai ales a sistemului circular);

   repartizarea judicioasa a personalului de deservire si organizarea folosirii rationale a mijloacelor de transport.

Pentru programarea activitatii de transport trebuie sa se cunoasca urmatoarele date:

-      programul de productie al intreprinderii pe perioada considerata;

-      necesarul de materiale pentru indeplinirea sarcinilor de plan (se extrage din planul de aprovizionare).

Intocmirea unui program de transport intern presupune o pregatire minutioasa prin parcurgerea urmatoarelor etape:

Intocmirea sub forma matriciala a unei situatii cu privire la cantitatile de materiale (pe sortimente) ce urmeaza a se asigura sectiilor de productie (consumatorii C1, C2, C3,, Cn) de la sursele de aprovizionare (depozitele D1, D2, D3,, Dm), asa cum este exemplificat in tabelul 1.

Tabelul 1. Modelul matematic corespunzator unei probleme de transport

Necesar consumatori

b1

b2

b3

bj

bm

Cantitati in depozite

Consumator

Depozit

C1

C2

C3

Cj

Cm

Total materiale extrase din depozite

a1

D1

x11

x12

x13

x1j

x1m

a2

D2

x21

x22

x23

x2j

x2m

a3

D3

x31

x32

x33

x3j

x3m

ai

Di

xi1

xi2

xi3

xij

xim





an

Dn

xn1

xn2

xn3

xnj

xnm

Total transportat la consumatori

                  1.      Se determina distantele dintre obiective in tone-metri, distantele medii de transport, numarul mediu de cicluri de transport, coeficientul mediu de manipulare

                  2.      Se intocmeste balanta capacitatii de transport care evidentiaza plusul sau deficitul de capacitate de transport pentru fiecare obiectiv in parte;

                  3.      Se determina necesarul de mijloace de transport, tinand cont de capacitatea de transport a fiecarui mijloc si de coeficientul de folosire al acestuia.

2 Elaborarea planului optim de transport

Elaborarea planului optim de transport face parte din clasa mult mai larga a problemelor modelate prin retele de transport.

O retea de transport modeleaza o situatie economica in care, dintr-un numar de puncte, numite surse (depozitele) trebuie transportata o anumita cantitate dintr-o substanta, intr-un alt numar de puncte denumite destinatii (consumatori). Situatia extrem de generala expusa, poate fi concretizata intr-un numar deosebit de mare de moduri, specificand daca exista sau nu puncte intermediare intre surse si destinatii, modul in care se face transportul (care sunt rutele posibile, costul transportului pe rute, limite maxime sau minime pentru cantitatea transportata pe fiecare ruta, timpul necesar transportului), scopurile urmarite etc.

3 Minimizarea cheltuielilor de transport (problema clasica de transport)

Se considera aprovizionarea a m consumatori, C1, C2, , Cm din n depozite D1,D2,, Dn cu o singura marfa.

In fiecare depozit Di se gaseste cantitatea de marfa ai, i = 1, 2, , n iar fiecare consumator Cj are nevoie de cantitatea de marfa bj, j = 1, 2, , m.

Costul transportului unei unitati de marfa de la Di la Cj este cij.

Scopul modelului este determinarea cantitatilor xij de marfa transportata de la depozitul Di la consumatorul Cj astfel incat costul transportului intregii cantitati de marfa sa fie minim. In situatia in care cij este infinit (foarte mare), transportul de marfa de la Di la Cj este imposibil.

Problemele in care este indeplinita relatia:

, (3)

se numesc echilibrate.

Modelele matematice ale problemei contin ca restrictii urmatoarele doua conditii:

                  4.      totalul marfii extrase dintr-un depozit sa nu depaseasca existentul in acel depozit, adica:

(4)

                  5.      cantitatea totala primita de un consumator sa nu fie mai mica decat necesarul acelui consumator, adica

(5)

Costul total de transport (functia obiectiv) este dat de relatia:

(6)

Cu cele de mai sus rezulta urmatoarele modele ale problemei clasice de transport:

                  6.      problema echilibrata:

(7)

                  7.      problema neechilibrata:

(8)

Problema echilibrata este o problema de programare liniara in forma standard si se poate rezolva folosind algoritmul simplex (dupa o re-notare corespunzatoare a necunoscutelor) care se gaseste sub forma de produse program (soft) ca de exemplu AB/QM sau WINQSB.

Pentru rezolvarea problemei neechilibrate trebuiesc aplicate regulile de aducere a ei la forma standard (folosirea variabilelor de compensare).

Exemplul 1. Se considera rezolvarea problemei de transport a unei marfi de la doua depozite D1 si D2 in care se gasesc cantitatile de marfa a1 respectiv a2 catre trei consumatori C1, C2, C3 care au necesarul b1, b2, b3.

se considera cazul problemei echilibrate, deci a1 + a2 = b1 + b2 + b3.

Costurile transportului cij de la depozitul i la consumatorul j sunt date de matricea urmatoare:

Consumator

Depozit

C1

C2

C3

D1

c11

c12

c13

D2

c21

c22

c23

Problema trebuie sa determine valorile xij ale cantitatilor transportate de la depozitul i la consumatorul j care sa asigure costuri minime:

Consumator

Depozit

C1

C2

C3

D1

x11

x12

x13




D2

x21

x22

x23

Modelul matematic al problemei este:

(9)

Prin re-notarea necunoscutelor modelul matematic devine:

(10)

Se constata ca acesta este un model de programare liniara in forma standard care are 6 necunoscute cu matricea A de forma:

(11)

Se poate constata ca o astfel de problema devine foarte repede uriasa. De exemplu o problema de transport cu n = 10 furnizori si m = 10 consumatori va avea m n = 100 necunoscute, iar matricea A a sistemului: m + n = 20 linii si m n = 100 coloane.

Se observa usor ca rangul matricei r(A) < m + n ceea ce face imposibila aplicarea algoritmului simplex (nu exista o baza de m + n, numarul de linii, vectori coloana liniari independenti necesari in primul pas). Problema se poate rezolva numai prin scrierea problemei extinse.

Daca se considera urmatoarele valori numerice pentru exemplul dat:

Consumator

Depozit

C1:

b1 = 5

C2:

b2 = 7

C3:

b3 = 3

D1:

a1 = 8

c1 = 2

c2 = 5

c3 = 7

D2:

a2 = 7

c4 = 4

c5 = 6

c6 = 2

Rezolvarea problemei se va face utilizand modulul Linear and Integer Programming din pachetul WINQSB si este prezentata in imaginile urmatoare care reprezinta: fereastra initiala pentru introducerea datelor sub forma tabelara, primul tabel simplex si solutia problemei sub forma tabelara.

xij

C1

C2

C3

D1

5

3

0

D2

0

4

3

a. fereastra initiala pentru introducerea datelor sub forma tabelara

b. primul tabel simplex

c. solutia problemei sub forma tabelara

Figura 3. Minimizarea cheltuielilor de transport cu ajutorul modulul

Linear and Integer Programming din pachetul WINQSB

3.1. Dualitatea simetrica

Considerandu-se scrierea unei probleme de programare liniara sub forma matriciala, prin definitie modelul primal I se afla in dualitate simetrica cu modelul dual II, conform relatiilor:

I. (12)

II. (13)

Prin conventie se spune ca fiecare model este simetricul celuilalt.

Legatura dintre solutiile celor doua modele este data de urmatoarele doua teoreme:

Teorema 1. Fie o solutie posibila a modelului I si o solutie posibila a modelului II, atunci

Consecinta: Daca solutiile , au proprietatea atunci este optima pentru modelul I, iar - optima pentru modelul II.

Teorema 2 (teorema ecarturilor complementare). Fie , solutii ale modelelor I respectiv II. Ele sunt optime daca si numai daca:

(14)

Dualitatea simetrica se aplica atunci cand rezolvarea modelului dual este mai simpla.

3.2. Dualitatea nesimetrica

Un model de programare liniara care nu are nici una din formele I sau II nu se afla in dualitate cu nici un alt model.

Similar dualitatii simetrice, s-au conceptul regulile prezentate mai jos pentru scrierea modelului dual pentru orice model de programare liniara. La scrierea modelului dual se considera urmatoarea clasificare a restrictiilor:

                  8.      pentru criteriul de tip MIN:

-        restrictia este concordanta

-        restrictia este neconcordanta

                  9.      pentru criteriul de tip MAX:

-        restrictia este concordanta

-        restrictia este neconcordanta

Model (primal) dat

Model dual

Numar de variabile

Numar de restrictii

Numar de restrictii

Numar de variabile

Minim

Maxim

Maxim

Minim

Termenii liberi ai restrictiilor

Coeficientii functiei obiectiv

Coeficientii functiei obiectiv

Termenii liberi ai restrictiilor

Coloanele matricei restrictiilor

Liniile matricei restrictiilor

Restrictie

concordanta

Variabila

nenegativa

neconcordanta

nepozitiva



egalitate

libera

Variabila

nenegativa

Restrictie

concordanta

nepozitiva

neconcordanta

libera

egalitate

In ceea ce priveste legatura dintre solutiile (optime sau nu) ale celor doua modele, sunt valabile rezultate asemanatoare celor din cazul dualitatii simetrice.

3.3. Rezolvarea problemelor de transport echilibrate prin utilizarea dualitatii

Pentru modelul problemei de transport modelul dual se scrie astfel:

(15)

Se constata ca scrierea modelului dual implica adoptarea variabilelor u1, u2 corespunzatoare numarului de depozite, respectiv v1, v2, v3 - corespunzatoare numarului de consumatori.

Rezolvarea modelului dual si obtinerea solutiei optime a modelului primal a condus la stabilirea urmatorului algoritm pentru rezolvarea problemelor de transport:

Pas 1. Se alege o solutie de baza avand numarul de componente nenule egal cu .

Pas 2. Se rezolva sistemul determinand o solutie particulara .

Pas 3. Daca pentru o componenta xαβ = 0 avem se cauta o alta solutie, pentru care xαβ' sa devina nenul

Pas 4. Solutia optima s-a atins atunci cand:

(16)

Exemplul 2. Pentru exemplul rezolvat clasic prin aplicarea algoritmului simplex utilizand pachetul de programe WINQSB, aplicarea algoritmului de mai sus este urmatoarea:

Pas 1: se alege urmatoarea solutie de baza cu m + n - 1 = 4 componente nenule:

xij

C1

C2

C3

D1

5

3

0

D2

0

4

3

Pas 2: se obtine urmatorul sistem de 4 ecuatii cu 5 necunoscute:

a carui rezolvare conduce la urmatoarea solutie:

Pas 3: - pentru: x13 = 0, u1 + v3 = 1 < c13 = 7;

- pentru: x21 = 0, u2 + v1 = 3 < c21 = 4.

Pas 4: se verifica usor ca este indeplinita conditia , rezultand, deci ca solutia de baza adoptata este cea optima

Problema principala in cazul aplicarii algoritmului de mai sus este gasirea unei solutii initiale de baza. Exista o multitudine de metode care incearca nu numai gasirea unei solutii initiale de baza, ci chiar gasirea uneia cat mai buna. Se expun in continuare urmatoarele metode:

   Metoda nord-vest;

   Metoda minimului pe linii;

   Metoda minimului pe coloane;

   Metoda costului minim;

   Metoda diferentelor maxime.

Schema comuna a acestor metode este urmatoarea:

Pas 1: Se alege o ruta initiala dupa o anumita regula.

Aceasta regula difera in functie de metoda folosita, astfel:

Metoda nord-vest

- ruta din coltul stanga sus al tabelului

Metoda minimului pe linii

- ruta de cost minim de pe prima linie (daca minimul este multiplu se ia prima din stanga)

Metoda minimului pe coloane

- ruta de cost minim de pe prima coloana (daca minimul este multiplu se ia cea mai de sus)

Metoda costului minim

- ruta de cost minim din intregul tabel (daca minimul este multiplu se ia una la intamplare)

Metoda diferentelor maxime

- Pentru fiecare linie si fiecare coloana se calculeaza diferenta dintre cele mai mici doua costuri ale rutelor acesteia (diferenta poate fi si 0 daca minimul este multiplu) si se gaseste maximul dintre aceste diferente;

- Dintre toate rutele de pe liniile si coloanele corespunzatoare acestui maxim se alege ruta de cost minim (daca minimul este multiplu se ia una la intamplare).

Pas 2: Se transporta pe aceasta ruta maximul posibil. Acest maxim este egal cu minimul dintre cantitatea care mai e disponibila la furnizorul corespunzator acestei rute si cantitatea care mai e necesara la consumatorul corespunzator rutei, in momentul alegerii acestei rute.

Pas 3: Dupa folosirea unei rute este clar ca fie se epuizeaza disponibilul furnizorului corespunzator, fie se asigura intregul necesar al consumatorului corespunzator, fie ambele. Daca se epuizeaza disponibilul furnizorului este clar ca nici o ruta care pleaca de la acesta nu va mai fi folosita si analog, daca se asigura intregul necesar al consumatorului, nici o ruta spre acesta nu va mai fi folosita. Rutele care nu vor mai fi folosite se numesc rute blocate, sunt cele nefolosite inca de pe linia sau/si coloana ultimei rute folosite si se evidentiaza in tabel prin hasurare.

Pas 4: Se alege ruta urmatoare, folosind una dintre urmatoarele metode:

Metoda nord-vest

cea mai apropiata ruta de ultima aleasa dintre cele neblocate

Metoda minimului pe linii

ruta de cost minim de pe prima linie pe care mai sunt inca rute neblocate (daca minimul este multiplu se ia prima din stanga)

Metoda minimului pe coloane

ruta de cost minim de pe prima coloana pe care mai sunt inca rute neblocate (daca minimul este multiplu se ia cea mai de sus)

Metoda costului minim

ruta de cost minim din intregul tabel dintre cele neblocate inca (daca minimul este multiplu se ia una la intamplare)

Metoda diferentelor maxime

se repeta procedeul de la pas 1 pentru rutele neblocate inca

Pas 5: Se reia algoritmul de la pas 2 pana cand nu mai ramane nici o ruta nefolosita sau neblocata.

Rezolvare:

Cei doi algoritmi prezentati mai sus sunt folositi pentru rezolvarea problemelor de transport si de modulul Network Modeling/Transportation Problem din pachetul de programe WINQSB asa cum se exemplifica in imaginile din figura 4.

3.4 Rezolvarea problemelor de transport neechilibrate

Problemele de transport neechilibrate se rezolva prin echilibrarea lor considerandu-se, dupa caz, un depozit sau consumator fictiv care sa echilibreze problema. Evident ca se va considera valoarea zero pentru costul transportului de la depozitul fictiv catre orice consumator respectiv de la orice depozit catre consumatorul fictiv.

a. fereastra principala pentru alegerea tipului de problema

b. tabelul pentru introducerea datelor

c. rezultatele obtinute prin rularea modelului

Figura 4. Rezolvarea problemelor de transport cu ajutorul modulului

Network Modeling/Transportation Problem din pachetul de programe WINQSB







Politica de confidentialitate


Copyright © 2019 - Toate drepturile rezervate

Transporturi




Minimizarea cheltuielilor de transport. Problema clasica