Programarea liniar

PROBLEMA CLASIC DE TRANSPORT

Problema clasic de transport face parte din clasa mult mai larg a problemelor modelate prin reele de transport. O reea de transport modeleaz o situaie economic n care, dintr-unanumit numr de puncte, numite surse, trebuie transportat o cantitate dintr-o anumit substan,ntr-un alt numr de puncte, numite destinaii. Situaia extrem de general de mai sus poate fi apoiconcretizat ntr-un numr deosebit de mare de moduri, specificnd dac exist sau nu puncte intermediare ntre surse i destinaii, 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 urmrite etc. Din aceast cauz exist o multitudine deprobleme care implic reele de transport, dintre acestea putnd aminti:

1. Problema clasic de transport 2. Problema transferului 3. Problema drumului de cost minim4. Problema fluxului maxim5. Problema fluxului maxim de cost minim6. Probleme de flux dinamic7. Problema cuplajului maxim8. Problema de afectare 9. Problema de ordonanare10. 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 puin o destinaie i fiecare destinaie este aprovizionat dela cel puin o surs;

2. pot exista perechi surs-destinaie ntre care nu se poate face transfer (rute blocate); 3. nu exist limitri n ceea ce privete cantitatea transportat pe fiecare rut;4. se cunosc cantitile disponibile n fiecare surs i cantitile necesare n fiecare destinaie;5. fiecrei rute i s-a asociat un cost care nu depinde de sensul de parcurgere. Scopul problemei este gsirea acelor cantiti care trebuie transportate pe fiecare rut astfel

nct s se asigure necesarul fiecrei destinaii, n limitele cantitilor aflate la surse, cu costulminim posibil.

Datele problemei sunt:

1. m = numrul de surse (furnizori); 2. n = numrul de destinatari (consumatori);3. {Ai, i = 1,...,m} = cantitile disponibile n fiecare surs;4. {Bj, j = 1,...,n} = cantitile necesare la fiecare surs;5. {cij, i = 1,...,m; j = 1,...,n} = costurile unitare pe fiecare rut (costul transportrii unei

uniti de msur de la sursa i la destinaia j). Acestea au fost organizate ntr-un tabel ca cel de mai jos:

92

Bazele cercetrii operaionale

DestinaiiSurse

C1 C2 } CnF1 c11 c12 } c1n A1F2 c21 c22 } c2n A2

Fm cm1 cm2 } cmn AmB1 B2 } Bm disponibilnecesar

Dac notm cu xij cantitatea care va fi transportat de la sursa i la destinaia j atunci avem de rezolvat problema:

t

t

d

n1,...,jm;1,...,i0x

n1,...,jBx

m1,...,iAx

xcmin

ij

j

m

1i

ij

i

n

1j

ij

m

1i

n

1j

ijijf

care este un caz particular de problem de programare liniar.ntr-o prim analiz, se observ imediat c problema nu are soluii admisibile dac

disponibilul total este mai mic dect cererea total. Matematic, afirmaia de mai sus este justificatprin relaiile obinute prin adunarea primelor m restricii i apoi a ultimelor n:

disponibil total = = cerere total

ttm

1i

n

1j

j

n

1j

ij

m

1i

i BxA

De asemenea, condiia ca este i suficient, deoarece, n acest caz, se

verific uor c soluia

tn

1j

j

m

1i

i BA

m

1i

i

iij

A

BAx

j este soluie admisibil.

n alt ordine de idei, chiar dac disponibilul total este mai mare dect cererea total, este clar c se va transporta doar necesarul, deoarece transportarea unei cantiti mai mari dect necesarul va duce la un cost suplimentar, n contrast cu scopul urmrit. Matematic, unei soluii n care una din ultimele n restricii ar fi verificat strict, i corespunde o soluie n care am sczutcantitatea suplimentar din valorile variabilelor implicate n restricie, care este de asemeneaadmisibil (aceste variabile nu apar n alte restricii dintre ultimele n, iar primele m vor fi cu att mai mult verificate dac xij scad) i care este evident mai bun, dnd un cost mai mic.

n concluzie, dac exist soluie optim, se va transport exact cantitatea cerut.Totui, n practic se poate ntlni oricare din cele trei cazuri:(1)

!

n

1j

j

m

1i

i BA

93

Programarea liniar

(2)

