PROBLEMA CLASICĂ DE TRANSPORT

 

 

Problema clasică de transport face parte din clasa mult mai largă a problemelor modelate prin rețele de transport. O rețea de transport modelează o situație economică în care, dintr-un anumit număr de puncte, numite surse, trebuie transportată o cantitate dintr-o anumită substanță, într-un alt număr de puncte, numite destinații. Situația extrem de generală de mai sus poate fi apoi concretizată într-un număr deosebit de mare de moduri, specificând dacă există sau nu puncte intermediare între surse și destinații, modul în care se face transportul (care sunt rutele posibile, costul transportului, limite minime și/sau maxime pentru cantitatea transportată pe fiecare rută, timpul necesar transportului), scopurile urmărite etc. Din această cauză există o multitudine de probleme care implică rețele de transport, dintre acestea putând aminti:

 

1.      Problema clasică de transport

2.      Problema transferului

3.      Problema drumului de cost minim

4.      Problema fluxului maxim

5.      Problema fluxului maxim de cost minim

6.      Probleme de flux dinamic

7.      Problema cuplajului maxim

8.      Problema de afectare

9.      Problema de ordonanțare

10.  Problema comis voiajorului

11.  Problema arborelui de cost minim

 

În continuare o vom detalia pe prima dintre acestea.

Caracteristicile unei probleme de transport clasice sunt:

 

1.  fiecare sursă aprovizionează cel puțin o destinație și fiecare destinație este aprovizionată de la cel puțin o sursă;

2.  pot exista perechi sursă-destinație între care nu se poate face transfer (rute blocate);

3.  nu există limitări în ceea ce privește cantitatea transportată pe fiecare rută;

4.  se cunosc cantitățile disponibile în fiecare sursă și cantitățile necesare în fiecare destinație;

5.  fiecărei rute i s-a asociat un cost care nu depinde de sensul de parcurgere.

 

Scopul problemei este găsirea acelor cantități care trebuie transportate pe fiecare rută astfel încât să se asigure necesarul fiecărei destinații, în limitele cantităților aflate la surse, cu costul minim posibil.

Datele problemei sunt:

 

1.      m = numărul de surse (furnizori);

2.      n = numărul de destinatari (consumatori);

3.      {Ai, i = 1,...,m} = cantitățile disponibile în fiecare sursă;

4.      {Bj, j = 1,...,n} = cantitățile necesare la fiecare sursă;

5.      {cij, i = 1,...,m; j = 1,...,n}  = costurile unitare pe fiecare rută (costul transportării unei unități de măsură de la sursa i la destinația j).

 

Acestea au fost organizate într-un tabel ca cel de mai jos:


 

Destinații

Surse

C1

C2

¼

Cn

 

F1

c11

c12

¼

c1n

A1

F2

c21

c22

¼

c2n

A2

Fm

cm1

cm2

¼

cmn

Am

B1

B2

¼

Bm

disponibil

necesar

 

Dacă notăm cu xij cantitatea care va fi transportată de la sursa i la destinația j atunci avem de rezolvat problema:

care este un caz particular de problemă de programare liniară.

Într-o primă analiză, se observă imediat că problema nu are soluții admisibile dacă disponibilul total este mai mic decât cererea totală. Matematic, afirmația de mai sus este justificată prin relațiile obținute prin adunarea primelor m restricții și apoi a ultimelor n:

disponibil total = = cerere totală

De asemenea, condiția ca  este și suficientă, deoarece, în acest caz, se verifică ușor că soluția  este soluție admisibilă.

În altă ordine de idei, chiar dacă disponibilul total este mai mare decât cererea totală, este clar că se va transporta doar necesarul, deoarece transportarea unei cantități mai mari decât necesarul va duce la un cost suplimentar, în contrast cu scopul urmărit. Matematic, unei soluții în care una din ultimele n restricții ar fi verificată strict, îi corespunde o soluție în care am scăzut cantitatea suplimentară din valorile variabilelor implicate în restricție, care este de asemenea admisibilă (aceste variabile nu apar în alte restricții dintre ultimele n, iar primele m vor fi cu atât mai mult verificate dacă xij scad) și care este evident mai bună, dând un cost mai mic.

În concluzie, dacă există soluție optimă, se va transportă exact cantitatea cerută.

