Programarea liniara - problema clasica de transport

Problema clasica 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 anumit numar de puncte, numite surse, trebuie transportata o cantitate dintr-o anumita substanta, intr-un alt numar de puncte, numite destinatii. Situatia extrem de generala de mai sus poate fi apoi 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, limite minime si/sau maxime pentru cantitatea transportata pe fiecare ruta, timpul necesar transportului), scopurile urmarite etc. Din aceasta cauza exista o multitudine de probleme care implica retele de transport, dintre acestea putand aminti:

Problema clasica de transport

Problema transferului

Problema drumului de cost minim

Problema fluxului maxim

Problema fluxului maxim de cost minim

Probleme de flux dinamic

Problema cuplajului maxim

Problema de afectare

Problema de ordonantare

Problema comis voiajorului

Problema arborelui de cost minim

In continuare o vom detalia pe prima dintre acestea.

Caracteristicile unei probleme de transport clasice sunt:

fiecare sursa aprovizioneaza cel putin o destinatie si fiecare destinatie este aprovizionata de la cel putin o sursa;

pot exista perechi sursa-destinatie intre care nu se poate face transfer (rute blocate);

nu exista limitari in ceea ce priveste cantitatea transportata pe fiecare ruta;

se cunosc cantitatile disponibile in fiecare sursa si cantitatile necesare in fiecare destinatie;

fiecarei rute i s-a asociat un cost care nu depinde de sensul de parcurgere.

Scopul problemei este gasirea acelor cantitati care trebuie transportate pe fiecare ruta astfel incat sa se asigure necesarul fiecarei destinatii, in limitele cantitatilor aflate la surse, cu costul minim posibil.

Datele problemei sunt:

m = numarul de surse (furnizori);

n = numarul de destinatari (consumatori);

= cantitatile disponibile in fiecare sursa;

= cantitatile necesare la fiecare sursa;

= costurile unitare pe fiecare ruta (costul transportarii unei unitati de masura de la sursa i la destinatia j).

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

Daca notam cu x_ij cantitatea care va fi transportata de la sursa i la destinatia j atunci avem de rezolvat problema:

care este un caz particular de problema de programare liniara.

Intr-o prima analiza, se observa imediat ca problema nu are solutii admisibile daca disponibilul total este mai mic decat cererea totala. Matematic, afirmatia de mai sus este justificata prin relatiile obtinute prin adunarea primelor m restrictii si apoi a ultimelor n:

disponibil total = = cerere totala

De asemenea, conditia ca este si suficienta, deoarece, in acest caz, se verifica usor ca solutia este solutie admisibila.

In alta ordine de idei, chiar daca disponibilul total este mai mare decat cererea totala, este clar ca se va transporta doar necesarul, deoarece transportarea unei cantitati mai mari decat necesarul va duce la un cost suplimentar, in contrast cu scopul urmarit. Matematic, unei solutii in care una din ultimele n restrictii ar fi verificata strict, ii corespunde o solutie in care am scazut cantitatea suplimentara din valorile variabilelor implicate in restrictie, care este de asemenea admisibila (aceste variabile nu apar in alte restrictii dintre ultimele n, iar primele m vor fi cu atat mai mult verificate daca x_ij scad) si care este evident mai buna, dand un cost mai mic.

In concluzie, daca exista solutie optima, se va transporta exact cantitatea ceruta.

Totusi, in practica se poate intalni oricare din cele trei cazuri:

In primul caz, problema are solutie optima, iar cantitatea in exces fata de cerere va ramane la furnizori, fiind reprezentata de variabilele de abatere din primele m restrictii. Aceste cantitati pot fi privite ca niste cereri ale unui consumator fictiv si tinand cont ca, de fapt, aceste cantitati nu sunt transportate nicaieri, costurile unitare pe rutele care ar lega furnizorii de acest consumator sunt 0. Adaugand acest consumator la tabel, cu cererea egala cu , vom obtine o problema de tipul (3).