n

1j

j

m

1i

i BA

(3)

n

1j

j

m

1i

i BA

n primul caz, problema are soluie optim, iar cantitatea n exces fa de cerere va rmne lafurnizori, fiind reprezentat de variabilele de abatere din primele m restricii. Aceste cantiti pot fiprivite ca nite cereri ale unui consumator fictiv i innd cont c, de fapt, aceste cantiti nu sunt transportate nicieri, costurile unitare pe rutele care ar lega furnizorii de acest consumator sunt 0. Adugnd acest consumator la tabel, cu cererea egal cu , vom obine o problemde tipul (3).

n

1j

j

m

1i

i BA

Analog, n al treilea caz, chiar dac disponibilul este mai mic dect necesarul, nu nseamnc nu se va mai transporta nimic, ci doar c unora dintre consumatori nu li se va satisface toatcererea. Aceast cerere nesatisfcut poate fi privit ca disponibilul unui furnizor fictiv i inndcont c, de fapt, aceast cantitate nu exist, costurile unitare pe rutele care ar lega consumatorii de acest furnizor sunt 0. Adugnd acest furnizor la tabel, cu disponibilul egal cu , vomobine o problem de tipul (3).

m

1i

i

n

1j

j AB

n concluzie, orice problem poate fi transformat ntr-o problem de tipul (3). Dei acestcaz este foarte rar n practic, el este cel mai simplu din punct de vedere matematic i va fi alespentru formalizarea problemei. O astfel de problem se numete problem de transport echilibrat.

De asemenea, este uor de vzut c, pentru o problem de transport echilibrat, toate soluiile admisibile verific toate restriciile cu egal. Astfel, dac mcar una din primele m restriciiar fi verificat cu "" atunci am avea prin nsumare:

!tm

1i

n

1j

j

n

1j

ij

m

1i

i BxA , n contradicie cu

n

1j

j

m

1i

i BA

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

t

n1,...,jm;1,...,i0x

n1,...,jBx

m1,...,iAx

xcmin

ij

j

m

1i

ij

i

n

1j

ij

m

1i

n

1j

ijijf

unde

n

1j

j

m

1i

i BA

care este forma standard a problemei de transport.

94

Bazele cercetrii operaionaleRezolvarea problemei de transport

Este evident c problema de transport la forma standard este o problem de programareliniar 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 obinuit cu, de exemplu, 50 de furnizori i 50 consumatori, va duce la un tabel simplex de 100 u 2500, i sunt cazuri i cu mii de furnizori iconsumatori), motiv pentru care algoritmul simplex sub forma clasic nu este aplicabil. Cum s-a vzut ns, exist i metode prin care se poate reduce mult volumul de calcule (vezi algoritmulsimplex 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 muli. Din acestmotiv este natural s cutm un algoritm special pentru problema de transport care s se foloseascla maximum caracteristicile acesteia.

Pentru ilustrarea celor de mai vom scrie matricea A desfurat:

1000

010000100001

1000

010000100001

1000

010000100001

1111

00000000

0000

11110000

0000

00001111

m linii

n linii

n coloane n coloane n coloane

m ori

Aceast matrice are m + n linii, mn 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:

1005050505050502

= 2% componente egale cu 1

Observnd c suma primelor m linii minus suma ultimelor n este 0, rezult c liniile matriciisunt liniar dependente, deci rangul lui A este mai mic dect m + n. Se poate gsi ns un minor de dimensiune m + n 1 cu determinantul diferit de 0 (cititorul l poate gsi singur), deci o baz a uneiprobleme de transport are dimensiunea m+n1 i o soluie de baz are cel mult m+n1 componentediferite de 0 (o soluie nedegenerat are deci m+n1 componente diferite de 0). Preferarea soluiilor nedegenerate se face din acelai motiv ca i la algoritmul simplex i anume evitarea ciclrii (la problema de transport este mult mai important acest aspect deoarece soluiile de baz aleacesteia 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 aprea dect varianta de optim finit, existnd ntotdeauna soluiiadmisibile (aa cum s-a demonstrat mai sus) iar minimul f nu este posibil, innd cont c avem de minimizat o funcie liniar cu toi coeficienii pozitivi pe o mulime de soluii cu toate componentele pozitive.

Ca i n algoritmul simplex, rezolvarea problemei de transport se face n dou etape: Etapa 1. Gsirea unei soluii iniiale de bazDeoarece fiecare variabil corespunde unei rute (este cantitatea transportat pe aceast rut)

iar fiecare rut corespunde unei perechi furnizor-consumator, vom identifica fiecare variabil xij cu95

Programarea liniarruta (i,j). A gsi o soluie de baz nedegenerat este echivalent cu a gsi cel mult m+n1 rute, dincele mn posibile, pe care s transportm toat cantitatea disponibil. Rutele vor fi organizate ntr-un tabel asemntor celui n care sunt organizate datele problemei, fiecrei rute corespunzndu-i o csu (i,j):

DestinaiiSurse

C1 C2 } Cj } CnF1 A1F2 A2 Fi Ai