Totuși, în practică se poate întâlni oricare din cele trei cazuri:

(1)

(2)

(3)

 

În primul caz, problema are soluție optimă, iar cantitatea în exces față de cerere va rămâne la furnizori, fiind reprezentată de variabilele de abatere din primele m restricții. Aceste cantități pot fi privite ca niște cereri ale unui consumator fictiv și ținând cont că, de fapt, aceste cantități nu sunt transportate nicăieri, costurile unitare pe rutele care ar lega furnizorii de acest consumator sunt 0. Adăugând acest consumator la tabel, cu cererea egală cu , vom obține o problemă de tipul (3).

Analog, în al treilea caz, chiar dacă disponibilul este mai mic decât necesarul, nu înseamnă că nu se va mai transporta nimic, ci doar că unora dintre consumatori nu li se va satisface toată cererea. Această cerere nesatisfăcută poate fi privită ca disponibilul unui furnizor fictiv și ținând cont că, de fapt, această cantitate nu există, costurile unitare pe rutele care ar lega consumatorii de acest furnizor sunt 0. Adăugând acest furnizor la tabel, cu disponibilul egal cu , vom obține o problemă de tipul (3).

În concluzie, orice problemă poate fi transformată într-o problemă de tipul (3). Deși acest caz este foarte rar în practică, el este cel mai simplu din punct de vedere matematic și va fi ales pentru formalizarea problemei. O astfel de problemă se numește problemă de transport echilibrată.

De asemenea, este ușor de văzut că, pentru o problemă de transport echilibrată, toate soluțiile admisibile verifică toate restricțiile cu egal. Astfel, dacă măcar una din primele m restricții ar fi verificată cu "<" atunci am avea prin însumare:

, în contradicție cu

iar dacă măcar una din ultimele n restricții ar fi verificată cu ">" atunci am avea prin însumare:

, în contradicție cu

În concluzie, orice problemă de transport este echivalentă cu o problemă de forma:

unde 

care este forma standard a problemei de transport.

Rezolvarea problemei de transport

 

Este evident că problema de transport la forma standard este o problemă de programare liniară la forma standard, dar, la fel de evident este și faptul că este o problemă de programare care devine foarte repede uriașă (un exemplu practic obișnuit cu, de exemplu, 50 de furnizori și 50 consumatori, va duce la un tabel simplex de 100 Ž 2500, și sunt cazuri și cu mii de furnizori și consumatori), motiv pentru care algoritmul simplex sub forma clasică nu este aplicabil. Cum s-a văzut însă, există și metode prin care se poate reduce mult volumul de calcule (vezi algoritmul simplex revizuit). În plus, datele problemei de transport au o structură cu totul deosebită, în matricea A a sistemului, toate componentele fiind 1 sau 0, din care 0 sunt mult mai mulți. Din acest motiv este natural să căutăm un algoritm special pentru problema de transport care să se folosească la maximum caracteristicile acesteia.

Pentru ilustrarea celor de mai vom scrie matricea A desfășurat:

 


m ori

 

n coloane

 

n coloane

 

n linii

 

m linii

 

n coloane

 
 

 

 

 

 


Această matrice are m + n linii, mŚn coloane și deci (m + n)Śmn componente din care doar 2mn sunt 1, restul fiind 0. O problema cu 50 furnizori și 50 consumatori va avea doar un procent de:

 

 = 2% componente egale cu 1

 

Observând că suma primelor m linii minus suma ultimelor n este 0, rezultă că liniile matricii sunt liniar dependente, deci rangul lui A este mai mic decât m + n. Se poate găsi însă un minor de dimensiune m + n – 1 cu determinantul diferit de 0 (cititorul îl poate găsi singur), deci o bază a unei probleme de transport are dimensiunea m+n–1 și o soluție de bază are cel mult m+n–1 componente diferite de 0 (o soluție nedegenerată are deci m+n–1 componente diferite de 0). Preferarea soluțiilor nedegenerate se face din același motiv ca și la algoritmul simplex și anume evitarea ciclării (la problema de transport este mult mai important acest aspect deoarece soluțiile de bază ale acesteia sunt, în general, puternic degenerate).