Analog, in al treilea caz, chiar daca disponibilul este mai mic decat necesarul, nu inseamna ca nu se va mai transporta nimic, ci doar ca unora dintre consumatori nu li se va satisface toata cererea. Aceasta cerere nesatisfacuta poate fi privita ca disponibilul unui furnizor fictiv si tinand cont ca, de fapt, aceasta cantitate nu exista, costurile unitare pe rutele care ar lega consumatorii de acest furnizor sunt 0. Adaugand acest furnizor la tabel, cu disponibilul egal cu , vom obtine o problema de tipul (3).

In concluzie, orice problema poate fi transformata intr-o problema de tipul (3). Desi acest caz este foarte rar in practica, el este cel mai simplu din punct de vedere matematic si va fi ales pentru formalizarea problemei. O astfel de problema se numeste problema de transport echilibrata.

De asemenea, este usor de vazut ca, pentru o problema de transport echilibrata, toate solutiile admisibile verifica toate restrictiile cu egal. Astfel, daca macar una din primele m restrictii ar fi verificata cu '<' atunci am avea prin insumare:

, in contradictie cu

iar daca macar una din ultimele n restrictii ar fi verificata cu '>' atunci am avea prin insumare:

, in contradictie cu

In concluzie, orice problema de transport este echivalenta cu o problema de forma:

unde 

care este forma standard a problemei de transport.

Rezolvarea problemei de transport

Este evident ca problema de transport la forma standard este o problema de programare liniara la forma standard, dar, la fel de evident este si faptul ca este o problema de programare care devine foarte repede uriasa (un exemplu practic obisnuit cu, de exemplu, 50 de furnizori si 50 consumatori, va duce la un tabel simplex de 100 2500, si sunt cazuri si cu mii de furnizori si consumatori), motiv pentru care algoritmul simplex sub forma clasica nu este aplicabil. Cum s-a vazut insa, exista si metode prin care se poate reduce mult volumul de calcule (vezi algoritmul simplex revizuit). In plus, datele problemei de transport au o structura cu totul deosebita, in matricea A a sistemului, toate componentele fiind 1 sau 0, din care 0 sunt mult mai multi. Din acest motiv este natural sa cautam un algoritm special pentru problema de transport care sa se foloseasca la maximum caracteristicile acesteia.

Pentru ilustrarea celor de mai vom scrie matricea A desfasurat:

m ori

n coloane

n coloane

n linii

m linii

	n coloane

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

= 2% componente egale cu 1

Observand ca suma primelor m linii minus suma ultimelor n este 0, rezulta ca liniile matricii sunt liniar dependente, deci rangul lui A este mai mic decat m + n. Se poate gasi insa un minor de dimensiune m + n - 1 cu determinantul diferit de 0 (cititorul il poate gasi singur), deci o baza a unei probleme de transport are dimensiunea m+n-1 si o solutie de baza are cel mult m+n-1 componente diferite de 0 (o solutie nedegenerata are deci m+n-1 componente diferite de 0). Preferarea solutiilor nedegenerate se face din acelasi motiv ca si la algoritmul simplex si anume evitarea ciclarii (la problema de transport este mult mai important acest aspect deoarece solutiile de baza ale acesteia sunt, in general, puternic degenerate).

Inainte de a da algoritmul pentru rezolvarea problemei de transport, trebuie remarcat ca intr-o problema de transport nu poate aparea decat varianta de optim finit, existand intotdeauna solutii admisibile (asa cum s-a demonstrat mai sus) iar minimul -¥ nu este posibil, tinand cont ca avem de minimizat o functie liniara cu toti coeficientii pozitivi pe o multime de solutii cu toate componentele pozitive.

Ca si in algoritmul simplex, rezolvarea problemei de transport se face in doua etape:

Etapa 1. Gasirea unei solutii initiale de baza