Fm Am

B1 B2 } Bj } Bm disponibilnecesar

ruta (i,j)

Spre deosebire de algoritmul simplex, gsirea unei soluii iniiale de baz nu este dificil. De fapt, este att de uor de gsit o astfel de soluie, nct exist o multitudine de metode n acest scop,care ncearc nu numai gsirea acesteia, ci chiar gsirea uneia ct 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 diferenelor maxime;Cu toate c sunt foarte multe, toate metodele urmeaz o schem comun:

Pasul 1. Se alege o rut iniial dup o anumit regul. Aceast regul difer n funcie de metodafolosit, fiind:

Metoda nord vest; ruta din colul stnga sus al tabeluluiMetoda minimului pe linii ruta de cost minim de pe prima linie (dac

minimul este multiplu se ia prima din stnga) 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 ntmplare)Metoda diferenelor maxime 1. Pentru fiecare linie i fiecare coloan se

calculeaz diferena dintre cele mai mici doucosturi ale rutelor acesteia (diferena poate fi i 0 dac minimul este multiplu) i se gsetemaximul dintre aceste diferene;

2. Dintre toate rutele de pe liniile i coloanelecorespunztoare acestui maxim se alege ruta de cost minim (dac minimul este multiplu seia una la ntmplare)

96

Pasul 2. Se transport pe aceast rut maximul posibil. Acest maxim este egal cu minimul dintre cantitatea care mai e disponibil la furnizorul corespunztor acestei rute i cantitatea caremai e necesar la consumatorul corespunztor rutei, n momentul alegerii acestei rute. Se

Bazele cercetrii operaionaletransport n acest fel pentru ca s se foloseasc ct mai puine rute i deci s se obin o soluie de baz.

Pasul 3. Dup folosirea unei rute este clar c fie se epuizeaz disponibilul furnizorului corespun-ztor, fie se asigur ntregul necesar al consumatorului corespunztor, 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 rutspre 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 evideniaz n tabel prin haurarea acestora.

Pasul 4. Se alege urmtoarea 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 stnga);

Metoda minimului pe coloane ruta de cost minim de pe prima coloan pe care maisunt 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 unala ntmplare);

Metoda diferenelor maxime se repet procedeul de la pasul 1 pentru ruteleneblocate nc.

Pasul 5. Se reia algoritmul de la pasul 2 pn cnd nu mai rmne nici o rut nefolosit sau neblocat.

Se observ c, dac prima metod este pur geometric, neinnd cont de costurile rutelor,toate celelalte ncearc s micoreze ct mai mult costul ntregului transport. Cu toate c, statisticvorbind, ultima metod este cea mai bun, ea dnd de foarte multe ori chiar soluia optim, totui iexistena celorlalte metode este justificat de faptul c sunt mai simplu de aplicat i exist cazuri n care fiecare d soluia cea mai bun.

Etapa 2. Gsirea soluiei optimeAlgoritmul care urmeaz reprezint algoritmul simplex pentru o problem de minim, aplicat

n cazul particular al problemei de transport.

Pasul 1. Se asociaz fiecrui furnizor Fi o variabil ui i fiecrui consumator Cj o variabil vj;Pasul 2. Fiecrei rute (i,j) folosit n soluia actual i se asociaz ecuaia ui + vj = cij, rezultnd un

sistem cu m + n necunoscute (m de ui i n de vj) i m + n 1 ecuaii (egal cu rangul matricii A);

Pasul 3. Se gsete o soluie particular a acestui sistem, egalnd una din necunoscute cu 0 (pe cea care apare de cele mai multe ori);

