PROGRAMARE LINIARA

PROGRAMARE LINIARA

1 CONSIDERATII GENERALE

O problema de programare liniara sete formata din doua parti distincte, si anume

un numar de restrictii liniare :

f_i(x₁,....,x_n) b_i, i=1,.,k,

f_j(x₁,....,x_n)=b_j, j=k+1,...,p, (1)

f_e(x₁,....,x_n) b_e,    e=p+1,...,m,

x_k k=1,2,.,n,

care exprima conditiile problemei 

- o functionala liniara f(x₁,....,x_n), obiectivul problemei maximizarea sau minimizarea acesteia

Problemele economice care conduc la modele de programare liniara sunt prezentate in curs si, ca atare nu le mai reluam aici Din aspectele prezentate in curs, a rezultat ca modelul matematic al unei probleme de programare liniara izvorat din practica de productie, este in general de forma :

n

[max] sau [min] z= c_j x_j

j=1

4

n

a_ij x_j = d_i ,    i=1,..,m; (3)

_j=1

x_j j=1,..,n . (4)

Vom numi forma standard a unei probleme de programare liniara, forma urmatoare

n

[max] sau [min] z= c_j x_j

j=1

n

a_ij x_j = d_i ,    i=1,..,m; (6)

_j=1

x_j j=1,..,n . (7)

Asadar, o problema de programare liniara este prezentata sub forma standard atunci cand restrictiile sale sunt numai egalitati, iar variabilele ce intra in model sunt toate pozitive.

Reamintim ca o restrictie de forma (3), care nu e de tip egalitate, poate fi adusa la forma unei egalitati, fie prin adaugarea

unei marimi pozitive fie prin scaderea unei marimi pozitive.

Pentru a ne obisnui cu limbajul utilizat, mai precizam ca problema de programare liniara (P.L.) se spune ca are forma canonica daca toate restrictiile (6) sunt inegalitati de acelasi sens. Asadar, o problema de (P.L.) se prezinta sub forma canonica, atunci cand toate restrictiile problemei au semnul cand se urmareste maximizarea functiei obiectiv, sau cand toate restrictiile problemei au semnul m cand trebuie minimizata functia obiectiv, in ambele cazuri variabilele (necunoscutele) problemei fiind nenegative.

O problema de P.L. este pusa sub forma standard de lucru daca :

este sub forma standard

in matricea coeficientilor exista o matrice unitate de dimensiune egala cu numarul restrictiilor;

termenii liberi ai restrictiilor sunt nenegativi.

O alta forma, mai concentrata, de scriere o reprezinta asa- zisa forma matriceala, adica:

[max] sau [min] z = CX    (8)

AX = d    (9)

X , unde (10)

a₁₁ .... a_1n

A = (a_ij) i = 1, . . . . .,m =

j = 1, . . . . .,n a_m1 ... a_mn

x₁

X = x₂ , C = (c₁, c₂, . , c_n)

x_n

d₁

d = d₂

d_n

2 SOLUTIILE UNEI PROBLEME DE PROGRAMARE LINIARA

In studiul rezolvarii metodelor de programare liniara, se porneste de la forma standard. Sa consideram, deci, modelul problemei de programare liniara sub forma standard

[max/min] z = CX, (11)

(M) AX =b,    (12)

X (13)

in care matricea A are m linii si n coloane. Presupunem, in plus, ca sistemul restrictiilor (12) are cel putin o solutie, in caz contrar rezolvarea modelului pierzandu-si sensul.

Daca rangul matricei A ar fi mai mic decat m, sistemul restrictiilor fiind totusi compatibil, o parte dintre ecuatiile cuprinse in (12) ar fi consecinte ale celorlalte, deci ar putea fi inlaturate. De aceea vom considera inca de la inceput ca rangul matricei A este egal cu m. De asemenea, vom considera ca numarul variabilelor n este strict mai mare decat numarul restrictiilor m, aceasta conditie evitand unicitatea solutiei sistemului de restrictii.

Vom numi simplu, solutie a modelului (M), un vector coloana X, n-dimensional, care verifica sistemul de restrictii (12). Daca, in plus, vectorul X verifica si conditiile de nenegativitate (13) se spune ca el reprezinta o solutie realizabila a modelului (M). In acest fel, rezolvarea modelului poate fi urmarita in spatiul vectorial n-dimensional, numit si spatiul solutiilor. In cele ce urmeaza, convenim sa notam cu M multimea solutiilor realizabile ale modelului (M).

Exemplul 3. Sa consideram, pentru exemplificare,

urmatoarele restrictii ale unui model de programare liniara:

x₁ + 2x₂ + x₃ + 2x₄ = 8

2x₁ + x₂ + x₃ + 3x₄ = 9

Solutia X₁ =(3 2 1 0)^t a acestui sistem este o solutie realizabila a modelului, deoarece nu are nici o componenta strict negativa. In schimb, solutia X₂ = (3 3 -3 1)^t este o solutie nerealizabila a modelului, avand componenta x₃ strict negativa (nu verifica conditia corespunzatoare de nenegativitate).

In construirea algoritmului de rezolvare a modelelor de programare liniara, vom tine seama indeosebi de natura diferitelor componente ale solutiilor, de a fi nule sau nu. In acest scop, sa consideram spatiul vectorial m-dimensional, numit spatiul restrictiilor, in care consideram cei n vectori-coloana ai matricei A, notati prin a_j , j=1, . . . , n precum si vectorul b, al termenilor liberi. Cu aceste notatii, sistemul de restrictii ( ) poate fi scris sub forma vectoriala (14), unde componentele x₁, x₂, x₃, . . . . , xn, ale unei solutii oarecare X, sunt marimi scalare nedeterminate :

x₁ a₁ + x₂ a₂ + x₃ a₃ + . . . . . + x_n a_n = b

In acest fel, fiecare componenta x_j, j 1, 2, 3, . . . . , n, a unei solutii, se ataseaza unui vector coloana a_j din matricea A.

Daca rangul matricei A este egal cu m, exista cel putin o grupa de m vectori dintre acestia, ce formeaza o baza in R^m . Daca in solutia X numai componentele x_j1, x_j2, . . . , x_jm ce corespund vectorilor din baza B, sunt diferite de zero, aceasta solutie se numeste solutie de baza a modelului (M).

Componentele unei solutii de baza pot fi de doua tipuri, si anume:

componentele ce corespund la vectori ce nu fac parte din baza respectiva, numite si componente nebazice, acestea fiind toate egale cu zero (prin definitie)

componente ce corespund la vectorii din baza, numite si componente bazice, dintre acestea facand parte toate acele componente ale solutiei ce sunt diferite de zero.

Din cele de mai sus, rezulta ca o solutie de baza se poate determina fixand mai intai m vectori-coloana din matricea A, care sa formeze o baza in R^m, dupa care efectuam urmatoarele operatii:

inlocuim in sistemul restrictiilor toate variabilele ce corespund vectorilor ce nu fac parte din baza considerata, prin zero;

rezolvam sistemul tip Cramer ramas, obtinand astfel si valorile componentelor bazice.