Înainte de a da algoritmul pentru rezolvarea problemei de transport, trebuie remarcat că într-o problemă de transport nu poate apărea decât varianta de optim finit, existând întotdeauna soluții admisibile (așa cum s-a demonstrat mai sus) iar minimul –¥ nu este posibil, ținând cont că avem de minimizat o funcție liniară cu toți coeficienții pozitivi pe o mulțime de soluții cu toate componentele pozitive.

Ca și în algoritmul simplex, rezolvarea problemei de transport se face în două etape:

 

Etapa 1. Găsirea unei soluții inițiale de bază

 

Deoarece fiecare variabilă corespunde unei rute (este cantitatea transportată pe această rută) iar fiecare rută corespunde unei perechi furnizor-consumator, vom identifica fiecare variabilă xij cu ruta (i,j). A găsi o soluție de bază nedegenerată este echivalent cu a găsi cel mult m+n–1 rute, din cele m·n posibile, pe care să transportăm toată cantitatea disponibilă. Rutele vor fi organizate într-un tabel asemănător celui în care sunt organizate datele problemei, fiecărei rute corespunzându-i o căsuță (i,j):

 

ruta (i,j)

 
Destinații

Surse

C1

C2

¼

Cj

¼

Cn

 

F1

 

 

 

 

 

 

A1

F2

 

 

 

 

 

 

A2

 

 

 

 

 

 

Fi

 

 

 

 

 

 

Ai

 

 

 

 

 

 

Fm

 

 

 

 

 

 

Am

 

B1

B2

¼

Bj

¼

Bm

disponibil

necesar

 

Spre deosebire de algoritmul simplex, găsirea unei soluții inițiale de bază nu este dificilă. De fapt, este atât de ușor de găsit o astfel de soluție, încât există o multitudine de metode în acest scop, care încearcă nu numai găsirea acesteia, ci chiar găsirea uneia cât mai bună. Vom expune dintre acestea:

 

1.      Metoda nord – vest;

2.      Metoda minimului pe linii;

3.      Metoda minimului pe coloane;

4.      Metoda costului minim;

5.      Metoda diferențelor maxime;

 

Cu toate că sunt foarte multe, toate metodele urmează o schemă comună:

 

Pasul 1.    Se alege o rută inițială după o anumită regulă. Această regulă diferă în funcție de metoda folosită, fiind:

 

Metoda nord – vest;

–

ruta din colțul stânga sus al tabelului

Metoda minimului pe linii

–

ruta de cost minim de pe prima linie (dacă minimul este multiplu se ia prima din stânga)

Metoda minimului pe coloane

–

ruta de cost minim de pe prima coloană (dacă minimul este multiplu se ia cea mai de sus)

Metoda costului minim

–

ruta de cost minim din întregul tabel (dacă minimul este multiplu se ia una la întâmplare)

Metoda diferențelor maxime

–

1.      Pentru fiecare linie și fiecare coloană se calculează diferența dintre cele mai mici două costuri ale rutelor acesteia (diferența poate fi și 0 dacă minimul este multiplu) și se găsește maximul dintre aceste diferențe;

2.      Dintre toate rutele de pe liniile și coloanele corespunzătoare acestui maxim se alege ruta de cost minim (dacă minimul este multiplu se ia una la întâmplare)

 

Pasul 2.    Se transportă pe această rută maximul posibil. Acest maxim este egal cu minimul dintre cantitatea care mai e disponibilă la furnizorul corespunzător acestei rute și cantitatea care mai e necesară la consumatorul corespunzător rutei, în momentul alegerii acestei rute. Se transportă în acest fel pentru ca să se folosească cât mai puține rute și deci să se obțină o soluție de bază.

 

Pasul 3.    După folosirea unei rute este clar că fie se epuizează disponibilul furnizorului corespun­zător, fie se asigură întregul necesar al consumatorului corespunzător, fie ambele.  Dacă se epuizează disponibilul furnizorului este clar că nici o rută care pleacă de la acesta nu va mai fi folosită și analog, dacă se asigură întregul necesar al consumatorului, nici o rută spre acesta nu va mai fi folosită. Rutele care nu vor mai fi folosite se numesc rute blocate, sunt cele nefolosite încă de pe linia sau /și coloana ultimei rute folosite și se evidențiază în tabel prin hașurarea acestora.

 

Pasul 4.    Se  alege următoarea rută, folosind regula:

 

Metoda nord – vest;

–