Pasul 4. Se calculeaz toi 'ij = ui + vj cij pentru toate rutele care nu fac parte din soluie (ceilalisunt 0, innd cont de felul cum au fost gsii ui, i = 1,...,m i vj, j = 1,...,n)

Pasul 5. Se analizeaz 'ij gsii.

97

Programarea liniar dac toi sunt mai mici sau egali cu 0 soluia gsit este optim o STOP dac exist 'ij strict pozitivi atunci soluia actual nu este optim i ruta

corespunztoare lui 'ij maxim va fi cea care intr n baz (dac maximul este multipluse ia una la ntmplare)

Pasul 6. Se construiete un circuit, pornind din aceast rut, trecnd doar prin rutele soluiei,mergnd doar pe vertical sau orizontal i fiecare trecere de la o rut la alta fcndu-sedoar perpendicular pe trecerea anterioar. S-a demonstrat c exist un singur circuit cu aceste proprieti i se poate demonstra uor c trece printr-un numr par de rute.

Pasul 7. ncepnd cu + din ruta care va intra n baz se noteaz alternativ cu "+" i "" rutelecircuitului;

Pasul 8. Se noteaz cu T minimul dintre cantitile transportate pe rutele notate cu "" i ruta pentru care s-a obinut acest minim este cea care va iei din baz (cazul minimuluimultiplu va fi analizat dup expunerea algoritmului);

Pasul 9. Se scade T din cantitile transportate pe rutele notate cu "" i se adaug la cele notatecu "+", rutele care nu sunt pe circuit pstrndu-i valoarea;

Pasul 10. Se reia algoritmul de la pasul 2

Aa cum s-a vzut mai sus, se poate ca la pasul 8 minimul T s fie multiplu. Atunci, pe toaterutele pe care se transporta T nu se va mai transporta nimic, adic vor disprea din soluie. Cum n soluie a intrat doar o singur rut rezult c noua soluie este degenerat. Cum existena acestui tip de soluii poate duce la ciclarea algoritmului, au fost imaginate mai multe metode de evitare, toatebazndu-se pe modificarea datelor iniiale, n aa fel nct, pe parcursul algoritmului, s nu maiavem nici o soluie degenerat. Aceast modificare (perturbare) poate fi fcut chiar de la nceputulrezolvrii, nct problema s nu mai aib nici o soluie degenerat, fie doar atunci cnd apare o soluie degenerat, eliminnd perturbaia imediat ce nu mai e necesar. Pentru a vedea cum trebuies arate o astfel de modificare, dm urmtoarea teorem care caracterizeaz existena soluiilordegenerate:

Teorem. O problem de transport are soluii degenerate dac i numai dac exist o submulime strict i nevid a furnizorilor i o submulime strict i nevid a consumatorilor astfelnct suma disponibilurilor furnizorilor din prima submulime este egal cu suma cererilorconsumatorilor din a doua.

Lem. Soluia este degenerat de k ori dac i numai dac mulimea furnizorilor i aconsumatorilor se pot partiiona n k submulimi )1, )2, ..., )k i :1, :2 ,..., :k astfel nctconsumatorii din fiecare clas :i se aprovizioneaz numai de la furnizorii din clasa )i.

n concluzie, dac vrem s dispar toate soluiile degenerate, trebuie modificate disponibilurile i cererile n aa fel nct s nu mai poat exista varianta din teorem. Una din metodele posibile este s adugm la fiecare furnizor Fi cantitatea Hi i s introducem un consumatorfictiv cu cererea egal cu H + H2 + ... + Hm, unde H este o valoare foarte mic (orict de mic este necesar). O alt variant este s adugm la fiecare furnizor Fi cantitatea iH i s introducem un consumator fictiv cu cererea egal cu H + 2H + ... + mH, unde H este de asemenea o valoare foarte mic (orict de mic este necesar). Se pot gsi, evident, i altele variante.

Aceast metod este foarte bun n cazul rulrii problemei pe calculator, dar, n cazulrezolvrii cu creionul pe hrtie, este, evident, greoaie.

n acest caz vom folosi varianta n care introducem perturbaia doar cnd este nevoie (adiccnd apare o soluie degenerat). Aceast situaie poate aprea fie chiar la soluia iniial, n urmaaplicrii uneia din metodele de gsire ale unei soluii iniiale, fie la pasul 8 din a doua etap dac T

