Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE





AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


PROGRAMARE LINIARA

algoritmi

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger
Metoda „backtracking”
Proiect ASDN - Algoritmul de minimizare Karnaugh
SISTEME EXPERT - Teoria si dezvoltarea sistemelor expert
Algoritmi speciali - Sortarea unui vector
Descrierea structurala
TEHNICI DE CAUTARE EURISTICE: Algoritm Generate-And-Test
ALGORITMI SI STRUCTURI DE DATE
ALGORITMUL HOOKE-JEEVES
Tehnici de programare structurata: Recursivitatea, Backtracking
Data mining cu Weka – Preprocesarea Datelor

PROGRAMARE LINIARA

1 CONSIDERATII GENERALE

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



-          un numar de restrictii liniare :

fi(x1,……..,xn)bi,               i=1,…,k,

fj(x1,……..,xn)=bj,               j=k+1,…..,p,                 (1)

fe(x1,……..,xn)be,              e=p+1,…..,m,

                     xk0,               k=1,2,…,n,

care exprima conditiile problemei ;

          - o functionala liniara, f(x1,……..,xn), 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=cj xj                             (2)       

                          j=1

                                                            4

                      

                                 n              

            aij xj = di ,              i=1,……,m;                           (3)

                            j=1         

                          xj   0,              j=1,……,n .                           (4)

           

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

                                                                                                       n

                           [max] sau [min] z=cj xj                             (5)      

                          j=1                      

                      

                                 n              

            aij xj = di ,              i=1,……,m;                           (6)

                            j=1         

                          xj   0,              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.

5

            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 0   ,   unde                                 (10)          

6


              a11 ………. a1n                                

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

                            j = 1, . . . . .,n              am1 ……… amn

           x1

X =     x2               ,  C = (c1, c2, … , cn)

                   

                     xn


                      d1

           d =     d2

                      

                     dn

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 0                                                                      (13)

7

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,

8

urmatoarele restrictii ale unui model de programare liniara:

x1 + 2x2 + x3 + 2x4 = 8