cea mai apropiată ruta de ultima aleasă dintre cele neblocate încă;

Metoda minimului pe linii

–

ruta de cost minim de pe prima linie pe care mai sunt încă rute neblocate (dacă minimul pe aceasta este multiplu se ia prima din stânga);

Metoda minimului pe coloane

–

ruta de cost minim de pe prima coloană pe care mai sunt încă rute neblocate (dacă minimul pe aceasta este multiplu se ia cea mai de sus);

Metoda costului minim

–

ruta de cost minim din întregul tabel dintre cele neblocate încă (dacă minimul este multiplu se ia una la întâmplare);

Metoda diferențelor maxime

–

se repetă procedeul de la pasul 1 pentru rutele neblocate încă.

 

Pasul 5.    Se reia algoritmul de la pasul 2 până când nu mai rămâne nici o rută nefolosită sau neblocată.

 

Se observă că, dacă prima metodă este pur geometrică, neținând cont de costurile rutelor, toate celelalte încearcă să micșoreze cât mai mult costul întregului transport. Cu toate că, statistic vorbind, ultima metodă este cea mai bună, ea dând de foarte multe ori chiar soluția optimă, totuși și existența celorlalte metode este justificată de faptul că sunt mai simplu de aplicat și există cazuri în care fiecare dă soluția cea mai bună.

 

 

 Etapa 2. Găsirea soluției optime

 

Algoritmul care urmează reprezintă algoritmul simplex pentru o problemă de minim, aplicat în cazul particular al problemei de transport.

 

Pasul 1.   Se asociază fiecărui furnizor Fi o variabilă ui și fiecărui consumator Cj o variabilă vj;

Pasul 2.   Fiecărei rute (i,j) folosită în soluția actuală i se asociază ecuația ui + vj = cij, rezultând un sistem cu m + n necunoscute (m de ui și n de vj) și m + n – 1 ecuații (egal cu rangul matricii A);

Pasul 3.   Se găsește o soluție particulară a acestui sistem, egalând una din necunoscute cu 0 (pe cea care apare de cele mai multe ori);

Pasul 4.   Se calculează toți Dij = ui + vj – cij pentru toate rutele care nu fac parte din soluție (ceilalți sunt 0, ținând cont de felul cum au fost găsiți ui, i = 1,...,m și vj, j = 1,...,n)

Pasul 5.   Se analizează Dij găsiți.

 

-       dacă toți sunt mai mici sau egali cu 0 soluția găsită este optimă ź STOP

-       dacă există Dij strict pozitivi atunci soluția actuală nu este optimă și ruta corespunzătoare lui Dij maxim va fi cea care intră în bază (dacă maximul este multiplu se ia una la întâmplare)

 

Pasul 6.         Se construiește un circuit, pornind din această rută, trecând doar prin rutele soluției, mergând doar pe verticală sau orizontală și fiecare trecere de la o rută la alta făcându-se doar perpendicular pe trecerea anterioară. S-a demonstrat că există un singur circuit cu aceste proprietăți și se poate demonstra ușor că trece printr-un număr par de rute.

Pasul 7.         Începând cu + din ruta care va intra în bază se notează alternativ cu "+" și "–" rutele circuitului;

Pasul 8.         Se notează cu q minimul dintre cantitățile transportate pe rutele notate cu "–" și ruta pentru care s-a obținut acest minim este cea care va ieși din bază (cazul minimului multiplu va fi analizat după expunerea algoritmului);

Pasul 9.         Se scade q din cantitățile transportate pe rutele notate cu "–" și se adaugă la cele notate cu "+", rutele care nu sunt pe circuit păstrându-și valoarea;

Pasul 10.     Se reia algoritmul de la pasul 2

 

 

Așa cum s-a văzut mai sus, se poate ca la pasul 8 minimul q să fie multiplu. Atunci, pe toate rutele pe care se transporta q nu se va mai transporta nimic, adică vor dispărea din soluție. Cum în soluție a intrat doar o singură rută rezultă că noua soluție este degenerată. Cum existența acestui tip de soluții poate duce la ciclarea algoritmului, au fost imaginate mai multe metode de evitare, toate bazându-se pe modificarea datelor inițiale, în așa fel încât, pe parcursul algoritmului, să nu mai avem nici o soluție degenerată. Această modificare (perturbare) poate fi făcută chiar de la începutul rezolvării, încât problema să nu mai aibă nici o soluție degenerată, fie doar atunci când apare o soluție degenerată, eliminând perturbația imediat ce nu mai e necesară. Pentru a vedea cum trebuie să arate o astfel de modificare, dăm următoarea teoremă care caracterizează existența soluțiilor degenerate:

 