98

Bazele cercetrii operaionalese obine pentru mai multe rute. Rmne de vzut doar cum trebuie fcut aceast perturbare.

Conform teoremei de mai sus rezult c mulimea furnizorilor i a consumatorilor se pot partiiona n k submulimi )1, )2, ..., )k i :1, :2 ,..., :k astfel nct consumatorii unei clase :i se aprovizioneaz numai de la furnizorii din clasa )i i reciproc. Pentru fiecare indice i d k1 vomalege o rut care corespunde unui furnizor din )i i unui consumator din :i+1 i vom aduga la furnizorul i consumatorul corespunztori acesteia cantitatea Hi (sau valoarea Hi ntr-o ordine dat a valorilor). Dac, la un moment dat, prin anularea unui parametru introdus, soluia rmnenedegenerat, 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 1000F1 3 5 6 7 5 4 3 5 5 6 3 6 700F1 2 4 5 3 6 7 4 5 7 4 6 7 400F1 3 4 2 6 8 4 6 7 4 7 8 3 900F1 3 5 6 4 7 8 3 5 6 9 3 6 400F1 2 4 6 3 7 8 9 4 6 2 4 2 400F1 3 5 2 6 7 8 9 5 3 6 7 3 700F1 9 4 5 3 6 2 7 8 9 4 7 5 400F1 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 soluia de baz:C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12

F1 200 500 200 900F2 200 500 700F3 300 500 800F4 200 800 1000F5 400 400F6 100 300 400F7 300 100 400F8 100 300 400F9 400 300 700

400 300 200 200 500 600 700 500 600 600 800 300

care este dublu degenerat. Aceasta nseamn c mulimea furnizorilor i consumatorilor pot fi partiionate fiecare n trei grupe. Pentru a le gsi vom porni de la un furnizor, vom gsiconsumatorii care se aprovizioneaz de la acesta, apoi furnizorii care aprovizioneaz aceticonsumatori i tot aa pn vom gsi prima grup din fiecare (furnizori i consumatori). Pentru cei rmai din fiecare vom continua procedeul pn vom gsi toate grupele.

n cazul nostru pentru F1 gsim consumatorii C4, C5 i C7, pentru acetia furnizorii F5 i F8,pentru acetia noul consumator C12 i am gsit prima grup:

consumatorii {C4, C5, C7, C12} se aprovizioneaz de la furnizorii {F1, F5, F8}Apoi, pentru F2 gsim consumatorii C3 i C10, pentru acetia furnizorul F7, pentru acesta

noul consumator C6, pentru acesta noul furnizor F3, pentru acesta noul consumator C8 i am gsit 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 corespunztoare unui furnizor din prima

grup i unui consumator din a doua, de exemplu (5,6) i o rut corespunztoare unui furnizor din adoua grup i unui consumator din a treia, de exemplu (3,9) i vom aduga la furnizorul F5 iconsumatorul C6 cantitatea suplimentar D iar la furnizorul F3 i consumatorul C9 cantitatea suplimentar E, cu D < E de exemplu, obinnd problema perturbat:

99

Programarea liniar

C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12F1 200 500 200 900F2 200 500 700F3 300 500 E 800+EF4 200 800 1000F5 D 400 400+DF6 100 300 400F7 300 100 400F8 100 300 400F9 400 300 700

400 300 200 200 500 600+ D

700 500 600+ E

600 800 300

care nu mai este degenerat.Rmne ca exerciiu verificarea faptului dac aceast soluie este optim i dac nu, s se

gseasc soluia de baz succesoare. Variante ale problemei de transport

Exist o gam foarte larg de fenomene economice care pot fi reprezentate prin modele deprogramare liniar de tip transport sau foarte asemntoare cu acestea. Prezentm n continuare cteva dintre acestea

1. Cu rute blocate

n anumite cazuri pot exista situaii n care anumite rute ntre furnizori i consumatori nu pot fi folosite, cel puin temporar. Rezolvarea acestor probleme se face cu un model de transportobinuit, 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 optimizareeste "constrns" s ocoleasc rutele interzise.

2. Cu puncte intermediare