Deoarece fiecare variabila corespunde unei rute (este cantitatea transportata pe aceasta ruta) iar fiecare ruta corespunde unei perechi furnizor-consumator, vom identifica fiecare variabila x_ij cu ruta (i,j). A gasi o solutie de baza nedegenerata este echivalent cu a gasi cel mult m+n-1 rute, din cele m·n posibile, pe care sa transportam toata cantitatea disponibila. Rutele vor fi organizate intr-un tabel asemanator celui in care sunt organizate datele problemei, fiecarei rute corespunzandu-i o casuta (i,j):

ruta (i,j)   Destinatii Surse	C1	C2	¼	Cj	¼	Cn
F1							A1
F2							A2
Fi							Ai
Fm							Am
	B1	B2	¼	Bj	¼	Bm	disponibil necesar

Spre deosebire de algoritmul simplex, gasirea unei solutii initiale de baza nu este dificila. De fapt, este atat de usor de gasit o astfel de solutie, incat exista o multitudine de metode in acest scop, care incearca nu numai gasirea acesteia, ci chiar gasirea uneia cat mai buna. Vom expune dintre acestea:

Metoda nord - vest;

Metoda minimului pe linii;

Metoda minimului pe coloane;

Metoda costului minim;

Metoda diferentelor maxime;

Cu toate ca sunt foarte multe, toate metodele urmeaza o schema comuna:

Pasul 1.    Se alege o ruta initiala dupa o anumita regula. Aceasta regula difera in functie de metoda folosita, fiind:

Pasul 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. Se transporta in acest fel pentru ca sa se foloseasca cat mai putine rute si deci sa se obtina o solutie de baza.

Pasul 3.    Dupa folosirea unei rute este clar ca fie se epuizeaza disponibilul furnizorului corespun­zator, 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 hasurarea acestora.

Pasul 4.    Se  alege urmatoarea ruta, folosind regula:

Metoda nord - vest;		cea mai apropiata ruta de ultima aleasa dintre cele neblocate inca;
Metoda minimului pe linii		ruta de cost minim de pe prima linie pe care mai sunt inca rute neblocate (daca minimul pe aceasta 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 pe aceasta 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); Document online: Contabilitate - intrebari Document online: Caracterizarea economico-organizatorica a s.c. tomtom srl s.r.l.
Metoda diferentelor maxime		se repeta procedeul de la pasul 1 pentru rutele neblocate inca.

Pasul 5.    Se reia algoritmul de la pasul 2 pana cand nu mai ramane nici o ruta nefolosita sau neblocata.

Se observa ca, daca prima metoda este pur geometrica, netinand cont de costurile rutelor, toate celelalte incearca sa micsoreze cat mai mult costul intregului transport. Cu toate ca, statistic vorbind, ultima metoda este cea mai buna, ea dand de foarte multe ori chiar solutia optima, totusi si existenta celorlalte metode este justificata de faptul ca sunt mai simplu de aplicat si exista cazuri in care fiecare da solutia cea mai buna.

Etapa 2. Gasirea solutiei optime

Algoritmul care urmeaza reprezinta algoritmul simplex pentru o problema de minim, aplicat in cazul particular al problemei de transport.

Pasul 1.  Se asociaza fiecarui furnizor F_i o variabila u_i si fiecarui consumator C_j o variabila v_j;

Pasul 2.  Fiecarei rute (i,j) folosita in solutia actuala i se asociaza ecuatia u_i + v_j = c_ij, rezultand un sistem cu m + n necunoscute (m de u_i si n de v_j) si m + n - 1 ecuatii (egal cu rangul matricii A);

Pasul 3.  Se gaseste o solutie particulara a acestui sistem, egaland una din necunoscute cu 0 (pe cea care apare de cele mai multe ori);

Pasul 4.  Se calculeaza toti D_ij = u_i + v_j - c_ij pentru toate rutele care nu fac parte din solutie (ceilalti sunt 0, tinand cont de felul cum au fost gasiti u_i, i = 1,,m si v_j, j = 1,,n)

Pasul 5.  Se analizeaza D_ij gasiti.

daca toti sunt mai mici sau egali cu 0 solutia gasita este optima STOP

daca exista D_ij strict pozitivi atunci solutia actuala nu este optima si ruta corespunzatoare lui D_ij maxim va fi cea care intra in baza (daca maximul este multiplu se ia una la intamplare)