Teoremă.  O problemă de transport are soluții degenerate dacă și numai dacă există o submulțime strictă și nevidă a furnizorilor și o submulțime strictă și nevidă a consumatorilor astfel încât suma disponibilurilor furnizorilor din prima submulțime este egală cu suma cererilor consumatorilor din a doua.

 

Lemă.  Soluția este degenerată de k ori dacă și numai dacă mulțimea furnizorilor și a consumatorilor se pot partiționa în k submulțimi F1, F2, ..., Fk și W1, W2  ,..., Wk astfel încât consumatorii din fiecare clasă Wi se aprovizionează numai de la furnizorii din clasa Fi.

 

În concluzie, dacă vrem să dispară toate soluțiile degenerate, trebuie modificate disponibilurile și cererile în așa fel încât să nu mai poată exista varianta din teoremă. Una din metodele posibile este să adăugăm la fiecare furnizor Fi cantitatea ei și să introducem un consumator fictiv cu cererea egală cu e + e2 + ...  + em, unde e este o valoare foarte mică (oricât de mică este necesar). O altă variantă este să adăugăm la fiecare furnizor Fi cantitatea iŚe și să introducem un consumator fictiv cu cererea egală cu e + 2Śe + ...  + mŚe, unde e este de asemenea o valoare foarte mică (oricât de mică este necesar). Se pot găsi, evident, și altele variante.

Această metodă este foarte bună în cazul rulării problemei pe calculator, dar, în cazul rezolvării cu creionul pe hârtie, este, evident, greoaie.

În acest caz vom folosi varianta în care introducem perturbația doar când este nevoie (adică când apare o soluție degenerată). Această situație poate apărea fie chiar la soluția inițială, în urma aplicării uneia din metodele de găsire ale unei soluții inițiale, fie la pasul 8 din a doua etapă dacă q se obține pentru mai multe rute. Rămâne de văzut doar cum trebuie făcută această perturbare.

Conform teoremei de mai sus rezultă că mulțimea furnizorilor și a consumatorilor se pot partiționa în k submulțimi F1, F2, ..., Fk și W1, W2  ,..., Wk astfel încât consumatorii unei clase Wi se aprovizionează numai de la furnizorii din clasa Fi și reciproc. Pentru fiecare indice i £ k–1 vom alege o rută care corespunde unui furnizor din Fi și unui consumator din Wi+1 și vom adăuga la furnizorul și consumatorul corespunzători acesteia cantitatea ei (sau valoarea ei într-o ordine dată a valorilor). Dacă, la un moment dat, prin anularea unui parametru introdus, soluția rămâne nedegenerată, acesta va fi anulat.

 

Exemplu:  Presupunem că în rezolvarea problemei:

 

 

C1

C2

C3

C4

C5

C6

C7

C8

C9

C10

C11

C12

 

F1

2

4

5

3

7

8

9

3

5

7

3

8

1000

F1

3

5

6

7

5

4

3

5

5

6

3

6

700

F1

2

4

5

3

6

7

4

5

7

4

6

7

400

F1

3

4

2

6

8

4

6

7

4

7

8

3

900

F1

3

5

6

4

7

8

3

5

6

9

3

6

400

F1

2

4

6

3

7

8

9

4

6

2

4

2

400

F1

3

5

2

6

7

8

9

5

3

6

7

3

700

F1

9

4

5

3

6

2

7

8

9

4

7

5

400

F1

8

3

4

2

6

3

7

8

3

7

4

8

800

 

800

300

600

400

500

200

700

300

200

600

600

500

 

 

s-a ajuns la soluția de bază:

 

 

C1

C2

C3

C4

C5

C6

C7

C8

C9

C10

C11

C12

 

F1

 

 

 

200

500

 

200

 

 

 

 

 

900

F2

 

 

200

 

 

 

 

 

 

500

 

 

700

F3

 

 

 

 

 

300

 

500

 

 

 

 