Exist situaii 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 pentruconsumul populaiei sunt mai nti colectate n mari depozite i apoi distribuite centrelor dedesfacere. 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 condiii aceast problem este echivalent cu dou probleme de transport obinuite.

3. Problema afectriiExist probleme de programare operativ care pot fi reprezentate prin modele liniare de tipul

problemei de transport. Un exemplu des ntlnit este urmtoarea problem concret de programare operativ a produciei:

"Un numr de lucrri Ll, L2,..., Ln trebuiesc executate ct mai repede. Acestea sunt efectuate de persoanele (muncitorii) Ml, M2,..., Mn, fiecare putnd executa oricare din lucrrile date.Cunoscnd timpul tij de execuie al lucrrii Li de ctre muncitorul Mj, scopul optimizrii este gsireaacelui mod de repartizare a lucrrilor pe muncitori astfel nct timpul total de execuie al lucrrilors fie minim"

100

Bazele cercetrii operaionalePentru modelarea matematic a acestei probleme, cunoscut n literatura de specialitate sub

numele de "problema afectrii", se introduc variabilele bivalente:

xij = contrarcazn0 Muimuncitorularepartizatestelucrarea Ldaca1 ji

Condiiile ca fiecare lucrare s fie repartizat unui muncitor precum i condiia ca fiecare muncitor s primeasc o lucrare se traduc prin restriciile:

dd

dd

nj11x

ni11x

m

1i

ij

n

1j

ij

n care variabilele xij satisfac cerina special:xij {0,1}

Obiectivul urmrit minimizarea timpului total de execuie conduce la urmtoarea funcieobiectiv:

(min) f =

n

1i

n

1j

ijij xt

Modelul rezultat difer de modelul problemei de transport echilibrate prin condiia impusvariabilelor de a fi doar 0 sau 1 (variabile bivalente). Totui rezolvarea sa se poate face cu algoritmul de la problema de transport, ns ea este greoaie, datorit faptului c soluiile de baz aleacestei probleme sunt puternic degenerate. Exist metode mai eficiente de abordare a problemeiafectrii, bazate pe teoria grafurilor.

4. Problema ncrcrii utilajelorFcnd parte din acelai cadru al programrii operative a produciei, problema ncrcrii

utilajelor (punctelor de lucru) ocup a poziie central. Aceast problem poate fi formulat astfel:"ntr-o secie a unei uniti economice se produc reperele (bunurile) P1, P2, ..., Pn care pot fi

realizate pe oricare din utilajele (grupele de utilaje) Ul,U2,...,Um. Se cunosc urmtoarele date: cantitile N1, N2,...,Nn din reperele date, care trebuie produse ntr-o anumit perioad; fondurile de timp disponibil F1, F2,...,Fm ale utilajelor, n perioada respectiv; cantitatea Pij din reperul Pj ce poate fi produs pe utilajul Ui ntr-o anumit perioad de

timp; costul cij al realizrii unei uniti specifice din reperul Pj pe utilajul Ui.Se dorete gsirea acelui mod de repartizare a sarcinilor de producie pe utilaje astfel nct

costul realizrii cantitilor planificate s fie minim."Modelul matematic asociat acestei probleme este:

101

Programarea liniar

t

dd

ddd

0x

nj1Nx

mi1FxP

1

xcmin

ij

j

m

1i

ij

i

n

1j

ijij

m

1i

n

1j

ijijf

unde xij reprezint cantitatea de repere Pj ce urmeaz a fi realizat pe utilajul Ui. Modelul esteasemntor modelului problemei de transport, pentru rezolvare putndu-se folosi algoritmul de la problema clasic de transport, cu unele modificri dictate de prezena "ponderilor" Pij.

5. Problema de transport a lui Koopmans

Aceast problem este, istoricete vorbind, anterioar problemei clasice de transport i de eas-a ocupat pentru prima oar T. C. Koopmans.

Problema se refer la la transportul materialelor de rzboi, efectuate n perioada celui de-al doilea rzboi mondial, din S.U.A. n Anglia i retur. ntruct cantitile de produse transportate n cele dou sensuri erau diferite, navele circulau de multe ori goale sau incomplet ncrcate. Avnd nvedere i faptul c transporturile pe mare ale aliailor se aflau sub ameninarea submarinelor i a aviaiei germane se punea problema asigurrii unei asemenea utilizri a mijloacelor de transportnct s se reduc la minimum capacitatea de transport neutilizat (msurat n tone-kilometri) i,implicit, s se reduc pierderile de nave.