2x1 +   x2 + x3 + 3x4 = 9

            Solutia X1 =(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 X2 = (3  3 –3  1)t este o solutie nerealizabila a modelului, avand componenta x3 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 aj , j=1, . . . , n precum si vectorul b, al termenilor liberi. Cu aceste notatii, sistemul de restrictii (12) poate fi scris sub forma vectoriala (14), unde componentele x1, x2, x3, . . . . , xn, ale unei solutii oarecare X, sunt marimi scalare nedeterminate :

                  x1 a1 + x2 a2 + x3 a3 + . . . . . + xn an = b               (14)

9

In acest fel, fiecare componenta xj, j= 1, 2, 3, . . . . , n, a unei solutii, se ataseaza  unui vector coloana aj 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 Rm . Daca in solutia X numai componentele xj1, xj2, . . . , xjm 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 Rm, dupa care efectuam urmatoarele operatii:

10

-          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:

                            x1  +  x2 +   x3 +  x4 + 3x5 = 6,

                        x1 + 3x2 + 2x3 + 3x4 +  x5 = 12

Solutia X1 = ( 3 3 0 0 0 )t este o solutie de baza realizabila si nedegenerata, avand doua componente nenule pozitive, ce corespund la vectorii a1 si a2 din R2, si anume:


                                  1                                    1

                     a1 =       1       si            a2 =      3

11

Pe de alta parte, solutia X2 = ( 15 0 0 0 –3 )t este o solutie de baza nerealizabila si nedegenerata, ce corespunde bazei

B2 = . In sfarsit, solutia X3 = ( 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,  B3 = ,

B4 = 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.

12

            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 Cnm) 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

13

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 cj xj                                                          (15)

                                   n                           j=1

            (M)         a aj xj = b                                                  (16)

                                j=1

                            x ³ 0                                                           (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 a1, a2, . . . , am, baza insasi fiind notata cu B. Pentru sistematizarea calculelor, toti vectorii-coloana aj, j = 1,2,…,n precum si vectorul b al termenilor liberi in baza B, XB se pot trece intr-un tabel de forma celui ce urmeaza:                                

                                                    14

                                       Tabelul 1

CB

B

XB

c1

c2

C3. .

. . . .

. . . .

. . .

. . . .

. .cn

a1

a2

A3. .

. . . .

. . . .

. . .

. . . .

. .an

C1

a1

x1

g11

g12

g13 ..

. . . .

. . . .

. . .

. . . .

.g1n

C2

a2

x2

g21

g22

g23 ..

. . . .

. . . .

. . .

. . . .

.g2n

:

:

:

:

:

: ..

. . . .

. . . .

. . .

. . . .

..:

:

:

:

:

:

: ..

. . . .

. . . .

. . .

. . . .

..:

:

:

:

:

:

: ..

. . . .

. . . .

. . .

. . . .

..:

:

:

:

:

:

: ..

. . . .

. . . .

. . .

. . . .

..:

cm

am

xm

gm1

gm2

gm3

. . . .

. . . .

. . .

. . . .

gmn

fj

_

F1

f2

f3

. . . .

. . . .

. . .

. . . .

fn

            Astfel, baza este trecuta pe coloana marcata cu B, componentele fiecarui vector aj , 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 aj, j = 1,2,…,n, coeficientii cj din functia de eficienta, ce corespund variabilelor atasate acestor vectori. De asemenea, tabelul contine si o coloana suplimentara CB, cu coeficientii cj corespunzatori variabilelor

15

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.

CB = (c1,c2,…,cm)                                (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 aj,

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

                                             m

fj = a ck gkj , j=1,2,3,…,n.                           (19)

                                 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 fj se obtine practic prin insumarea produselor dintre fiecare element al coloanei CB si elementul corespunzator de pe coloana aj a tabelului

            Expresia matriceala a cantitatilor fj este deci urmatoarea:

16

fj = CB aj , 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 = 2x1+3x2+x3+4x4

                                    x1   +  x3+2x4=8,

 x2+2x3+x4=10,

xj 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.

CB

B

XB

2           3              1              4

a1               a2                     a3                   a4

2

3

a1

a2

8

10

1           0              1              2

0           1              2              1

Fj

–

2           3              8              7

            

f1= 2·1+3·0 =2 ; f2= 2·0+3·1 =3 ; f3= 2·1+3·2 =8 ; f4= 2·2+3·1 =7

17

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 cj - fj  [ 0, j=1,2,3,…,n, in cazul modelului de maxim respectiv fj - cj [ 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 Dj = cj - fj [ 0 pentru problema de maxim, respectiv  Dj = fj - cj [ 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 cj - fj > 0, in cazul unui model de maxim, respectiv fj - cj , 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.):

18

Tabelul 2.

CB

B

XB

c1             c2 . . . . . . . cm . . . . . . . cj . . . . . . . . cn

a1        a2. . . . . . . . am . . . . . . aj. . . . . . . . an

c1

a1

X1

g11            g12. . . . . . . g1m. . . . . . .g1j. . . . . . . g1n

c2

a2

X2

g21            g22. . . . . . . g2m. . . . . . .g2j. . . . . . .g2n

:

:

:

:            :                 :                 :                :

ci

ai

xi

gi1        gi2. . . . . . . gim. . . . . . . gij    . . . . . . gin

:

:

:

:            :                 :                 :                :

cm

am

xm

gm1          gm2. . . . . . .gmm. . . . . . .gmj. . . . . . gmn

Dj=cj-fj

c1-f1       c2-f2.. . . . . cm-fm . . . . .cj-fj       . . cn-fn

            Se observa ca, fata de tabelul 1, am renuntat la linia fj, inlocuind-o cu Dj.

            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 aj, caruia ii corespunde o diferenta Dj 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

19

care diferenta Dj = cj-fj >0, de preferat (dar nu obligatoriu) pe cel pentru care diferenta pozitiva Dj 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 ai 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 XB si coloana care intra aj, impartirea facandu-se numai la componentele strict pozitive ale lui aj si se alege raportul cel mai mic, pentru ca noua solutie sa aiba componentele nenegative.

Elementul gij, care apare incercuit in tabelul 2 si care se gaseste la intersectia coloanei vectorului aj, ce urmeaza sa intre in baza, cu linia vectorului ai, ce iese din baza B, se numeste ”pivot”.

Componenta yi, ce urmeaza sa ia locul componentei xi, 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”.

20

Urmatoarele expresii permit calculul componentelor noii solutii de baza Y :

                   xi  

      yj    =                                                                                  (21)

                   gij

                                    

         yk = xk - yjgkj = xk -  xi  gkj, pentru k=1,2,…,i-1,i+1,..,m   (22)



                                      gij

In legatura cu aceste relatii, se impun conditiile:

                                                  xi

                                                       0                                  (23)      

                                                  gij

xk gij - xi gkj

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

      gij

                         xi                                                                   gij

                                                                                                                                    Tabel vechi

                                   xk                                           gkj


                                xi

                        yj  =                                                                                           

                                gij

                                xk gij – xi gkj                                   Tabel nou

                        yk =

                                     gij                      

                  

Fig. 1 Calculul componentelor solutiei Y

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

21

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

         x1                                   g1j                                     x1/g1j

         x2                                   g2j                                       x2/g2j


   

         xm                                  gmj                                    xm/gmj

       

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

De remarcat este faptul ca acolo unde componenta gkj [ 0 raportul nu se face, iar dintre rapoartele ultimei coloane ne oprim la cel mai mic, acesta indicand linia vectorului ai 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.

22

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 fj, j=1,…,n, apoi diferentele Dj = cj - fj, in cazul modelului de maxim, respectiv Dj = fj - cj, 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 aj, a carui diferenta Dj 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 xi /gij, dintre care cel mai mic determina un vector ai, 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 ;

23

-          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 = 5x1+7x2+2x3+2x4

                               x1+3x2 - x3+0x4=40

                                     -x2+2x3+  x4=10

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

Completam urmatorul tabel:

CB

B

XB

5          7             2               2

a1              a2            a3               a4

5

2

a1

a4

40

10

1          3            -1               0

0         -1             2               1

/

Dj

220

0         -6             3               0

5

2

a1

a2

45

5

1         5/2           0             1/2

0        -1/2           1             1/2

/

Dj

235

0        -9/2           0            -3/2

24

            Deoarece pe linia diferentelor Dj, exista o diferenta strict pozitiva (c3-f3=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 a3 este negativa fapt ilustrat si in figura 3; urmeaza ca vectorul a4 este cel care trebuie sa iasa din baza;


  XB                                    a3

                                 40                                 -1                     –

                                 10                                  2                     5

Fig 3 Calculul rapoartelor xm/gmj

-          pivotul, incercuit in tabel, s-a determinat la intersectia coloanei a3 cu linia a4;

-          s-au inscris, in coloana B, vectorii ce formeaza noua baza, respectiv a1 si a3;

25

-          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 CB cu coeficientii c1 si c3, corespunzatori vectorilor din noua baza.

Componentele bazice ale noii solutii se citesc pe coloana XB, ele fiind urmatoarele: x1=45, x2=0, x3=5, x4=0. Prin urmare, noua solutie are forma urmatoare:

X=(45,0,5,0), iar Zmax=235

            Pentru testarea optimalitatii acestei noi solutii s-au calculat in tabel diferentele cj-fj. 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);

26

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 = 2x1+3x2+x3+4x4

                                        x1   +  x3+2x4=8

                                           x2+2x3 + x4=10

                                  xj ³ 0, j=1,2,3,4

27

            Completam urmatorul tabel:

CB

B

XB

2             3              4            1

A1            a2             a3          a4

2

3

a1

a2

8

10

1             0              1           2

0             1              2           1

/

Dj

46

0             0             -7          -3

            Sa explicam, pe scurt, cum s-au obtinut rezultatele pe linia Dj:         2·8+3·10=46

c1-f1=2-(2·1+3·0)=2-2=0

c2-f2=3-(2·0+3·1)=3-3=0

c3-f3=1-(2·1+3·2)=1-8=-7 etc.

Cum toate diferentele sunt negative sau zero, avem solutie optima finita (8,10,0,0), f max=46.

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

[max]f=2x1+x2+3x3+5x4+9x5

x1+2x3+x4+3x5=15

  x2+x3+2x4+x5=12

xj0, j=1,2,3,4,5

Construind tabelul simplex vom gasi pornind de la solutia de baza x1=15, x2=12, x3=x4=x5=0

28

CB

B

XB

2              1                 3                 5               9

a1             a2                a3                a4             a5

2

1

a1

a2

15

12

1              0                 2                 1               3

0              1                 1                 2               1

/

Dj

42

0              0                -2                 1               2

9

1

A5

A2

5

7

1/3           0               2/3              1/3            1

-1/3           1               1/3              5/3            0

/

Dj

52

-2/3           0            -10/3              1/3            0

9

5

A5

A4

18/5

21/5

2/5         -1/5            3/5                 0             1

-1/5          3/5            1/5                 1             0

/

Dj

267/5

-3/5         -1/5         -17/5                0             0

           

            Algoritmul simplex a luat sfarsit, solutia optima fiind xopt=(0,0,0,21/5,18/5), careia ii corespunde f max=267/5.

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

[min]f = 2x1+x2+3x3+5x4-x5

                2x1+x2+ x3            = 4

                  x1+     2x3+     x5 =  7

                 3x1+    2x3+x4      = 10

      xj0, j=1,2,3,4,5

29

CB

B

XB

2                1               3               5              -1

a1               a2              a3             a4              a5

1

-1

5

A2

a5

a4

4

7

10

2                1               1               0               0

1                0               2               0               1

3                0               2               1               0

/

Dj

47

+14             0                6               0               0

2

-1

5

a1

a5

a4

2

5

4

1               ½            1/2             0               0

0              -1/2            3/2             0               1

0              -3/2            1/2             1               0

/

Dj

19

0                -7              -1              0               0

            Dupa cum rezulta din tabel, pe linia Dj s-au facut diferentele fj-cj, deoarece este o problema de minim. Solutia optima este xopt=(2,0,0,4,5), caruia ii corespunde fmin=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

30

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.

31

            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

32

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 Dj, 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 = x1+2x2+2x3+x4

                                       x1+x2+2x3+ x4=10

2x1+ x2+2x3+2x4=12

 x1+3x2+2x3+2x4=16

xj0, j=1,2,3,4

            Modelul largit in cazul de fata va fi :

[min]f = x1+2x2+2x3+x4+MU1+MU2+MU3

                                      x1+  x2+2x3+ x4+U1=10

                                    2x1+  x2+2x3+2x4+U2=12

                                      x1+3x2+2x3+2x4+U3=16

                                      xj0, j=1,2,3,4, Uk 0, k=1,2,3

33

iar tabloul simplex corespunzator este:

CB

B

XB

1         2        2          1

M       M       M

a1        a2        a3          a4

U1      U2      U3

M

M

M

U1

U2

U3

10

12

16

1         1         2          1

2         1         2          2

1         3         2          2

1         0        0

0         1        0

0         0        1

/

Dj

38M

4M-1   5M-2   6M-2   5M-1

0         0        0

2

M

M

a3

U1

U2

5

2

6

1/2      1/2       1         1/2

1          0         0           1

0          2         0           1

1/2      0        0

           1        0

           0        1

/

Dj

8M+10

M     2M-1      0        2M

           0        0

2

1

M

a3

a4

U2

4

2

4

0        1/2       1           0

1          0         0           1

-1         2         0           0

                     0

                     0

                     1

/

Dj

4M+10

-M     2M-1      0           0

                     0

2

1

2

a3

a4

a2

3

2

2

1/4        0          1          0

1          0          0           1

-1/2        1          0          0

/

Dj

12

-1/2        0          0          0

           

Deci xopt=(0,2,3,2) si fmin=12

34

PROBLEME DE PROGRAMARE LINIARA PROPUSE SPRE REZOLVARE

 

1.      [max]f =2x1+x2+x3+3x4+2x5+9x6




 x1+x4+2x5+ x6  =10

 x2+x4+ x5+2x6  =20

 x3+x4+3x5+3x6=30

 xj0, j=1,2,3,4,5,6

R : xopt=(0,0,0,0,0,10) ; fmax=90

2.  [max]f=2x1+x2+3x3+5x4+9x5

      x1+2x3+ x4+3x5=15

      x2+ x3+2x4+ x5 =12

      xj0, j=1,2,3,4,5

R : xopt=(0,0,0,21/5,18/5) ; fmax=267/5

3.  [max]f=2x1+x2+6x3+5x4+7x5+11x6+3x7

      x1+ x3+  x4+  x5+3x6+2x7 =18

      x2+ x3+2x4+3x5+2x6+  x7 =24

xj0, j=1,2,3,4,5,6,7

R : xopt=(0,6,18,0,0,0,0) ; fmax=114

35

4.  [max]f=x1+x2+3x3+5x4+5x5+7x6

      x1+ x3+2x4+ x5+2x6=14

      x2+ x3+ x4+2x5+3x6=18

     xj0, j=1,2,3,4,5,6

R : xopt=(0,0,0,10/3,22/3,0) ; fmax=160/3

5.  [max]f=-x1+2x2+x3+3x4-x5-2x6

     x1+x2+2x3+3x5=15

     2x2+x3+x4+5x5=20

     x2+2x3+x5+x6  =10

     xj0, j=1,2,3,4,5,6

R : xopt=(5,0,5,15,0,0) ; fmax=45

6.  [max]f=x1+2x2+3x3+x4

                    1

     x1- x3+         x4=1

                    2

     x2+x3 - x4             =1

     xj0, j=1,2,3,4

 R : optim infinit

36

7.  [max]f=2x1+3x2+2x3

       x1+ x2+2x3 4

     2x1+ x2+ x3 2

      x1-3x2+2x3 5

      xj0, j=1,2,3

R : xopt=(0,2,0) ; fmax=6

8.  [min]f=5x1+2x2+x3+x4+3x5

     3x1+ x3+2x4 =20

      x1+ x2+3x4    =10

     5x1+ x4+ x5    =1

     xj0, j=1,2,3,4,5

                                                           R : xopt=(0,7,18,10) ; fmin=33

9.  [max]f=3x1+4x2+2x3+x4

     2x1+2x3+x410

     3x1+2x2+ x4 6

       x1+2x2+x3+4x4 12

      xj0, j=1,2,3,4

R : xopt=(0,3,5,0) ; fmax=22

37

10.[min]f=x1+2x2+2x3+x4

      x1+2x2+2x3+x4    =10

      2x1+x2+2x3+2x4 =12

      x1+2x2+2x3+2x4=44/3

      xj0, j=1,2,3,4

        R : xopt=(0,8/3,0,14/3) ; fmin=10

1[min]f=x1+2x2+2x3+x4

      x1+2x2+2x3+x4   =10

      2x1+x2+2x3+2x4=12

      x1+2x2+2x3+2x4=16

      xj0, j=1,2,3,4

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

12.[max]f=3x1+2x2+x3+5x4+2x5

     x1+2x2+x3+3x4+x5=10

     2x1+x2+x3+x4+3x5 =4

     xj0, j=1,2,3,4,5            

                                                R : xopt=(2/5,0,0,16/5,0) ; fmax=86/5

38

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 (U1,U2,U3). 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.

Denumire

utilaj

Timpul unitar de masina pe produs (min)

Timpul total disponibil pe grup de utilaj       (min)

A

B

U1

9

10

9000

U2

12

6

8400

U3

19

5

9500

Beneficiu

(u.m)

20

25

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

39

            Indicatie.  Modelul matematic al problemei este:

[max]f=20x1+25x2

9x1+10x2 9000

12x1+6x2 8400

19x1+5x2 9500

xj0, j=1,2

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

2. 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 – tij (min/set piese), fondurile de timp disponibile Tdi (min/luna) si beneficiul planificat – bj (u.m/set piese) sunt prezentate in tabelul de mai jos:

                 Tipuri de

                   produse

Gr. de                 ”j”

utilaje”i”

tij

Tdi

A

B

1

11

9

9900

2

7

12

8400

3

6

16

9600

bj

90

100

40

3. 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 (tig), fondurile de timp disponibile (Fdi) si beneficiul planificat (bg) sunt prezentate in tabelul de mai jos:

                  Tipuri de

                 subans.”g” 

Tipuri de

utilaje”i”

tig

Fdi

A

B

C

1

2

3

1

1

2

1

3

1

4

2

2

200

200

200

bg

20

30

50

4. 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.

41

Datele sunt sistematizate in tabelul de mai jos:

Tipul

barelor

Nr. procedeelor de debitare

Cantitatea necesara de piese (buc)

1

2

3

4

5m

1

0

0

0

20

3m

0

2

1

0

21

2m

1

0

2

3

22

Rest

0

1

0

1

5. 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 (tij), fondurile de timp disponibile (Fdi) si beneficiul planificat (bj). Datele sunt prezentate in tabelul de mai jos:

     Tipuri de               aparate

Ateliere           (j) (i)

tij(ore/aparat)

Fdi

(ore/luna)

A

B

C

D

1

2

3

15

25

10

35

20

15

15

9


20

2700

3100

1250

bj

120

150

160

50

42

6. 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 (tig) pentru fiecare tip de piesa si fondurile de timp disponibile ale grupelor de utilaje (Fdi) 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 (bg).

     Tipuri de piese

                        (g)

Grupa                de utilaje (i)

tig(ore/piesa)

tdi

(ore/sapt.)

a

B

c

d

1

2

3

4

0,5

2

4

2

1

0

4

4

4

2

1

0

0

6

1

1

130

180

240

200

bg(um/luna)

5

6

1

1

7. 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:

43

Lungimea

pieselor(m)

Posibilitati de debitare

Cantitatea necesara

1

2

3

4

5

6

4

3

2

2

0

0

0

2

1

0

0

4

1

1

0

1

0

2

0

1

2

30

32

31

Resturi

0

0

0

1

0

1

8. 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 :

               Norma de timp

                       unitara pe

                             utilaje

Produsul

A

B

C

D

P1

2

4

1

5

P2

4

1

2

1

P3

3

2

4

1

P4

6

8

6

2

Fondul de timp disponibil

400

380

410

390

44

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 cij xij                                (25)

 i=1  j=1

                        

                                                                                             

                               

                               

                                                

                                    

45

                                    n

                       a xij =  ai ,  i=1,2,…,m                            (26)

                                               j=1

                                  m    

                                 a xij = bj ,    j=1,2,…,n                          (27)

                                               i=1  

                                  m               n

                                 a ai = a bj                                           (28)

                                               i=1            j=1

xij 0                                                    (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.

46

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:

47

           Intreprinderi

Depozite

1

2

3

4

Cantitatea

disponibila

A

5

4

2

1

1300

B

2

5

4

5

1300

C

3

3

2

4

700

Cantitatea necesara

1000

1200

800

300

3300

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:

48

Depozite

Intreprinderi

Cantitatea existenta in depozite

1

2

3

4

A

5

4

2



1

1300

1000

300

B

2

5

4

5

1300

900

400

C

2

3

2

4

700

400

300

Cantitatea

nec. pe intrep.

1000

1200

800

300

3300

            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.

           

49

            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 :

50

m + n – 1                                        (30)

in care : m – numarul de furnizori

          n – numarul de consumatori.                                                          In exemplul de fata, m + n – 1 = 3 + 4 – 1 = 6.   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=1000Χ5+300Χ4+900Χ5+400Χ4+400Χ2+300Χ4=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

51

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

52

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: 1-4+5-4+2-4= -4

53

                         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 : 4-5+2-5= -4

                         5                      4

–                  + 

+                  –

                         2                      5

            Conturul poligonal al casutei B-4 are colturile in B-4, B-3, C-3, C-4. Suma algebrica este: 5-4+2-4= -1

                         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: 3-5+4-5+4-2= -1

54

                         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: 3-5+4-2=0

                         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.

55

            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.

56

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:

57

Depozite

Intreprinderi

Cantitatea

disponibila

1

2

3

4

A

5

4

2

1

1300

100

1200

B

2

5

4

5

1300

900

0

400

C

3

3

2

4

700

400

300

Cantitate

necesara

1000

1200

800

300

3300

 

            Volumul de transport in noua varianta este urmatorul:

100Χ5+1200Χ4+900Χ2+0Χ5+400Χ4+400Χ2+300Χ4=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= -1

58

                         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

                         4                      1

                         –                  +

                         +     –                                             

                       5        4

                                      +     –

                                     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= -1

                       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=3

                       2                       4

–                  +

+                  –

                       3                       2

59

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

                       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

                                      +     –

                                   700      0

60

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

Depozite

Intreprinderi

Cantitatea

disponibila

1

2

3

4

A

5

4

2

1

1300

100

900

300

B

2

5

4

5

1300

900

300

100

C

3

3

2

4

700

700

0

Cantitate

Necesara

1000

1200

800

300

3300

Volumul de transport in noua varianta este urmatorul:

100Χ5+900Χ4+300Χ1+900Χ2+300Χ5+100Χ4+700Χ2+0Χ4=9500

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= -1

61

                       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

                       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 = 3

                       2                      4

–                  +

+                  –

                       3                      2

            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 

–                  +

+                  –

                       3                      2

62

            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:

                       900                

–                  + 

+                  –

                       300              100          

            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:

63

Depozite

Intreprinderi

Cantitate

disponibila

1

2

3

4

A

5

4

2

1

1300

100

800

100

300

B

2

5

4

5

1300

900

400

0

C

2

3

2

4

700

700

0

Cantitate

necesara

1000

1200

800

300

3300

           

            Volumul de transport in noua varianta este urmatorul:

100Χ5+800Χ4+100Χ2+300Χ1+900Χ2+400Χ5+0Χ4+700Χ2+0Χ4==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

64

            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

–                + 

+                –

                       3                       2

            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

–                + 

+                –

                       3                       2

            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.

65

            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.

66

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:

Furnizori

Beneficiari

Disponibil

( t )

1

2

3

F1

2

1

3

7

F2

5

3

1

8

F3

2

4

3

5

Necesar ( t )

6

7

7

20

            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.

67

            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 aij din tabel semnifica distantele de la depozitul i la intreprinderea j, in Km.

Depozite

Intreprinderi

Disponibil

(buc.)

1

2

3

4

D1

8

3

5

2

10

D2

4

1

6

7

15

D3

1

9

4

3

25

Necesar (buc.)

5

10

20

15

50

            3. Fie problema de transport data in urmatorul tabel:

Furnizori

Beneficiari

Disponibil

( t )

1

2

3

4

F1

3

2

2

4

70

F2

1

2

3

4

10

F3

3

2

2

1

20

Necesar ( t )

50

25

15

10

100

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

68

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

                 Beneficiari, j   

Depozite, i

B1

B2

B3

Disponibil

( t )

D1

2

1

3

7

D2

5

3

1

8

D3

2

4

3

5

Necesar ( t )

6

7

7

20

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

Sa se intocmeasca planul optim de transport.








Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 673
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2019 . All rights reserved

Distribuie URL

Adauga cod HTML in site