Pasul 6.        Se construieste un circuit, pornind din aceasta ruta, trecand doar prin rutele solutiei, mergand doar pe verticala sau orizontala si fiecare trecere de la o ruta la alta facandu-se doar perpendicular pe trecerea anterioara. S-a demonstrat ca exista un singur circuit cu aceste proprietati si se poate demonstra usor ca trece printr-un numar par de rute.

Pasul 7.        Incepand cu + din ruta care va intra in baza se noteaza alternativ cu '+' si '-' rutele circuitului;

Pasul 8.        Se noteaza cu q minimul dintre cantitatile transportate pe rutele notate cu '-' si ruta pentru care s-a obtinut acest minim este cea care va iesi din baza (cazul minimului multiplu va fi analizat dupa expunerea algoritmului);

Pasul 9.        Se scade q din cantitatile transportate pe rutele notate cu '-' si se adauga la cele notate cu '+', rutele care nu sunt pe circuit pastrandu-si valoarea;

Pasul 10.    Se reia algoritmul de la pasul 2

Asa cum s-a vazut mai sus, se poate ca la pasul 8 minimul q sa fie multiplu. Atunci, pe toate rutele pe care se transporta q nu se va mai transporta nimic, adica vor disparea din solutie. Cum in solutie a intrat doar o singura ruta rezulta ca noua solutie este degenerata. Cum existenta acestui tip de solutii poate duce la ciclarea algoritmului, au fost imaginate mai multe metode de evitare, toate bazandu-se pe modificarea datelor initiale, in asa fel incat, pe parcursul algoritmului, sa nu mai avem nici o solutie degenerata. Aceasta modificare (perturbare) poate fi facuta chiar de la inceputul rezolvarii, incat problema sa nu mai aiba nici o solutie degenerata, fie doar atunci cand apare o solutie degenerata, eliminand perturbatia imediat ce nu mai e necesara. Pentru a vedea cum trebuie sa arate o astfel de modificare, dam urmatoarea teorema care caracterizeaza existenta solutiilor degenerate:

Teorema. O problema de transport are solutii degenerate daca si numai daca exista o submultime stricta si nevida a furnizorilor si o submultime stricta si nevida a consumatorilor astfel incat suma disponibilurilor furnizorilor din prima submultime este egala cu suma cererilor consumatorilor din a doua.

Lema. Solutia este degenerata de k ori daca si numai daca multimea furnizorilor si a consumatorilor se pot partitiona in k submultimi F F F_k si W W ,, W_k astfel incat consumatorii din fiecare clasa W_i se aprovizioneaza numai de la furnizorii din clasa F_i

In concluzie, daca vrem sa dispara toate solutiile degenerate, trebuie modificate disponibilurile si cererile in asa fel incat sa nu mai poata exista varianta din teorema. Una din metodele posibile este sa adaugam la fiecare furnizor F_i cantitatea eⁱ si sa introducem un consumator fictiv cu cererea egala cu e e + e^m, unde e este o valoare foarte mica (oricat de mica este necesar). O alta varianta este sa adaugam la fiecare furnizor F_i cantitatea i e si sa introducem un consumator fictiv cu cererea egala cu e e + m e, unde e este de asemenea o valoare foarte mica (oricat de mica este necesar). Se pot gasi, evident, si altele variante.

Aceasta metoda este foarte buna in cazul rularii problemei pe calculator, dar, in cazul rezolvarii cu creionul pe hartie, este, evident, greoaie.

In acest caz vom folosi varianta in care introducem perturbatia doar cand este nevoie (adica cand apare o solutie degenerata). Aceasta situatie poate aparea fie chiar la solutia initiala, in urma aplicarii uneia din metodele de gasire ale unei solutii initiale, fie la pasul 8 din a doua etapa daca q se obtine pentru mai multe rute. Ramane de vazut doar cum trebuie facuta aceasta perturbare.