Dei problema de transport a lui Koopmans a avut un caracter tactico-militar, ea poate ficonsiderat - dup cum a fcut mai trziu nsui Koopmans - i ca o problem economic.Economic vorbind, reducerea capacitii de transport neutilizate a navelor mrete rentabilitateatransporturilor maritime. Firete c am putea aplica o soluie optim a acestei probleme pe plan mondial numai n cazul n care ar exista o form oarecare de administrate internional a navelor ide dirijare a transporturilor maritime. Totui, se poate vedea c modelul lui Koopmans poate s-igseasc aplicarea nu numai la transportul maritim, ci i n transportul feroviar, n cel auto, precumi n alte domenii similare.

Matematic, aceast problem se poate formula astfel:"Fie n porturi din care se expediaz i n care sosesc ncrcturi. Notm cu wi un volum dat

de mrfuri expediate (exprimate, de pild, n tone), iar cu pi - un volum dat de mrfuri care se aducn decursul unei anumite perioade n portul i (i = 1, 2,..., n). Se cunosc distanele sij dintre porturi (exprimate, de pild, n kilometri), acestea fiind date n matricea:

S =

0ss

s0sss0

n2n1

2n21

1n12

Dac xij reprezint volumul efectiv de mrfuri care urmeaz s fie transportate din portul i nportul j, iar yij - capacitatea de ncrcare a vaselor care circul din portul i in portul j date, deasemenea, sub forma unor matrici:

102

Bazele cercetrii operaionale

X = Y =

0xx

x0xxx0

n2n1

2n21

1n12

0yy

y0yyy0

n2n1

2n21

1n12

atunci necunoscutele problemei sunt mrimile yij (i,j = 1, 2,..., n), adic capacitile de ncrcare a navelor ce vor fi trimise din portul i n portul j.

Funcia obiectiv f va stabili mrimea "transporturilor goale", adic mrimea tonajuluineutilizat al navelor. Mrimea tonajului neutilizat pe traseul dintre portul i i portul j va fi (yij xij),deci mrimea capacitii de transport neutilizate pe toate traseele (n tone kilometri) va reprezenta:

f =

n

1i

n

1j

ijijij xys

Problema examinat const n a gsi minimul acestei funciiCondiiile auxiliare pe care trebuie s le satisfac necunoscutele yij pot fi notate sub forma

urmtoarelor ecuaii:

dd

dd

nj1py

ni1wy

j

n

1i

ij

i

n

1j

ij

Primele n ecuaii 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 portoarecare j din toate celelalte porturi trebuie s fie egal cu pj.

Trebuie menionat c - ntocmai ca n problema de transport - dintre cele n + n ecuaii de echilibru, numai (2n - 1) ecuaii sunt independente. Aceasta se explic prin faptul c

, adic tonajul total al navelor care pleac din toate porturile este egal cu tonajultotal al navelor care sosesc n toate porturile. ntruct problema are (n

n

1j

j

n

1i

i pw

2 n) necunoscute yjj (i,j = l, 2,...,n), dar exist 2n 1 ecuaii de echilibru independente, numrul gradelor de libertate (numrulvariabilelor secundare) va fi (n2 n) (2n 1) = n2 3n + 1.

n afar de relaiile de echilibru exist i condiiile de nenegativitate: yij t xij t 0

condiia yij t xij nseamn c tonajul vaselor care pleac din portul i spre portul j trebuie s fie maimare sau egal cu cantitatea de mrfuri 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 att funciaobiectiv, ct i ecuaiile de echilibru sunt relaii liniare n raport cu necunoscutele yij. Aceastproblem poate fi uor transformat ntr-un model de programare neliniar dac, de pild, n loculdistanei sij ntre porturi, introducem cheltuielile de transport cu meniunea c aceste cheltuieli nu cresc direct proporional, ci mai lent dect distanele. Aceasta problem poate fi uor nlocuitprintr-o problem dual, lund ca funcie obiectiv rentabilitatea total a tuturor transporturilor peplan mondial. n acest caz, problema de minimizare a tonajului neutilizat al navelor ar fi nlocuitprintr-o problem de maximizare a rentabilitii totale a transporturilor.

103