Din definitia solutiei de baza, deducem ca o astfel de solutie poate avea cel mult m componente diferite de zero, aceste componente in mod obligatoriu la vectori-coloana liniari independenti ai matricei A. In cazul cand o solutie de baza are mai putin de m componente diferite de zero, se zice ca ea este degenerata, in caz contrar ea fiind nedegenerata.

Exemplul 3.2. Fie urmatorul sistem de restrictii, apartinand unui model de programare liniara:

x₁ + x₂ + x₃ + x₄ + 3x₅ = 6,

x₁ + 3x₂ + 2x₃ + 3x₄ + x₅ = 12

Solutia X₁ = ( 3 3 0 0 0 )^t este o solutie de baza realizabila si nedegenerata, avand doua componente nenule pozitive, ce corespund la vectorii a₁ si a₂ din R², si anume:

1 1

a₁ = 1 si a₂ 3

Pe de alta parte, solutia X₂ = ( 15 0 0 0 -3 )^t este o solutie de baza nerealizabila si nedegenerata, ce corespunde bazei

B₂ = . In sfarsit, solutia X₃ = ( 0 0 6 0 0 )^t este o solutie de baza si degenerata, avand o singura componenta nenula, in cazul nostru strict pozitiva. Se poate observa ca aceasta solutie poate corespunde la mai multe baze, ca de exemplu, B₃ = ,

B₄ = etc..

In continuare, prezentam cateva rezultate teoretice legate de solutiile problemei de programare liniara care simplifica, cautarea solutiilor optime.

Mentionam, fara demonstratie, urmatoarele teoreme:

Teorema 3. Multimea solutiilor realizabile, corespunzatoare unui model de programare liniara, este o multime convexa.

Teorema 3.2. Daca functia de eficienta a unui model de programare liniara are optim finit, valoarea optima este atinsa cel putin intr-un varf al multimii solutiilor realizabile.

Teorema 3.3. Daca functia de eficienta a unui model de programare liniara are optim finit, atunci multimea solutiilor optime ale acestui model este o multime convexa, iar varfurile ei se afla printre varfurile multimii solutiilor realizabile ale modelului.

Conform teoremelor prezentate, determinarea solutiilor optime ale unui model de programare liniara ar putea fi facuta calculand si corectand mai intai toate solutiile de baza ale modelului (acestea fiind in numar limitat, numarul lor fiind cel mult egal cu C_n^m) pentru a extrage pe cele realizabile ce maximizeaza, respectiv minimizeaza functia de eficienta (functia obiectiv). Un astfel de procedeu cere un volum mare de calcule, mai ales in cazul unui model de dimensiuni mari, cand el devine practic imposibil.

3 BAZELE MATEMATICE ALE METODEI SIMPLEX PRIMAL PENTRU REZOLVAREA PROBLEMELOR DE PROGRAMARE LINIARA

Metoda simplex primal, sau metoda imbunatatirilor succesive, evita cercetarea exhaustiva a tuturor solutiilor de baza ale unui model de (P.L.), construind succesiv solutii realizabile de baza din ce in ce mai bune ale modelului pana cand este obtinuta o solutie de baza optima. Evident, prin solutie mai buna vom intelege o solutie care da pentru functia de eficienta o valoare mai mare, respectiv mai mica decat cele precedente, dupa

cum functia de eficienta trebuie sa devina maxima, respectiv minima. In descrierea si justificarea metodei algoritmului simplex primal, ne vom referi initial la un model de (P.L.) in care functia de eficienta trebuie sa devina maxima, model de forma urmatoare:

n

[max] z = a c_j x_j    (15)

n j=1

(M) a a_j x_j = b    (16)

j=1

x (17)

Sa presupunem ca dispunem de o solutie realizabila de baza a modelului, notata cu X, solutie pe care o putem considera, fara a micsora generalitatea rationamentelor ce urmeaza, corespunzand bazei formate din vectorii a₁, a₂, . . . , a_m, baza insasi fiind notata cu B. Pentru sistematizarea calculelor, toti vectorii-coloana a_j, j = 1,2,.,n precum si vectorul b al termenilor liberi in baza B, X^B se pot trece intr-un tabel de forma celui ce urmeaza:

Tabelul 1

Astfel, baza este trecuta pe coloana marcata cu B, componentele fiecarui vector a_j , j = 1,2,.,n se gasesc in tabel pe coloanele corespunzatoare acestor vectori. Pentru uniformitate, in tabel s-au notat si componentele vectorilor din baza sub forma generala, desi ei apar in particular ca vectori unitari.

Pentru scopuri legate de calculele ce urmeaza a fi efectuate, tabelul mai contine deasupra vectorilor a_j, j = 1,2,.,n, coeficientii c_j din functia de eficienta, ce corespund variabilelor atasate acestor vectori. De asemenea, tabelul contine si o coloana suplimentara C^B, cu coeficientii c_j corespunzatori variabilelor

atasate vectorilor din baza. Aceasta din urma coloana reprezinta, sub forma transpusa, un vector-linie m-dimensional, ce are drept componente acele componente ale vectorului C ce corespund vectorilor din baza B, in ordinea indicata de baza.

C^B = (c₁,c₂,.,c_m)    (18)

In calculele ce urmeaza a fi prezentate, legate de testarea optimalitatii, sau de imbunatatire a solutiei X, cu ocazia calculelor apar anumite sume ce pot fi atasate vectorilor a_j,

j=1,.,n, sume pe care le vom nota conventional prin f_j si care au urmatoarele expresii:

m

f_j = a c_k g_kj , j=1,2,3,.,n.

k=1

Aceste sume, jucand un rol deosebit de important in aplicarea algoritmului simplex, se ataseaza tabelului 1, sub forma unei linii suplimentare.

De observat ca fiecare cantitate f_j se obtine practic prin insumarea produselor dintre fiecare element al coloanei C^B si elementul corespunzator de pe coloana a_j a tabelului

Expresia matriceala a cantitatilor f_j este deci urmatoarea:

f_j = C^B a_j , j=1,2,3,.,n.    (20)

Sa redam cele de mai sus pe un exemplu numeric.

Exemplul 4. Fie modelul de (P.L.):

[max] z = 2x₁+3x₂+x₃+4x₄

x₁ + x₃+2x₄=8,

x₂+2x₃+x₄=10,

x_j 0, j=1,2,3,4

Se observa ca modelul de (P.L.) este pus sub forma standard de lucru, ceea ce inseamna ca:

este sub forma standard

in matricea coeficientilor exista o matrice unitate de dimensiune egala cu numarul restrictiilor;

termenii liberi ai restrictiilor sunt nenegativi.

f₁= 21+30 =2 ; f₂= 20+31 =3 ; f₃= 21+32 =8 ; f₄= 22+31 =7

Prezentam, in continuare, fara demonstratie urmatoarele teoreme:

Teorema 4. (Testul de optimalitate a solutiei sau criteriul optim). Daca pentru o solutie realizabila de baza X, a unui model de programare liniara, avem c_j - f_j 0, j=1,2,3,.,n, in cazul modelului de maxim respectiv f_j - c_j 0, j=1,2,3,.,n, in cazul modelului de minim, atunci solutia X este optima.