Conform teoremei de mai sus rezulta ca multimea furnizorilor si a consumatorilor se pot partitiona in k submultimi F F F_k si W W ,, W_k astfel incat consumatorii unei clase W_i se aprovizioneaza numai de la furnizorii din clasa F_i si reciproc. Pentru fiecare indice i £ k-1 vom alege o ruta care corespunde unui furnizor din F_i si unui consumator din W_i+1 si vom adauga la furnizorul si consumatorul corespunzatori acesteia cantitatea eⁱ (sau valoarea e_i intr-o ordine data a valorilor). Daca, la un moment dat, prin anularea unui parametru introdus, solutia ramane nedegenerata, acesta va fi anulat.

Exemplu Presupunem ca in rezolvarea problemei:

s-a ajuns la solutia de baza:

care este dublu degenerata. Aceasta inseamna ca multimea furnizorilor si consumatorilor pot fi partitionate fiecare in trei grupe. Pentru a le gasi vom porni de la un furnizor, vom gasi consumatorii care se aprovizioneaza de la acesta, apoi furnizorii care aprovizioneaza acesti consumatori si tot asa pana vom gasi prima grupa din fiecare (furnizori si consumatori). Pentru cei ramasi din fiecare vom continua procedeul pana vom gasi toate grupele.

In cazul nostru pentru F₁ gasim consumatorii C₄, C₅ si C₇, pentru acestia furnizorii F₅ si F₈, pentru acestia noul consumator C₁₂ si am gasit prima grupa:

consumatorii se aprovizioneaza de la furnizorii

Apoi, pentru F₂ gasim consumatorii C₃ si C₁₀, pentru acestia furnizorul F₇, pentru acesta noul consumator C₆, pentru acesta noul furnizor F₃, pentru acesta noul consumator C₈ si am gasit a doua grupa:

consumatorii se aprovizioneaza de la furnizorii

A treia grupa va fi, evident: se aprovizioneaza de la furnizorii

Conform regulii de perturbare, vom alege o ruta corespunzatoare unui furnizor din prima grupa si unui consumator din a doua, de exemplu (5,6) si o ruta corespunzatoare unui furnizor din a doua grupa si unui consumator din a treia, de exemplu (3,9) si vom adauga la furnizorul F₅ si consumatorul C₆ cantitatea suplimentara a iar la furnizorul F₃ si consumatorul C₉ cantitatea suplimentara b, cu a < b de exemplu, obtinand problema perturbata:      

care nu mai este degenerata.

Ramane ca exercitiu verificarea faptului daca aceasta solutie este optima si daca nu, sa se gaseasca solutia de baza succesoare.

Variante ale problemei de transport

Exista o gama foarte larga de fenomene economice care pot fi reprezentate prin modele de programare liniara de tip transport sau foarte asemanatoare cu acestea. Prezentam in continuare cateva dintre acestea

1. Cu rute blocate

In anumite cazuri pot exista situatii in care anumite rute intre furnizori si consumatori nu pot fi folosite, cel putin temporar. Rezolvarea acestor probleme se face cu un model de transport obisnuit, in care rutelor interzise li se asociaza costuri unitare de transport foarte mari in raport cu costurile rutelor utilizabile. Prin aceste costuri de penalizare foarte mari, algoritmul de optimizare este 'constrans' sa ocoleasca rutele interzise.

2. Cu puncte intermediare

Exista situatii in 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 populatiei sunt mai intai colectate in mari depo­zite si apoi distribuite centrelor de desfacere. Problema de optimizare costa in minimizarea cheltuielilor de transport de la furnizori la centrele intermediare la care se adauga costul transportului­ de la aceste centre la consumatorii finali.

In anumite conditii aceasta problema este echivalenta cu doua probleme de transport obisnuite.

3. Problema afectarii

Exista probleme de programare operativa care pot fi reprezentate prin modele liniare de tipul problemei de transport. Un exemplu des intalnit este urmatoarea problema concreta de pro­gramare operativa a productiei:

