Definitia,obiectul si scopul cercetarii operationale: metode deductiv-analitice si metode se simulare. Cercetarea este înteleasa nu ca o investigatie stiintifica ci ca o cautare. Cercetarea operationala este o metoda stiintifica de analiza logica si cantitativa a proceselor ce se desfasoara in organisme considerate in întregul lor si in strânsa interdependenta cu mediul lor înconjurator. Cercetarea operationala e o abordare stiintifica a rezolvarii problemei de conducere organizatorica. Cercetarea e un ansamblu e un ansamblu de metode si tehnici rationale de analiza si sinteza a fenomenelor de organizare in vederea elaborarii deciziei optime. Cercetarea operationala este aplicarea metodelor procedee si mijloace stiintifice in probleme legate de modul de functiune a unui sistem ce permite factorul de decizie care controleaza functiile sistemului sa gaseasca solutii optime pentru rezolvarea problemelor organizatorice. Obiectul cercetarii operationale il reprezinta pregatirea deciziei. Metode deductiv analitice se pot utiliza cand procesul studiat se exprima printr-un model matematic a carui structura si complexitate permit gasirea sau conceperea uniu algoritm de calcul ce conduce in mod riguros la obtinerea solutiei optime cautate. Din aceasta categorie fac parte teoria grafurilor jocurilor strategice, fenomenelor de asteptare. Specificul programelor matematice consta in optimizarea valorii unei functii de mai multe variabile numita functie obiectiv scop sau functie de mai multe variabile numita functie obiectiv, scop sau functie de eficienta. Pentru gasirea solutiei de extrem avantajoase sau neavantajoase in procesul modelelor. Pentru rezolvarea problemei se impune variabilelor din model sa satisfaca un anumit numar de de relatii descriptive specifice problemei analizate. La programarea matematica s-au individualizat o serie de metode particulare aplicabile in functie de caracterizarea functiei obiectiv si al restrictiilor. Astfel nu exista o metoda generala de rezolvare a programului matematic. Teoria grafurilor este utila in rezolvarea problemelor primind ordonarea unui numar finit de obiecte cu aplicatii in studiul organigramelor si schemelor de organizare a intreprinderilor si fluxurilor tehnologice si in rezolvarea de problemelor de transport si circulatie. Sta la baza analizei drumului critic. Teoria jocurilor strategice: conflictele cu scop de a stabili criterii si metode de adoptare a deciziilor optime in situatii de conflict cand se ciocnesc interesele unor parti. Teoria fenomenelor de asteptare aparuta din necesitatea ameliorarii efectului economic negativ al fenomenului de aglomerare in diverse puncte se servire. Metoda de simulare Utilizate cand particularitatile structural-functionale ale procesului studiat permit formalizarea metematica a problemei dar datorita complexitatii problemei prezentei elementelor cu caracter aleator nu exista sau nu se poate concepe un algoritm de rezolvare acceptabil. Simularea a fost stimulata de utilizatorul calculatorului. Prin simulare intelegem utilizarea unui model a unui sistem realizat astfel ca pe care experimentul prin modificarea sistematica a unor parametri functionali ai modelului sa obtinem informatii in ceea ce priveste structura impreuna cu modul de functiune al originalului. Cai de utilizare a simularii in silvicultura. 1) Realizarea de experimente pentru cunoasterea comportamentului unor sistem dimamic complex 2) Proiectarea sistematica prin stabilirea pe modele de simulare a parametrului structural-functional optiuni ce urmeaza apoi a se transpune practic 3) Prognoza evolutiei structurii si functionarii unor sisteme pe baza cunoasterii legilor ce determina aceasta evolutie 4) Realizarea de experimente pe modele ipotetice ale unor situatii reale in scopul formarii deprinderilor necesare adoptarii deciziilor in conditiile conducerii unor sisteme reale.
Modelul matematic general al problemelor de tip transport
in forma sa generala modelul problemei transporturilor se refera la o problema echilibrata in care totalul necesarului la cei n consumatori este egal cu totalul disponibilului la cei m furnizori adica : ∑ai =∑bj .Impunand conditia de a satisface intgral necesarul bj al fiecaruia dintre cei j consumatori , se pot formula o serie de restrictii de forma : ∑xij = bj (j = 1 ,2 . . , n) . Similar ,impunand conditia epuizarii disponibilului existent la fiecare furnizor se ajunge la m restrictii de forma : ∑xij =ai (i = 1,2 . . , m) . Modelul mai trebuie completat cu conditiile de nenegativitate : xij ≥ 0 ( i = 1,2,.m) si (j =1,2,.n) si cu functia obiectiv : f(x) = ∑ ∑ cijxij (min) sau (max) .Problema clasica de transport este de minimizare . In raport cu semnificatia valorilor cij , functia obiectiv poate fi insa si de minimizare . Sistemul de ecuatii liniare contine m x n necunoscute si m + n - 4 ecuatii liniar independente deoarece se respecta si conditia ∑ai =∑bj .Se ajunge astfel la un sistem compatibil nedeterminat care admite in principiu un nr foarte mare de solutii posibile obtinute prin rezolvarea sistemelor determinate identificate prin atribuirea de valori arbitrare unui numar de (m-1) (n-1) necumoscute .Se poate dovedi ca cel putin o solutie care minimizeaza valoarea functiei obiectiv se gaseste prin rezolvarea unuia din sistemele determinate ce se obtin din sistemul nedeterminat prin anularea a m x n -(m + n -1) necunoscute .O solutie de baza nedegenerata are un nr m + n - 1 componente strict pozitive si ( m-1 )(n-1 ) componente nule .Daca nr componentelor strict pozitive e < de m + n - 1 spunem ca solutia este degenerata .Metode de determinare a unei solutii de baza .O solutie de baza se poate obtine prin utilizarea unui algoritm ce consta in alegera intamplatoare la ficare pas a unei variabile strict pozitive xij careia i se atibuie valoarea maxima definita de relatiile : : ∑xij = bj (j= 1 ,2 . . , n) . ∑xij =ai (i = 1,2 m) .
adica xij =min .Toate celelalte variabile de pe linia i sau coloana j vor lua valoarea xij = 0 dupa cum ai≤bj sau bj≤ai Valorile ai sau bj se recalculeaza si devin : a'i=ai - bj daca bj<ai ; b'j=bj - ai daca ai<bj . Aceasta metoda poate fi particularizata prin alegera anumitor criterii de introducerea in solutia de baza a valorilor xij strict pozitive .procedeul coltului de nord vest Criteriul de alegere la fiecare pas a variabilelor strict pozitive care sa participe in solutia de baza este pozitionarea lor in celula din coltul de nord vest fie in tabelul initial fie in tabelele reduse ce rezulta prin eliminarea unei linii sau a unei coloane dupa cu m ai<bj sau .bj < ai .Totusi procedeul coltului de NV prezinta avantajul ca aplicarea lui are un caracter mecanic ceea ce permite realizarea unui program de calcul simplu in ipoteza prelucrarii electronice a datelor . Procedeul elementului minim pe linie .Pentru introducera variabilelor strict pozitive in solutia de baza se alege la fiecare pas al prelucrarii algoritmului pozitia corespunzatoare elementului minim din fiecare linie .Daca ai>bj se trece la pozitia corespunzatoare elementului imediat urmator ca valoare de pe aceeasi linie ; astfel se trece la o alta linie pana la atribuirea de valori tuturor celor m x n variabile .daca apar doua sau mai multe valori min egale se prefera mai intai pozitia cer permite realiz pe ruta respectiva a unui vol mai mare de transport .Avand la baza un criteriu economic solutia initiala obtinuta e de obicei mai apropiata de cea optima comparativ cu celelalte 2 procedee mentionate Procedeul elementului minim pe coloana .Se aplica in mod similar cu observatia ca analiza se realizeaza de data aceasta pe coloane. Procedeul elementului minim din tabel are drept criteriu de introducere al variabilelor strict pozitive in solutia de baza elementul minim din tabelul initial sau din tabelele reduse obtinute prin eliminarea la fiecare pas a unei linii (daca ai<bj) sau a unei coloane (daca bj<aj). Analiza facandu-se pe ansamblu, solutia astfel obtinuta este de obicei mai avantajoasa decat cele furnizate prin procedeele prezentate anterior. Variabilele strict pozitive s-au introdus in ordinea x22,x14,x21. Se constata ca in aceasta aplicatie solutia obtinuta coincide cu cea furnizata prin procedeul elementului minim pe linie.
Procedeul diferentelor maxime . Pentru fiecare linie si coloana se face diferenta dintre elementul imediat urmator ca valoare elementului minim si elementul minim. La fiecare pas se identifica diferenta maxima repartizandu-se in solutia de baza variabila corespunzatoare elementului minim care a generat diferenta maxima. Daca doua sau mai multe diferente maxime sunt egale se ia in considerare mai intai diferenta care provine din numere mai mici ; daca si acestea sunt egale, se prefera pozitia care permite realizarea unui volum mai mare de transport. Diferentele se recalculeaza la fiecare pas, fie pe linie, fie pe coloana. Desi ceva mai laborios, procedeul duce la solutii initiale mai apropiate de cea optima. Datorita caracterului obligat al repartizarii la ultimul pas se poate intampla ca uneori solutia astfel obtinuta sa fie mai dezavantajoasa decat cea obtinuta printr-un alt procedeu. Observatia este valabila si pentru celelalte procedee prezentate, ierarhia lor apreciata pe baza valorii functiei obiectiv, schimbandu-se de la o aplicatie la alta.
Algoritmi de optimizare reprezinta numai solutii initiale, pornind de la care, prin algoritmul de optimizare ales (metoda distributiva sau metoda distributiva modificata) se obtine in mod iterativ, prin imbunatatiri succesive, solutia optima.
3.. Metode de det a solutiei optime.Metoda distributiva.
Pt fiecare celula ocupata cu cantitati Xij strict pozitive se poate construi cate un singur contur poligonal de transfer cu laturi orizontale sau verticale,un nr par de varfuri,un singur varf intr-o celula cu Xij=0,iar toate celelalte varfuri in celule cu cantitati Xij strict pozitive. Dar nu pe toate contururile poligonale realizabile astfel se pot efectua transferuri avantajoase,care sa se soldeze cu reducerea valorii functiei obiectiv. Pt cunoasterea efectului transferului realizabil pe fiecare contur poligonal asupra functiei obiectiv se distribuie in mod alternativ semnele + si - varfurilor fiecarui contur poligonal,incepand cu + in varful cu valoarea Xij=o si se insumeaza algebric valorile Cij situate in varfuri,considerate cu semnul + sau - atribuit fiecarui varf. Se obtin astfel (m-1) (n-1) valori dij care indica efectul transferului pe conturul definit de celula din pozitia i , j a tabelului. Pt problema tipica de transport ,in care se urmareste minimizarea valorii functiei obiectiv,se alege drept contur favorabil conturul cu val dij minima. Cantitatea de transferat este val xij minima din varfurile cu semnul minus. Cantitatea de transferat se aduna la valorile xij situate in varfurile cu semnul + si se scade la valorile xij in varfurile carora li sa atribuit semnul -. In urma transferului se modifica pozitia celor ocupate cu valori xij nule si cu valori xij strict pozitive,ceea ce impune reluarea calculelor incepand cu determinarea de noi valori dij. Solutia optima in problema de minimizare se obt atunci cand toarte valorile dij sunt nule sau pozitive. Pt ilustrarea modului de lucru sa aplicam met distributiva pt modelul matematic pornind de la solutia initiala obtinuta prin procedeul coltului de n-v. Solutia optima se recunoaste prin faptul ca toate valorile dij sunt nule sau pozitive,deci nu mai exista nici un contur poligonal de transfer cu efect favorabil asupra functiei obiectiv.
4...Det sol optime prin metoda distributiva modificata.
Met distributiva se dovedeste a fi greoaie in aplicare atunci cand modelul contine un nr mare de furnizori si consumatori,deoarece se intampina greutati in identificarea si construirea fiecarui contur poligonal in vederea stabilirii semnelor atribuite varfurilor. Contururile pot avea forme pronuntat neregulate,chiar cu laturi intersectate ,intersectia nu se considera varf,iar nr mare de varfuri poate conduce la calculul eronat al valorilor dij. Avantajul metodei distributive modificate consta in posibilitatea determinarii anticipate a celui mai avantajos contur de transfer la fiecare iteratie ,fara necesitatea construirii fiecarui contur poligonal de transfer posibil. Pt fiecare celula ocupata cu cantitati xij strict pozitive se scrie cate o ecuatie de forma : Ui+Vi=Cij. Se ajunge astfel la un sistem in care numarul necunoscutelor depaseste cu unu nr ecuatiilor. Sistemul se rezolva prin atribuirea valorii arbitrare 0 uneia dintre necunoscute(U1=0). Pt fiecare celula ocupata cu valori xij nule se scrie cate o ecuatie de costuri comparative de forma : Eij=Cij-(Ui+Vj). Valorile Eij ,ca si cele dij indica efectul asupra functiei obiectiv obtinut prin realizarea transferului pe conturul poligonal definit de celula ocupata cu valoarea xij=0. analiza semnului si marimii costurilor comparative Eij permite identificarea la fiecare iteratie a celui mai avantajos contur precum si recunoasterea solutiei optime. Valoarea cu care se modifica functia obiectiv la fiecare iteratie rezulta din produsul Eij xt, unde xt este cantitatea de transferat pe conturul definit de celula situata in pozitia i,j.
Probleme de transport al caror model matematic are o structura speciala. Aplicatii de interes forestier. La formularea modelului matematic al unor probleme cu specific forestier se constata ca, desi este vorba de un model de transport, aplicarea metodelor de solutionare descrise este ingreunata de forma specifica in care se prezinta modelul. Probleme de transport neechilibrate . In modelul matematic general al problemei transporturilor se constata ca totalul necesarului este intotdeauna egal cu totalul disponibilului. Aceasta conditie de echilibru nu este insa respectata in modelele concrete care reflecta un anumit proces tehnioco - economic. Restrictia se prezinta in astfel de situatii sub forma : ∑ai ≠ ∑bj . Pentru rezolvarea problemei este necesara aducerea ei la forma echilibrata prin introducerea in modelul matematic a unui consumator fictiv de ordinul n + 1 (daca ∑ai > ∑bj) sau a unui furnizor fictiv de ordinul m + 1 (daca ∑ai < ∑bj). Pe coloana n + 1 corespunzatoare consumatorului fictiv s-au pus in evidenta m variabile de egalizare de forma xin+1 care vor prelua surplusul de disponibil: ∑xin+1 = ∑ai − ∑bj. Se ajunge astfel la o problema echilibrata in care este respectata conditia: ∑ai = ∑bj . Probleme de transport cu rute blocate si cu rute obligate. In unele siotuatii speciale de natura economica sau tehnica (deteriorarea unui pod, producerea de alunecari de teren) unele rute puse in evidenta in modelul matematic devin impracticabile si trebuie evitate. In alte situatii, anumite considerente privind desfasurarea procesului tehnologic pot impune parcurgerea obligatorie a anumitor rute chiar daca, sub aspect pur matematic, aceasta s-ar solda cu pierderi. Evitarea rutelor blocate se face prin substituirea distantelor de transport corespunzatoare lor cu distante fictive foarte mari in raport cu celelalte valori cij. Parcurgerea rutelor obligate se asigura substituind distantele respective cu valoarea fictiva zero. Probleme de transport cu centre intermediare. Atunci cand problema formulata initial nu este omogena sub aspectul mijloacelor de transport folosite ( transportul cu funiculare sau trasul cu vite la cioata la un depozit situat la un drum forestier, transportul cu mijloace auto pana la rampa de incarcare in vagoane, transportul pe calea ferata pana la fabrica de prelucrare) se constiutuie centre intermediare in locurile in care se face transferul materialului dintr-un mijloc de transport in altul. Astfel , problema initiala se descompune in doua sau mai multe probleme independente, omogene sub aspectul mijloacelor de transport folosite, in care aceleasi centre intermediare au pe rand rolul de consumatori, pentru o problema, sau furnizori, pentru problema urmatoare. Probleme de transport cu capacitati impuse. Datorita parcului de mijloace auto limitat utilizabil la efectuarea transporturilor, asigurarea aplicabilitatii solutiei optime presupune nedepasirea capacitatilor de transport impuse din considerente tehnico- economice pe anumite rute. In astfel de situatii, se repartizeaza in mod definitiv prin solutia initiala cantitatile de transport pe rutele cu capacitati impuse. Prin algoritmul de optimizare nu se vor lua in considerare contururile de transfer avantajoase care au varfuri situate in celulele corespunzatoare rutelor cu capacitati impuse. Probleme de transport care impun comasarea centrelor. In cazul in care problemele de transport sunt de mari dimensiuni, cu numerosi furnizori si consumatori, timpul necesar rezolvarii problemei creste foarte mult. Astfel, rezolvarea cu mijloace manuale a unei probleme cu 40 de parchete si 15- 20 depozite se face prin circa 50 de iteratii in aproape 100 de ore. In domeniul exploatarilor forestiere, la nivelul unui I.F.E.T. se pot intalni zeci si chiar sute de parchete, ceea ce impune comasarea centrelor. Prin acest procedeu, toate parchetele dintr-un bazinet sau dintr-o unitate de productie se comaseaza prin cumularea disponibilului si calcularea unor distante de transport medii ponderate cu volumul aferent fiecarui parchet. Se ajunge astfel la probleme cu dimensiuni rezonabile care pot fi solutionate rapid fie pe cale traditionala, fie prin utilizarea calculatoarelor electronice. Atunci cand este cazul comasarea se poate realiza si la nivelul consumatorilor. Probleme de transport care admit solutii multiple. La aplicarea algoritmului de optimizare se constata ca uneori apar valori dij sau Eij nule pentru celule ocupate cu cantitati xij nule. In aceste conditii, realizarea transferului pe ruta respectiva nu are nici un efect asupra functiei obiectiv, dar solutia se modifica prin schimbarea pozitiei necunoscutelor strict pozitive si a valorilor lor. Prezenta solutiilor optime multiple reprezinta de obicei un avantaj, deoarece la stabilirea solutiei care se va transpune in practica se pot lua in considerare si alte elmente nesurprinse initial in modelul matematic (starea drumurilor, declivitati, posibilitati de alimentare cu carburanti).
Degenerarea in problemele de tip transport.
O solutie degenerate are un nr de componente nule mai mare decat (m-1)(n-1). Degenerarea se manifesta prin faptul ca nu pt toate celule ocupate cu valori xij nule se pot construi contururi poligonale de transfer care sa prezinte valoarea xij=0 intr-un singur varf sau prin imposibilitatea solutionarii sistemului de ecuatii in Ui siVj atribuin unei singure necunoscute valoarea arbitrara 0. Posibilitatea aparitiei degenerarii se recunoaste in modelul matematic prin faptul ca totalul necesarului la unul sau mai multi consumatori este egal cu totalul disponibilului la unul sau mai multi furnizori. Degenerarea poate sa apara chiar ocazia determinarii solutiei initiale sau pe parcursul aplicarii algoritmului de optimizare atunci cand doua sau mai multe varfuri carora li sau atribuit semnul de - apar valori xij minime egale. Pt depasirea impasului legat de continuarea calculelor atunci cand se manifesta degenerarea trebuie stabilite care pozitii i,j corespund unor zerouri esentiale care apartin solutiei nedegemerate si care pozitii coresp unor zerouri neesentiale care in mod normal ar trebui ocupate cu cantitati xij strict pozitive. In acest scop se poate utiliza met perturbatiei care consta in substituirea unor val xij nule in nr egal cu zerourile suplimentare in rap cu solutia nedegenerate,cu valori pozitive infinit mici epsilon. In aceste cond pozitiile respective se pot considera varfuri nenule si pt ele putem formula si ecuatii in Ui si Vj. Dupa utilizare valorile epsilon se egaleaza cu zero. Degenerarea poate sa dispara pe parcursul efectuarii iteratiilor atunci cand valorile epsilon sun situate in varfuri cu semnul + ale conturului poligonal de transfer avantajos. Pe parcursul aplicarii algoritmului de optimizare uneori degenerarea se poate manifesta din nou.
Reoptimizarea problemelor de tip transport Modelul matematic al problemelor de tip transport exprima analitic procese tehnico-economice sau organizatorice ale caror particularitati sunt exprimate cantitativ asa cum se prezinte ele la un moment dat. Datorita caracterului dinamic al proceselor studiate o serie de parametri surprinsi initial in modelul matematic sufera modificari care pun la îndoiala optimalitatea solutiei initiale. In aceste conditii problema modificata poate fi tratata ca o problema noua independenta de cea initiala. Rezolvarea ei aplicând metoda distributiva sau metoda distributiva modificata duce la gasirea noii solutii optime renuntându-se la volumul mare de calcul necesar pentru solutionarea problemei initiale dar angajându-ne totusi la calcule laborioase. Prin reoptimizare se întelege determinarea solutiei optime a unei probleme al carei model matematic difera prin cel putin un parametru de modelul al carui optim se cunoaste prin care studiul efectelor modificarilor survenite asupra optimalitatii solutiei problemei initiale. REOPTIMIZAREA IN CAZUL MODIFICARIIVALORILOR CIJ Pentru reoptimizarea problemelor in al caror model matematic survin astfel de modificari se porneste de la solutia de baza optima evidentiata in ultimul tabel obtinut prin aplicarea metodei distributive sau a metodei distributive modificata. In acest tabel se opereaza modificarile care au aparut prin înlocuirea valorilor CIJ initiale co noile valori precizate si se recalculeaza valorile GIJ si EIJ . In urma recalcularii pot aparea doua situatii: 1) noile valori GIJ sau EIJ raman in continuare nule sau negative in problema de maximizare respectiv nule sau pozitive in problema de minimizare; solutia optima a problemei initiale ramane valabila in continuare modificându-se doar valoarea optima a functiei obiectiv daca valorile CIJ modificate apar in celule cu valori XIJ strict pozitive. 2) In urma recalcularii se intalneste cel putin o valoare EIJ sau GIJ negativa la problemele de minimizare sau pozitiva la cele de maximizare. Se continua iteratiile pornind de la ultimul tabel al problemei initiale in care se opereaza modificarile survenite pana când criteriul de optimalitate este din nou satisfacut.
8... Formularea modelului matematic general al unei probleme de programare liniara. Moduri de prezentare a modelului. Reguli de aducere a modelului la forma dorita.Sub forma sa algebrica modelulmatematic al problemei de programare liniara se prezita astfel :a11x1+ a12x2+....+a1jxj+...+a1nxn=b1 ; a21x1+a22x2+...+a2jxn=b2 ; am1x1+am2x2+....+amjxj+.+amnxn=bm. xj≥0. f(x)=c1x1+c2x2+.+cjxj .+cnxn ,max sau min.Sistemul formar din m ecuatii si n necunoscute repr restrictiile problemei. Prin relatia,xj≥0 sau formulat conditiile de nenegativitate impuse de interpretarea concreta economica sau tehnica a solutiilor. Functia obiectiva este reprez matematic prin relatia f(x)=c1x1+c2x2+.+cjxj .+cnxn . Valorile aij repr coef tehnici constanti planificati sau determinati direct sau pe cale statistica prin cuantificarea unor relatii specifice procesului modelat. Valorile xj desemnaza necunoscutele problemei iar coef bj sunt marimi constante obt prin modelarea a procesului studiat. Functia obiectiv care exprima matematic scopul urmarit prin rezolvarea problemei poate fi de maximizare sau de minimizare. Modelul matematic prezentat prin relatiile : ai1x1 +ai2x2+...+aijxj+ +ainxn=bi ; f(x)=c1x1+c2x2+.+cjxj .+cnxn este in forma standard caracterizata prin faptul ca toate restrictiile sunt ecuatii si toate variabilele sunt nenegative. Forma algebroca restransa a modelului matematic general al problemei se poate exprima astfel :sa se det maximul(minimul) functiei :f(x)=Σcjxj ; daca au loc relatiile restrictive :Σaijxj=bi ;xj≥0. Matricial modelul matematic al problemei se poate scrie :Ax=b ;x≥0, f(x)=c'x . Sub forma sa vectoriala modelul matematic al problemei de programare liniara se prezinta astfel ΣPjxj=P0 ;xj≥0,f(x)=Σcjxj. In modelul de mai sus Pj repr vactorii coloana ai coef necunoscutelor xj iar P0 vectorul coloana al termenilor liberi din restrictie. Pron formularea modelelor matematice ale unor probleme concrete nu se ajunge in totdeauna la structura specifica formei standard deoarece unele restrictii se pot prezenta ca inecuatii. Daca modelul problemei este privit dintr-un punct de vedere pur matematic se poate renunta si la cond de nenegativitate. In functie de sensul inecuatiilor restrictive din modelul matematic si de caracterul functiei obiectiv deosebim :restrictii concordante si neconcordante. Numim restrictii concordante toate restrictiile de sensul ''≤'' pt problemele de maximizare si de sensul ''≥'' pt problemele de minimizare. Forma canonica a modelului matematic al unei probleme de programare liniara se caract prin faptul ca are toate restrictiile concordante si toate variabilele nenegative. Prin urmare in rap cu caracterul functiei obiectiv se pot identifica urmatoarele doua forme canonice :Ax≤b,x≥0 , f(x)=c'x si Ax≥b, x≥0 , f(x)=c'x. Pt rezolvarea problemei modelului matematic trebuie adus intr-o forma ordonata. In acest scop se pot utiliza urm transformari:1) o inegalitate este echivalenta cu o egalitate si o cond de nenegativitate prin introducerea unei variabile de egalizare xe astfel :ax≤b devine ax+xe=b,xe≥0 ; ax≥b devine ax-xe=b,xe≥o. 2) o ecuatie se poate transforma in doua inecuatii de sens contrar astfel:ax=b devine ax≥b si ax≤b.3)sensul unei inecuatii se poate schimba prin inmultirea cu -1. 4) o variabila nepozitiva se poate substitui cu o variabila nenegativa prin rel:x'=-x unde x≤0 si x'≥0. 5) putem gasi oricand doua valori x1 si x2 astfel ca intr-un model in care apare o variabila x de semn oarecare sa fie respectata cond de nenegativitate utilizand relatia :x=x1-x2, unde x1≥0 si x2≥0. 6) caracterul unei functii obiectiv se poate schima prin transformarea :min[f(x)]=-max[-f(x)].
__________ ______ ____ _______
Metode de determinare a unei solutii de baza admisibile. Daca rangul matricei A este m iar m<n o solutie de baza admisibila se obtine din m vectori coloana liniari. Acesti vectori alcatuiesc un sistem de referite sau coordonate specifice fiecarei solutii de baza. De aceea componentelor tuturor celorlalti vectori care nu participa in baza B se recalculeaza in raport cu vectorii din baza. Daca baza aleasa este chiar matricea unitate M recalcularea nu mai este necesara. Explicatia consta in faptul ca in matricea unitate fiecare vector este versor adica unitar in raport cu axa proprie. De aceea practic daca restrictiile specifice problemei nu permit identificarea matricei unitate M se pot introduce m variabile artificiale Xa si se asociata lor matricea unitate. Introducerea unei baze artificiale complica structura modelului initial dar ne scuteste de recalcularea componentelor vectorilor din afara bazei in raport cu baza aleasa. De aceea uneori când nu dorim sa complicam structura modelului matematic se poate proba la recalculare. In determinarea unei solutii initiale de baza se poate aplica si metoda celor doua faze.
10.. Teoreme de baza ale alg simplex. Forma gen a tab simplex. Reguli practice de aplic a alg simplex.Alg simplex are la baza 4 teoreme prin care se limiteaza spatiul cautarilor pt gasirea sol optime in multimea de sol posibile si se precizeaza criteriul de optimalitate ce permite recunoast. sol optime.1) daca o problema de programare liniara are o sol optima atunci ea are si o sol de baza optima(sol optima se gaseste printre sol de baza, teorema ingusteaza spatiul de cautare a sol optime la un nr finit de sol de baza)=> ca e suficient sa analizam prin efectul lor asupra fct ob toate sol de baza posibile si sa identificam baza coresp valorii sol optime.2) orice solutie de baza a unei probleme de programare liniara reprez. un pct de extrem al multimii sol posibile si invers (orice pct de extrem al multimii sol reprezinta o sol de baza) deoarece multimea sol posibile real totdeauna un poligon convex.(se dau patru inecuatii si se determina 4 drepte care marginesc un poligon). Sol optima se afla in unul din cele 6 colturi: matricea m linii si n coloane =>Cmn 3) pornind de la o baza admisibila coresp unei sol neoptime se poate det o baza noua cu o val a fct obiectiv mai apropiata de cea optima care difera de baza precedenta printr-un sg vector coloana. 4) criteriul de optimalitate e val dif:Dj=Cj-Zj Cj=coef necunoscutelor din fct ob Zj= produselor dintre comp fiecarui vector coloana al matricei A si coef din fct ob ai necunosc. ce participa in baza cu val strict >0> Sol optima se recunoaste prin faptul ca in problema de maximizare toate val Dj trebuie sa fie =0 sau <0 iar in cea de minimizare sa fie =0 sau >0. Dj indica efectul asupra fct ob obtinut prin introd in baza a oricarui vector Pj.Cantitatea exacta cu care se modif fct ob in urma introducerii in baza a oricarui vector Pj se obtine cu rel: Ij=Dj*min(P0/Pj)(min >0 dintre comp vectorului col al termenilor liberi raportat la componentele vectorului ce intra in baza.) Se pot formula 6 reguli de aplicare a alg simplex: 1) se testeaza optimalitatea sol initiale prin analiza semnului diferentelor Cj-Zj (conf teor 4) daca sol initiala nu este optima se aplica regulile 2-6. 2) se det care vector din afara bazei (vector col Pj cu m+1 j n are efectul cel mai favorabil asupra fct ob prin introd lui in baza;indiatii in acest sens dau Dj iar masura modif fct ob este data de Ij; de aceea ,la fiecare iteratie intra in baza vectorul col cu Ij max pozitiv la maximizare si invers. 3) se det care vector iese din baza prin identificarea pe coloana vectorului care intra in baza a raportului min pozitiv dintre componentele vect Po si cele ale vect care intra in baza(Pj). Elementul de pe col vect Pj care intra in baza coresp rap min pozitiv se numeste elem pivot . 4) se completeaza matricea unitate E in ordinea coloanelor indicata de participarea vectorilor in noua baza. 5) toate componentele situate pe linia elementului pivit se impart la valoarea acestuia. 6) toate celelalte comp ale vectorilor coloana se recalculeaza dupa regula dreptunghiului definit de elementul de recalculat si elem pivot astfel: val recalculata este dif dintre val initiala si rap dintre prod componentelor de pe diagonala care nu contine elem pivot si elementul pivot. (aplicatie.
11.. Dualitatea in probleme de programare lineara. Proprietati . Dualitatea, principiu fundamental in matematica, permite identificarea pentru orice problema de programare lineara a unei probleme noi a carei structura si solutionare sunt foarte strans legate de cele ale problemei initiale. Cele doua probleme construite pe baza principiului dualitatii constituie o pereche de probleme conjugate. Rezolvarea problemei duale permite, in afara verificarii corectitudinii calculelor prin aplicarea algoritmului simplex problemei initiale, obtinerea solutiei optime pentru problemele in care modelul matematic are o structura deopsebita (m >> n) printr-un numar sensibil mai mic de iteratii. Dupa structura modelului matematic deosebim : a) probleme dual simetrice : Ax ≥ b x ≥ 0 f(x) = Cx (min) ; YA' ≤ C Y ≥ 0 f(Y) = Yb (max) ; b) probleme dual nesimetrice : Ax = b x ≥ 0 f(x) = Cx (min) ; YA' ≤ C Y = oarecare f(Y) = Yb (max). Se constata ca perechea de probleme conjugate are urmatoarele proprietati : 1) oricare dintre cele doua probleme poate fi considerata duala celeilalte sau primala este duala dualei ; 2) numarul variabilelor din problema primala este agal cu numarul restrictiilor din problema duala si invers ; 3) componentele vectorului coloana al termenilor liberi (b) din problema primala formeaza coeficientii necunoscutelor din functia obiectiv a dualei si invers ; 4) coeficientii din restrictii ai necunoscutelor din problema duala se obtin prin transpunerea matricei coeficientilor necunoscutelor din restrictiile problemei primale ; 5) variabilele duale corespunzatoare unor restrictii primale concordante sunt nenegative, cele corespunzatoare unor restrictii neconcordante sunt nepozitive, iar cele corespunzatoare unor restrictii sub forma de egalitati sunt de semn oarecare; 6) unor variabile primale nenegative le corespund restrictii duale concordante, unor variable primale nepozitive le corespund restrictii neconcordante, iar unor variabile de semn oarecare le corespund restrictii sub forma de egalitati. Se demonstreaza ca daca una din problemele conjugate are cel putin o solutie optima, atunci si perechea ei va avea cel putin o solutie optima si ca maximul functiei obiectiv al unei probleme este egal cu minimul functiei obiectiv al problemei conjugate. Evident fiind vorba de probleme diferite, unde interpretarea economica a solutiilor si semnificatiile atribuite variabilelor sunt deosebite, si solutiile gasite prin aplicarea algoritmului simplex sunt diferite. O caracteristica importanta o constituie insa posibilitatea identificarii solutiei optime a problemei duale in ultimul tabel simplex al problemei primale. De aceea, daca se considera mai avantajoasa din punct de vedere practic rezolvarea problemei duale, se pot obtine usor solutiile problemei initiale, aplicand algoritmul simplex prin primal problemei duale. Legatura stransa intre problemele conjugate a condus la elaborarea unor metode specifice de rezolvare, dintre care amintim algoritmul simplex dual si algoritmul simplex primal- dual. O solutie optima este realizabila atat primal cat si dual. Algoritmul simplex dual este dintr-un anumit punct de vedere dualul algoritmului simplex primal. Se porneste de la o baza dual admisibila care evident nu este primal admisibila. Se determina mai intai variabila care iese din baza, alegandu-se variabila pentru care nu este satisfacuta conditia de nenegativitate, apoi variabila care intra in baza prin raportul minim facut insa cu una din componentele negative. Dupa determinarea noii baze se face un pivotaj dupa care se testeaza optimalitatea solutiei si eventual se reiau calculele. Prin eliminarea treptata a componentelor nenegative se ajunge in final la o solutie admisibila atat dual cat si primal care este chiar solutia optima. Algoritmul primal- dual se aplica in acelsi timp atat problemei primale cat si celei duale. Prin aplicarea algoritmului se determina simultan solutia optima pentru cele doua probleme conjugate pe baza teoremei ecarturilor complementare.
12...Degenerarea
in probleme de programare liniara : O
sol degen are un nr de componente(+) ca rangul matricei A. Aparitia degenerarii conduce
practic la imposibilitatea aplicarii alg de optimizare.Vectorii coloana bj ai
mod matem determina intr-un spatiu Rm un con poliedric convex al
conditiilor.Pozitia vect Po in conul poliedric al conditiilor indica dpdv geom
prezenta sau absenta degenerarii.Astfel cand Po se afla in interiorul conului
poliedric al cond problema nu este degenerata.Degenerarea se poate incadra in
unul din urm 3 tipuri:1)vectorul Po se suprapune peste una din muchiile
poligonului conv al cond. 2)vect Po se suprapune peste
una din fetele conului poliedric al cond. 3) rangul matricei A este< decat
nr restrictiilor. Cazuri de degenerare:
1) vectorul Po se suprapune pe una
din muchiile conului poliedric convex al sol.: vectorul Po este coliniar cu
unul din vectorii coloana ai matricei A si trece prin unul din varfurile
conului poliedric convex al solutiilor .In modelul matem situatia se recunoaste
prin faptul ca Po are comp prop cu cele ale unui vector coloana Pj.Degenerarea
se manifesta pe parcursul aplicarii alg simplex prin aparitia la determ
vectorului ce iese din baza a 2 sau mai multe valori min pozitive egale ale rap
Po/Pj ,fiind imposibila det vect care iese din baza.Pt cont calc se poate
folosi metoda perturbatiei (metoda e) sau metoda lexicografica. Metoda perturbatiei consta in deplasarea vect
Metoda lexicografica permite stabilirea vect care iese din baza prin analiza rapoartelor dintre componentele vectorilor problemei luate pe linie in ordinea in care apar in tabelul simplex si componentele vectorului care intra in baza.Iese din baza vect corespunzator sirului de rapoarte in care se realizeaza mai repede o val algebrica minima. vectorul Po se suprapune peste una din fetele conului poliedric convex al cond. In modelul matem degenerarea se recunoaste prin faptul ca Po are una sau mai multe componente nule.Daca vect Po are o sg componenta nula ,la determinarea vect care iese din baza se ia ca rap min pozitiv valoarea 0.Daca nr comp nule ale lui Po este>1 apar 2 sau mai multe val minime egale cu 0 ale rap Po/Pj unde Pj este vectorul care intra in baza ,neputandu-se stabili vectorul care iese din baza =>se aplica metoda e sau met lexicografica.3) rangul matricei A este mai mic decat nr restrictiilor ;rang A<m=>doua sau mai multe restrictii au comp prop..Met de rezolvare: se introduce o baza artif si asociata ei o matrice unitate de rang m (dupa care se aplica alg simplex).Identificarea restrictiilor care sunt combin liniare si eliminarea restrictiilor mai putin puternice ajungandu-se la un model nou simplificat in care opereaza numai cele mai puternice restrictii prin eliminare :=>rang A' =m'.
13...Reoptimizarea problemelor de programare lineara in cazul modificarii componentelor vectorului coloana al termenilor liberi sau al coeficientilor necunoscutelor din functia obiectiv
modelul matematic formulat la un moment dat este expresia matematica a unor realitati de natura tehnico-economica asa cum se manifesta ele la un moment dat. Natura complexa a proceselor modelate face ca valorile coeficientilor prin care se exprima cantitativ relatiile dintre componente sa fie supuse unor modificari legice sau intamplatoare. Pot sa apara variabile suplimentare dupa cum se poate restrange numarul variabilelor si a restrictiilor. Se pot modifica componentele vectorilor Pj Po sau coeficientii necunoscutelor din functia obiectiv. In aceste cazuri se ajunge la un model matematic nou. Acesta poate fi tratat si rezolvat ca un model fara legatura cu problema initiala renuntandu-se astfel la volumul mare de calcule implicat la rezolvarea problemei initiale. O a doua varianta de abordare consta in reoptimizarea solutiei problemei initiale. Prin reoptimizare se intelege determinarea solutiei optime a unei probleme al carei model matematic difera prin cel putin un parametru de model al carui optim se cunoaste prin analiza efectelor modificarilor survenite asupra optimalitatii solutiei problemei initiale.
Reoptimizarea in cazul modificarilor coeficientilor necunoscutelor din functia obiectiv
Ax=b, x≥0, f(x Cx(max) sau (min) C'=C+ΔC. In acest caz in tab simplex se va modifica criteriul de optimalitate Δj=Cj-Zj. Analiza se face in ultimul tabel simplex al problemei initiale (Cj-Zj)'=Cj-Zj+CBl/Bb-ΔCBl/B+ΔCj .Δ j'=Δj+ΔΔj. Δj' respecta in continuare criteriul de optimalitate desi valorile numerice raman nemodificate. In acest caz solutia optima a problemei initiale ramane valabila in continuare modifica doar
Functia obiectiv f'(x)=(C+ C)Bl/Bb. Pentru reoptimizare se lucreaza cu ultimul tabel simplex al problemei initiale in care se modifica val coeficientilor nec si se recalculeaza criteriul de optimalitate. Al 2-lea caz recalc val Δj pt modificarile survenite in coefic Cj ai necunoscutelor din fucntia obiectiv se consulta ca pt cel putin un vector coloana criteriul de optimalitate nu este satisfacut. In acest caz pornind de la sol optima a probl initiale se opereaza modificari in ultimul tabel simplex si se continua iteratiile pana la obtinerea noii solutii optime. Volumul de calcul este sensibil mai mic decat in alternativa tratarii probl modific ca fiind o problema noua.
Reoptimizarea in cazul modificarilor componentelor vectorului coloana Po b'=b+ΔbxB=1/Bb, x'B=1/Bb' b+ΔB) x'B=1/Bb+1/BΔB x'B=Xb=ΔXb. Criteriul de optimalitate Δj=Cj-Zj nu este afectat de modificarile componentelor lui b astfel incat solutia optima initiala si solutia modif satisfac in continuare criteriul de optimalitate. In reoptimizare se pot intalni 2 situatii: 1)componentele noii solutii x'B respecta in continuare conditiile de nenegativitate. Noua solutie optima sa va det cu relatia x'B=1/Bb', iar noua valoare a fctiei obiectiv va fi f'(x CBl/Bb'. Matricea B este alcatuita din vectorii care participa in baza optima a problemei initiale, dar cu componentele luate din forma standard a modelului matematic.
Algoritmul Simplex: B=matrice,
b'=matrice. Etape 1) se determina matricea transpusa Btaw 2)se
obtine matricea B* 3)se obtine matricea 1/B=B*/detB, se inmulteste 1/B cu b'
II)desi criteriul de optimalitate nu este afectat noua sol fiind aparent optima
ea nu este admisibila deoarece are cel putin o comp neg. in cazul in care nu se
respecta cond de nenegativitate se aplica in continuare algoritmul simplex dual
pt care o sol admisibila poate sa contina si elemente negative. O alta var a reoptimizarii in cazul modif matricei b consta in
formularea modelului matern dual in care comp vectorului
14...Modelul matematic generalal problemei sortarii primare a materialului lemnos
|
sortimentul |
Lumgimea |
Necesar(buc) |
|
S1 S2 Si Sm |
L1 L2 Li Lm |
N1 N2 Ni Nm |
Materialul lemos apt pt realizarea acestor sortimente a fost grupat pe categorii de lungime. Pt fiecare categorie se poate formula cate un model matematic distinct. In continuare abordam problema pt una din aceste categorii pentru care lungimea trunchiurilor apta pt realizarea sortim impuse este L. prima etapa in rezolvarea problemei consta in analiza variantelor posibile de debitare. S-au ridicat n variante. Notam cu aij nr de bucati din sortimentul l obtinute prin varianta de debitare i.
15...Modelul matematic pentru optimizarea transportul agregatelor minerale din balastiere
pentru realizarea unor betoane speciale se recomanda ca agregatele sa aiba o compozitie si granulatie. Statia de betoane poate fi aprovizionata de la 4 balastiere care livreaza material in urmatoarele proportii : x1 x2 x3 x4-proportia in care trebuie adus materialul de la cariera 1234. nu se admit alte functii sau alte surse de aprovizionare. X1+x2+x3+x4=1. Xij≥0 j=1 . Beneficiile obtinute prin furnizarea de material de la cariera sunt : B1 B2 B3 B4 f(x)=∑BjXj(max) Elementele care participa i,j=1.2...n -nr de ordine al unitatii amenajistice j=1.2...m -indicele perioadei in care se face recoltarea j=5.10 sau 20 si=suprafata u a.i. vi=vol la ha al arboretelor din u.a.i care se poate exploatat in perioada j. Cij- reprez cresterea curenta a arboretului i in perioada j Xijreprezinta suprafata din u a. i. care se poate recolata in perioada j ; bij-reprezinta sacrificiul de exploatabilitate al arboretului i in ipoteza recoltarii lui j. Pij=venitul obtinut din recoltarea arboretului i in perioada j. ∑xij≤Si, i=1.2...n.
Modelul matematic pentru determinarea
posibilitatilor de produse principale la codru regulat ; variante de
formulare a functiei obiectiv numarul de ordine al unitatii al unitatii
amenajistice i,i=1,2,.,n j-indicele perioadei la care
se recolteaza arboretul i j=1,2,.,m si=suprafata
unitatii amenajistice. Volumul la hectar al arboretului i care se poate
exploata in perioada j . cij=cresterea curenta a arboretului in perioada
p. bij=sacrificiul de
exploatabilitate in ani prin taierea arboretului i in perioada j. pij=sentimentul
obtinut din srboretul i din exploatarea lui in perioada j. 
Xij>=0
i=1,2,...n j=1,2,..m
17...Modele matematice pentru determinarea compozitiei tel a arboretelor -intr-o UP s-a identificat prin cartare de tipuri de statiune pe care se pot cultiva specii. Sa se determine supraf de cultivat cu fiecare specie pe fiecare tip de statiune a.i. sa se realizeze cel putin cantitatea de material lemnos tj prognozate pt fiecare specie iar beneficiul total obtinut Cij sa fie maxim. Speciile trebuie astfel cultivate incat sa nu se depaseasca supraf bi disponibile pt fiecare tip de statiune i. in principiu beneficiile Cij sunt legate de valorile pij care reprezinta cresteri medii la hectar al productiei totale la varsta exploatabilitatii pe tipurile de statiune i=1.2.n cu speciile j=1.2.m; f(x)=∑∑CijXij (max) xij≥0 j=1.2.m; i=1.2.n ∑Xij≤bi; i=1.2.n; ∑PijXij≥tj j=1.2.n b)o alta abordare a problemei consta in analiza consumului de substante nutritive si microelemente a speciilor forestiere cunoscand disponibilul fiecarui tip de statiune pe de o parte si solicitarile economice fata de cantit de masa lemnoasa. Speciile trebuie astfel alese incat consumul de substante nutritive realizat sa nu depaseasca potentialul nutritiv al statiunii. Ca obiectiv se urmareste fie maximizarea consumului de substante nutritive fie minimizarea diferentei dintre cantitatea de substante nutritive disponibile si consumate.
18...Modelul matematic pentru determinarea amplasamentului optim al investitiilor
la un moment dat in zona de lucru a unei firme exista munitati de productie si se urmareste crearea de noi unitati de productie in r. Unele pct pot sa coincida cu cele existente deja ceea ce echivaleaza cu extinderea capacitatii de productie a unitatilor existente a.i. capacitatea max de productie fiecarei unitati r+1.2....m, m+1.....m+r ; bj-necesarul de produse in cele n centre de consum ; pi-pretul de cost unitar relzultat in unitatea i propusa ; Ii-investitia specifica pt unitatea de productie licu volori nule pt i=1.2...m si cu li>0 pt i=m+1, m+2,...m+r. Cij-pretul de cost unitar al transportului pe ruta i,j cu i=1,2...m+r, j=1,2....n ; En-coeficientul normat al eficientei economice a investitiilor. Daca notam Xij cantitatea de produse de la furnizorul i la consumatorul j, functia obiectiv urmareste minimizarea costurilor de productie, investitii si transporturi. F(x)=∑ pi+liEn+Cij)Xij(min) ∑Xij=bj, j=1.2..n ∑Xij=ai i=1.2...m+r Xij>0 i=1.2...m+r j=1.2...n
Teoria fenomenului de asteptare: exista situatii cind sunt anumit e aglomerari in puncte de servire => nu intregul fond de timp este utilizat pt. productie. Intr-un proces de asteptare participa urm. 3 elem.: consumatorii care beneficiaza de un anumit serviciu, statia de servire care satisface cererile consum., sirul de asteptare format atunci cind servirea consumatorilor nu se face exact la momentul sosirii lor. Construirea modelului de asteptare se poate face cunoscind ritmul sosirii consumatorilor, ritmul de servire si disciplina sirului de asteptare. Astfel probabilitatea realizarii a n sosiri in unit. de timp este: P(n)=e-lln/n!, posibilitatea de a realiza n serviri in unit. de timp este Q(n)=e-mmn/n!. In silv. fen. de asteptare se caract. de obicei prin prezenta unui singur post de servire in regim stationar cu disciplina sirului de asteptare: primul sosit - primul servit. Ritmul sosirilor si al servirilor se poate determina pe cale experimentala prin cronometrare. Testul X2 permite incadrarea fenomenelor in legea Poisson . Optimizarea procesului sub aspect tehnico-economic presupune sa actionam fie asupra ritmului sosirilor prin modificarea ritmului servirii. Rezolvarea problemei se face prin incercari. Timpul mediu de asteptare in sir : ta 1/m-l m=j/m-l. Numarul zilnic al sosirilor este de sz10=10*60*l timpul servirilor zilnice este sz10*12, timpul de asteptat este tA=ta*sz10. Timpul de asteptare a rampei: tR=10-sz10; Costul asteptarii este C=0.5*tA+1.25*tR.
20... Teoria grafurilor: se aplica la rezolvarea unor probleme ce pot fi rezolvate prin diagrame, scheme de comunicatie, scheme de succesiune a activitatii. Se caracterizeaza printr-un nivel ridicat de abstractizare si generalitate deoarece sub aspect structural - functional poate fi aplicata la un mare nr. de sisteme. Obiectivul urmarit este parcurgerea traseului dintre starea initiala si cea finala definit de un anumit nr. de stari intermediare a.i. efectul obtinut sa fie optim in raport cu criteriul de evaluare adoptat. Graful este definit astfel G=( X, . Acestuia i se asociaza un grafic in care fiecare element al multimii X numit virf sau nod se reprezinta printr-un punct iar fiecarei conexiuni numita arc se reprezinta printr-un segment orizontal de la xi la xj cu conditia ca xj sa apartina xi). Reprezentarea grafica a nodurilor si arcelor are doar rolul de de a evidentia relatiile deintre elemente si de aceea reprezentarea nu se face la scara si nu prezinta interes nici pozitia nodurilor nici distanta dintre ele. Un graf mai poate fi definit prin cuplu (X,A) A=multimea arcelor. Nr arcelor ce alcatuiesc un drum defineste lungimea lui. Daca lungimea drumului este egala cu 1 si el este circuit drept se numeste bucla. Un drum elementar intilneste fiecare virf o singura data. Drumul simplu este alcatuit din arce distincte. Altfel drumul este compus. Un drum hamiltonian intilneste o data si numao o data fiecare nod. Un graf este complet atunci cind contine cel putin un arc intre doua noduri oarecare indiferent de directia acestora. Oricarui graf i se poate asocia o matrice de structura MG in care elementele Mij pot lua valoarea 1 daca se poate identifica un arc sau valoarea 0 daca acest arc nu exista. Lantul elementar trece o singura data prin virfurile grafului.
Determinarea drumului optimintr-un graf: determinarea drumului de valoare minima sau maxima dintre virfurile xi , xj. Algoritm FORD: 1). fiecarui nod xi i se ataseaza o variabila li, valorile initiale sunt 0 si +00. 2) pt. fiecare arc se determina atunci cind are sens valoarea diferentei pornind de la nodul xo. Pt. sol optima toate diferentele Cij-lj+li trebuie sa fie nenegative. 3) se determina multimea axelor (xi,xj)cu li-lj=Cij.
Cind se urmareste det. drumului max. in pasul 1 lui li i se da valoarea -00., iar criteriul de optimalitate este Cij-lj+li
Definitia,obiectul si scopul cercetarii operationale: metode deductiv-analitice si metode se simulare.
Modelul matematic general al problemelor de tip transport
3.. Metode de det a solutiei optime.Metoda distributiva.
4...Det sol optime prin metoda distributiva modificata.
Probleme de transport al caror model matematic are o structura speciala. Aplicatii de interes forestier.
Degenerarea in problemele de tip transport.
Reoptimizarea problemelor de tip transport
8... Formularea modelului matematic general al unei probleme de programare liniara. Moduri de prezentare a modelului. Reguli de aducere a modelului la forma dorita.
Metode de determinare a unei solutii de baza admisibile.
10.. Teoreme de baza ale alg simplex. Forma gen a tab simplex. Reguli practice de aplic a alg simple
11.. Dualitatea in probleme de programare lineara. Proprietati
12...Degenerarea in probleme de programare liniara
13...Reoptimizarea problemelor de programare lineara in cazul modificarii componentelor vectorului coloana al termenilor liberi sau al coeficientilor necunoscutelor din functia obiectiv
> Reoptimizarea in cazul modificarilor coeficientilor necunoscutelor din functia obiectiv
>Reoptimizarea in cazul modificarilor componentelor vectorului coloana
>Algoritmul Simplex
14...Modelul matematic generalal problemei sortarii primare a materialului lemnos
15...Modelul matematic pentru optimizarea transportul agregatelor minerale din balastiere
Modelul matematic pt det posibilitatilor de produse principale la codru regulat ; variante de formulare a functiei obiectiv
17...Modele matematice pentru determinarea compozitiei tel a arboretelor
18...Modelul matematic pentru determinarea amplasamentului optim al investitiilor
19... Teoria fenomenului de asteptare:
20... Teoria grafurilor
@ probleme de tip transport prin care se urm maximizarea val fctieti obiectiv
@ metoda >> grafica nu este ! ! ! !!!!!
|