In cadrul tabelului de programare liniara vom nota diferentele cu D_j = c_j - f_j 0 pentru problema de maxim, respectiv D_j = f_j - c_j 0 pentru cea de minim.

Teorema 4.2. (Criteriul de imbunatatire a solutiei). Fiind data o solutie de baza realizabila X, nedegenerata, a unui model de programare liniara, daca exista cel putin un indice j, j=1,2,.,n, pentru care sa avem c_j - f_j > 0, in cazul unui model de maxim, respectiv f_j - c_j , in cazul unui model de minim, atunci se poate determina o alta solutie realizabila de baza Y, care sa dea o valoare mai buna decat X pentru functia de eficienta iar baza corespunzatoare solutiei Y sa difere de baza corespunzatoare solutiei X printr-un singur vector

Prezenta in continuare urmatorul tabel complet al unui model de (P.L.):

Tabelul 2.

Se observa ca, fata de tabelul 1, am renuntat la linia f_j, inlocuind-o cu D_j

Pentru a continua algoritmul simplex deci pentru a imbunatatii solutia cu care am pornit, trebuie sa stim:

ce vector nebazic poate intra in combinatie cu m-1 vectori bazici, pentru a forma impreuna o baza mai buna;

ce vector bazic este inlocuit cu vectorul nebazic gasit.

Conform celor aratate mai sus, vectorul a_j, caruia ii corespunde o diferenta D_j strict pozitiva, este cel ce urmeaza sa intre in noua baza, fapt indicat printr-o sageata alaturata coloanei acestui vector. Asadar, vom alege pe oricare din vectorii nebazici pentru

care diferenta D_j = c_j-f_j >0, de preferat (dar nu obligatoriu) pe cel pentru care diferenta pozitiva D_j este cea mai mare. Daca sunt mai multe diferente maxime egale, se alege oricare dintre ele.

De asemenea, pe coloana B a tabelului, este mentionat in mod special vectorul a_i ce urmeaza sa iasa din baza, fapt ilustrat de sageata ce se gaseste in dreptul lui.

Pentru a gasi vectorul ce trebuie eliminat din baza se face raportul, componenta cu componenta, intre coloana X^B si coloana care intra a_j, impartirea facandu-se numai la componentele strict pozitive ale lui a_j si se alege raportul cel mai mic, pentru ca noua solutie sa aiba componentele nenegative.

Elementul g_ij, care apare incercuit in tabelul 2 si care se gaseste la intersectia coloanei vectorului a_j, ce urmeaza sa intre in baza, cu linia vectorului a_i, ce iese din baza B, se numeste "pivot".

Componenta y_i, ce urmeaza sa ia locul componentei x_i, se obtine prin impartirea acesteia la pivot, celelalte componente bazice ale solutie Z determinandu-se din tabelul 2, prin regula ilustrata in figura 1, cunoscuta sub numele de "regula dreptunghiului".

Urmatoarele expresii permit calculul componentelor noii solutii de baza Y

x_i

y_j = (21)

g_ij

y_k = x_k - y_jg_kj = x_k - x_i g_kj, pentru k=1,2,.,i-1,i+1,..,m (22)

g_ij

In legatura cu aceste relatii, se impun conditiile

x_i

(23)

g_ij

x_k g_ij - x_i g_kj

0, pentru k=1,2,.,i-1,i+1,i+2,.,m (24)

g_ij

x_i g_ij

Tabel vechi

x_k g_kj

x_i

y_j =

g_ij

x_k g_ij - x_i g_kj Tabel nou

y_k =

g_ij

Fig. 1 Calculul componentelor solutiei Y

Deoarece prin ipoteza avem x_i > 0, inegalitatea (23) impune conditia g_ij > 0, adica pivotul trebuie sa fie strict pozitiv.

Precizam mai sus ca, pentru a gasi vectorul ce trebuie eliminat din baza, se face raportul, componenta cu componenta, intre coloana X^B si coloana vectorului a_j care intra in baza. Ilustrarea acestor operatii este prezentata in figura 2.

x₁ g_1j x₁/g_1j

x₂ g_2j x₂/g_2j

x_m g_mj x_m/g_mj

Fig 2. Operatiile efectuate pentru gasirea vectorului ce trebuie eliminat din baza

De remarcat este faptul ca acolo unde componenta g_kj 0 raportul nu se face, iar dintre rapoartele ultimei coloane ne oprim la cel mai mic, acesta indicand linia vectorului a_i ce urmeaza a fi eliminat din baza B. Aceasta regula poarta numele de criteriu de iesire din baza.

Algoritmul simplex este deci un algoritm iterativ, in care sunt cercetate succesiv solutii realizabile de baza din ce in ce mai bune, pornind de la o solutie realizabila de baza oarecare, pana cand este obtinuta o solutie optima.

Etapele ce trebuie parcurse la o iteratie oarecare, cand se dispune de o solutie X, sunt urmatoarele

Etapa intai ( Verificarea optimalitatii

Cu ajutorul unui tabel de forma tabelului 1 se calculeaza cantitatile f_j, j=1,.,n, apoi diferentele D_j = c_j - f_j, in cazul modelului de maxim, respectiv D_j = f_j - c_j, in cazul modelului de minim. Daca toate aceste diferente sunt nepozitive, solutia cercetata X este potima si algoritmul ia sfarsit. In caz contrar, se trece la etapa urmatoare.

Etapa a doua (Imbunatatirea solutiei

Aplicand criteriul de intrare in baza, se determina mai intai un vector a_j, a carui diferenta D_j este strict pozitiva, in cazul cand exista mai multe diferente de acest fel alegandu-se cea mai mare dintre ele. Apoi, pentru aplicarea criteriului de iesire din baza, se fac rapoartele x_i /g_ij, dintre care cel mai mic determina un vector a_i, ce urmeaza sa paraseasca baza. In sfarsit, determinand pivotul, formulele (21) si (22) dau posibilitatea completarii tabelului corespunzator noii solutii imbunatatite. Aplicarea acestor formule se poate face prin urmatoarele operatii succesive:

se completeaza coloana B cu vectorii ce formeaza noua baza ;

se imparte linia pivotului la pivot;

se completeaza coloanele corespunzatoare vectorilor din noua baza, acestia devenind vectori unitari

se calculeaza celelalte elemente, aplicand regula dreptunghiului.

Sa ilustram functionalitate algoritmului pe un exemplu numeric.

Exemplul 4.2 Fie modelul de (P.L.)

[max] z = 5x₁+7x₂+2x₃+2x₄

x₁+3x₂ - x₃+0x₄=40

-x₂+2x₃+ x₄=10

x_j 0, j=1,2,3,4

Completam urmatorul tabel

Deoarece pe linia diferentelor D_j, exista o diferenta strict pozitiva (c₃-f₃=3), deducem ca solutia realizabila x nu verifica criteriul de optim. In tabel s-a facut efectiv trecerea la o solutie realizabila de baza mai buna, prin efectuarea urmatoarelor operatii:

dintre rapoartele 40/-1 si 10/2 se considera numai cel corespunzator celei de-a doua linii; deoarece prima componenta a vectorului a₃ este negativa fapt ilustrat si in figura 3; urmeaza ca vectorul a₄ este cel care trebuie sa iasa din baza;

X^B a₃

Fig 3 Calculul rapoartelor x_m/g_mj

pivotul, incercuit in tabel, s-a determinat la intersectia coloanei a₃ cu linia a₄

s-au inscris, in coloana B, vectorii ce formeaza noua baza, respectiv a₁ si a₃

s-a impartit linia a doua prin 2 (pivotul), rezultatele trecandu-se pe linia a doua din iteratia a doua;

celelalte elemente de pe linia intai a iteratiei a doua s-au calculat cu ajutorul regulii dreptunghiului;

s-a completat coloana C^B cu coeficientii c₁ si c₃, corespunzatori vectorilor din noua baza.

Componentele bazice ale noii solutii se citesc pe coloana X^B, ele fiind urmatoarele: x₁=45, x₂=0, x₃=5, x₄=0. Prin urmare, noua solutie are forma urmatoare:

X ), iar Z_max

Pentru testarea optimalitatii acestei noi solutii s-au calculat in tabel diferentele c_j-f_j. Deoarece nu mai exista nici o diferenta strict pozitiva, deducem ca solutia X este optima si aplicarea algoritmului simplex a luat sfarsit.

Sa ne ocupam acum de operatiile premergatoare aplicarii operatiilor cerute de algoritmul simplex. Pentru a putea incepe aplicarea algoritmului simplex, in scopul gasirii solutiei optime pentru un model de (P.L.), trebuie sa fie indeplinite doua conditii si anume:

a)      modelul sa fie sub forma standard de lucru (cu restrictii de tip egalitati);