'Un numar de lucrari L_l, L₂,, L_n trebuiesc executate cat mai repede. Acestea sunt efectuate de persoanele (muncitorii) M_l, M₂,, M_n, fiecare putand executa oricare din lucrarile date. Cunoscand timpul t_ij de executie al lucrarii L_i de catre muncitorul M_j, scopul optimizarii este gasirea acelui mod de repartizare a lucrarilor pe muncitori astfel incat timpul total de executie al lucrarilor sa fie minim'

Pentru modelarea matematica a acestei probleme, cunoscuta in literatura de specialitate sub numele de 'problema afectarii', se introduc variabilele bivalente:

x_ij =

Conditiile ca fiecare lucrare sa fie repartizata unui muncitor precum si conditia ca fiecare muncitor sa primeasca o lucrare se traduc prin restrictiile:

in care variabilele x_ij satisfac cerinta speciala:

x_ij I

Obiectivul urmarit - minimizarea timpului total de executie - conduce la urmatoarea functie obiectiv:

(min) f =

Modelul rezultat difera de modelul problemei de transport echilibrate prin conditia impusa variabilelor de a fi doar 0 sau 1 (variabile bivalente). Totusi rezolvarea sa se poate face cu algoritmul de la problema de transport, insa ea este greoaie, datorita faptului ca solutiile de baza ale acestei probleme sunt puternic degenerate. Exista metode mai eficiente de abordare a problemei afectarii, bazate pe teoria grafurilor.

4. Problema incarcarii utilajelor

Facand parte din acelasi cadru al programarii operative a productiei, problema incarcarii utilajelor (punctelor de lucru) ocupa a pozitie centrala. Aceasta problema poate fi formulata astfel:

'Intr‑o sectie a unei unitati economice se produc reper­ele (bunurile) P₁, P₂, , P_n care pot fi realizate pe oricare din utilajele (grupele de utilaje) U_l,U₂,,U_m. Se cunosc urmatoarele date:

cantitatile N₁, N₂,,N_n din reperele date, care trebuie produse intr‑o anumita perioada;

fondurile de timp disponibil F₁, F₂,,F_m ale utilaje­lor, in  perioada respectiva;

cantitatea P_ij din reperul P_j ce poate fi produsa pe utilajul U_i intr‑o anumita perioada de timp;

costul c_ij al realizarii unei unitati specifice din reperul P_j pe utilajul U­_i.

Se doreste gasirea acelui mod de repartizare a sarcinilor de productie pe utilaje astfel incat costul realizarii cantitatilor planificate sa fie minim.'

Modelul matematic asociat acestei probleme este:

unde x_ij reprezinta cantitatea de repere P_j ce urmeaza a fi realizata pe utilajul U_i. Modelul este asemanator modelului problemei de transport, pentru rezolvare putandu-se folosi algoritmul de la problema clasica de transport, cu unele modificari dictate de prezenta 'ponderilor' P_ij.

5. Problema de transport a lui Koopmans

Aceasta problema este, istoriceste vorbind, anterioara problemei clasice de transport si de ea s-a ocupat pentru prima oara T. C. Koopmans.

Problema se refera la la transportul materialelor de razboi, efectuate in perioada celui de‑al doilea razboi mondial, din S.U.A. in Anglia si retur. Intrucat cantitatile de produse transportate in cele doua sensuri erau diferite, navele circulau de multe ori goale sau incomplet incarcate. Avand in vedere si faptul ca transporturile pe mare ale aliatilor se aflau sub amenintarea submarinelor si a aviatiei germane se punea problema asigurarii unei asemenea utilizari a mijloacelor de transport incat sa se reduca la minimum capacitatea de transport neutilizata (masurata in tone-kilometri) si, implicit, sa se reduca pierderile de nave.