800

F4

 

200

 

 

 

 

 

 

 

 

800

 

1000

F5

 

 

 

 

 

 

400

 

 

 

 

 

400

F6

 

100

 

 

 

 

 

 

300

 

 

 

400

F7

 

 

 

 

 

300

 

 

 

100

 

 

400

F8

 

 

 

 

 

 

100

 

 

 

 

300

400

F9

400

 

 

 

 

 

 

 

300

 

 

 

700

 

400

300

200

200

500

600

700

500

600

600

800

300

 

 

care este dublu degenerată. Aceasta înseamnă că mulțimea furnizorilor și consumatorilor pot fi partiționate fiecare în trei grupe. Pentru a le găsi vom porni de la un furnizor, vom găsi consumatorii care se aprovizionează de la acesta, apoi furnizorii care aprovizionează acești consumatori și tot așa până vom găsi prima grupă din fiecare (furnizori și consumatori). Pentru cei rămași din fiecare vom continua procedeul până vom găsi toate grupele.

În cazul nostru pentru F1 găsim consumatorii C4, C5 și C7, pentru aceștia furnizorii F5 și F8, pentru aceștia noul consumator C12 și am găsit prima grupă:

 

-       consumatorii {C4, C5, C7, C12} se aprovizionează de la furnizorii {F1, F5, F8}

 

Apoi, pentru F2 găsim consumatorii C3 și C10, pentru aceștia furnizorul F7, pentru acesta noul consumator C6, pentru acesta noul furnizor F3, pentru acesta noul consumator C8 și am găsit a doua grupă:

 

-       consumatorii {C3, C6, C8, C10} se aprovizionează de la furnizorii {F2, F3, F7}

 

A treia grupă va fi, evident: {C1, C2, C9, C11} se aprovizionează de la furnizorii {F4, F6, F9}

Conform regulii de perturbare, vom alege o rută corespunzătoare unui furnizor din prima grupă și unui consumator din a doua, de exemplu (5,6) și o rută corespunzătoare unui furnizor din a doua grupă și unui consumator din a treia, de exemplu (3,9) și vom adăuga la furnizorul F5 și consumatorul C6 cantitatea suplimentară a iar la furnizorul F3 și consumatorul C9 cantitatea suplimentară b, cu a < b de exemplu, obținând problema perturbată:      

 

 

C1

C2

C3

C4

C5

C6

C7

C8

C9

C10

C11

C12

 

F1

 

 

 

200

500

 

200

 

 

 

 

 

900

F2

 

 

200

 

 

 

 

 

 

500

 

 

700

F3

 

 

 

 

 

300

 

500

b

 

 

 

800+b

F4

 

200

 

 

 

 

 

 

 

 

800

 

1000

F5

 

 

 

 

 

a

400

 

 

 

 

 

400+a

F6

 

100

 

 

 

 

 

 

300

 

 

 

400

F7

 

 

 

 

 

300

 

 

 

100

 

 

400

F8

 

 

 

 

 

 

100

 

 

 

 

300

400

F9

400

 

 

 

 

 

 

 

300

 

 

 

700

 

400

300

200

200

500

600

+ a

700

500

600

+ b

600

800

300

 

 

care nu mai este degenerată.

Rămâne ca exercițiu verificarea faptului dacă această soluție este optimă și dacă nu, să se găsească soluția de bază succesoare.

 

 Variante ale problemei de transport

 

Există o gamă foarte largă de fenomene economice care pot fi reprezentate prin modele de programare liniară de tip transport sau foarte asemănătoare cu acestea. Prezentăm în continuare câteva dintre acestea

 

1. Cu rute blocate

 

În anumite cazuri pot exista situații în care anumite rute între furnizori și consumatori nu pot fi folosite, cel puțin temporar. Rezolvarea acestor probleme se face cu un model de transport obișnuit, în care rutelor interzise li se asociază costuri unitare de transport foarte mari în raport cu costurile rutelor utilizabile. Prin aceste costuri de penalizare foarte mari, algoritmul de optimizare este "constrâns" să ocolească rutele interzise.

 