b)      sa dispunem de o solutie realizabila de baza, pe care o vom numi solutie initiala.

In privinta conditiei (a), precizam ca orice restrictie scrisa sub forma de inegalitate se poate pune sub forma unei egalitati daca se adopta o variabila suplimentara, numita variabila de compensare. Pentru ca aceasta variabila de compensare sa se supuna si ea conditiilor de nenegativitate, ea se adauga cu coeficientul +1 daca inegalitatea are sensul si cu coeficientul -1 daca inegalitatea are sensul

In ceea ce priveste conditia (b), determinarea unei solutii realizabile de baza initiale constituie uneori o parte importanta a rezolvarii modelului, pentru aceasta existand metode speciale.

In continuare se prezinta inca trei exemple numerice rezolvate.

Exemplul 4.3 Fie modelul de P.L.

[max] f = 2x₁+3x₂+x₃+4x₄

x₁ + x₃+2x₄=8

x₂+2x₃ + x₄=10

x_j 0, j=1,2,3,4

Completam urmatorul tabel:

Sa explicam, pe scurt, cum s-au obtinut rezultatele pe linia D_j

c₁-f₁=2-(21+30)=2-2=0

c₂-f₂=3-(20+31)=3-3=0

c₃-f₃=1-(2 2)=1-8=-7 etc.

Cum toate diferentele sunt negative sau zero, avem solutie optima finita (8,10,0,0), f _max

Exemplul 4.4 Fie modelul de (P.L.):

[max]f=2x₁+x₂+3x₃+5x₄+9x₅

x₁+2x₃+x₄+3x₅=15

x₂+x₃+2x₄+x₅=12

x_j 0, j=1,2,3,4,5

Construind tabelul simplex vom gasi pornind de la solutia de baza x₁=15, x₂=12, x₃=x₄=x₅=0

Algoritmul simplex a luat sfarsit, solutia optima fiind x_opt careia ii corespunde f _max

Exemplul 4.5 Fie modelul de (P.L.) :

[min]f = 2x₁+x₂+3x₃+5x₄-x₅

2x₁+x₂+ x₃ = 4

x₁+ 2x₃+ x₅ = 7

3x₁+ 2x₃+x₄ = 10

x_j 0, j=1,2,3,4,5

Dupa cum rezulta din tabel, pe linia D_j s-au facut diferentele f_j-c_j, deoarece este o problema de minim. Solutia optima este x_opt=(2,0,0,4,5), caruia ii corespunde f_min=19.

Prezentam, in continuare, cateva observatii legate de aplicarea algoritmului simplex .

Observatia 4. Criteriul de iesire din baza, asa cum am precizat mai inainte, cere ca vectorul care intra in baza sa contina cel putin o componenta pozitiva. Daca din criteriul de optim rezulta ca solutia nu este optima si vectorul care trebuie sa intre in baza nu are nici o componenta pozitiva, atunci problema nu admite optim finit (optimul este infinit).

Observatia 4.2. In cazul cand in tabelul simplex optim avem diferente nule si in dreptul altor vectori care nu fac parte din baza

optima, problema admite solutie optima multipla. Pentru a gasi si alte solutii optime se continua algoritmul simplex introducand in baza unul din vectorii din afara bazei caruia ii apartine o diferenta nula.

Precizam, inaintea exemplului 4.3,ca determinarea unei solutii realizabile de baza initiale necesita - in anumite cazuri - aplicarea unor metode speciale. In acest sens prezentam in continuare una dintre metode si anume metoda "coeficientilor de penalizare".

Dupa ce modelul a fost adus la forma standard, avem grija ca toti termenii liberi sa fie nenegativi, in caz contrar schimbam semnele unora dintre restictii. Apoi, scriind matricea A a sistemului de restrictii, observam ce vectori unitari se gasesc printre coloanele ei. In cazul in care matricea A contine toti cei m vectori unitari, acestia formeaza baza initiala cautata. Daca matricea A nu contine toti cei m vectori unitari (eventual nici unul), introducem unele variabile suplimentare numite variabile artificiale, totdeauna cu coeficienti egali cu +1, in anumite restrictii convenabil alese, pana cand matricea sistemului de restrictii va contine m vectori-coloana unitari.

Deoarece variabilele artificiale strica vechiul echilibru al restrictiilor (care erau egalitati), vom obtine astfel un model numit model largit ,ale carui solutii nu corespund totdeauna cu solutiile modelului ce trebuie rezolvat. Evident, pentru ca o solutie a modelului largit sa ofere si o solutie a modelului initial, trebuie ca in ea toate variabilele artificiale sa fie nule. Astfel, vom cauta sa fortam anularea variabilelor artificiale, prin introducerea acestora in functia de eficienta cu coeficienti egali cu +M, in cazul unui model de minim, respectiv cu coeficienti egali cu -M, in cazul unui model de maxim, M, coeficientul de penalizare , fiind considerat ca un numar arbitrar foarte mare. Rolul acestor termeni suplimentari din functia de eficienta este acela de a nu lasa aceasta functie sa-si atinga valoarea minima, respectiv valoarea maxima, pana cand nu se anuleaza toate variabilele artificiale. Este limpede ca daca, prin aplicarea algoritmului, s-a ajuns la o solutie optima a modelului largit, fara ca toate variabilele artificiale sa aiba valori nule in aceasta solutie, modelul initial este imposibil.