Desi problema de transport a lui Koopmans a avut un caracter tactico‑militar, ea poate fi considerata ‑ dupa cum a facut mai tarziu insusi Koopmans ‑ si ca o problema economica. Economic vorbind, reducerea capacitatii de transport neutilizate a navelor mareste rentabilitatea transporturilor maritime. Fireste ca am putea aplica o solutie optima a acestei probleme pe plan mondial numai in cazul in care ar exista o forma oarecare de administrate interntionala a navelor si de dirijare a transporturilor maritime. Totusi, se poate vedea ca modelul lui Koopmans poate sa‑si gaseasca aplicarea nu numai la transportul maritim, ci si in transportul feroviar, in cel auto, precum si in alte domenii similare.

Matematic, aceasta problema se poate formula astfel:

'Fie n porturi din care se expediaza si in care sosesc incarcaturi. Notam cu w_i un volum dat de marfuri expediate (exprimate, de pilda, in tone), iar cu p_i ‑ un volum dat de marfuri care se aduc in decursul unei anumite perioade in portul i (i = 1, 2,, n). Se cunosc distantele s_ij dintre porturi (exprimate, de pilda, in kilometri), acestea fiind date in matricea:

S =

Daca x_ij reprezinta volumul efectiv de marfuri care urmeaza sa fie transportate din portul i in portul j, iar y_ij ‑ capacitatea de incarcare a vaselor care circula din portul i in portul j date, de asemenea, sub forma unor matrici:

X =     Y =

atunci necunoscutele problemei sunt marimile y_ij (i,j = 1, 2,, n), adica capacitatile de incarcare a navelor ce vor fi trimise din portul i in portul j.

Functia obiectiv f va stabili marimea 'transporturilor goale', adica marimea tonajului neutilizat al navelor. Marimea tonajului neutilizat pe traseul dintre portul i si portul j va fi (y_ij - x_ij), deci marimea capacitatii de transport neutilizate pe toate traseele (in tone kilometri) va reprezenta:

f =

Problema examinata consta in a gasi minimul acestei functii

Conditiile auxiliare pe care trebuie sa le satisfaca necunoscutele y_ij pot fi notate sub forma urmatoarelor ecuatii:

Primele n ecuatii arata ca tonajul total al navelor trimise dintr‑un port oarecare i in toate celelalte porturi trebuie sa fie egal cu w_i iar ultimele n ca tonajul total al navelor sosite intr‑un port oarecare j din toate celelalte porturi trebuie sa fie egala cu p_j.

Trebuie mentionat ca ‑ intocmai ca in problema de transport ‑ dintre cele n + n ecuatii de echilibru, numai (2n ‑ 1) ecuatii sunt independente. Aceasta se explica prin faptul ca , adica tonajul total al navelor care pleaca din toate porturile este egal cu tonajul total al navelor care sosesc in toate porturile. Intrucat problema are (n² - n) necunoscute y_jj (i,j = l, 2,,n), dar exista 2n - 1 ecuatii de echilibru independente, numarul gradelor de libertate (numarul variabilelor secundare) va fi (n² - n) - (2n - 1) = n² - 3n + 1.

In afara de relatiile de echilibru exista si conditiile de nenegativitate:

y_ij ³ x_ij ³

conditia y_ij ³ x_ij inseamna ca tonajul vaselor care pleaca din portul i spre portul j trebuie sa fie mai mare sau egal cu cantitatea de marfuri care urmeaza a fi transportata pe acest traseu.'

Aceasta este formularea matematica a modelului lui Koopmans. Din aceasta formulare se vede ca modelul lui Koopmans este o problema de programare liniara, deoarece atat functia obiectiv, cat si ecuatiile de echilibru sunt relatii liniare in raport cu necunoscutele y_ij. Aceasta problema poate fi usor transformata intr-un model de programare neliniara daca, de pilda, in locul distantei s_ij intre porturi, introducem cheltuielile de transport cu mentiunea ca aceste cheltuieli nu cresc direct proportional, ci mai lent decat distantele. Aceasta problema poate fi usor inlocuita printr‑o problema duala, luand ca functie obiectiv rentabilitatea totala a tuturor transporturilor pe plan mondial. In acest caz, problema de minimizare a tonajului neutilizat al navelor ar fi inlocuita printr-o problema de maximizare a rentabilitatii totale a transporturilor.