2. Cu puncte intermediare

 

 Există situații în care aprovizionarea consumatorilor nu se face direct de la furnizori ci prin intermediul unor centre intermediare. De exemplu, cea mai mare parte a bunurilor produse pentru consumul populației sunt mai întâi colectate în mari depo­zite și apoi distribuite centrelor de desfacere. Problema de optimizare costă în minimizarea cheltuielilor de transport de la furnizori la centrele intermediare la care se adaugă costul transportului­ de la aceste centre la consumatorii finali.

În anumite condiții această problemă este echivalentă cu două probleme de transport obișnuite.

 

3. Problema afectării

 

Există probleme de programare operativă care pot fi reprezentate prin modele liniare de tipul problemei de transport. Un exemplu des întâlnit este următoarea problemă concretă de pro­gramare operativă a producției:

           

"Un număr de lucrări Ll, L2,..., Ln trebuiesc executate cât mai repede. Acestea sunt efectuate de persoanele (muncitorii) Ml, M2,..., Mn, fiecare putând executa oricare din lucrările date. Cunoscând timpul tij de execuție al lucrării Li de către muncitorul Mj, scopul optimizării este găsirea acelui mod de repartizare a lucrărilor pe muncitori astfel încât timpul total de execuție al lucrărilor să fie minim"

 

Pentru modelarea matematică a acestei probleme, cunoscută în literatura de specialitate sub numele de "problema afectării", se introduc variabilele bivalente:

 

xij =

 

Condițiile ca fiecare lucrare să fie repartizată unui muncitor precum și condiția ca fiecare muncitor să primească o lucrare se traduc prin restricțiile:

 

 

în care variabilele xij satisfac cerința specială:

 

xij Î {0,1}

 

Obiectivul urmărit – minimizarea timpului total de execuție – conduce la următoarea funcție obiectiv:

 

(min) f =

 

Modelul rezultat diferă de modelul problemei de transport echilibrate prin condiția impusă variabilelor de a fi doar 0 sau 1 (variabile bivalente). Totuși rezolvarea sa se poate face cu algoritmul de la problema de transport, însă ea este greoaie, datorită faptului că soluțiile de bază ale acestei probleme sunt puternic degenerate. Există metode mai eficiente de abordare a problemei afectării, bazate pe teoria grafurilor.

 

4. Problema încărcării utilajelor

 

Făcând parte din același cadru al programării operative a producției, problema încărcării utilajelor (punctelor de lucru) ocupă a poziție centrală. Această problemă poate fi formulată astfel:

 

"Într‑o secție a unei unități economice se produc reper­ele (bunurile) P1, P2, ..., Pn care pot fi realizate pe oricare din utilajele (grupele de utilaje) Ul,U2,...,Um. Se cunosc următoarele date:

 

-       cantitățile N1, N2,...,Nn din reperele date, care trebuie produse într‑o anumită perioadă;

-       fondurile de timp disponibil F1, F2,...,Fm ale utilaje­lor, în        perioada respectivă;

-       cantitatea Pij din reperul Pj ce poate fi produsă pe utilajul Ui într‑o anumită perioadă de timp;

-       costul cij al realizării unei unități specifice din reperul Pj pe utilajul U­i.

 

Se dorește găsirea acelui mod de repartizare a sarcinilor de producție pe utilaje astfel încât costul realizării cantităților planificate să fie minim."

Modelul matematic asociat acestei probleme este:

 

 

unde xij reprezintă cantitatea de repere Pj ce urmează a fi realizată pe utilajul Ui. Modelul este asemănător modelului problemei de transport, pentru rezolvare putându-se folosi algoritmul de la problema clasică de transport, cu unele modificări dictate de prezența "ponderilor" Pij.

 

5. Problema de transport a lui Koopmans

 

Această problemă este, istoricește vorbind, anterioară problemei clasice de transport și de ea s-a ocupat pentru prima oară T. C. Koopmans.

Problema se referă la la transportul materialelor de război, efectuate în perioada celui de‑al doilea război mondial, din S.U.A. în Anglia și retur. Întrucât cantitățile de produse transportate în cele două sensuri erau diferite, navele circulau de multe ori goale sau incomplet încărcate. Având în vedere și faptul că transporturile pe mare ale aliaților se aflau sub amenințarea submarinelor și a aviației germane se punea problema asigurării unei asemenea utilizări a mijloacelor de transport încât să se reducă la minimum capacitatea de transport neutilizată (măsurată în tone-kilometri) și, implicit, să se reducă pierderile de nave.