De obicei, in calcule, nu particularizam valoarea lui M, dar pe parcursul aplicarii algoritmului simplex il privim ca pe un

numar suficient de mare (in raport cu celelalte valori numerice

din model).

Deoarece valorile variabilelor artificiale trebuie sa fie nule, orice vector artificial care a iesit din baza nu va mai fi cercetat pentru o eventuala introducere in baza, deci nu se va mai calcula diferenta D_j, corespunzatoare lui, putand renunta la coloana acelui vector din tabel.

Sa redam cele de mai sus printr-un exemplu numeric.

Exemplul 4.6 Se da urmatorul model de (P.L.) :

[min]f = x₁+2x₂+2x₃+x₄

x₁+x₂+2x₃+ x₄=10

2x₁+ x₂+2x₃+2x₄=12

x₁+3x₂+2x₃+2x₄=16

x_j 0, j=1,2,3,4

Modelul largit in cazul de fata va fi :

[min]f = x₁+2x₂+2x₃+x₄+MU₁+MU₂+MU₃

x₁+ x₂+2x₃+ x₄+U₁=10

2x₁+ x₂+2x₃+2x₄+U₂=12

x₁+3x₂+2x₃+2x₄+U₃=16

x_j 0, j=1,2,3,4, U_k 0, k=1,2,3

iar tabloul simplex corespunzator este:

Deci x_opt=(0,2,3,2) si f_min=12

PROBLEME DE PROGRAMARE LINIARA PROPUSE SPRE REZOLVARE

max]f =2x₁+x₂+x₃+3x₄+2x₅+9x₆

x₁+x₄+2x₅+ x₆ =10

x₂+x₄+ x₅+2x₆ =20

x₃+x₄+3x₅+3x₆=30

x_j 0, j=1,2,3,4,5,6

R : x_opt=(0,0,0,0,0,10) ; f_max=90

[max]f=2x₁+x₂+3x₃+5x₄+9x₅

x₁+2x₃+ x₄+3x₅=15

x₂+ x₃+2x₄+ x₅ =12

x_j 0, j=1,2,3,4,5

R : x_opt=(0,0,0,21/5,18/5) ; f_max=267/5

[max]f=2x₁+x₂+6x₃+5x₄+7x₅+11x₆+3x₇

x₁+ x₃+ x₄+ x₅+3x₆+2x₇ =18

x₂+ x₃+2x₄+3x₅+2x₆+ x₇ =24

x_j 0, j=1,2,3,4,5,6,7

R : x_opt=(0,6,18,0,0,0,0) ; f_max=114

[max]f=x₁+x₂+3x₃+5x₄+5x₅+7x₆

x₁+ x₃+2x₄+ x₅+2x₆=14

x₂+ x₃+ x₄+2x₅+3x₆=18

x_j 0, j=1,2,3,4,5,6

R : x_opt=(0,0,0,10/3,22/3,0) ; f_max=160/3

[max]f=-x₁+2x₂+x₃+3x₄-x₅-2x₆

x₁+x₂+2x₃+3x₅=15

2x₂+x₃+x₄+5x₅=20

x₂+2x₃+x₅+x₆ =10

x_j 0, j=1,2,3,4,5,6

R : x_opt=(5,0,5,15,0,0) ; f_max=45

[max]f=x₁+2x₂+3x₃+x₄

1

x₁- x₃+ x₄=1

2

x₂+x₃ - x₄ =1

x_j 0, j=1,2,3,4

R : optim infinit

[max]f=2x₁+3x₂+2x₃

x₁+ x₂+2x₃

2x₁+ x₂+ x₃

x₁-3x₂+2x₃

x_j 0, j=1,2,3

R : x_opt=(0,2,0) ; f_max=6

[min]f=5x₁+2x₂+x₃+x₄+3x₅

3x₁+ x₃+2x₄ =20

x₁+ x₂+3x₄ =10

5x₁+ x₄+ x₅ =1

x_j 0, j=1,2,3,4,5

R : x_opt=(0,7,18,10) ; f_min=33

[max]f=3x₁+4x₂+2x₃+x₄

2x₁+2x₃+x₄

3x₁+2x₂+ x₄

x₁+2x₂+x₃+4x₄

x_j 0, j=1,2,3,4

R : x_opt=(0,3,5,0) ; f_max=22

[min]f=x₁+2x₂+2x₃+x₄

x₁+2x₂+2x₃+x₄ =10

2x₁+x₂+2x₃+2x₄ =12

x₁+2x₂+2x₃+2x₄=44/3

x_j 0, j=1,2,3,4

R : x_opt=(0,8/3,0,14/3) ; f_min=10

[min]f=x₁+2x₂+2x₃+x₄

x₁+2x₂+2x₃+x₄ =10

2x₁+x₂+2x₃+2x₄=12

x₁+2x₂+2x₃+2x₄=16

x_j 0, j=1,2,3,4

R: Problema nu are solutie, deoarece contine si o variabila artificiala nenula.

[max]f=3x₁+2x₂+x₃+5x₄+2x₅

x₁+2x₂+x₃+3x₄+x₅=10

2x₁+x₂+x₃+x₄+3x₅ =4

x_j 0, j=1,2,3,4,5

R : x_opt=(2/5,0,0,16/5,0) ; f_max=86/5

PROBLEME DE PROGRAMARE LINIARA CU APLICATII IN PROCESUL DE PRODUCTIE PROPUSE SPRE REZOLVARE

In cadrul unei sectii de productie trebuie executate doua produse A si B, fiecare cu prelucrari pe trei utilaje (U₁,U₂,U₃). Timpul unitar pe produs si pe masina, timpul total disponibil pe fiecare grupa de utilaj si beneficiul pe unitatea de produs sunt prezentate in tabelul de mai jos.

Se cere sa se determine cantitatile executate din fiecare produs, astfel incat sa se obtina un beneficiu maxim pe baza datelor din tabel.

Indicatie. Modelul matematic al problemei este:

[max]f=20x₁+25x₂

9x₁+10x₂

12x₁+6x₂

19x₁+5x₂

x_j 0, j=1,2

Se transforma inegalitatile in egalitati prin introducerea variabilelor de compensare si se porneste algoritmul simplex.

Un atelier de prelucrari mecanice este specializat in prelucrarea de seturi de piese ce urmeaza a fi prelucrate lunar in conditiile realizarii unui beneficiu total lunar maxim.

Datele privind normele de timp - t_ij (min/set piese), fondurile de timp disponibile T_di (min/luna) si beneficiul planificat - b_j (u.m/set piese) sunt prezentate in tabelul de mai jos:

Se cere un program optim de fabricatie pentru trei utilaje principale din cadrul unui atelier de sudura care realizeaza seturi de piese sudate necesare fabricarii la a trei tipodimensiuni de subansamble in conditiile realizarii unui beneficiu maxim la nivel

de atelier si a incarcarii maxime a celor trei utilaje analizate. Datele referitoare la normele de timp (t_ig), fondurile de timp disponibile (F_di) si beneficiul planificat (b_g) sunt prezentate in tabelul de mai jos:

Se cere modelul matematic care sa conduca la minimizarea resturilor materiale. Se dau bare de 7 metrii din care trebuie debitate urmatoarele repere

20 buc. repere a 5m

21 buc. repere a 3m

22 buc. repere a 2m.

Datele sunt sistematizate in tabelul de mai jos

Intr-o sectie de produse formata din trei ateliere se realizeaza patru tipuri de aparate. Se cere sa se determine cantitatea optima pe luna din fiecare tip de aparat in conditiile realizarii unui beneficiu maxim la nivel de sectie si incarcarii maxime a capacitatii de productie disponibile.

Se cunosc urmatoarele date: normele de timp (t_ij), fondurile de timp disponibile (F_di) si beneficiul planificat (b_j). Datele sunt prezentate in tabelul de mai jos:

Tipuri de aparate Ateliere    (j) (i)	tij(ore/aparat)				Fdi (ore/luna)
	A	B	C	D
bj

In cadrul unui atelier de prelucrari mecanice care are patru grupe de utilaje se realizeaza tipurile de piese a,b,c,d. Normele de timp (t_ig) pentru fiecare tip de piesa si fondurile de timp disponibile ale grupelor de utilaje (F_di) sunt prezentate in tabelul de mai jos. Se cere sa se determine numarul de piese/luna din fiecare tip pentru a asigura beneficiul maxim/luna, cunoscandu-se beneficiul unitar (b_g).

In vederea realizarii unui dispozitiv de sudat trebuie debitate bare de otel unidimensionale cu lungimea de 8m. Din debitare rezulta repere si resturi. Se cere modelul matematic care sa conduca la minimizarea costurilor. Datele sunt prezentate in tabelul urmator

Un atelier dispune de patru grupe de masini - unelte A,B,C,D, pe care se pot prelucra patru produse diferite. Sa se determine care produse trebuie sa se execute si in ce conditii pentru a se asigura incarcarea maxima a utilajelor. Fondul de timp disponibil pe fiecare grupa de utilaj, ca si normele de timp pe unitatea de produs si pe utilaj, sunt prezentate in tabelul de mai jos :

4 MODELE LINIARE DE TIP TRANSPORT. FOLOSIREA PROGRAMARII LINIARE IN OPTIMIZAREA PLANULUI DE TRANSPORT

FORMULAREA PROBLEMEI

In activitatea de conducere, organizare si planificare se intalnesc o serie de probleme privind repartizarea unor cantitati de la unitatile furnizoare la cele consumatoare. Astfel, pentru elaborarea planului de transport intern la o intreprindere se pune problema de a repartiza anumite cantitati privind un anumit material de la depozite (furnizori) la unitati de productie - sectii, ateliere (consumatori). Aceasta repartizare trebuie facuta in asa fel incat sa se asigure costuri minime de transport.

Modelul general al unei probleme de transport, atunci cand existentul la furnizori este egal cu necesarul la beneficiari (problema de tip echilibrat), este format din urmatoarele relatii :

m n

[min]f = a a c_ij x_ij (25)

i=1 j=1

n

a x_ij = a_i , i=1,2,.,m (26)

j=1

m

a x_ij = b_j , j=1,2,.,n (27)

i=1

m    n

a a_i = a b_j     (28)

i=1 j=1

x_ij (29)

in care ai - cantitatile existente la cei m furnizori

bj - necesarul la cei n consumatori

xij - cantitatea de material transportata de la furnizorul i la beneficiarul j

cij - costul unitar al materialului transportat de la furnizorul i la beneficiarul j

Rezolvarea acestei probleme de transport inseamna a gasi din multimea sistemului de restrictii (26), (27), in conditiile relatiei (28), acea solutie care minimizeaza relatia (25).

O problema de transport se rezolva in doua etape. In cadrul primei etape se determina o solutie initiala a problemei, iar in cazul celei de-a doua etape se efectueaza optimizarea acesteia.

Pentru determinarea unei solutii de baza se pot folosii diferite procedee, cum sunt: procedeul coltului de Nord-Vest (al diagonalei principale), procedeul diferentelor maxime, procedeul costurilor minime, procedeul elementului minim pe linie, procedeul elementului minim pe coloana.

Pentru optimizarea solutiei de baza, in cadrul etapei a doua se pot folosi, de asemenea, mai multe metode, cum sunt: metoda distributiva, metoda potentialelor, metoda stepping-stone (treapta-scara).

Dintre procedeele si metodele enumerate vom utiliza in cadrul primei etape procedeul coltului de Nord-Vest, iar in cea de-a doua etapa metoda distributiva.

REZOLVAREA UNEI PROBLEME DE TIP TRANSPORT ECHILIBRATA

Sa consideram ca o intreprindere trebuie sa aprovizioneze o anumita materie prima, pe care o are in trei depozite (A,B si C), patru fabrici pe care le subordoneaza, conform tabelului de mai jos:

Depozitele A si B au un disponibil din materia prima data de cate 1300 tone, iar depozitul C un disponibil de 700 tone. Corespunzator prevederilor continute in planul de aprovizionare tehnico-materiala, prima fabrica are nevoie de o cantitate de 1000 tone, fabrica a doua de 1200 tone, fabrica a treia de 800, tone iar fabrica a patra de 300 tone. Distantele de la depozite la fabrici sunt prezentate in acelasi tabel.

Etapa I

Folosirea procedeului coltului de Nord-Vest sau a diagonalei principale se prezinta in urmatorul tabel:

In colturile din dreapta sunt trecute distantele. Potrivit procedeului coltului Nord-Vest se porneste de la casuta A-1 situata in coltul Nord-Vest al matricei la care a fost repartizata cantitatea maxima de materie prima ce poate fi luata de la depozitul A pentru a acoperi necesarul acesteia. Dupa ce se satisface cantitatea necesara la A-1 (1000 tone), cele 300 tone ce mai raman inca la depozitul A se repartizeaza la casuta A-2, epuizandu-se prin aceasta cantitatea existenta in acest depozit.

La fabrica 2, unde sunt necesare 1200 tone, s-au repartizat 300 tone la depozitul A in casuta A-2 si 900 tone in casuta B-2 de la depozitul B, unde mai raman disponibile 400 tone.

La fabrica 3, unde sunt necesare 800 tone, s-au repartizat 400 tone de la depozitul B in casuta B-3 si 400 tone in casuta C-3 de la depozitul C, unde mai raman disponibile 300 tone.

La fabrica 4, unde sunt necesare 300 tone, se repartizeaza cele 300 tone disponibile existente in depozitul C in casuta C-4.

Din analiza tabelului se constata ca se porneste de la coltul Nord-Vest, acoperindu-se cantitatile necesare beneficiarilor, in mod complet, in ordinea lor, trecand de la un furnizor la altul numai dupa ce s-a terminat de repartizat cantitatea existenta la un furnizor pe diferiti beneficiari, in mod complet, ajungandu-se in final la coltul Sud-Est, mergandu-se deci pe directia diagonalei principale. De asemenea, se constata repartizarea intregii cantitati existente la furnizori (pe linie) si satisfacerea cantitatilor necesare la diferiti consumatori (pe coloane).