Deși problema de transport a lui Koopmans a avut un caracter tactico‑militar, ea poate fi considerată ‑ după cum a făcut mai târziu însuși Koopmans ‑ și ca o problemă economică. Economic vorbind, reducerea capacității de transport neutilizate a navelor mărește rentabilitatea transporturilor maritime. Firește că am putea aplica o soluție optimă a acestei probleme pe plan mondial numai în cazul în care ar exista o formă oarecare de administrate internțională a navelor și de dirijare a transporturilor maritime. Totuși, se poate vedea că modelul lui Koopmans poate să‑și găsească aplicarea nu numai la transportul maritim, ci și în transportul feroviar, în cel auto, precum și în alte domenii similare.

Matematic, această problemă se poate formula astfel:

 

"Fie n porturi din care se expediază și în care sosesc încărcături. Notăm cu wi un volum dat de mărfuri expediate (exprimate, de pildă, în tone), iar cu pi ‑ un volum dat de mărfuri care se aduc în decursul unei anumite perioade în portul i (i = 1, 2,..., n). Se cunosc distanțele sij dintre porturi (exprimate, de pildă, în kilometri), acestea fiind date în matricea:

 

S =

 

Dacă xij reprezintă volumul efectiv de mărfuri care urmează să fie transportate din portul i în portul j, iar yij ‑ capacitatea de încărcare a vaselor care circulă din portul i in portul j date, de asemenea, sub forma unor matrici:

X =     Y =

 

atunci necunoscutele problemei sunt mărimile yij (i,j = 1, 2,..., n), adică capacitățile de încărcare a navelor ce vor fi trimise din portul i în portul j.

Funcția obiectiv f va stabili mărimea "transporturilor goale", adică mărimea tonajului neutilizat al navelor. Mărimea tonajului neutilizat pe traseul dintre portul i și portul j va fi (yij – xij), deci mărimea capacității de transport neutilizate pe toate traseele (în tone kilometri) va reprezenta:

 

f =

 

Problema examinată constă în a găsi minimul acestei funcții

Condițiile auxiliare pe care trebuie să le satisfacă necunoscutele yij pot fi notate sub forma următoarelor ecuații:

 

Primele n ecuații arată că tonajul total al navelor trimise dintr‑un port oarecare i în toate celelalte porturi trebuie să fie egal cu wi iar ultimele n că tonajul total al navelor sosite într‑un port oarecare j din toate celelalte porturi trebuie să fie egală cu pj.

Trebuie menționat că ‑ întocmai ca în problema de transport ‑ dintre cele n + n ecuații de echilibru, numai (2n ‑ 1) ecuații sunt independente. Aceasta se explică prin faptul că , adică tonajul total al navelor care pleacă din toate porturile este egal cu tonajul total al navelor care sosesc în toate porturile. Întrucât problema are (n2 – n) necunoscute yjj (i,j = l, 2,...,n), dar există 2n – 1 ecuații de echilibru independente, numărul gradelor de libertate (numărul variabilelor secundare) va fi (n2 – n) – (2n – 1) = n2 – 3n + 1.

În afară de relațiile de echilibru există și condițiile de nenegativitate:

 

yij ³ xij ³ 0

 

condiția yij ³ xij înseamnă că tonajul vaselor care pleacă din portul i spre portul j trebuie să fie mai mare sau egal cu cantitatea de mărfuri care urmează a fi transportată pe acest traseu."

Aceasta este formularea matematică a modelului lui Koopmans. Din această formulare se vede că modelul lui Koopmans este o problemă de programare liniară, deoarece atât funcția obiectiv, cât și ecuațiile de echilibru sunt relații liniare în raport cu necunoscutele yij. Această problemă poate fi ușor transformată într-un model de programare neliniară dacă, de pildă, în locul distanței sij între porturi, introducem cheltuielile de transport cu mențiunea că aceste cheltuieli nu cresc direct proporțional, ci mai lent decât distanțele. Aceasta problemă poate fi ușor înlocuită printr‑o problemă duală, luând ca funcție obiectiv rentabilitatea totală a tuturor transporturilor pe plan mondial. În acest caz, problema de minimizare a tonajului neutilizat al navelor ar fi înlocuită printr-o problemă de maximizare a rentabilității totale a transporturilor.