NOTA - Pentru ca problema sa poata fi rezolvata prin folosirea algoritmului problemei de transport, trebuie ca numarul casutelor ocupate sa fie egal cu cel dat de expresia :

m + n - 1    (30)

in care : m - numarul de furnizori

n - numarul de consumatori. In exemplul de fata, m + n - 1 = 3 + 4 - 1 Din analiza solutiei de baza rezulta ca exista sase casute ocupate cu cantitati, ceea ce inseamna ca problema poate fi rezolvata. Daca numarul casutelor neocupate era mai mic decat cel din relatia (30), atunci era necesar sa se completeze casute libere cu zero pana la verificare relatiei dupa o anumita regula.

Dupa obtinerea solutiei de baza se calculeaza volumul total de transport ce va trebui efectuat, facand suma tonelor/kilometri pentru toate casutele matricei unde au fost repartizate cantitati.

Vol. total=10005+3004+9005+4004+4002+3004=14300 tone/kilometri

Etapa a II-a - Imbunatatirea succesiva a solutiei de baza pana la obtinerea variantei optime.

Pentru imbunatatirea solutiei de baza se foloseste metoda distributiva, potrivit careia se efectueaza transferuri ciclice ale unor cantitati repartizate dupa unele contururi poligonale cu unghiuri drepte, astfel incat sumele cantitatilor transferate pe linii

si coloane sa nu modifice totalul disponibil (pe fiecare linie) pe furnizor si totalul necesar (pe coloane) la consumatori.

Pentru ca exista atatea posibilitati de imbunatatire a solutiei de baza cate casute libere exista in matricea planului de transport, se va determina in prealabil casuta cu cea mai mare perspectiva de imbunatatire, prin folosirea procedeului intocmirii ciclurilor casutelor libere. In acest sens se vor construi contururi poligonale, astfel incat un colt sa se afle intr-o casuta libera a matricei planului de transport a solutiei analizate, iar restul colturilor in casute unde exista deja repartizate cantitati. La conturul poligonal astfel format se trece in coltul liber semnul +, iar dupa aceea, in mod alternativ, semnele - si + la celelalte colturi.

Odata cu aceasta se vor trece in fiecare colt distantele corespunzatoare. Ca regula, in fiecare casuta nu se poate forma decat un unghi drept.

Dupa construirea conturilor poligonale dupa regulile amintite se face suma algebrica a distantelor din colturi, luandu-se pentru fiecare distanta semnul coltului unde se afla. Se va considera casuta cu cea mai mare perspectiva de imbunatatire

aceea prin care insumarea algebrica a distantelor va avea cea mai mare valoare negativa.

Pentru exemplificare, pornim de la datele prezentate in cel de-al doilea tabel. Intrucat in cadrul acestui plan exista sase casute libere, se vor construi sase contururi poligonale dupa regulile aratate anterior, efectuandu-se suma algebrica a distantelor. Fiecare casuta se va nota printr-un simbol format din initiala furnizorului (depozitului), corespunzator liniei pe care se situeaza casuta, si cifra corespunzatoare consumatorului (fabricii) de la coloana pe care se afla aceasta. Spre exemplu, A-3 va simboliza casuta de pe linia depozitului A si coloanei fabricii a treia.

Casuta A-3 va fi un dreptunghi cu coltul liber in A-3 si cu celelalte colturi in A-2,B-2,B-3. Suma algebrica va fi:2-4+5-4=-1

4 2

5 4

Pentru casuta A-4 se formeaza un contur poligonal cu varfurile in casutele A-4, A-2, B-2, B-3, C-3, C-4. Suma algebrica este

4 1

- +

+ -

5 4

+ -

2 4

Casuta B-1 are conturul poligonal in colturile casutelor B-1, A-1, A-2, B-2. Suma algebrica este

5 4

2 5

Conturul poligonal al casutei B-4 are colturile in B-4, B-3, C-3, C-4. Suma algebrica este

4 5

2 4

Pentru casuta C-1 conturul poligonal are colturile in casutele C-1, A-1, A-2, B-2, B-3, C-3. Suma algebrica este

4 4

- +

5 4

+ -

3 2

Conturul poligonal al casutei C-2 are colturile in C-2, B-2, B-3, C-3. Suma algebrica este

5 4

3 2

Din analiza sumelor algebrice obtinute pentru cele sase contururi poligonale rezulta aceeasi valoare negativa maxima pentru casutele A-4 si B- Inseamna ca acestea reprezinta casutele cu cea mai mare perspectiva de imbunatatire a planului de transport. Intrucat ambele casute au aceeasi valoare negativa maxima, se trece la imbunatatirea solutiei de baza prin efectuarea unor transferuri ciclice dupa conturul poligonal al casutei B- In acest scop se trec in colturi, in loc de distante, cantitatile corespunzatoare repartizate prin solutia de baza a planului de transport, care trebuie imbunatatita.

Pentru transferul ciclic se procedeaza astfel :

se analizeaza marimea cantitatilor de la colturile cu semnul negativ al conturului poligonal, identificandu-se cantitatea cea mai mica;

se adauga cantitatilor existente la colturile cu semnul plus cantitatea minima de la colturile cu semnul minus, scazandu-se aceasta cantitate de la colturile cu semnul minus;

se elaboreaza un nou plan de transport, in care se trec noile cantitati obtinute prin efectuarea transferului ciclic in casutele corespunzatoare colturilor conturului poligonal, toate celelalte casute ramanand neschimbate, ca in solutia de baza;

pe baza noului plan se calculeaza volumul de transport, care trebuie sa fie mai mic decat in varianta anterioara.

In felul acesta s-a obtinut o noua varianta de plan de transport, care la randul ei trebuie imbunatatita. In acest scop se folosesc aceleasi operatii efectuate pentru imbunatatirea solutiei de baza. Imbunatatirea variantelor de plan de transport se efectueaza pana in momentul in care, facand suma algebrica a distantelor de pe conturul poligonal, nu se mai obtin valori negative.

Continuand problema propusa, rezulta ca B-1 este o casuta cu perspectiva de imbunatatire a variantei de plan de transport. Se prezinta conturul poligonal al acesteia, trecand in loc de distante cantitatile corespunzatoare casutelor unde se afla colturile conturului. Constatam ca la colturile cu semnul negativ, cantitatea cea mai mica este 900.

1000 300

900

Aceasta cantitate se aduna la colturile cu semnul + si se scade la colturile cu semnul -. In acest fel se obtine un transfer ciclic de cantitati, asa cum se arata in conturul poligonal, care se reprezinta inca odata, insa cu noile cantitati repartizate la colturi.

100 1200

900 0

In functie de noile cantitati se intocmeste un plan de transport in care se trec cantitatile obtinute, toate celelalte casute ramanand neschimbate. Planul de transport obtinut este prezentat in tabelul urmator

Volumul de transport in noua varianta este urmatorul

10700 tone kilometri.

In continuare se cauta o noua varianta de plan de transport, imbunatatita fata de cea existenta. In acest scop se foloseste procedeul ciclurilor casutelor libere si pe aceasta baza se determina casuta cu cea mai mare perspectiva de imbunatatire. Casutele libere in actualul plan sunt: A-3, A-4, B-4, C-1 si C-2. Pentru acesta se vor obtine urmatoarele contururi poligonale:

Pentru A-3 colturile sunt situate in casutele A-3, A-2, B-2, B-3. Suma algebrica este: 2-4+5-4

4 2

5 4

Pentru A-4 colturile sunt situate in casutele A-4, A-2, B-2, B-3, C-3, C-4. Suma algebrica este: 1-4+5-4+2-4

4 1

- +

+ -

+ -

2 4

Pentru B-4 colturile sunt situate in casutele B-4, B-3, C-3, C-4. Suma algebrica este: 5-4+2-4=

4 5

2 4

Pentru C-1 colturile sunt situate in casutele C-1, B-1, B-3, C-3. Suma algebrica este: 4-2+3-2

2 4

3 2

Pentru C-1 colturile sunt situate in casutele C-2, B-2, B-3, C-3. Suma algebrica este: 3-5+4-2

5 4

3 2

Casuta cu cea mai mare perspectiva de imbunatatire este A-4, care are suma algebrica cu valoarea negativa cea mai mare.

1200

+ -

0 400

+ -

400 300

Ca urmare reprezentam conturul lui A-4 trecand cantitatile din planul de transport ce urmeaza a fi imbunatatit in colturi. Cantitatea cea mai mica la colturile cu semn negativ (300) se va aduna si scadea conform regulii cunoscute. In felul acesta se obtine urmatoarea repartizare:

900 300

- +

+ -

300 100

+ -

Cu noua repartizare a cantitatilor se intocmeste varianta de plan de transport, ca in tabelul urmator:

Volumul de transport in noua varianta este urmatorul:

tone km.

In noua varianta volumul de transport s-a redus de la 10700 tone/km la 9500 tone/km. In continuare se trece la imbunatatirea acestei variante, calculandu-se ciclul casutelor libere (A-3, B-4, C-1, C-2).

Pentru A-3 colturile sunt situate in casutele A-3, A-2, B-2, B-3. Suma algebrica este: 2-4+5-4

4 2

5 4

Pentru B-4 colturile sunt situate in casutele B-4, B-3, C-3, C-4. Suma algebrica este: 5 - 4 + 2 - 4 = - 4

Pentru C-1 colturile sunt situate in casutele C-1, B-1, B-3,C-3.Suma algebrica este: 4 - 2 + 3 - 2 = 3

2 4

Pentru C-2 colturile sunt situate in casutele C-2, B-2, B-3,C-3.Suma algebrica este :3 - 5 + 4 - 2 = 0

5 4

Avand doua casute cu aceeasi valoare negativa maxima, A-3 si B-4,se considera casuta cu cea mai mare perspectiva de imbunatatire A-3. Se reprezinta conturul poligonal al casutei A-3 cu cantitatile corespunzatoare din planul de transport la colturi:

Cantitatea de 100 tone fiind cea mai mici din colturile cu semnul minus este transferata ciclic. In felul acesta se obtine urmatoarea repartizare:

800 100

400 0

Cu noua repartizare a cantitatilor se intocmeste varianta de plan de transport, ca in tabelul urmator:

Volumul de transport in noua varianta este urmatorul:

1005+8004+1002+3001+9002+4005+04+7002+04==9400 tone/Km

In continuare se cauta o noua varianta de plan de transport, calculandu-se ciclul casutelor libere (B-4, C-1, C-2).

Pentru B-4, colturile sunt situate in casutele B-2, A-4, A3, B-3. Suma algebrica este: 5 - 1 + 2 - 4 = 2

2 1

4 5

Pentru C-1, colturile sunt situate in casutele C-1, B-1, B-3, C-3. Suma algebrica este: 3 - 2 + 4 - 2 = 0

2 4

Pentru C-2, colturile sunt situate in casutele C-2, B-2, B-3, C-3. Suma algebrica este: 3 - 5 + 4 - 2 = 0

5 4

Analizand ciclul casutelor libere, se constata ca nu mai exista sume algebrice cu semnul minus. Aceasta inseamna ca planul de transport elaborat nu mai poate fi imbunatatit deci el reprezinta varianta optima. Constatam ca fata de volumul de transport prevazut in solutia de baza (14300 tone/Km), prin imbunatatirile aduse s-a ajuns la varianta optima (9400tone/Km). Problema de transport rezolvata face parte din categoria problemelor de tip echilibrat, in care volumul total disponibil la furnizori este egal cu volumul necesar la diferiti consumatori.

In practica se intalnesc situatii in care solutia de plan de transport contine mai putin de m+n-1locuri ocupate. In acest caz solutia obtinuta este degenerata. Pentru a elimina degenerarea si a face posibil calculul se pune zero intr-o casuta libera, considerand-o ca fiind ocupata, cu conditia ca in conturul poligonal ce se formeaza pentru efectuarea transferului casuta respectiva sa fie intr-un varf par.

De asemenea, sunt cazuri in care volumul disponibil total al furnizorului depaseste volumul necesarului total al consumatorilor. In aceasta situatie se introduce o coloana suplimentara corespunzatoare unui consumator fictiv, in care costurile unitare sunt egale cu zero, necesarul acestei coloane fiind egal cu diferenta dintre cantitatea disponibila si necesarul real la consumatori. Pentru rezolvare, folosim metoda prezentata anterior, in coloana consumatorului fictiv evidentiindu-se insa cantitatile care raman in stoc la furnizor.

In cazul cand volumul necesarului total depaseste volumul disponibilului total, solutionarea se face in doua variante: daca exista sau nu prioritati in repartizarea cantitatilor repartizate. Daca exista prioritati, se satisfac mai intai consumatorii cu prioritati, folosindu-se metoda cunoscuta de rezolvare.

Daca nu exista prioritati, se introduce in problema un furnizor fictiv care urmeaza a expedia o cantitate egala cu diferenta dintre volumul total necesar la consumatori si volumul real disponibil la furnizori, ajungandu-se astfel la cazul unei probleme de transport echilibrate ce se rezolva prin metode obisnuite.

PROBLEME DE TIP TRANSPORT PROPUSE SPRE REZOLVARE

Consideram problema de transport data de urmatorul tabel:

Disponibilul furnizorilor, necesarul beneficiarilor si costurile unitare de transport (in lei) sunt prezentate in tabel. Sa se intocmeasca planul optim de transport cu cheltuieli minime.

2. Se considera problema de transport pentru care datele sunt concentrate in tabelul de mai jos. Se solicita realizarea acelui plan de transport care sa fie optim avand drept criteriu de optimizare minimizarea cheltuielilor de transport (buc. Km).

NOTA: Coeficientii a_ij din tabel semnifica distantele de la depozitul i la intreprinderea j, in Km.

3. Fie problema de transport data in urmatorul tabel:

NOTA: Coeficientii a_ij reprezinta distantele de transport (Km).

4. In mod asemanator problemei nr. 3, consideram urmatoarea problema:

Coeficientii a_ij au aceeasi semnificatie ca in problema nr. 3.

Sa se intocmeasca planul optim de transport.