Proiectarea Si Optimizarea Problemelor de Programare Semidefinita

Proiectarea Si Optimizarea Problemelor de Programare Semidefinita

Byadmin ianuarie 1, 2024

ADNOTARE

Acest proiect de diplomă a fost implementat pentru proiectarea și optimizarea problemelor de programare semidefinită, care mai apoi poate fi utilizat cu cu ușurință în cadrul unei optimizări mai complexe în urma cerecetărilor mai aprofundate, sau la elaborarea unui soft mai sofisticat în care se va conține și metoda de optimizare care am elaborat-o și descris-o în acest proiect.

Primul capitol al proiectului conține descrierea în Problema de MAX-CUT si relaxările ei, bazate pe programarea semidefinita. Aici sunt descrise toate metodele de relaxare și care parțial au fost implementate în acest proiect.

În capitolul doi este descris Metoda punctului interior, Metoda punctului interior pentru optimizarea combinatoriala, noțiune și exemple de Optimizarea combinatorială, optimizare combinatorie, metode de soluționare: metoda combinatorială, metoda de Continuitate, optimizarea globală.

Capitolul trei descrie dualitatea în programarea neliniară, noțiune de gradient, algoritmul de optimizare funcțiilor, care utilizeaza gradientul, optimizarea neliniară fără restricții, metoda barierei logaritmice, destinația fiecărei, și funcțiile îndeplinite în la elaborarea acestui proiect..

În capitolul patru se analizează problemele referitoare la rezolvarea numerica a problemei MAX-CUT, adica toate metodele care au fost aplicate pentru elaborarea acestui proiect: determinarea tăieturii MAX-CUT, metoda gradientului cu fracționare a pasului, metoda barieirei logaritmice, factorizarea Cholesky, metoda gradientului.

În capitolul cinci se analizeaza proiectarea tehnico-economica a proiectului de diploma, sunt estimate cheltuielile proiectului și costul proiectului. Este prezentată analiza efectului social de la întroducerea proiectului în exploatare.

În capitolol șase se analizează problemele referitoare la protecția muncii și sanitaria de producere, unde se analizează acțiunea factorilor nocivi de la exploatarea calculatorului și standardele de lucru cu tehnica de calcul.

Sunt anexate codurile sursă a Proiectului elaborat în C++Builder. De asemenea sunt anexate schemele generale de lucru și schemele rulării al proiectului.

Adnotation

This project of diploma was creating for designed the semidefinite problems, which can be easily used into complex operations maken after more deeply researches. It also can be used for elaboration of sophistry soft which contain the metod of maximization elaborated down this work.

I the first chapter of project contain the description of MAX-CUT problem and its relaxions based on semidefinit programe . Here are described the methods of relaxions which were in this project.

II the second chapter is described the Method of interior point used for combinatorial maximisation. It also containt methods of solving, the method of continuity, the global maximization.

III the third chapter are analising the problems acording to the numerical solving of MAX – CUT problem, and all the probleme used for elaborating this project; the determination of MAX – CUT, the method of gradient, with step fraction, the method of logarithm barier, Cholesky fraction.

IV the fourth chapter is analysed the technico – economical projection of this work, are estimated its expences and cost. Is prezented the social efect from its introduction in explotation.

V the firth chapter contains the problems concerning the work protection and its sanitary where are analised, harm full factors at the computer explotation.

At the end are added the sources of project elaborated in C++Builder. The schemes of work and the schemes of rolling the project are also added here.

ÎNTRODUCERE

În prezent produsele soft se implementează foarte rapid, din cauza dezvoltării enorme a tehnologiilor informaționale, acumulării cunoștințelor și bibliotecilor de date, creării rețelelor pentru comunicare și schimb de informații.

Scopul acestui proiect este de a proiecta și elabora un soft de optimizare a metodelor numerice folosind Programare Semidefinită. Aplicații ale problemelor care folosesc programarea semidefinită conține multe aplicații, care se abat de la teoria proectului structurat. I:a general multe probleme de optimizare(cu restrictii limitate) pot fi introduse in metoda celor mai mici pătrate, la rîndul său, pot fi reformulate ca probleme care folosesc programarea semidefinită (SDP). Aceasta SDP asigura originalitatea aproximării polinomiale temporale acestei probleme. De obicei, aproximarea relaxărilor SDP este mai rentabilă decît programarea liniară. Noi ilustrăm punctul nostru de vedere cu o singură aplicație din teoria grafurilor: Metoda taieturii Max-Cut, a fost instrumentară în cele din urmă la calcularea SDP. Aceasta metodă de asemenea arată, cum SDP apare ca o relaxare a problemei, care folosește aproximarea patratică.

Problema de MAX-CUT constă în, tăierea grafului în două părți, așa că maximizarea numerică să se petreacă în partea tăiată în care sumă să fie maximă. De fiecare dată, cînd vîrful grafului este primit este de partea unei parti tăiate a grafului toate marginele care sunt unite cu acest vîrf sunt ingetate sau in afara acestei parti.

Problema determinării tăieturii maxime într-un graf este o problemă de optimizare discretă. Fiind dat un graf finit și neorientat, problema constă în împarțirea vîrfurilor grafului în două mulțimi de vîrfuri care se leaga între ele cu muchii și suma muchiilor este maximș. În general, rezolvarea problemelor de așa natură necesită o enumerare completă a soluțiilor admesibile. O tehnică actuală de rezolvare a problemelor de optimizare combinatorială constă in relaxarea convexă a domeniului de soluții admesibile. Un rol important în aceste probleme îl joacă relaxarea semidefinită care transformă problema originală, data în spațiul vectorial n , într-o problemă de programare liniară în spațiul matriciilor simetrice semidefinite nxn. Problema relaxată este o problemă de programare convexă și poate fi rezolvată într-un timp polinomial.

În lucare problema determinării tăieturii maxime se reformulează ca o problemă de programare patratică cu restricții pătratice. Se prezintă relaxările bazate pe programarea semidefinită. Se arată ca toate aceste relaxari sunt echivalente între ele și că sunt produse de dualitatea Lagrange. Se discută metoda punctului interior pentru rezolvarea problemei de MAX-CUT, în particular metoda funcției de barieră. Calcularea gradientului funcției de barieră logaritmică necesită determinarea elemenetelor unei matrice inverse. O tehnică actuală de rezolvare constă în transformarea problemei originale, dată în spațiul vectorial n, într-o problemă de programare liniară în spațiul matriciilor simetrice semidefinite de dimensiune nxn.

1. Determinarea tăieturii max-Cut într-un graf cu ajutorul programării semidefinite.

Problema de MAX-CUT constă în, tairea grafului în doua părți, așa ca maximizarea numerica sa se petreaca în partea tăiată în care suma sa fie maximă. De fiecare dată, cînd vîrful grafului este primita este de partea unei părți tăiate a grafului toate marginele care sunt unite cu acest vîrf sunt înghețate sau în afară acestei părți. Deoarece vi va avea așa de mulți vecini în partea cealalta, așa cum sunt de partea lui. În așa fel jumatate de vîrfuri va fi tăiată.

În decurs de mulți ani aceasta ne este stiut ca apoximarea Max-Cut.

Problema de MAX-CUT- este o problemă de optimizare combinatorie în grafurile neorientate. Un asemena graf, problema este ca în compartiemntul de înjumatatire pe ramuri în doua părți, în care suma trebuie ponderii arborior trebuie sa fie maximă, fata de jumatatea cealalta. Noi vom cerceta la caz general unde graful este finit.

Problema de Max-Cut are aplicații la proiectarea lanturilor și fizicii statice.

Problema de Max-Cut – este strîns legata de așa zisul micsorarii polytope, structura importanta în domeniul programarii. Aceasta este deja stiut ca Max-Cut – este problema deplina NP și , ce ramîne de finisat în NP- pentru unele cazuri eceptionale. În putine cazuri speciale pot fi solutionate. Dacă graful – nu-i contractibil, atunci graful întreg, dupa demonstratia Barahona care demonstra ca, relaxarea multilant a primit din produsul inecuatiilor sub forma triunghiulara asemanator cu varibila optimala MC(Inecuatiile în forma triungiulare ne dau restrictii , ca pentru orice noduri dintr-un graf, este posibil de taiat numai sau un vîrfsau 2 vîrfuri, care sunt unite între ele).

Pe aceasta foaie, noi focusam problema care este definită între limitele frontierei(de sus) cu variabila optimala MC, care folosește relaxările programarea semidefinită (SDP1). Relaxările multilaterale ale programarii semidefinite pentru problema Max-Cut pot fi primite prin diferite căi. Toate procedurile sunt bazate într-o oarecare forma de maxim și planificarea variabilelor între problemele de domenii diferite.

În relaxările ale programarii semidefinite Lovasz и Schrijver procedura care înseamna N+, care poate fi repetata, pentru primirea minimului și minimizarea relaxărilor în programarea semidefinită. Raspunsul cheie – este ca procedura, repetarii Nt, t timpul, N – numarul variabilelor întregi din problema. Pentru Max-Cut, n se egalaeaza cu numarul de vîrfuri în graf.

În afară de asta, optimizînd functia liniara corespunzatoare, va fi exact variabilă optimala a MAX-CUT.

În alt caz, programînd relaxările semidefinite – necatînd teoria duala, care sunt aratate ca fiind foarte stricte. Ultima lucrare a lui Lasserre întroduce tipul relaxarilor a programarii semidefinite, relaxarea programata, corespunzînd întelusului ale problemelor polinomiale logice în probleme de un domeniu mai înalt. Lasserre prezintă conditiile corepunzatoare și suficiente sub care variabilă optimala ale problemei MAX-CUT sunt atinse dupa numarul de optimizari.

Pîna ce o alta cale de a primi aceste relaxari – este dualitatea Lagrange. În aceasta metoda se ia o reformulare a problemei de Max-Cut și formeaza dualitatea Lagrange. Aceasta este echivalenta cu relaxarea Shor și procedura S-Yakubovitch(care vor fi descrise mai jos).

Un plus are aceasta metoda asupra celor doua mai sus descrise – este, ca este necesa sa alegem restictiile(posibil chiar nu ne trebuie),care sunt incluse în formularea problemei inițiale. Aceasta alegere determina structura și tipul relaxariilor SDP.

Aici noi vom ne vom familiariza, cu citeva relaxari SDP1 pentru Max-Cut. Relaxarea de baza SDP poate fi primita dacă vom folosi relaxarea lui Lagrange și în asemenea mod ridicînd la patrat formularea logica Max-Cut din domeniul n în Sn, al spatiului matricial de tipul nxn. Aceste relaxari noi au fost obtinute folosind a doua reformulare, adica în asemena mod formularea Max-Cut în spatiul Sn și apoi rezolvînd problema în spatiul . Noi demonstram ca aceasta relaxare, care este SDP2, – întarita de relaxarea Goemans-Williamson. A doua relaxare, – înaintarea restrictiilor aspre SDP1.

1.1 Întroducere in Programarea Semidefinita

Problema de Programare Semidefinita(semidefinite programming problem(SDP))- este de fapt o problema de programare liniara unde restrictiile terbuie sa fie nenegative, adica pozitiv semidefinite. Forma initiala a problemei de programare semidefinita este:

Unde C, AK, si X- toate matriciile de tipul n x n, bk – scalar, iar restrictia inseamna, ca X, este o matrice arbitrara, trebuie sa fie neorientata, pozitiv semidefinita. Aici se are in vedere, relatie dintre produsului standart intern in spatiul matriciilor simetrice, adica pentru matriciile simetrice A si B, AB=trace(AB).

Unde variabila duala y este m-vectorul Lagrange, care este limitat de restrictiile ale inecuatiilor

Din problema de progamare semidefinita(SDP) reiesa problema de programare liniara cind sunt toate matrici diagonale. SDP- un exemplu mai generalizat a problemelor de programare liniare neorientate, unde se face cautarea, pentru minimzarea functie obiective liniare unde restrictiile sunt liniare. Cum este si neorientata(pentru SDP)lemei inițiale. Aceasta alegere determina structura și tipul relaxariilor SDP.

Aici noi vom ne vom familiariza, cu citeva relaxari SDP1 pentru Max-Cut. Relaxarea de baza SDP poate fi primita dacă vom folosi relaxarea lui Lagrange și în asemenea mod ridicînd la patrat formularea logica Max-Cut din domeniul n în Sn, al spatiului matricial de tipul nxn. Aceste relaxari noi au fost obtinute folosind a doua reformulare, adica în asemena mod formularea Max-Cut în spatiul Sn și apoi rezolvînd problema în spatiul . Noi demonstram ca aceasta relaxare, care este SDP2, – întarita de relaxarea Goemans-Williamson. A doua relaxare, – înaintarea restrictiilor aspre SDP1.

1.1 Întroducere in Programarea Semidefinita

Problema de Programare Semidefinita(semidefinite programming problem(SDP))- este de fapt o problema de programare liniara unde restrictiile terbuie sa fie nenegative, adica pozitiv semidefinite. Forma initiala a problemei de programare semidefinita este:

Unde C, AK, si X- toate matriciile de tipul n x n, bk – scalar, iar restrictia inseamna, ca X, este o matrice arbitrara, trebuie sa fie neorientata, pozitiv semidefinita. Aici se are in vedere, relatie dintre produsului standart intern in spatiul matriciilor simetrice, adica pentru matriciile simetrice A si B, AB=trace(AB).

Unde variabila duala y este m-vectorul Lagrange, care este limitat de restrictiile ale inecuatiilor

Din problema de progamare semidefinita(SDP) reiesa problema de programare liniara cind sunt toate matrici diagonale. SDP- un exemplu mai generalizat a problemelor de programare liniare neorientate, unde se face cautarea, pentru minimzarea functie obiective liniare unde restrictiile sunt liniare. Cum este si neorientata(pentru SDP) asa si e nenegativa(pentru LP).

Metoda punctului Interior.

In punctul interior al algoritmului intra::

micsorarea potentiala.

Injumatatirea pasului urmator.

Metoda punctului interior poate fi numai primala, duala, sau primal-duala. Algoritmul primal-dual este foarte apropiat timpului prezent. Cum si LP, algoritmul primal-dual poate sa solutioneaze SDP.

Ultima inecuatie este conditia de complimentar complimentaritate pentru SDP. Algoritmul Prima-Dual folosesc metoda lui Newton, pentru solutionarea partilor drepte care sunt condiitiile de complimentaritate. Cum numai este calculata calea cautarii, masurarile care sunt luatede lungul acestei directii ca acel nou sa indeplinesaca conditiile de complimentaritate. Acest proces este ciclic si necesita mult timp.

Aplicații ale problemelor care folosesc programarea semidefinită: contine multe aplicații, care se abat de la teoria proectului structurat. La general multe probleme de optimizare(cu restrictii limitate) pot fi introduse in metoda celor mai mici patrate, la rindul sau, pot fi reformulate ca SDP. Aceasta SDP asigura originalitatea aproximarii polinomiale temporale acestei probleme. De obicei, aproximarea relaxarilor SDP este mai rentabila decit programarea liniara. Noi ilustrăm punctul nostru de vedere cu o singura aplicatie din teoria grafurilor: Metoda taieturii Max-Cut, a fost instrumentara in cele din urma la calcularea SDP. Aceasta metoda deasemenea arata, cum SDP apare ca o relaxare a problemei, care folosește aproximarea patratica. Presupunem, ca G=(V,E;W),-este un graf finit, neorientat

cu limitele taieturii Max-Cut in graf care consta in aflarea vîrfurilor V={vi}in=1 si nodurilor (vi ,vj)E. Aceasta se poate reformula ca o problema de optimizare:

Unde xi=1 pentru i=1,2,3…n si xj=-1. Facind legaturi intre vîrfuri, in caz contrar MAX-CUT este clar, ca problema NP-complexa. Noi inlocuim restrictia patratica xi2=1 cu o forma restricta, punem aceasta restrictie in functia scop, pentru ca sa primim o forma a relaxarii Lagrange.

Unde Q-matricea patratica nxn, i – multiplicatorul Lagrange. Marimea optimala (MC-LR), asigura marimea vectoriala superioara(MC), adica t<t(). In particular, aceasta este legatura trebuie sa ramina pentru , care se minimzeaza t(), atunci noi vom avea:

Unde e –vectorul tuturor elementelor Diag() de pe diagonala, matrice a carui i sunt situate pe diagonala. Noi acum initializam, problema interioara de MAX-CUT este infinit de important daca multiplicatorul lui Lagrange nui – negativ senidefinit, adica noi avem o restrictie semidefinita ascunsa. Si inafara de aceasta, cum noi adugam aceasta restrictie semidefinita Q-Diag()0 la problema initiala minimizata, atunci maximizarea interioara o sa fie cind x=0. Noi am inlaturat partial restrictia x si o parte din problema MAX-CUT.

Asadar, de aici reiesă că, MC poate sa fie solutie a SDP urmatoare:

Care este duala:

Aici, Diag(x) –vector care are i-intrari, i- elemente pe diagonala a matriciei X. Aceste perechi SDP pot fi solutionate prin algoritmul punctului-interior primal-dual.

În acesata lucrare, vom considera vîrfurile grafurilor finite, ponderate, și neorientate G(V,U), unde V=(v1, v2,… vn)este mulțimea vîrfurilor(nodurilor), iar U-este mulțimea muchiior , mulțime care nu contine bucle și muchii multiple. Fiecarei muchii (vi, vj)U i se asociaza o valoare(ponderea) aij=aji0. Vom defini aij=0 în cazul care (vi, vj)U, adica în cazul cînd vi și vj nu sunt adiacente. Matricea de adiacenta sociata acestui graf va fi notata A=( aij).

Fie SV o submulțime nevida a lui V.

Definitie : O tăietură (S) este o mulțime de muchii (vi, vj)U cu proprietatea ca, dacă viS, atunci vjV\S.

Se pune problema determinarii taieturii (S) cu valoarea maximă a sumei ponderilor muchiilor, adica a partitionarii mulțimii V în doua parte S și V\S astfel ca suma este maxim posibila oricare ar fi SV. Aceasta problema numita și problema MAX-CUT, are diverse aplicații. Problema Max-Cut, face parte în caz general din clasa problemelor – PN necomplete și poate fi usor rezolvabila într-un timp polynomial numai în cazuri speciale, de exemplu, cînd graful este planar.

Problema considerata poate fi formulata ca problema de programare patratica cu restrictii patratice. Pentru aceasta, vom întroduce variabilele xi: i=1,2,3,4,…n, sau xi=1 și xi=-1 dupa cum vîrful vi aprtine sau nu mulțimii S.

Dacă vîrfurile vi și vjS sau mulțimii V\S, atunci xi=xj, și deci xixj=xi2=xj2=1. În cazul cînd xi=-xj, adica

avem viS, atunci vjV\S, sau invers și atunci vom avea xixj=1, rezulta ca:

unde x=(x1, x2,… xn)T și e=(1,1,1,…1)T, iar Diag(Ae) este matricea diagonalacu diagonala formata de vectorul Ae.

Matricea L=Diag(Ae)-A se numeste matricea Laplace asogiata grafului G cu matricea adiacenta A. Elementele lij al acestei matrice satisfac relatiile: lij=-aij=lji, ij,

deco matricea lui Laplace L este pozitiv semidefinită. Notînd Q=1/4L, problema determinarii unei taieturi maxime în grafuri neorientate poate fi reformulata astfel :

Aceasta problema este un caz particular al unei probleme de programare patratica cu restrictiipatratice și este deficila de rezolvat : este o problema NP-completă. Mentionam ca în functia obiectiv q(x) lipseste componenta liniara, prezenta, în caz general, în funcțiile patratice. Printr-un procedeu simplu functia patratica :

în care , mai poate fi redusa. Într-adevar, definim matricea simetrica de dimensiune (n+1)x(n+1).

și considerăm vectorul : , unde variabila suplimentara satisface relatia : Atunci :

Dacă solutia optimă , atunci , iar dacă , atunci este o solutie optimă și pemtru , adica dacă putem schimbă cu .

1.2 Relaxarea Lagrange

Considerăm problema Max-Cut, în care matricea Q=1/4L este pozitiv semidefinită. Vom asocia acestei probleme functia Lagrange:

unde : u=(u1,u2,…un)n. Pentru xn cu xi2=1, i=1,2,3,..n și un avem:

L(x,u)=xTQx=q(x)

De unde problema

(1.1)

o putem rescrie astfel:

(1.2)

Considerăm acum functia duala: , Se constata imediat ca :

și

unde prin q* aici se are și în continuare valoarea optimă a fuctiei obiectiv din problema de mai sus, adica: q*=max{xTQxxi2=1, i=1,2,3,…n}.

Inegalitate A›=B semnifica ca matricea A-B pozitiv semidefinită.

Deci, problema duala asociata problemei (1.1) este de forma:

(1.3)

Domeniul solutiilor admesibile T={unDiag(u)-Q} este pozitiv semidefinită} pentru care problema (1.3) este o mulțime convexa și, prin urmare problema (1.3) este o problema de programare convexa polinomiala.

Așadar, problema duala (1.3) este mai usor de rezolvat decit problema problema (1.1) care este o problema NP-completă.

1.3 Relaxarea semidefinită Shor

Relaxarea Lagrange ne da marginea superioara pentru valoarea optimă q* și mai poate fi scrisa astfel:

(1.4)

Așa dar problema determinarii granitei B se reduce la rezolvarea problemei(1.3). Notam eiT=(0,0,0,…0,1,0,…0) vectorul cu unitatea pe pozitia i, i=1,2,3,4,…n. Fie matricea E=eeT. Atunci putem scrie Diag(u)=uiEi. Cu aceste notari problema (1.3) devine:

(1.5)

Problema (1.5) este o problema de PS și duala ea poate fi formulata în felul urmator:

unde Tr() reprezintă urma matriciei, adica Tr(A)=aij.

Așa cum Tr(EiX)=xi,j, problema de mai sus o putem rescrie:

(1.6)

unde diag(X) semnifica vectorul, componentele caruia sunt elemente de pe diagonala principala a matriciei X. Pe de alata parte xTQx=Tr(QxxT). Dacă notam X=xxT, atunci funcțiile obiectiv (1.1) și (1.6) coincid. Este clar ca matricea X=xxT este pozitiv semidefinită și rang(xxT)=e. Se demonstreză ca problema (1.1) este echivalenta urmatoarei probleme:

(1.7)

Renuntînd în (1.6) la conditia ca rang(X)=1 se ajunge la problema relaxata.Deci, dualitatea Lagranje reproduce relaxarea semidefinită pentru problema (1.1) unde putem afirma ca:

B=max{Tr(QX)diag(X)=e, X>=0} (1.8)

1.4 Relaxarea Goemans-Williamson și Analiza calitativa a relaxarii semidefinite

Fie matricea X o solutie admesibila pentru relaxarea semidefinită. Deoarece X este pozitiv semidefinit, exista sistemul format din n vectori y1,y2,..ynn pentru care X este matricea Gram în raport cu produsul sacalar euclidian: X=YYT, unde Y=[ y1,y2,..yn] este matricea a carei coloane sunt vectorii yi, i=1,2,..n. Aceasta înseamna ca elementele a matriciei X sunt xij și se determina din relatiile xij=yiyiT . din conditia diag(x)=e rezulta ca xij=║yi║2≤1 pentru i=1,2,..n iar din conditia X>=0 rezulta ca pentru toti i,j=1,2,..n avem: xij2<xiixjj=1.

Deci produsul scalar yiTyi[-1,1] este o relaxare pentru produsul xij{-1 sau 1}. De aici rezulta urmatoarea relaxare vectoriala:

(1.9)

Sa notam prin ungiul dintre vectorii normalizati yi și yj, atunci cos= yiTyi. Vectorul r este un vector aleator, care separa nodurile vi și vj dacă marimele rTvi sau rTvj au semne opuse.De aici obtinem: 2/(Tr(Qarcsin[X]))=Tr(Qx), unde arcsin[X] este matricea cu elemenetele arcsin(xij). Cu alte cuvinte, problema de programare semidefinită este echivalenta cu urmatoarea problema de prgramare semidefinită neliniara:

(1.10)

Problema (1.10) este echivalenta cu problema (1.1).

1.5 Alte relaxari

Amintim ca functia duala a fost definită astfel: . Vom arata ca :

(1.11)

Într-adevar, pentru u{unDiag(u)-Q>0}. Fie astfel încit Diag(u)-Q<=0 si considerăm problema:

(1.12)

Problema (1.12) este o problema de programare convexa. Conditia necesara și suficienta Karush-Kuhn-Tucker pentru va sa fie o solutie optimă pentru problema(1.12) este sa existe , , i=1,2..n, asfel ca :

(1.13)

Fie atunci Din prima ecuatie avem:

, adica xL(x,u)=0, de unde rezulta ca rezolva problema de optimizare neconditionata:

Prin urmare,

Luand aceasta în consideratie din (1.4) avem:

Fie acum x=(x1,x2,…, xn)n cu xi2=1, i. Atunci: ║x║2=xxT=eeT=n și xTDiag(u)=eTu.

Este evident ca :

q*=max{xTQxxi2=1, i=1,2,..n}=max{L()xi2=1, i=1,2,..n} ≤ max{L()║x║2=n}

unde , ales asfel încit: Diag()-Q>=0.

Prin urmare :

(1.14)

Mentionam ca relaxarea sferica (1.14) a fost obtinuta aici direct de catre dualitatea Lagrange. Așa cum Diag(u)-Q>=0 rezulta ca ui≥1/4lii>0, i. Considerăm acum functia:

L(x,-u)=xT(Q+Diag(u))x-eTu

Este clar că

:

Precum și matricea Q este pozitiv semidefinită, din Q+Diag(u)<=0 rezulta ca vectorul uRn poate avea componente și pozitive și negative.

Iar relaxarea spectrala va fi urmatoarea:

(1.15)

Întra-devar problema (1.15) este echivalenta cu urmatoarea problema de programarea semidefinită:

Dar I-Diag(u)=Diag(e-u). Notînd z=e-u și lund i consideratie ca eTu=0 avem ca problema (1.15) este echivalenta problemei (1.16):

(1.16)

Diferite formulari ale Max-Cut

Noi putem reformula problema de Max-Cut în felul urmator. Se poate ca în graful dat G sa fie instalat {1,2,…n} și este scrisa matricea de incidenta a ei(G). Noi mai departe presupunem ca graful de care merge vorba este finit și, vîrfurile nu sunt vide,

așa ca A(G)0. Fie, L înseamna matrice lui Laplacce care este legata de graf; de aici rezulta ca L:=Diag(A(G)*e)-A(G), unde Diag(A(G)) este operator liniar și reintoarce matricea diagonala cu vectorul care sa format de pe diagonala ca argument. Fie, vectorul v{1}n este orice minim a grafului care a fost înterpretat , seturile sunt: {i: vi=+1} și {i: vi=-1} este forma vorfurilor în care a fost creat graful.

Apoi noi vom putea sa reformula problema:

Problema determinarii taieturii maxime într-un graf este o problema de optimizare discreta. Fiind dat un graf finit și neorientat, problema consta în impărțirea vîrfurilor grafului în doua mulțimi de vîrfuri care se leaga între ele cu muchii și suma muchiilor este maximă. În general, rezolvarea problemelor de așa natura necesita o enumerare completă a solutiilor admesibile. O tehnica actuala de rezolvare a problemelor de optimizare combinatoriala consta în relaxarea convexa a domeniului de solutii admesibile. Un rol important în aceste probleme il joaca relaxarea semidefinită care transforma problema originala, dată în spatiul vectorial n , într-o problema de programare liniara în spatiul matriciilor simetrice semidefinite n x n. Problema relaxata este o problema de programare convexa și poate fi rezolvata într-un timp polinomial.

În lucare problema determinarii taieturii maxime se reformuleaza ca o problema de programare patratica cu restrictii patratice. Se prezintă relaxările bazate pe programarea semidefinită. Se arata ca toate aceste relaxari sunt echivalente între ele și ca sunt produse de Dualitatea Lagrange.

Relaxari ale programarii semidefinite

A aparut un mare înteres pentru solutiile relaxarilor programarii semidefinite programînd relaxările pentru probleme de optimizare combinatoriala. Relaxările programarii semidefinite sunt solutionate prin metoda punctului interior. Granitele care au fost primite din relaxările programarii semidefinite cele mai dese ori sunt cele mai reusite decit acele care au fost primite folosind relaxările din programarea liniara, dar de cele mai dese ori sunt cele mai costistoare. Acesteia au fost calculate în interese teoretice dar și pina la ultima demonstrare a metodei punctului interior pentru problemele de programare semidefinită. Interesul a aparut mai departe pentru Goemans and Williamson, care aratat, ca granitele erau generate semidefinit programînd relaxările pentru maxim care erau taiate din și efectuarea problemelor erau rezolvabile mai usor fata de cele care erau primite din relaxările programarii liniare.

Pentru exemplu de relaxare a programarii semidefinite, vom analiza

Unde QRnxn – este simetrica.

Aceasta ne permite sa reformulam problema patratica min trace(Qx) care apartine:

Aceasta – este o rеstrictie foarte nerentabila. Aceasta ne da o noua relaxare a programarii semidefinite:

Cum numai noi o sa avem o relaxare care ne va satisface, noi vom putea sa, folosim o ramura si tăietura, pentru ca sa solutionam problema optimăl. Helmberg a demonstrat, ca relaxarea SDP in general este limitata 0 – 1.

Sunt multe inecuatii de acest tip, și ramura și tăiererii ei, care folosesc relaxările SDP, ca sa solutioneze problema patratica {-1,1} cu matricii pozitiv semidefinite. Ei largesc folosind criteriul, ca doua variabile sau luînd una și aceași marime sau lund marimi aceleași dar cu semne diferite. Aceasta imparte relaxarea SDP în doua subprobleme SDP, ficare continind {-1,1}. Multe restrictii provin de la functia obiectiva. Locul îngust de pe ramura și metoda taierii reprezintă temporar necesar, pentru solutionarea fiecarei relaxari, și în final pentru detreminarea directia punctuui interior. O cale se micsoreaza dar de dată aceasta noi vom introduce în variable marimile –1 sau 1.

Helmberg a propus o metoda, care sa determine variabila care a fost instalata în cazul rezolvarii relaxarilor SDP.

Contrastul, Wolkowicz și Zhao priveau relaxările SDP ca la o programare ntreaga mai dificila. Aceasta trebuia crearea unor metode de solutionare care vor fi utile în continuare. Pentru asemenea probleme, la început relaxările SDP nu aveau punctul interior, adica nu aveau o matrice pozitiv semidefinită, care trebuia sa satisfaca toate restrictiile.

Pentru depașirea acestei greutati, autorii aduc problema la un domeniu mai jos, unde solutiile care erau determinate erau înscrise în metoda punctului interior. La concret, dacă X – matricia varibilelor pentru formularea problemei SDP originale, matricea V – este determinata pentru ca în problema poate fi dedusa din punct de vedere a matriciei Z , și X =VZVT.

Cu aceasta reformulare, metoda punctului interior poate fi folosit cu succes, pentru solutionarea relaxarilor programarii semidefinite..

Un alt aspect interesant – determinarea alternativei, o relaxare semidefinită un pic mai slaba, care permite exploatarea matriciei originale pentru instalare, care acopera problema. Relaxarea rezultanta contine restrictii semidefinite și restrictii liniare.

O singura cale pentru solutionarea problemelor rare, care folosesc etodele programarii semidefinite trebuie sa analizeze problema duala. Benson și Helmberg și Rendl au înaintat nu demult niste metode , care pot sa obtina niste granite bine stabilite și uneori solutii optimale pentru asmenea probleme de optimizare combinatoriala analizînd dualitatea problemelor sau relaxarea duala.

Metoda punctului interior

Metoda punctului interior pentru optimizarea combinatoriala

Întroducere în problema Optimizării

Formularea problemei de Minimizare

Problema de bază a optimizării constă în minimizarea unei mărimi scalare E care reprezinta valoarea unei functii care depinde de n parametri notati (x1, x2, … xn). Se cer parametrii pentru care marimea E este minimă scris pe scurt:

minimizeaza E=f(x1, x2, … xn).

Problema optimizării a fost formulata ca o problemă de minimizare. Este aceasta o limitare a deferentei?

Valoarea E înglobeaza criteriile de proiectare ale sistemului într-un singur numar care adesea masoara diferenta dintre performanta ceruta și performanta obtinuta. Funcției f i se mai spune funcție obiectiv.

Multimea celor n parametri va fi manevrata ca un vector coloana:

x=[ x1, x2, … xn]T

Vom nota cu xmin multimea parametrilor pentru care E este minimă iar valoarea minimă o vom nota cu Emin.

Minime locale și globale

Dacă Emin este ceamai mica valoare posibila a lui E pentru orice x din domeniul de definiție atunci se spune ca punctul xmin este un punct de minim global. Acestain general s-ar putea sa nu fie unic. În practica este foarte dificil de stabillit dacă un minim gasit este global sau nu. De cele mai multe ori se poate spune ca punctul reprezinta un minim doar înntr-o vecinatate se spune in acest caz ca este un minim local.

Gradienți

Unele metode de optimizare necesita informatii legate de derivatele partiale de ordinul unu sau doi ale funcției obiectiv în raport cu parametrii de optimizare. Vectorul gradient Jacobian notat g este definit ca fiind transpusa vectorului gradient f care este un vector linie în care apar derivatele partiale de ordinul

Întroducere în problema optimizarii

Matricea patratica simetrică de dimensiune nxn care contine derivatele partiale de ordinul doi ale funcției f este cunoscuta sub numele de matricea Hessiansi este notata cu H:

Restrictii

În problemele practice de optimizare exista anumite restrictii între parametri acestea restrangand domeniul admisibil de cautare al minimului. O restrictie des întalnita este restrictia de domeniu corespunzatoare parametrului xi care este de forma:

xL,i < xi < xU,i

unde xL,i și xU,i reprezinta limite fixate inferioara și respectiv superioara. Mai în general exista restrictii de tip inegalitate între parametri:

g(x1, x2, …xn)<0

Domeniul de cautare în care restrictiile sunt satisfacute se numeste regiune admisibila.

Este de asemena posibil ca între parametri de optimizat s-a existe și restrictii de tip egalitate:

h(x1, x2, …xn)=0

Optimizarea cu restrictii este mult mai dificila decat cea fără restrictii De multe ori problemele de optimizare cu restrictii sunt reformulate astfel încat ele sa se reduca la rezolvarea unor probleme de optimizare fără restrictii.

Convergenta

Înainte de a compara diferite tehnici de optimizare trebuie gasite raspunsuri la urmatoarele doua întrebari:

A convers valoarea lui E catre un minim și este acest minim unul global.

Care a fost rata viteza de convergenta.

Valoarea lui E în timpul iteratiilor este în majoritatea cazurilor singura marime care sa reflecte progresul algoritmului de minimizare. Dacă E nu mai scade un numar de iteratii este posibil sa se fi atins un minim. Totuși este aproape imposibil sa se prezica dacă acest minim este unul global. Nici una din tehnicile iterative de optimizare nu garanteaza convergenta catre un minim global.

Viteza relativa de convergenta este de obicei evaluata prin numarul de evaluari de functii f necesare pentru a reduce valoarea E de un anumit numar de ori. Aceasta deoarece evaluarea funcției obiectiv este operatia cea mai mare consumatoare de timp în problemele practice de inginerie.

Probleme de optimizari vectoriale

În majoritatea problemelor optimizarea înseamna satisfacerea mai multor cerinte aceasta însemnand ca multe functii obiectiv f(x), i=1,2,..n trebuie minimizate simultan. Problema poate redusa la una de tipul(1) folosind de exemplu minimizarea în sensul celor mai mici patrate sau un criteriu de tip “minimăx”.

Minimizarea în sensul celor mai mici patrate consta în minimizarea expresiei:

minimizeaza

în care wi se numesc ponderi sau factori de penalizare și scopul lor este de a pondera importanta diferitor obiective de minimizat. Criteriul de tip minimăx consta în minimizarea celei mai mari valori: minimizeaza E=maxwi fi(x).

Dezavantajul acestei din urma abordari il constituie faptul ca E este o funcție discontinua neputandu-se deci defini derivatele ei în raport cu parametrii de optimizare.

Optimizarea unidimensionala

Optimizarea unidimensionala corespunde cazului n=1 problema simplificandu-se:

minimizeaza E=f(x)

Optimizarea reprezinta deci o cautare a minimului într-o dimensiune. Foarte multe proceduri de minimizare multidimensionala se reduc la o multime de optimizari unidimensionale și de aceea aceasta problemă trebuie rezolvata eficient și cu acuratete.

Functii unimodale

O funcție f de un singur argument se spune ca este unimodala atunci cand xmin este singura valoare a lui x pentru care f(x)<f(y) pentru orice y=1,2,..n domeniul de definiție. Aceasta definiție nu face referire la derivatele funcției și de aceea ea poate fi aplicata atat functiilor continue cat și celor discontinue:

Functii convexe

O funcție continua este convexa dacă pentru orice x și y din domeniul de definiție și orice cuprins intre 0 și 1 are loc inegalitatea:

f(x+(1-)y)< f(x)+(1-)f(y)

Dacă inegalitatea este stricta functia se numeste strict convexa. Functia f se numeste concava dacă f este convexa.

Geometric o funcție este strict convexa dacă o linie dreapta care uneste orice doua puncte de pe grafic este situata deasupra graficului.

Dacă o funcție este convexa atunci minimul local este de asemenea global.

Optimizare în n dimensiuni

Dacă o funcție este suficient de multe ori derivabila ea poate dezvoltata în serie Taylor

f(x+x) = f(x) + gTx + ½ x TH x + ….

Unde g reprezinta vectorul Jacobian iar H reprezinta matricea Hessian. Dacă derivatele de ordinul unu exista atunci într-un minim local vectorul gradient g are toate componentele nule. Dacă exista și derivate de ordinul doi matricea Hessian H este pozitiv definita în punctul de minim.

Metoda punctului interior, inițial a fost metoda pentru programarea liniara, apoi au descoperit un diapazon mai larg de aplicații, în care intrau și probleme discrete, care apar în domeniul informational și în operatii de cercetare, și mai ales probleme de calcul infinit, aparute inițial în stiintele stiintifice și la proiectarea lor.

Acest subcapitol descrie baza conceptuala și aplicațiile metodei punctului interior pentru probleme discrete. Aici se va vorbi despre:

definirea domeniului și natura problemelor de optimizare combinatoriala și arata folosirea acestei metode pentru aceste tipuri de probleme.

are contrastul combinatoriu și discontinuu a metodei punctului interior pentru solutionarea lor și la crearea ideii de baza.

se va discuta metoda punctului interior, cum sa minimizam o functie, ca sa gasim solutii bune in probleme de optimizare combinatorie.

Aici ne va da ideie de programare semidefinită și metodele de folosire in optimizarea combinatorie.

noi vom urmari rolul principal cum a jucat optimizarea in stiintele stiintifice și artificiale.

2.2 Optimizarea combinatoriala.

În aceasta parte, noi vom discuta citeva exemple de probleme de optimizare liniara și vom ilustra algoritmul metodei punctului interior pentru rezolvarea acestor tipuri de probleme.

2.2.1. Exemplu de problemă de optimizare combinatorială.

Așa dar realitatea tipica a unui exemplu de optimizare combinatoriala, vom cerceta urmatoarea problema: deservirea specificatiei zborurilor avioanelor de la aeroport pentru minimizarea ei. Specificatia zborurilor consta din zborurii multe, care leaga multe orase, cu un grafic determinat de sosire/plecare. Sunt citeva restrictii pentru deservire. Fiecare aeroport trebuie sa permita calatoria incolo și înapoi pe ruta. Fiecare pilot trebuie de asemenea sa piloteze acel marsut, și deasemenea se poate pe alte rute, deoarece în oricare aeroport poate sa se transfere în alt avion. Este o sinhronizare a restrictiilor , care blocheaza specificatia pilotilor, palnurilor de zbor. Trebuie sa fie concedii de scurta durata care sunt incluse în specificatia zborurilor din aeroport. Numai unele comenzi sunt calificate, casa sa deserveasca anumite planuri. Costul operational consta din mai multe componente, unele chiar mai eficace decit altele.

Probleme de acest tip sunt numite probleme de optimizare combinatoriala, sunt doar în numar finit de combinatii posibile, dar in princiiu, se poate de enumerat toateить, se înlatura acele, care nu se vor îndeplini și pe acei care nu le vor îndeplini, se alege acea care este mai eficace. Este clar ca trebuie sa fie cea mai rationala decit o simpla operatiune, din numarul de combinari care sunt încluse.

Alt exemplu, vom cerceta reteaua de legaturi care consta din cheii ale legaturilor cu un port (de ex: terestra, oceanica, prin sputnic) într-o oarecare masura. Un sunet telefonic, care ia nastere într-o singura cheie poate alege alte căi (chei), ca sa se termine în alta cheie, se instaleaza porturi de transmisie a informatie pe drum. Problema consta în alegerea drumului minim de retea, care poate efectua o asemena miscare. Dupa aceia ce, reteaua este elaborata și va fi construita, deservirea retelei va include diferite probleme de optimizare combinatoriala, de exemplu: chemarea și afisarea rutelor dinamice.

Așa dar al treilea exemlu, vom cerceta concluziile logice inductive, problema principala e în intelectul artificial și în studiierea mecanicii. Concluziile logice care sunt inductive reprezintă un proces, care construieste ipoteza de reguli generale din exemple.

Aceste concluzii includ urmatorii pași:

Tragînd concluzii din exemple, în care au fost descoperite modele compacte și abstracte de date sau tipuri de date ascunse данных;

Facînd presupuneri sa ajungînd la abstractii;

Studiind, adica modificînd abstractul care au facut presupuneri în compararea rezultatelor reale;

Formînd întrebari, ca sa genereze exemple noi.

Raspunsuri la probleme logice cu concluzii inductive nu sunt unicale. La concluziile inductive, unul vrea un raspuns simplu, care sa demonstreze puncutul de vedere ales. Raspunsurile simple se socot ca cele mai originale raspunsuri. O singura cale trebuie sa precautam – simplicitatea.

Cercetam problemele de natura liniara, o problema in economie, stiintile sociale, și atiintele arheologice. În aceasta problema noi am definit mai multe obiecte, noi dorim sa le arnjam într-o ordine oarecare. Este o legatura în repartizarea obiectelor i înaintea obiectului j și importanta repartizarii obiectului înainte, de obiectul i scop care trebuie sa comande obiectul care este opus minimizarii.

Chiar și alte 4 exemplu care sunt aratate mai sus care rezulta din fațetele vietii și arata imaginar, ca sa arate altfel, ele toate au o structura matematica comuna și pot fi descrise întro notaie generala care apeleaza la o programare definită. În programarea definită, necunoscutele sunt przentate ca variabile, care primesc la finit sau discret in definirea marimilor.. Diferite restrictii sau conditii in problema sunt acparate de marimile algebrice ale acestor variabile.

De exemplu: In problema de definire a comenzilor de linii avia care au fost descrise mai sus, noi le vom nota prin: xij – toatalitatea de solutii, care vor fi apelate de i. Fie rutele le vom nota –j, apelurile comenzilor – m și n – zborurile. Dacă variabila xij primeste valoarea 1, atunci noi vom spune, ca apelul comenzii, care eu l-am numit in zborul j, va fi cij. Dacă va fi marimea – 0, atunci apelulu comenzii il vom numi j. In așa fel, orarul general de zboruri care a fost dedicata pentru aeroport e – m.

aceasta trebuie de minimizat., ciu conditia ca fiecare zbor trebuiesa contina un singur apel exprimat prin variabila m.

(2.2.1)

Noi singuri trebuie sa mentionam care variabile pot sa prieasca orice valoare in afară de 0 și 1. Aceasta conditiee este notata:

xij{0,1}, 1 ≤ i ≤ m; 1 ≤ j ≤ n (2.2.2)

Alta conditie in apel pot fi exprimate printr-o metoda analogica. In asemenea caz, toata, formularea problemei de programare de apel al zborurilor din aeroport trebuie sa fie minimizate.

Programarea liniara reprezintă un tip de probleme de optimizare combinatoriala simpla și speciala unde restrictiile de tipul (3) lipsesc și ne este dată functia obiectiva, noi trebuie sa o minimizam liniar și neliniar .

Forma standart este urmatoare:

(2.2.3)

Cifra 1 ne arata interpretarea geometrica a programei liniare in spatiul euclidian. Fiecare inecuatie liniara este reprezentat printr-o dreapta care imparte planul în doua ju,matati. Fiecare inecuatie cere asta pentru solutionare, ca sa fie satisgacute, ea trebuie sa apartina și sa se includa în una din aceste jumatati. Regiunea care este intersectata de de aceste jumatati este aratata prin o cifra din aceasta regiune. Functia obiectiva, care trebuie sa fie minimizata asupra regiunii în cauza, este definită ca o curba de alunecare. Dupa cum linia este în trecere prin regiunea dată în directia solutionarii, marimea obiectiva se micsoreaza:

Teorema fundamentala a programarii liniare ne indica ca,solutia optimala al programarii liniare reesa din vîrful determinat de catre restrictiile sale. Acest rezultat ne da o natura combinatorie probleme de optimizare.

Probleme combinatoriale apar în diferite domenii. Acestea includ:

teoria grafurilor(colorarea grafurilor)

inecuatiile liniare,

teoria numerilor(factorizarea,logarimul discret),

Teoria de grup,

Teoria reșoului

Intelectul artificial.

Toate aceste probleme, matematic ar putea fi discrete. Metodele de solutionare ale acestor tipuri de rpobleme de asemenea au mult comun.

Solutionarea problemelor combinatoriale a fost un obiect de studiu important.

2.2.2 Domeniul și Efectul calcularii

Noi utilizam cu citeva din exemplele date un spatiu farte largaplicatie a metodei punctului interior și a efectului de solutionare cu ajutorul ei.

Relaxarea Simplex duala cu relaxările LD și ADP, cu care noi începem rezolvarea problemei. Fiecare pas al metodei punctului interior include în sine rezolvarea un sistem liniar de de inecuatii. Pina cind relizarea unei simple rezolvari ale acestor sisteme liniare se poate trece de metoda Simplex. Aceste realizari inițiale folosesc din multe disciplini ca de exeplu algebra liniara, analaiza digitala, arhitectura coputeriala, structurile de date înaintate și geometria diferențiale

Probleme mari din tabele pot fi solutionate prin metoda punctului interior. Aceasta metoda trebuie sa se acomodeze cu solutiile problemelor din viata reala din diferite domenii, așa cum sunte: telecomunicatiile, transportul și securitatea, care earu imposibile de solutionat mai devreme prim metoda Simplex. Relizarea efectiva, metoda punctului interior are un plus farte avantajos: ele pot folosi paralelismul foarte usor și efectiv. Aici din nou, la solutionarea problemei de baza in fiecare iteratie, – solutionarea unei sau mai multe sisteme de ecuatii. Aceste sisteme au un model asemanator cu solutionarea solutiei in fiecare iteratie a algoritmurilor punctului interior.

Metoda punctului interior in comparatie cu metoda Simplex sa indeplinit, ca sa demonstram indeplinrea este direct generata in exemplul de sus. In comparatie cu metoda Simplex metoda punctului interior in probleme nu chiar mari, accelerarea de la 2 și ordine de valori au vost inregistrate și comparate. In afară de asta metoda punctului interior a avut succes la verificarea indeplinirii mai mult de 2500 de exemple, unde Metoda Simplex a esuat.

Cum este arătat in fig. de mai sus, cimpul portilor poate fi abstractizat matematic ca un graf de retea. Fiecare nod al grafului, de asemenea este cunoscut ca un lant care are proprietatea de a avea ca pondere numarul maxim de linii conectate(vezi exemplele de mai sus). Problema combinatorie este aceia ca sa fie gasite lantul model care sa nu depaseasca posibilitatea lanturilor verticale și orizontale. Aceasta problema se poate de reformulat ca problema de programare totala.

Metoda punctului interior a obtinut cu succes solutiile globale optimale la solutionarea problemelor de importanta globala de acest tip. Pe de alta parte

In cazul altor probleme cobinatoriale, metodele de calcul numeric euristic sunt solutionate de catre acesta metoda. De multe ori, metoda euristicxa pur și simplu o codeaza rezolvarea curenta ssau asteptarea structurala a solutiei din clasa specifca in clasa algoritmului. Aceasta restrictie se poate usor de de transformat în problema de crestere exponentiala, care neglijeaza metoda combinatorala. Metoda punctului interior a precautat metoda unica ca sa solutioneze și sa elaboreze alti lagoritmi pentru probleme combinatoriale.

Metode de Soluționare

Metode de solutionare a problemelor combinatoriale pot fi clasificate in doua grupe:metode combinatoriale și neîntrerupte.

2.3.1 Metoda combinatorială

Metoda combinatoriala formeaza o consecutivitate de stari care au fost extrase din culegerea discreta și finita. Fiecare stare prezintă solutia suboptimala sau soltia originala a problemei oroginale. Aceasta poate garf, sau un vîrf, o mulțime de submulțimi a culegerii finite sau unui oarecare altui obiect combinatorial . In fiecare pas de baza al algoritmului, fiecare stare urmatoare aleasa cu condirtia de a imbunati starea urmatoare. Imbunatatirea poate fi ca solutia masurabila din punct de vedere a functiei obiective. Imbunatatirea este indreaptata la cautarea locala.

Cautare Locala, care noi o numim, este ca procedura de solutionare cerceteaza numai legaturile care au fost configurate și se alege strict acea care imbunatateste solutia precedenta. In așa fel, cautarea locala – poate pretui independent dacă acesta deplasare poate sa faca orice variabilă globala. Dar in realitate, metoda combinatoriala are insuficienta de informatii pentru a primi o asemena nota. In multe cazuri, imbunatairea locala stricta poate sa fie solutia locala minima, pentru care – calitatea este mai rea decit minimul global. Pentru evitarea minimului local, metodei combinatoriale trebuie sa recurga la metode, ca de exmplu, intorcind in starea inițiala sau parasind starea de consecutivitate. Problemele combinatoriale mai importante sufera din cauza suplusului de minimuri locali atunci cind spatiul cautarii se limiteaza la discret. Petru problemele de optimizare combinatoriala, fenomenul de numarul maxim de minimi locali poate sa faca o problema pentru metoda combinatoaruiala. Pe din alata parte, pentru clasa de probleme restricte, putem sa eliminam posibilitatea minimului local și sa demonstram ca imbunatatirea locala de asemenea poate sa detina intiietate la imbunatatirea globala. Pentru multe clase de asemenea probleme, timpul polinomial al algoritmurilorpoate sa decurga mai lent decit timpul global.. Ca contrast, tot timpul polinomial al algoritmilor pentru solutionarea probleme de programarea neliniara are forma unei metode de continuitate.

2.3.2 Metoda de Continuitate

In aceasta metoda in probleme discrete solutiile, sunt o mulțime de solutii posibile in problema combinatoriala dată. Proproetatile topologice și geometrice al spatiului de continuitate joaca un rol important pentru construirea algoritmului, și in deosebi pentru analiza a eficacitatii proprii.

Algoritmul include in sine prin formarea punctelor a unui spatiu largit, care este aproximativ solutia problemei combinatoriala originala. La fiecare pas de baza al algoritmului, urmatorul punct care a fost primita din urma consecutivitatii punctului posterior face ca aproximarea globala sa fie foarte buna

De obicei este posibil unind traiectoria continuitatii.

Particularitatea topologica: bazata pe spatiul continuitaii ca exemplu, legatura dintre nivelele funcții, optimizata care a fost folosita pentru numarul minimului local și alegerea formularii efective a problemei de optimizare continua.

Particularitatea geometrica ca exemplu, distanta, volumul și curba traiectoriei folosita pentru analiza eficienta al algorimului, deoarece particularitatea topologica ajuta la determinare dacă algoritmul corespunzator va coincide total.

2.3.3 Optimizarea Globala.

In ficare pas de baza al algoritmului, subecuatia este solutiionata, pentru a primi urmatorul punct in continuitate. Subecuatia trebuie sa satisfaca urmatoarele doua conditii::

(i) aceasta trebuie sa fie o aproximare globala in problema originala; și

(ii) trebuie sa ca solutia sa fie solutionata efectiva.

Teorema: Dind orice tip P și punctul interior xP, exista o transformare T, care transforma P in P’, și x, unde x’P’. Pentru ca asta sa fie posibil, trebuie sa fie in spatiul limitat care are forma unui cerc limitat cu B(x’,R) P, Raza R, centrul x’, care contine P’și cercul inscris B(x’,r)P de raza r, centrul x’ apartine in P’ așa dar coeficintul R/r – este cela mai mare n care este submulțime al lui T.

Cercul inscris este folosit ca spatiu pentru optimizare al subecuatiilor și satisface cele doua conditii de mai suscare au fost enuntate mai sus.

3. Rezolvarea numerică a problemei MAX-CUT

3.1 Determinarea Tăieturii Maxime

3.1.1 Întroducere.

Problema determinarii taieturii maxime intr-un graf este o problema de optimizare discreta. Fiind dat un graf finit și neorientat, problema consta in impărțirea vîrfurilor grafului in doua mulțimi de vîrfuri care se leaga intre ele cu muchii și suma muchiilor este maximă. In general, rezolvarea problemelor de așa natura necesita o enumerare completă a solutiilor admesibile. O tehnica actuala de rezolvare a problemelor de optimizare combinatoriala consta in relaxarea convexa a domeniului de solutii admesibile. Un rol important in aceste probleme il joaca relaxarea semidefinită care transforma problema originala, dată in spatiul vectorial n , intr-o problema de programare liniara in spatiul matriciilor simetrice semidefinite n x n. Problema relaxata este o problema de programare convexa și poate fi rezolvata intr-un timp polinomial.

In lucare problema determinarii taieturii maxime se reformuleaza ca o problema de programare patratica cu restrictii patratice. Se prezintă relaxările bazate pe programarea semidefinită. Se arata ca toate aceste relaxari sunt echivalente intre ele și ca sunt produse de Dulaitatea Lagranje.

În acesata lucrare, vom considera vîrfurile grafurilor finite, ponderate, și neorientate G(V,U), unde V=(v1, v2,… vn)este mulțimea vîrfurilor(nodurilor), iar U-este mulțimea muchiior , mulțime care nu contine bucle și muchii mulțiple. Fiecarei muchii (vi, vj)U i se asociaza o valoare(ponderea) aij=aji0. Vom defini aij=0 in cazul care (vi, vj)U, adica în cazul cind vi și vj nu sunt adiacente. Matricea de adiacenta sociata acestui graf va fi notata A=( aij).

Fie SV o submulțime nevida a lui V.

Definitie : O tăietura (S) este o mulțime de muchii (vi, vj)U cu proprietatea ca, dacă viS, atunci vjV\S.

Se pune problema determinarii taieturii (S) cu valoarea maximă a sumei ponderilor muchiilor, adica a partitionarii mulțimii V in doua părți S și V\S astfel ca suma este maxim posibila oricare ar fi SV. Aceasta problema numita și problema MAX-CUT, are diverse aplicații. Problema Max-Cut, face parte in caz general din clasa problemelor –PN necomplete și este foarte greu rezolvabila intr-un timp polynomial numai in cazuri speciale, de exemplu, cind graful este planar.

Problema considerata poate fi formulata ca problema de programare patratica cu restrictii patratice. Pentru aceasta, vom introduce variabilele xi: i=1,2,3,4,…n, sau xi=1 și xi=-1 dupa cum vîrful vi aprtine sau nu mulțimii S.

Dacă vîrfurile vi și vjS sau mulțimii V\S, atunci xi=xj, și deci xixj=xi2=xj2=1. Ina cazul cind xi=-xj, adica avem viS, atunci vjV\S, sau invers și atunci vom avea xixj=1, rezulta ca:

unde x=(x1, x2,… xn)T și e=(1,1,1,…1)T, iar Diag(Ae) este matricea diagonalacu diagonala formata de vectorul Ae.

Matricea L=Diag(Ae)-A se numeste matricea Laplace asogiata grafului G cu matricea adiacenta A. Elementele lij al acestei matrice satisfac relatiile: lij=-aij=lji, ij,

dacă matricea lui Laplace L este pozitiv semidefinită. Notind Q=1/4L, problema determinarii unei taieturi maxime in grafuri neorientate poate fi reformulata astfel :

(3.1)

Aceasta problema este un caz particular al unei probleme de programare patratica cu restrictiipatratice și este deficila de rezolvat : este o problema NP-completă. Mentionam ca in functia obiectiv q(x) lipseste componenta liniara, prezenta, in caz general, in funcțiile patratice. Printr-un procedeu simplu functia patratica :

in care , mai poate fi redusa. Intr-adevar, definim matricea simetrica de dimensiune (n+1)x(n+1).

și considerăm vectorul : , unde variabila suplimentara satisface relatia : Atunci :

Dacă solutia optimă , atunci , iar dacă , atunci este o solutie optimă și pemtru , adica dacă putem schimbă cu .

Relaxarea Semidefinită

Problema (1) este o problema NP-completă. Ea este un caz particular al unei probleme de programare patratica cu retrictii patratice și este dificila de rezolvat. In general, rezolvarea problemei de optimizare combinatoriala necesita o enumerare completă a solutiilor admesibile. De aceia, analizam relaxarea ei. Ideea de baza consta in relatia xTQx =Tr(xTQx), unde Tr)= reprezintă urma matriciei, adica Tr(A)=.

Notam cu X = xTx, este pozitiv semidefinită și rang(xTx) = 1. Din x2 = 1, i=1,2,..n rezulta ca diag(xTx)=e, unde diag(X) semnifica vectorul de pe diagonala principala a matriciei X. Se demonstreză ca problema considerata (1) este echivalenta urmatoarei probleme:

(3.2)

Renuntind in (2) la conditia de rang(X) = 1, se ajunge la problema relaxata:

(3.3)

semidefinită și duala, ei poate fi formulata in felul urmator:

(3.4)

Domeniul solutilor admesibile este urmatorul: pentru problema (1.4) este o mulțime convexa, și prin urmare, problema (3.1) este o problema de programare convexa, care are o complexitate polinomiala.

Așadar, problema duala (3.2) este mai “usor” de rezolvat decit problema considerata (1.1), care este o problema NP-completă.

Notam vectorul eTi = (0,0,..0,1,0,..0,0), unde unitatea este pe pozitia i, i=1,2..n. Fie matricea Ei = eieTi. Atunci putem scrie: Diag(u)=. Cu aceste notari problema (3.2) devide :

(3.5)

Goemans și Wiliamson au estimat ca: q*=max{xTQ│x2i=1, i=1,2,..n } ≤ 0.87856 min{eTu│uT}

3.2 Metoda gradientului cu fractionare a pasului

Formularea unei problemede optimizare fara restrictii impune determinarea componentelor vectorului de pozitie x=(x1, x2, …xn)T, care minimizeaza sau maximizeaza functia – obiectiv(scop) f(x,), xn. Din punct de vedere formal nu exista o deosebire intre minimizarea sau maximizare functiei obiectiv, deoarece minimul f(x) are loc pentru maximul lui –f(x).

Fie problema de optimizare neconditionata:

f(x)min;

xRn;

Metodele numerice de cautare a minimului reprezintă procese iterative astfel incit, pornind de la un vector inițial x(0) se genereaza șirul de vectori { x(k)}, pentru care f(x(0)) >f(x(1))> … > f(x(k)) > … O deplasare tipica intre x(k) și x(k+1) este dată de relatia recurenta: x(k+1)= x(0)+kd(k), in care d(k)- defineste directia de deplasare, iar k- determina marimea acestei deplasari. Gradientul unei funcții indica directia celei mai mari cresteri. Alegind directia de cautare in sensul opus al gradientului, adica in sensul antigradientului, determinat de – f(x), ne vom plasa pe directia celei mai rapide descresteri. Avansul de-a lungul acestei directii va avea loc atita timp cit valoarea functiei scade, dupa care directia de avans se va schimba conform unei noi orientari a antigradientului și așa mai deoarte, pina se atinge minimul.

Alegind antigradientul ca directie de deplasare, obtinem procesul iterativ:

x(k+1) =x(k) – kf(x(k)) (3.6)

Valoarea parametrului k se determina din conditia minimizarii functiei in directia antigradietului:

f(x(k) – kf(x(k)))= min f(x(k) – f(x(k))) (37.)

Metoda de gradient (1.1) in care lungimea pasului se alege din (3.7) se numeste metoda celei mai rapide descresteri.

In conexiune cu utilizarea calculatoarelor metoda gradientului e mai eficienta, dacă marimea pasului de deplasare k se determina prin modificarea lui. Algoritmul corespunzator se bazeaza pe urmatorii pași:

se alege valoarea arbitrara (una și aceași la fiecare iteratie), se determina punctul x(k) – f(x(k)) și se calculeaza f(z);

se verifica conditia

f(z)-f(x(k)) -║ f(x(k))║2 (3.8)

unde este o constanta arbitrara in intervalul (0,1);

dacă este indeplinita inegalitatea (3.8), atunci valoarea este acceptata și se va lua k = . In caz contrar se fractioneaza prin imlutirea lui cu un numar arbitrar pozitiv și <1. Procesul se continua pina cind este satisfacuta conditia (3.8).

Așadar, k = trebuie astfel de determinat incat sa fie asigurata descresterea functiei – obiectiv conform conditiei (37).

Metoda gradientului in care k se determina prin procedeul descris se numeste metoda gradientului cu fractionarea pasului.

Exemplu: Fie problema de minimizare neconditionta:

f(x1,x2)=x1 ,x2 min

Sa aplicam metoda celei mai rapide descresteri, considerind punctul inițial x(0)=(1,1)T

f(x) = , d(0) = -f(x(0))=

Avem: f(x(0)), (). Conditia ()=0 implica .

Constatam ca x(1) = x(0) +0d(0) și f(x(1))=f(x(0)), și așa procedam cu restul.

Noi vom continua procesul, pina cind:

║f(x(k))║< (3.9)

unde >0 este precizia de atingere a minimului.

Mentionam, ca in general, atunci cind ne apropiem de un punct de minim local al functiei f, metoda gradientului converge lent. Se constata cu usurinta ca in metoda celei mai rapide descresteri:

(d(k+1), d(k)) = 0, adica f(x(k+1)) f(x(k))

Acest lucru inseamna ca pentru funcții cu panta mare, adica pentru funcții suprafata carora reprezintă o “ripa” metoda celei mai rapide descresteri converge foarte lent; din acest motiv inegalitatea (4) este greu de asigurat . In practica metoda gradientului este oprita chiar dacă nu a fost atinsa conditia (4), dar se constata variatii semnificative in valorile functiei obiectiv corespunzatoare citorva iteratii consecutive.

3.3 Funcția de barieră logaritmică

La inceput metoda barieierei logaritmice foloseau metoda Newton, pentru solutionarea consecutivitatea problemei de forma:

unde parametrul se micsoreaza tinzind la zero.

Asemenea tipuri de algoritmi au fost anlizati de catre Faybusovich iar mai tirziu de catre alti invatati. Fie, ca conditia X este pozitiva semidefinită a barierei logaritmice, conditia este sustinut și supus coordonarii metodei lui Newton, in procesul dat minimizarile mari cere o corectie pentru pașii lui Newton. Metoda Primala-duala in scurt timp va fi cea mai des folosita. Aceste metode de minimizare a intervalului dual : Tr(CX) – bTy =Tr(XS) și aplicind functia duala primala combinatorie a barierei logaritmice: fpd = -(log(det(X)) + log(det(S))) = -log(det(XS)).

Asociem problemei duale (1.4) functia de bariera logaritmica:

B(u) = ln det(Diag(u)-Q)

Aici det inseamna determinantul matriciei considerate.

Prin urmare

B(u) = diag(C-1(u)) (3.10)

Metoda punctului interior pentru problema (1.4) consta in rezolvarea șirului de probleme de optimizare neconditionata:

ETu – klndet((u)-Q)min (3.11)

un

unde parametrul de bariera k este un numar real fixat și k0. Conditia de optimalitate pentru problema de optimizare conditionata (1.7) este:

e – kdiag(C-1(u))=0 (3.12)

Problema (3.11) poate fi rezolvata cu ajutorul metodelor de gradient (metoda celei mai mici descresteri, metoda gradientului conjugat, s.a); criteriul de stopare fiind indestularea aproximativa a conditiei (3.12). Aceasta necesita calculul gradientului , functiei de bariera B(u) dat prin formula (3.10). Dupa cum se vede din (3.10), avem nevoie de elemenetele de pe diagonala principala a mtariciei invese C-1(u). Este bine cunoscut ca inversarea matriciilor este o operatie costisitoare și trebuie evitata in practica.

3.5 Factorizare Cholesky

Metoda lui Cholesky de rezolvare a sistemelor de ecuatii algebrice se mai numeste metoda radacinii patrate și consta in descompunerea sistemului Ax = b in doua sisteme triunghiulare:

LTy = b, Lx = y.

Aici L și LT sunt matriciile:

și

In aceasta metoda se presupune ca matricea A este o matrice simetrica și poztiv definită.

Matricea L se alege astfel, incit A = LTL. Aceasta descompunere a matriciei A se numeste Factorizare Cholesky Are loc:

Teorema: Dacă matricea A este simetrica și pozitiv definită, atunci exista o matrice unica inferior triunghiulara LT cu elemenetele diagonale pozitive, astfel incit A = LTL.

Inmulțind matricele LT cu L și egalind produsul obtinut cu matricea A obtinem formulele de calcul pentru elemenetele lij:

; , j=1,2,..n

Dupa ce sau obtinut primele (k-1) coloane ale matriciei L se calculeaza elemenetele coloanei k astfel:

Sistemul Ax = b este compatibil definit dacă Ikk 0, k=1,2..n. Intr-adevar, deoarece pentru determinantul matriciei A are loc relatia:

A=LTL=L2 = (l11*l22*..*lnn)2 0.

Rezulta ca acest sistem are o solutie unica.

Fiind determinata Matricea LT, obtinem doua sisteme de ecuatii liniare algebrice cu matrice triunghiulare in raport cu vectorii necunoscuti x și y:

Din primul sistem, in mod direct, calculam componenetele vectorului y dupa formulele:

In sfirșit din al doilea sistem , cu matricea superioara triunghiulara susccesiv determinam solutia sistemului Ax = b:

3.6 Metoda gradientului în Optimizarea Necondiționată.

Majoritatea algoritmilor iterativi care urmaresc sa determine un punct de minim x* al functiei f: RnR se bazeaza pe un algoritm general:

Se considera un punct inițial x0 care satisface conditia:

c(x0) = {xRnf(x) f(x0)} (3.13)

Considerind ca, la iteratia k, (k=0,1,2,…) suntem in posesia punctului xk, punctul xk+1 se pbtine prin relatia: xk+1 = xk + pkdk (42) unde dkRn, este o directie de descrestere a functiei f, pornind din xk, iar scalarul pk este pasul pe directia dk.

Majoritatea algoritmilor folosesc proprietatea ca directia antigradientului (-f(x)) este directia de maximă descrestere a functiei f in vecinatatea punctului x și astfel directia dk se “leaga” intr-un fel sau altul de directia gradientului.

Fie M(x), matrice patratica de ordinul n, pozitiv definită de punctul x.

Atunci, pașii algoritmului general la iteratia k sunt:

Pasul 1. Este cunoscut punctul xk.

Pasul 2. Se calculeaza f(xk), iar dk= -M(xk) f(xk).

Pasul 3. – Dacă dk=0 salt la pasul 7.

Dacă dk0 salt la pasul 4.

Pasul 4. Se determina pasul pk de inaintare pe directia dk deci:

F(xk+pkdk) = (3.14)

Pasul 5. Se determina din nou punctul xk+1 cu formula (3.13).

Pasul 6. k: = k + 1 și salt la pasul 2.

Pasul 7. Algoritmul se opreste și x: = xk

Teorema 3. Fie xk șirul generat de algoritmul generat. Șirul este sau finit, xi atunci se termina cu un punct xk, in care f(xk) = 0, sau finit, și atunci orice punct limita x* satisface conditia f(x) = 0.

3.7 O procedura eficienta de calculare a gradientului în Max-Cut

Notam elemenetele de pe diagonala principala a matriciei C-1(u) prin . Așa cum

, din cele de mai sus rezulta:

Prin urmare calculul elemenetelor se reduce la minimizarea a n funcții patratice cu una și aceași matrice pozitiv definită C(u).

Fie acum cunoscuta factorizarea Cholesky pentru matricea C(u), adica

C(u)=FT(u)F(u),

unde F(u) este o matrice inferior triunghiulara. Atunci:

Notam prin rin solutiile sistemului de ecuatii liniare:

FT(u)ri = ei, unde i=1,2,..n (3.15)

Așa dar, avind factorizarea Cholesky componentele gradientului functiei de bariera B(u) pot fi calculate astfel:

unde vectorii ri sunt solutiile sistemului (1.9).

Remarcăm că dacă se cunoaste Factorizarea Cholesky C(u) = FTF usor poate fi calculata și valoarea functiei scop in problema (3.15):

Un exemplu de problemă rezolvată prin metoda tăierea Max-Cut într-un graf, este arătat în Anexa 7 (vezi Anexa 7), iar algoritmul metodei de tăiere MAX-CUT într-un graf este aratat în anexa 2 (vezi anexa2). Schema tăieri MAX-CUT a unui graf este arătat în anexa 3 (vezi anexa 3).

4. PROIECTAREA TEHNICO-ECONOMICĂ A PROIECTULUI

4.1 Definirea sistemului informațional

Sistemul informațional poate fi definit ca ansamblul datelor, informațiilor, fluxurilor și circuitelor informaționale, procedurilor și mijloacelor de tratare a informațiilor menite să contribuie la stabilirea și realizarea obiectivelor organizației.

De reținut că o asemenea definire a sistemului informațional are un caracter cuprinzător, în sensul că include spre deosebire de definițiile date de alți specialiști și informațiile, fluxurile informaționale și mijloacele de prelucrare a datelor, După opinia noastră, definirea sistemului informațional pornind de la rolul său în ansamblul activităților întreprinderii este o condiție sine-qua-non pentru înțelegerea corectă nu numai a problematicii informaționale, ci și, în genere, a problematicii manageriale.

Accentuăm asupra acestui aspect întrucât, nu de puține ori, mai ales unii informaticieni, pun semnul egalității între sistemul informatic, care se rezumă în esență la culegerea, transmiterea și prelucrarea cu mijloace automatizate a informațiilor, și sistemul informațional care, conform definiției de mai sus, este sensibil mai cuprinzător.

Raporturile dintre sistemul informațional și cel informatic sunt de întreg-parte (figura nr.1)

Definiția de mai sus are și un caracter realist prin aceea că nu condiționează ca ansamblul elementelor încorporate să fie riguros organizate prin integrate. într-o societate comercială sau regie autonomă există un sistem informațional chiar dacă componentele sale nu sunt integrate sau organizate riguros, ceea ce firește că se reflectă în diminuarea calității sale de ansamblu.

Lucrul cu Softurile Informational moderne elaborate cu ajutorul diferitor instrumentarii Soft este destul de dificil mai ales în cazul când numărul de clienți și de fișiere accesate în sistemul dat este destul de mare. De obicei elaborarea unui astfel de algoritm, efectuat fără utilizarea unor instrumentarii, tehnici specializate durează mult timp (până la câteva luni) și este strict individual pentru fiecare caz aparte. În final rar se obține o versiune a algoritmului care să nu includă careva erori sau să poată prelucra necesarul cererilor rulate în seansul specific de lucru.

Proiectul calculat și precăutat este elaborat utilizând modele și metode programabile optimizate. El poate fi utilizat în cele mai diverse ramuri: de la sisteme de rețea locale (rețele de calculatoare universitare, școlare, corporative, linii tehnologice) și până la unități de accesare din sfera socială globală.

Din aceste raționamente am recurs la proiectarea și elaborarea Softului Informational : ”Determinarea Taieturii maxime intr-un graf folosind Programarea Semidefinita” și implementarea lui practică care ar fi destul de rentabila, dat fiind faptul că el permite realizarea unui set foarte larg de solutionare de probleme MAX-CUT.

Prin utilizarea unei tehnici sigure și a mijloacelor soft moderne se micșorează cheltuielile pentru întreținerea tehnică, care frecvent sunt comensurabile sau chiar depășesc cheltuielile necesare procurării computerilor și programelor soft.

Cercetările asupra algoritmului studiat și elaborat întră în categoria lucrărilor experimentale și de producere. Organizarea și petrecerea optimă a Lucrărilor Experimentale și de Producere permite ridicarea calității și eficienței producției. În acest capitol am prezentat partea organizatorică a lucrărilor petrecute și aprecierea lor economică.

Lucrarea de diplomă conține nuanțe atât de lucrări de cercetări științifice cît și de lucrări de producere experimentală.

LEP conține următoarele etape generale:

elaborarea și concordarea sarcinii tehnice;

colectarea și studierea materialelor referitor la tema dată;

elaborarea sarcinii tehnice;

calculul cheltuielilor pentru LEP;

designul sarcinii tehnice;

argumentarea economică;

elaborarea antiproiectului;

elaborarea principiilor de rezolvare a sarcinii;

elaborarea structurilor principale;

elaborarea și testarea modelelor posibile;

documentarea proiectului;

elaborarea proiectului tehnic;

elaborarea modelului algoritmului;

controlul tehnologic;

argumentarea proiectului tehnic.

elaborarea documentației pe algoritmul experimental:

elaborarea documentației textuale;

calculul cheltuielilor pe materiale.

4.2 Etapele de proiectare.

La elaborarea lucrării s-a aplicat un algoritm bine întemeiat, în scopul micșorării timpului de lucru. Succesiunea acestui algoritm este următoarea:

Pregătirea pentru descrierea sarcinii.

Familiarizarea cu descrierea sarcinii.

Elaborarea algoritmului.

Scrierea programului conform schemei-bloc elaborate.

Depănarea programei.

Pregătirea documentației conform sarcinii.

Cheltuielile de muncă depuse pentru realizarea acestui proiect se calculează după formula :

t = to + tf + ta + ts + td + tdoc (4.1)

to – cheltuielile de timp obținute la pregătirea pentru descrierea sarcinii.

tf – cheltuielile de timp obținute la familiarizarea cu descrierea sarcinii.

ta – cheltuielile de timp obținute la elaborarea algoritmului.

ts – cheltuielile de timp obținute la scrierea programului conform schemei-bloc elaborate.

td – cheltuielile de timp obținute la depănarea programei.

tdoc – cheltuielile de timp obținute la pregătirea documentației conform sarcinii.

Cheltuielile de timp pentru familiarizarea cu descrierea sarcinii, ținând cont de calificarea programatorului:

Tf=Q*B/(85*k) [ore] (4.2)

Unde: Q=qc(1+p) numărul convențional de instrucțiuni în program

q – numărul de operatori. Numărul de operatori este de 1500. Estimarea acestui număr s-a efectuat cu ajutorul conducătorului de diplomă.

c – coeficient de complexitate (c =1.8, deoarece complexitatea programului este puțin dificilă).

p – coeficient de corecție a programului în timpul elaborării. Deoarece problema a fost discutată la începutul elaborării softului, schimbările adăugătoare au fost minime (p = 0.05).

B – coeficientul majorării cheltuielilor de lucru în urma insuficienței descrierii problemei. Deoarece cheltuielile utilizate pentru finisarea programului au fost puțin mai mari, acest coeficient este egal cu 1.8.

k– coeficientul de calificare a programatorului (k = 0.8, deoarece stajul de lucru e pînă la 2 ani).

Q=1500*1,8*(1+0,05)=2835

Tf= 2835*1,8/(85*0,8)=75,04 [ore]

Cheltuielile de timp pentru elaborarea algoritmului:

Ta=Q/22*k=2835/(22*0,8)=161,07 (ore)

Cheltuielile de timp pentru scrierea programului conform schemei-bloc elaborate:

Ts=Q/23*k=2835/(23*0,8)=154,07 (ore)

Cheltuielile de timp pentru depănarea programei

Td=Q/4,3*k=2835/(4,3*0,8)=824,13 (ore)

Cheltuielile de timp pentru pregătirea documentației conform sarcinii

Tdoc=Tm+Tr=Q/(19*k)+0,75*Q/(19*k)=1,75*2835/(19*0,8)=326,4 (ore)

Deoarece am lucrat asupra programului câte 9 ore pe zi, rezultă că timpul de lucru Tlucru se v-a calcula în felul următor: tzi = 9 ore/zi ;

t = to + tf + ta + ts + td + tdoc =14+75,04+161,07+154,07+824,13+326,4 = 1554,71.

Tlucru= t / tzi= 1554,71 / 9 =172 zile

Etapele cercetării științifice.

În general efectuarea lucrărilor de cercetare științifică include următoarele etape:

Lucrările pregătitoare. La această etapă se face cunoștință cu direcțiile și natura lucrărilor de cercetare științifică, studierea experienței anterioare în domeniile corespunzătoare de cercetarea și motivarea tehnico-economică preventivă.

Etapa se încheie cu întărirea sarcinii tehnice.

Prelucrarea teoretică a temei. Aici se efectuează alegerea și motivarea direcției alese de cercetare și metodele de rezolvare a problemelor formulate, elaborarea ipotezelor de lucru, calculele teoretice, elaborarea metodicii cercetărilor experimentale.

Faza experimentală. La etapa dată se efectuează proiectarea, implimentarea, depanarea și montarea machetei. Etapa se finalizează cu efectuarea experimentelor, prelucrarea datelor obținute și verificarea lor cu rezultatele cercetărilor teoretice.

Faza perfecționării teoretice. La această etapă se realizează un șir de lucrări ce țin de corectarea părții teoretice în conformitate cu rezultatele obținute din experiență.

Faza finală. Etapa se caracterizează prin generalizarea rezultatelor cercetărilor efectuate, se elaborează darea de seamă pentru lucrarea de cercetare științifică, se determină eficacitatea reală a ei. Etapa se finalizează cu acordarea și întărirea rezultatelor cercetării la consiliul tehnico-științific.

Pentru cercetarea unor probleme complicate se utilizează o metodă complexă, care se bazează pe analiza în complex a proceselor și scopurilor din problema pusă. Metoda mai presupune și elaborarea unui scop, necesită determinări a fluxului de intrare și ieșire a informației, Întroducerea criteriilor de optimizare. Mai ales sunt importante metodele de modelare, care permit studierea proceselor complexe într-un regim de analiză preliminară.

4.4 Evaluarea economică a proiectului.

Lucrarea de diplomă conține nuanțe atât de lucrări de cercetări științifice cît și de lucrări de producere experimentală.

Proiectul: "Determinarea taieturii MAX-CUT intr-un graf cu ajutorul Programarii Semidefinite“ este destul de simplu pentru lucru poate fi la indemina oricarui utilizator care incearca sa optimizeze un graf prin metoda MAX-CUT.

Proiectul este destinat pentru studierea metodelor de optimizare, ar fi foarte bine daca de acest soft s-ar folosi in institutii superioare si posterioare, la catedre de matematica si centre de cercetare in domeniul matematicii superioare aplicate de catre doctori in stiinte in domeniul respectiv, profesori, lectori asistenti, studenti si alte persoane care ar avea nevoie de optimizare a unei probleme de programare semidefinita. Algoritmul care a fost elaborat pentru crearea programului de cercetare a taieturii maximea intr-un graf cu ajutorul programarii semidefinite – este compatibil si foarte util pentru programator. Proiectul dat cere o atentie deosebita in cazul testarii manuale al programului.

Cercetind in continuare tematica proiectului dat si folosindu-ne de resursele electronice, se poate de creat un soft foarte sofisticat pentru calculele complexe din compartimentul de optimizarea cu ajutorul programarii semidefinite. Se poate de comparat acest proiect cu diferite softuri care sunt legate de domeniul calculelor, operatiunilor si metodelor din matematica superioara.

Pentru vinzarea acestui Soft este necesara licenzia pentru rularea programului.

4.5 Planificarea grafului-rețea.

Proiectele tehnologice contemporane sunt caracterizate de următoarele particularități:

tehnica nouă utilizată este foarte complexă și este construită utilizând ultimele elaborări științifice; accelerării vitezei de elaborare a proiectelor; proiectele referitoare la complexele tehnicii de calcul și softului sunt supuse uzurii morale foarte rapide; necesitatea proiectării de sistemă la elaborarea softului și sistemelor tehnice.

Toate acestea au dus la necesitatea de creare a noi metode de planificare. Una din aceste metode prezintă modelarea procesului de elaborare, adică prezentarea legăturilor și caracteristicilor lucrărilor în procesul elaborării proiectului.

Metodele tradiționale de planificare presupun utilizarea celor mai simple modele de construirea diagramelor de tip consecutive și ciclice.

Dar în asemenea diagrame nu este posibil de a prezenta legăturile dintre niște lucrări, de unde rezultă imposibilitatea de a afla cât de importantă este lucrarea dată pentru executarea scopului final. Pot apărea diferite întârzieri în timp, ce apar pe porțiuni de interconectare a lucrărilor, care sunt complicat de prezentat în diagrame. De obicei, în procesul dirijării se culege informația despre lucrările efectuate și aproape nu se culege și nu se prezintă informația referitor la prognoza finisării lucrărilor viitoare, de aceia este imposibil de a prognoza rezultatele diferitor variante de soluționare la modificările planului inițial de lucru. Este de asemenea complicat de a reflecta și dinamica lucrărilor, de a corecta toată diagrama în legătură cu schimbarea termenilor de efectuare a unei lucrări, ce este necesar de a efectua ca să nu schimbăm termenul de efectuare a întregului complex de lucrări.

Aceasta este doar o parte mică din neajunsurile metodelor utilizate în prezent pentru planificarea și prezentarea grafică a planurilor de pregătire a producerii. Aceste neajunsuri în mare pare sunt excluse de către sistemele de planificare și dirijare în rețea utilizate în prezent.

Sistemele de planificare și gestiune în rețea prezintă un complex de metode grafice și de calcul, metode de control și de organizare, care asigură modelarea, analiza și reconstruirea dinamică a planului de executare a proiectelor complexe.

Sistemele de planificare și gestiune în rețea este o metodă cibernetică creată pentru gestiunea cu sisteme dinamice complexe cu scopul asigurării condiției de optim pentru careva indicatori. Așa indicatori, în dependență de condițiile concrete, pot fi:

– timpul minim pentru elaborarea întregului complex de lucrări;

– costul minim al elaborării proiectului;

– economia maximală a resurselor.

Particularitățile sistemului de planificare și gestiune în general sunt următoarele: se realizează metoda proiectării de sistem la rezolvarea problemelor de organizare a gestiunii proceselor; se utilizează modelul informațional-dinamic special (graful-rețea) pentru descrierea matematico-logică a procesului și calculul automat (conform algoritmului) a parametrilor acestui proces (durata, costul, forțele de muncă, etc.); se utilizează sisteme de calcul pentru prelucrarea datelor operative pentru calculul indicatorilor și primirea rapoartelor analitice și statistice necesare.

Documentul de bază în sistemul de planificare și gestiune în rețea este graful-rețea (modelul rețea), care prezintă modelul informațional-dinamic, în care sunt prezentate legăturile și rezultatele tuturor lucrărilor, necesare pentru atingerea scopului final.

Tab.4.1

Graful-rețea : determinarea evenimentelor grafului

Pentru fiecare lucrare se determină timpul de îndeplinire a ei. Este foarte greu de prezis timpul de îndeplinire a unor lucrări, de aceea alegem timpul probabil.

Tab.4.2.

Determinarea duratei lucrărilor (timpul în zile)

4.6 Calculul parametrilor grafului-rețea.

Tab.4.3

Calculele parametrilor grafului-rețea.

Aprecierea economică a proiectului constă în determinarea eficienței așteptate a utilizării rezultatelor cercetării. Pentru determinarea eficienții economice este necesar de calculat cheltuielile pentru efectuarea cercetărilor.

Unul din capitolele, care se include în planul de cheltuieli este “Materialele și semifabricatele procurate”. Denumirea materialelor, prețul lor și cantitatea necesară sânt date în tabel. De asemenea aici se includ și cheltuielile de transport, luate ca 10% din suma totală a prețurilor materialelor.

Tab.4 .4

Materialele și semifabricatele procurate

Mărimea salariilor lunare pentru diplomant și conducătorul diplomei au fost stabilite la 250.00 lei și 650.00 lei respectiv. Mai jos, conform timpului de lucru vom calcula salariile respective pe toată durata cercetării.

S(C) == 827,3 (lei) (4.3)

S(D) == 1954,6 (lei) (4.4)

unde: Nzl – numărul de zile lucrate.

Conform datelor calculate anterior Nzl(D) = 172.(zile)

Deoarece consultațiile oferite de către conducătorul diplomei aveau loc în primele 20 săptămâni o dată pe săptămână și în ultimele 4 săptămâni de două ori, rezultă că Nzl(C) = 28 (ore).

Nzlt – numărul de zile lucrătoare într-o lună. Sl – salariile lunare.

Tab.4.5

Prezentarea salariilor de bază

Salariile suplimentare constituie 12% din salariile de bază.

Tab.4.6

Prezentarea salariilor suplimentare

Defalcările în fondul social de asigurare sunt calculate în procente de la salariul lunar și cel suplimentar, și constituie 28% :

(2781,8+333,83) * 28% = 872.37 (lei).

În cheltuielile pentru elaborarea softului dat mai intră și cheltuielile legate de folosirea calculatorului. Calculatorul este mediul principal, cu ajutorul căruia s-a realizat proiectul de diplomă.

t = (ta + ts + td + tdoc )/9 = (161,07+154,07+824,13+326,4)/9 =163 (zile)

Așadar, conform etapelor de proiectare calculatorul a fost utilizat pe o perioadă de 163 zile, timp în care s-au desfășurat o serie de activități. Deoarece procurarea soft-ului și hard-ului în domeniul Tehnologiilor Informaționale este considerată investiție capitală, vom amortiza aceste cheltuieli timp de 2 ani, fiindcă aceste produse sunt supuse uzurii morale rapide. Să calculăm cheltuielile de energie electrică:

Ec = P C N [kW] (4.5)

unde:

Ec – suma de bani cheltuită pentru energia folosită;

P – Puterea de lucru a calculatorului;

C – prețul (costul) unui kwatth;

N – numărul de ore.

Luând în considerație că am lucrat 9 ore pe zi atunci N =163 9= 1467(ore)

Ec = PCN = 0,40.651467 = 381,4 (lei)

Norma de amortizare constituie 30% din costul calculatorului, care este de 6500 lei, iar imprimanta 3250 lei.

Amortizarea calculatorului și a imprimantei se calculează conform formulei:

Acalculator= 6500*0.3*163/365 = 580,54 (lei)

Aimprimanta= 3250*0.2*163/365 = 217,73 (lei)

Tab.4.7

Cheltuieli pentru hard

Cheltuielile folosite pentru utilizarea calculatorului includ amortizarea și cheltuielile de energie, 1542,5 lei.

În timpul realizării sarcinii vor apărea cheltuielile suplimentare. Aceste cheltuieli sunt legate de gestionare, deservire, remunerarea muncii aparatului de conducere, cheltuieli legate de repararea încăperilor de producție, a inventarului, protecția muncii și a mediului ambiant etc.

Mărimea cheltuielilor de regie constituie 140% de la salariul de bază și cel suplimentar:

3115.63140% = 4361,9 (lei) (4.7)

În continuare se vor estima toate cheltuielile suportate pentru elaborarea softului. Ele vor include următoarele cheltuieli:

Cheltuieli pentru materiale .

Cheltuieli pentru salariul de bază.

Cheltuieli pentru salariul suplimentar.

Defalcări în fondul social.

Cheltuieli pentru arenda calculatorului.

Cheltuieli de regie.

Tab.4.8

Cheltuieli suportate pentru elaborarea programului

Tab.4.9

Estimarea prețului programului

În cazul măririi numărului de cereri a acestui soft, la vânzarea lui va fi necesar de inclus numai cheltuielile de multiplicare care sunt foarte mici comparativ cu costul lui. În rezultat vom obține un supraprofit, ceea ce ar fi foarte rentabil pentru programator. Dar mai luând în considerație lansarea proiectului pe plan mondial profitul poate deveni imprevizibil, ceia ce ar duce la sporirea bunăstării cum a programatorului așa și a companiei de sprigin.

4.7 Determinarea eficacității Sociale de la implimentare a proiectului

Acest Proiect de Diploma are un caracter de cercetare, a metodelor de Optimizare in grafuri cu ajutorul Programării Semidefinite.

Proiectului de diplomă este destinat: pentru Universitati de Cercetare in domeniul Matematicii Superioare și mai ales pentru capitolul Optimizarea in Metode Numerice și Cercetări Operționale.

Tab.4.10

Evaluarea eficacității sociale de la implimentare :

5. Protecția muncii

Întroducere

Lucrul în domeniul protecției muncii în timpul de față urmărește una din cele mai importante direcții în domeniul ocrotirii sănătății și ușurarea condițiilor de muncă prin Întroducerea tehnologiilor noi și automatizarea producerii, înlăturarea muncii manuale pe regiunile dăunătoare ceea ce pozitiv se reflectă asupra sănătății oamenilor.

Sub noțiunea de protecție a muncii (PM) înțelegem un sistem de acte legislative, social-economice, tehnice, igienice și măsuri curativo-profilactice, care asigură securitatea, sănătatea oamenilor în procesul de producție. Asigurarea protecției muncii se realizează cât la proiectarea proceselor de producție, atât și la procesul de realizare a lor. Direcția tranșantă de îmbunătățire a condițiilor de muncă este trecerea la noi tehnologii avansate cu un înalt grad de protecție a muncii.

Protecția muncii este asigurată prin conducerea procesului de producție după standardele de protecție a muncii, normele igienice, instrucții pentru protecția muncii. Importanța tot mai majoră în asigurarea protecției muncii o capătă conducerea după sistemul standardelor de securitate a muncii (SSSM). În standarde sunt formulate cerințele de protecție față de procesele de producție, utilaj, producția industrială, mijloace de protecție individuală a lucrătorilor, sunt stabilite normele și cerințele față de parametrii care caracterizează zgomotul, vibrația, ultrasunetul, impurificarea aerului, protecția electrică și antiincendiară.

Cu problemele de protecție a muncii este legată și organizarea științifică a muncii, care ia în considerație crearea condițiilor bune de lucru, folosirea îmbrăcămintei speciale, instrumentelor de muncă speciale etc.

Metodele de protecție a muncii sunt compuse din cercetarea condițiilor de lucru în acela timp și a proceselor tehnologice, a utilajului, a încăperii de producție, analiza cazurilor accidentale și a bolilor profisionale. Măsurile legate de crearea condițiilor de protecție în procesul muncii la întreprinderi se efectuiază în mod planificat. Ele sunt concretizate în urma semnării contractului colectiv dintre administrație și comitetul sindical local. Aceste măsuri conțin trei parți: măsuri pentru prevenirea bolilor profesionale, măsuri pentru prevenirea cazurilor accidentale, măsuri pentru îmbunătățirea condițiilor de muncă.

Conducerea cu protecția muncii este însărcinată cu îndeplinirea următoarelor funcții:

Determinată de formarea organelor de conducere a protecției muncii, coordonarea și organizarea lucrărilor în domeniul protecției muncii, reglamentarea obligațiilor și ordinii de interacțiune a persoanelor care sunt antrenate în conducere, primirea și realizarea hotărârilor (conducerea totală și răspunderea pentru starea protecției muncii este lăsată pe seama directorului; coordonarea lucrărilor pentru protecția muncii se îndeplinește sub conducerea inginerului principal). Organizarea nemijlocită a protecției muncii la întreprinderi este pusă pe seama secțiilor (birouri) pentru protecția muncii, inginerilor de protecția muncii.

Pregătirea organizării lucrului la întreprinderi pentru crearea condițiilor sănătoase de lucru a muncitorilor, preîntâmpinarea cazurilor accidentale în procesul producerii și a bolilor profisionale (pentru aceste probleme răspunderea totală este pe seama secției protecției muncii).

Printre problemele de bază pe care le rezolvă secția de protecție a muncii mai sunt: îmbunătățirea organizării măsurilor pentru protecția muncii, Întroducerea ideilor noi în domeniul protecției muncii, efectuarea controlului situației protecției muncii la întreprinderi.

Problemele administrației secției și maiștrilor de producere sunt:

asigurarea bunăstării utilajului, sculelor, mijloacelor de transport, îngrădirilor, organizarea corectă a locurilor de muncă, controlul lucrărilor, dacă acestea se conduc de instrucții în activitatea sa, efectuarea la timp a instructajului persoanelor noi angajate.

Controlul nivelului protecției muncii este îndreptat la verificarea condițiilor de muncă a muncitorilor, la determinarea abaterilor de la standardele (SSSM), normele și legile controlului de stat și a altor documente normative a protecției muncii, controlul îndeplinirii de către servicii și subunități a obligațiunilor în domeniul protecției muncii, la primirea hotărârilor efective pentru înlăturarea neajunsurilor.

Formele de bază de control pot fi: controlul operativ a șefului sau a altor conducători, controlul social-administrativ (cu trei nivele), controlul efectuat de serviciile de protecție a muncii la întreprindere, controlul efectuat de organele superioare, controlul efectuat de organele de control statal și inspecția tehnică a muncii.

Controlul social-administrativ se îndeplinește la trei nivele. La primul nivel de control maistrul și inspectorul social pentru protecția muncii în fiecare zi controlează, înainte de începerea lucrului, securitatea la locurile de muncă.

La nivelul doi de control, în fiecare săptămână conducătorul secției și inspectorul social superior pentru protecția muncii, împreună cu tehnologul, mecanicul și energeticianul secției controlează nivelul securității muncii în secție.

La nivelul trei de control, în fiecare lună inginerul principal a uzinei și inspectorul principal cu atragerea specialiștilor întreprinderii (mecanicul principal, energeticianul principal, tehnologul principal) fac controlul condițiilor și protecției muncii la întreprindere în general, verifică eficacitatea controlul de nivelurile întâi și doi.

Munca reprezintă activitatea rațională a omului, orientată spre satisfacerea necesităților materiale și spirituale ale societății. În procesul muncii omul interacționează cu mijloacele de producție, cu mediul de producție și cu obiectele muncii. În acelaș timp el, de regulă, se expune influenței unui mare număr de factori, diverși după natura sa, formele de manifestare și a unui șir de alți indicatori, care influențează asupra sănătății și capacității de muncă a omului.

Factorii de producție în dependență de consecințele lor se împart în periculoși și dăunători. Factorul, influiența căruia asupra lucrătorului în anumite condiții duce la traumă sau la altă înrăutățire rapidă a sănătății, se numește factor periculos de producție. Factorul, influiența căruia asupra lucrătorului în anumite condiții duce la îmbolnăvire sau scăderea capacității de muncă, se numește factor dăunător de producție. În dependență de nivelul și durata acțiunii, factorul dăunător poate deveni periculos.

După natura acțiunii asupra organismului uman factorii de producție periculoși și dăunători se împart în 4 grupe: fizici, chimici, biologici, psihofiziologici.

Securitatea muncii – starea condițiilor de muncă, din care este exclusă influiența factorilor de producție periculoși și dăunători asupra lucrătorilor. Acestă problemă este examinată și soluționată de către disciplina protecția muncii.

Protecția muncii este un sistem de acte legislative, social-economice, organizatorice, tehnice, acțiuni și mijloace igienice și curativ-profilactice, ce asigură munca securitatea, păstrarea sănătății și capacității de muncă a omului în procesul muncii. Protecția muncii reprezintă o disciplină științifică care enunță problemele securității muncii, prevenirii traumatismului și bolilor profesionale, incendiilor și exploziilor in producție, organizarea muncii. În legislația RM, în documentele normative și literatură de rînd cu termenul «protecția muncii» uneori se utilizează termenul «tehnica securității și sănitariei de producție».

Tehnica securității – sistem de acțiuni organizatorice și mijloace tehnice ce preîntîmpină sau reduc influența asupra lucrătorilor a factorilor de producție periculoși.

Sanitaria de producție – un sistem de mijloace tehnice și acțiuni organizatorice, ce preîntîmpină sau reduc influența asupra lucrătorilor a factorilor de producție dăunători.

Securitatea de incendiu – stare a obiectelor, pentru care cu o probabilitate fixată se exclude posibilitatea apariției și evoluției incendiului și influența lui asupra oamenilor, de asemenea și asigurarea protecției bunurilor materiale.

Condițiile de lucru neprimejdioase asigură productivitatea muncii, contribue la susținerea stării normale psihofiziologice a lucrătorilor. De condițiile de muncă depinde productivitatea și calitatea muncii, eficacitatea folosirii resurselor de muncă. În procesul de soluționare a problemelor tehnice este necesar de accentuat problema interacțiunii mediului de producție cu mediul ambiant. Urmările activității omului se reflectă pe scara nu numai locală sau regională dar și globală. Protecția mediului ambiant devine cea mai principală problemă socială și economică.

Starea condițiilor de muncă și securitatea muncii la centrul de calcul, încă nu corespund cerințelor moderne. Operatorii pentru pregătirea datelor, programatorii și alți lucrători se lovesc de acțiunea astfel de factori fizici de producție periculoși și dăunători, ca prezența zgomotului, radiația, pericolul de electrocutare, etc.

5.1 Controlul protecției muncii

Protecției muncii i se acordă o importanță mare, care este asigurată legislativ, material, organizatoric și științific. Asigurarea legislativă este bazată pe existența a multor legi, regulamente, articole în domeniul protecției muncii.

Asigurarea organizatorică constă în aceia, că conform legii la întreprinderi, unde sînt mai mult de 50 de angajați trebuie să fie un inginer al tehnicii securității, iar la întreprinderi unde sînt 1000 și mai mulți angajați, trebuie să existe un serviciu întreg și un punct medical.

Conform legii la fiecare întreprindere se formează conturi speciale pentru îndeplinirea măsurilor de ameliorare a condițiilor de muncă – aceasta este asigurarea materială. Este interzis de a folosi aceste fonduri în alte scopuri.

Înoirea tehnicii duce la apariția factorilor noi necunoscuți. Pentru cercetarea acțiunii lor asupra omului există diferite instituții și catedre – asigurarea științifică.

Sindicatele reprezintă fonduri speciale, pe lîngă contractul colectiv, elaborează o convenție de măsuri de ameliorare a condițiilor de muncă.

Controlul stării protecției muncii se efectuiază în 3 etape:

Inginerul laboratorului cu instructorul obștesc de la sindicate controlează starea protecției muncii în laboratorul dat în fiecare zi vizual.

Șeful catedrei cu președintele comisiei protecției muncii al laboratorului controlează o dată în săptămînă.

Șeful catedrei și președintele comisiei protecției muncii a comitetului sindical cu inginerul tehnicii securității controlează o dată în lună.

În laborator se efectuiază instructajul angajaților pe protecția muncii. Există următoarele tipuri de instructaj:

Întroductiv – se efectuiază de inginerul tehnicii securității.

Primar la locul de lucru – se efectuiază de inginerul laboratorului.

Periodic – se efectuiază de inginerul laboratorului nu mai rar de o dată în 6 luni:

Neplanificat – se efectuiază cînd s-a produs accidentul, angajatul s-a transferat la un alt loc de lucru sau s-a schimbat procesul de studiu.

Curent – se efectuiază înainte de lucrările de autorizare.

Starea nivelului de protecție a muncii în laborator se poate de calculat cu ajutorul coieficientului nivelului de respectare a regulilor de protecție a muncii de către lucrători:

( 5.1 )

5.2 Analiza condițiilor de muncă, tehnica securității

Totalitatea de factori ai mediului de producție, care influințiază condițiile de muncă a omului în procesul de lucru formează condițiile de muncă. Condițiile de muncă se formează în rezultatul interacțiunii dintre mai mulți factori naturali, social-economici, tehnici și organizatorici. Problema îmbunătățirii condițiilor de muncă se formează și trebuie rezolvată la toate etajele de proiectare și exploatare a utilajelor și proceselor tehnologice. Necesitatea de a îmbunătăți condițiile de muncă și de a ridica în acelaș timp nivelul tehnic de producere este una din problemele de bază ale societății. Este necesar de a proiecta, construi și întroduce în producție numai acele utilaje și tehnologii care asigură formarea condițiilor de muncă favorabile. Prin aceasta ĺ. Posibil de a crea condiții necesare pentru protejarea sănătății lucrătorilor, evitarea accidentelor, ridicarea eficienței economice și nivelului de viață a oamenilor.

Etapa inițială a analizei condițiilor de muncă constă în determinarea factorilor dăunători și periculoși și acțiunii lor asupra organismului uman. După origine factorii dăunători și periculoși se împart în 4 clase: factorii fizici, chimici, biologici și psihofiziologici.

Factorii fizici caracterizează procesul tehnologic sau utilajul industrial, la care se referă temperatura majorată a aerului, părți mobile a utilajului, părțile acute a utilajului, lucrul la înălțime, diferite radiații.

Factorii chimici caracterizează mediul înconjurător. La care se referă prăfuirea mediului, existența substanțelor periculoase în aer, umeditatea ș.a.

La factorii biologici se referă microorganismele (plantele și animalele).

La factorii psihofiziologici se referă supraîncărcările fizice (statice și dinamice) și supraîncărcările mintale și emoționale.

Factorii ce acționează la locul de muncă asupra individului sînt prezentați în tabelul 5.1

Tab.5.1.

Factorii ce acționează la locul de muncă asupra individului

Cerințele de bază a protecției muncii, necesare la proiectarea mașinelor și mecanizmelor sunt securitatea omului, fiabilitatea și comoditatea în exploatarea. Securitatea instalațiilor de producere se asigură prin alegerea corectă principiilor de funcționare a lui, schemelor cinematice, parametrilor funcționale și tehnologice a proceselor, folosirii diferitor mijloace de protecție. Ultimii trebuie să fie introduși în construcții de folosire. În cazul existenței la agregate motoarelor electrice, el trebuie să fie conficționat conform regulilor destinate componenții sistemelor electrice. Trebuie să fiu prevăzute mijloacele de protecție contra câmpurilor electromagnetice și electrice, impurificarii atmosferei cu: gaze, aburi, praf etc.

Influența câmpurilor electromagnetice de mare intensitate asupra omului constă în absorbția de către țesuturile corpului uman a energiei, însă influența principală îi revine câmpului electric. Nivelul de influență a câmpurilor electromagnetice asupra omului depinde de frecvență, de puterea emisiei, de durata acțiunii, de regimul de emisie (prin impulsuri sau continuu), și de asemenea de proprietățile individuale ale organismului. Influența câmpului electric de frecvență joasă provoacă dereglări în activitatea funcțională a sistemului cardio-vascular, și chiar la schimbări privind componența sângelui.

Influența câmpului electromagnetic de frecvență înaltă se reflectă sub forma efectului termic, care duce la ridicarea temperaturii corpului, la supraîncălzirea locală a țesuturilor corpului și a organelor cu o termoreglare slabă. Ca rezultat unii lucrători suferă din cauză insomniei, simt dureri în regiunea inimii, dureri de cap, ușor obosesc.

O mare importanță pentru funcționarea titulară a instalațiilor au dispozitive de control și măsurare și dispozitivelor de reglare și de dirijare. Locul de muncă și dispozitive de muncă trebuie să se proiecteze luând în vedere capacități fiziologici și psihologici a omului. E necesar de a organiza posibilitatea înregistrării rapide și corecte datelor dispozitivelor de măsurare șu control și dispozitivelor de reglare și de dirijare.

Lucrarea de diplomă, care prevede diagnosticarea și testarea funcționării titulare a aparatului M/D3 cu aparate destinate testării, a fost îndeplinită în laboratorul de cercetări științifice a catedrei de microelectronică a Universității Tehnice din Moldava, într-o încăpere cu suprafața de 75 m2 și volumul de 260 m3 și în care au lucrat 10 persoane, cărora le revine o suprafață mai mare ca norma sanitară prevăzută pentru un om (norma de un om fiind de 15 m3 și 4,5 m2).

Condițiile de muncă sanitaro-igienice sunt determinate de următorii factori: temperatura aerului, umeditate, viteza fluxului de aer, iluminare, ventilare.

În laborator sunt îndeplinite lucrări fără surplus de căldură. Reișind din STAS 12.1.005-88, care determină condițiile optimale și condițiile meteorologice admisibile pentru zona de lucru în laborator, în perioada caldă și rece a anului (temperatura aerului se menține în limita de 22-24˚C, viteza fluxului de aer nu este mai mare de 0.1 m/s și umiditatea relativa de 40-60 %).

Pentru locurile de muncă este folosită iluminarea naturală laterală cât și iluminarea artificială. Ziua, în caz dacă lumina naturală nu satisface normele, este adăugată și cea artificială, astfel încât putem avea iluminare combinată. Iluminarea naturală și artificială este reglamentată de normele de construcție și producere (CNCP 2-4-79).

În calitate de mărime normată pentru iluminarea naturală se folosește coeficientul de luminozitate naturală, pentru iluminarea artificială – mărimea luminozității minimale.

În general, în urma analizei condițiilor sanitar-igienice și a factorilor de producție dăunători și periculoși, putem face concluzia, că condițiile de lucru în ‘laboratorul de cercetări științifice’ a catedrei de microelectronică sunt satisfăcătoare, iar colaboratorii lui nu sunt supuși acțiunii factorilor de producție ce ar putea provoca apariția diferitor boli profesionale.

5.3 Cerințele ergonomice a locului de muncă

Locul de lucru a operatorului este zona înzestrată cu mijloace de prezentare a informației, organe de comandă și alt utilaj necesar, în care se desfășoară activitatea de muncă a omului. Organizarea locului de muncă constă în îndeplinirea unui sistem de măsuri pentru înzestrarea locului de muncă cu mijloace de muncă și amplasarea lor într-o anumită ordine. Scopul organizării locului de muncă este optimizarea condițiilor de activare a omului, asigurarea securității și eficienței maximale a muncii.

Cu studierea complexă și organizarea locului de muncă se ocupă o ramură a științei numită ergonomie. Principalul obiect de studiu al ergonomiei este sistemul «om-mașină-mediul de producere». Ergonomia studiază posibilitatea de acordare a construcției utilajului și posibilitățile psihologice și fiziologice ale omului cu scopul creării unor condiții în care munca să fie mai productivă și în acelaș timp să aducă muncitorilor satisfacție fizică și morală, să asigure securitatea și comfortul în procesul de muncă, păstrînd sănătatea și capacitatea de muncă a oamenilor. Printre sarcinile ergonomiei este elaborarea metodelor de evidență a fectorului uman la crearea și tehnicii și tehnologiei.

Există următorii indici ergonomici a locului de muncă, care asigzră eficiența maximală, securitatea și comfortul muncii:

Indicii igienici, care caracterizează factorii mediului înconjurător – temperatura, componența fizico-chimică a aerului, zgomotul, etc.

Indicii antropometrici și biomecanici, care caracterizează corespunderea dintre mijloacele de muncă, dimensiunile, forma și masa corpului uman, forța și direcția mișcărilor.

Indicii fiziologici și psihofiziologici, care determină corespondența dintre procesul de muncă și posibilitațile energetice, vizuale, rapiditatea și alte posibilități fiziologice ale omului.

Indicii psihologici, care caracterizează posibilitatea de gîndire, memorizare și reacționare a omului.

Indicii estetici, care se folosesc pentru determinarea necesităților estetice ale omului și oformarea estetică a locului de muncă și mediului de producere.

Locul de muncă trebuie adaptat pentru tipul concret de muncă în dependență de calificarea și posibilitățile psihofiziologice a lucrătorilor. Locurile de muncă se împart în locuri de muncă automatizate și mecanizate, locuri unde se îndeplinesc lucrări manuale. La organizarea locului de muncă se respectă următoarele cerințe ergonomice generale:

Se asigură un spațiu de lucru suficient, care permite muncitorului să îndeplinească mișcările necesare la exploatarea și deservirea tehnică a utilajului.

Se organizează legăturile fizici, vizuale și auditive suficiente dintre om și utilaj.

Repartizarea locurilor de muncă în încăperile de producere în corespundere cu recomandațiile științifice.

Iluminarea naturală și artificială, nivelul admisibil al zgomotului, ventilarea aerului se efectuiază în corespundere cu normele prevăzute de standardul corespunzător.

Se asigură protecția lucrului împotriva factorilor dăunători și periculoși.

Planificarea locului de muncă în laborator se efectuiază în corespundere cu particularitățile psihofiziologice ale omului și situația igienică generală. Organizarea locului de muncă satisface cerințelor de comoditate, economisirea de energie și timp a operatorului, să utilizeze rațional suprafețele de producere, să asigure deservirea comodă a calculatorului cu respectarea tehnicii securității. Locul de lucru al operatorului, care lucrează cu monitorul calculatorului trebuie situat la o anumită distanță de la fereastră, avînd în vedere ca lumina să cadă dintr-o parte. Monitorul, tastiera se plasează în așa mod ca să se afle în zona de acces a mînilor operatorului și să se escludă mișcările neproductive. Scaunul pe care este așezat operatorul trebuie să aibă înălțimea de aproximativ 0,4 m, lungimea speteazei scaunului de 0,3 m, lățimea spetezei de 0,11m, raza de curbare 0,3 – 0,35m. Se recomandă ca scaunul să repete forma corpului uman și să fie puțin înclinat înapoi. O însemnătate mare are repartizarea pe panourile de comandă a mijloacelor de semnalizare și displeiului de control. Întrerupătoarele, comutatoarele și manivelele asigură consumul minimal de energie musculară și nervoasă.

În timpul lucrului pot apărea situații, care cer din partea operatorului decizii rapide. Pentru îndeplinirea cu succes a lucrului în aceste condiții este necesară organizarea rațională a mediului înconjurător, care protejază operatorul de influiența factorilor iritativi cum sînt culoarea necorespunzătoare a dispozitivelor și calculatorului, repartizarea incomodă a semnalizării și tastelor de comandă etc. Prin toate metodele se micșorează încordarea fizică și psihică a operatorului și factorii ce aduc la oboseală.

Culoarea încăperilor de producție influențează mult asupra stării sistemului nervos, dispoziției și capacității de muncă a operatorului. Încăperile centrului de calcul sînt vopsite în corespundere cu dispozitivele tehnice. Alegerea culorii se argumentează științific, considerînd așa factori cum sînt construcția clădirii, caracterul muncii îndeplinite, nivelul de iluminare, numărul de lucrători în încăpere etc. Culorile aprinse înviorează încăperea și acționează pozitiv asupra stării psihologice a lucrătorilor. Culorile roșii trebuie folosite pentru semnalizare, iar utilajul trebuie să aibă culori deschise. Pereții încăperii se vopsesc în culori verzi, galbene, albastre deschise.

Climatul psihologic în colectivul de muncă este de asemenea un factor important al mediului de producție, de care depinde starea emoțională a lucrătorilor și deci productivitatea și calitatea muncii. Problemele social-psihologice trebuie analizate și soluționate permanent de către conducere.

5.4 Semnalizarea antiincendiară.

Una din sarcinile protecției muncii la întreprinderi este asigurarea securității de incendiu. Prin securitatea de incendiu se înțelege elaborarea unui șir de măsuri tehnice și organizatorice, care permit excluderea posibilității de izbucnire și răspîndire a incendiului, precum și apărarea oamenilor și bunurilor materiale de factorii periculoși ce apar în urma lui.

La facultatea CIM, unde se folosesc aparate electrice și materiale arzătoare, securitatea de incendiu are o însemnătate prioritară.

Una din măsurile de prevenire a incendiilor este semnalizarea antiincendiară. Semnalizarea la timp a apariției și locului incendiului determină in mare măsură lichidarea lui rapidă.

Sistemul automat de semnalizare incendiară se folosește pentru înștiințarea serviciilor de pază antiincendiară despre izbucnirea incendiului în careva încăpere a întreprinderii.

Sistemul de semnalizare antiincendiară se include în sistemul de stingere automată a incendiului sau se instalează ca sistem independent în încăperile cu pericol de incendiu, care nu sînt prevăzute cu sistem de stingere. În caz de necesitate semnalizarea antiincendiară se include în sistemul de pază. Sarcina sistemului automat de semnalizare antiincendiară este detectarea izbucnirii incendiului, conectarea instalațiilor de stingere automată și înștiințarea echipei de pompieri despre locul incendiului. Sistemul constă din traductoare, instalate în încăperile ce trebuie apărate de incendiu, stația de primire instalată în încăperea echipei de pompieri, sursa de alimentare cu energie electrică și rețeaua electrică care leagă traductoarele cu stația de primire.

Se folosesc semnalizatoare antiincendiare manuale și automate. Semnalizatoarele manuale cu acționarea prin taste se instalează la locuri ușor vizibile, de exemplu pe scările clădirilor cu multe etaje, în coridoare, la ușile de intrare etc. Pentru anunțarea echipei de pompieri trebuie spartă sticla de pe semnalizator și apăsată tasta.

Sistemul automat de semnalizare antiincendiară funcționează pe baza transmiterii semnalelor apărute la scurtcircuirea rețelei electrice. La semnalizatoarele de tipul PB-231 scurt-circuirea contactelor are loc în rezultatul deformării termice a unei plăci bimetalice. Ele lucrează la temperatura 60, 80, 100 C pentru încăperile cu o suprafață de pînă la 15 metri.

Semnalizatoarele termice cu acțiunea diferențială de tipul ATIM-I funcționează pe principiul diferenței dintre forțele termoelectrice de pe partea neagră și argintie a termocuplului. Ele se declanșează la creșterea bruscă a temperaturii (cu viteza de 30 C/sec). Aceste semnalizatoare se instalează în încăperi cu pericolul de explozie cu suprafața de pînă la 30 metri.

Semnalizatoarele combinate de tipul SI-I cu elemente sensibile în formă de cameră de ionizare pentru reacționarea la fum și termorezistențe pentru reacționarea la temperatură se declanșează la temperaturi de 50-80 C. La nimerirea fumului în camera de ionizare se schimbă curentul de ionizare în rezultatul absorbției de către fum a radiației gama, provenită de la un izotop radioactiv. Acest tip de semnalizatoare se folosește în încăperi cu o suprafață de pînă la 100 metri.

Dispozitivul de semnalizare de tipul DI-1 se folosesc pentru detectarea fumului cu semnalizarea prin semnale sonore și lumină și pentru declanșarea sistemului automat de stingere a incendiului. Împreună cu semnalizatoarele manuale și termice se folosesc stațiile de primire pentru rețele electrice cu 30 de raze cu conectarea traductoarelor după schema radială.

Traductoarele sistemului de semnalizare antiincendiară pot fi conectate la stația de primire după schema radială sau circulară. În schemele radiale stația de primire este conectată cu fiecare traductor printr-un cablu aparte, numit rază. Raza constă din 2 conductoare separate – conductor direct și invers. În schema circulară toate traductoarele se conectează în serie cu un conductor comun, unit la stația de primire. La întreprinderi mari la stația de primire se conectează cîteva rețele circulare care includ pînă la 50 de traductoare.

Alegerea sistemului de semnalizare antiincendiară se efectuiază după sensibilitate și zona de acțiune.

5.5 Noțiuni despre electrotraumatism

Acțiunea dăunătoare asupra oamenilor curentului electric, câmpului electric și static se manifestă prin electrotraumatizm și bolile profesionale. În corespundere cu STAS 12.1.009-76 electrotraumatizm eveniment care se caracterizează prin totalitatea electrotraumelor, adică traumelor provocate de acțiunea curentului electric sau de arcul electric. Oamenii ce au suferit electrotraumă sunt predispuse la bolile ce necesit tratament medical de lungă durată, iar aproximativ 12% din ele devin invalizi.

Urmările electrocutării depind de un șir de factori. Factorul de bază îl constituie amplituda și durata acțiunii curentului electric a sura corpului uman. Pentru curent alternativ cu frecvența de 50Hz și durata acțiunii 1s au loc următoarele:

0,6…1,5 mA – curentul de prag, care provoacă exitarea ușoară ;

10…15 mA – curentul de prag, care provoacă contracția mușchilor, care nu dă posibilitatea omului de a se elibera sinestăcător de la curentul. Parcurgerea curentului prin corpul omului pe un parcus de timp îndelungat este periculoasă pentru viață;

25…50 mA – curentul provoacă contracția mușchilor respiratori, este posibilă moartea de la înnădușire;

100 mA și mai mult – curent mortal.

Curentul direct este in 4 – 5 ori mai puțin periculos de cît curent alternativ de frecvența de 50 Hz. La creșterea frecvenței peste 1kHz pericolul electrocutării se micșorează. Urmările electrocutării depind și de drumul parcurs de curent prin omul. Cel mai periculos drum este “măna piciorul” sau “măna măna”. Rezistența corpului uman depinde de mai mulși factori așa ca: starea pielei, amplituda, stării fizice și psihice etc; și poate să varieze în limitele largi. În cazul folosirii curentului de 50Hz pentru calcule rezistența omului se socoate de 1kΩ. Amplituda tensiunei aplicate de asemenea influiențează asupra urmărilor electrocutării.

Conform STAS 12.1019-79 electrosecuritatea trebuie să fie asigurată de: construcția instalațiilor electrice; mijloace tehnice de protecție, festivități organizaționale și tehnice.

5.6 Calcularea protecției “legarea la nul”

Legarea la nul este o măsură de protejare a omului de electrocutare prin deconectarea strictă și rapidă a rețelei în caz de apariție a tensiunii pe carcasă (străpungerea izolației). Deconectarea strictă se efectuează, dacă curentul de scurt circuit format prin faza și firul nul este destul de mare pentru că declanșatorul să funcționeze corect. Firul nul de protecție se socoate firul care unește părțile legate la nul cu punctul neutral împămîntat a bobinei tensiunii curentului sau cu echivalentul ei. Legarea la nulul se folosește în rețele până la 1000V.

Legarea la nul transformă scurtcircuitul la carcasa în scurtcircuit monofazic în rezultatul căruia reacționează protecția maximală a curentului care selectiv deconectează regiunea defectat de la reția.

Controlul legării la nulul: dispozitiv legat la nulul se controlează înainte de al introduce în expluatare și periodic în procesul funcționării și după reparație. Pentru măsurarea rezistenței “faza – nulul” se poate de folosit oarecare dispozitiv de măsurare a rezistenții de montaj (MC – 08, M372 ș.a.).

unde ISCP – curentul de scurtcircuit la pământ,

ISC – curentul de scurcircuit.

Scopul calculării instalației “legarea la nul” – determinarea secțiunii firului nul, care satisface condiție funcționării protecției maximale de curent. Valoarea protecției se determină după puterea instalației electrice protejate (expluatate).

Curentul de scurtcircuit trebuie să depășască valoarea curentului de protecție conform cerniților ПЭУ (pentru siguranțe IS.C.In, unde In curentul nominal al siguranței). Modul de calculare este următorul:

Alegem raza firului nul și fazic egală cu 4,5mm pentru puterea transformatorului de 750kW și calculăm suprafața secțiunii firului fazic și nul

Calculăm rezistențile firelor fazic și nul

unde RF,RN,LF,LN – lungimea și secțiunea firului fazic și nul corespunzător; ρ – rezistența electrică specifică ρCu=0,018 Ω·mm2/m, ρAl=0,028 Ω·mm2/m.

Se calculează rezistența circuitului “faza – nul”

unde RF – rezistența activă a firului fazic, Ω; RN – rezistența activă a firului nul, Ω; XC – rezistența inductivă a rețelei “faza-nul” și pentru rețele cu tensiune joasă (până la 1000V) și firele din cupru și aluminiu ea să neagă, deci XC este foarte misă și nu se e în considerație.

Calculăm curentul de scurtcircuit

unde ZT/3 – coeficientul de rezistență transformatorului și este egal cu 0,0364 pentru puterea transformatorului 750kW.

Comparăm valoarea curentului de scurtcircuit cu valoarea curentului nominal al siguranței.

Deci diametrul firelor este ales corect.

Măsuri antiincendiare

Laboratorul de cercetări științifice în care s-au efectuat lucrările, corespunde după pericolul de incendiere categoriei B, reieșind din normele de construcție și producere (pericolul de explozie și incendiu).

Cauza incendiului în laborator poate fi ieșirea din funcțiune a aparatelor sau dispozitivelor. De asemenea, o cauză a incendiului poate fi și suprasolicitarea echipamentelor.

Pentru a micșora probabilitatea incendiului în laborator trebuie să ne conducem de următoarele principii: de a controla bunăstarea echipamentului electric, de a controla bunăstarea izolației, folosirea siguranțelor.

În caz de incendiu este necesar de a deconecta dispozitivele de la rețea. Pentru stingerea incendiului se folosește extinctorul OY-5, care se află în laborator.

În concordanță cu normele de construcție și producere (NCP-2-80) încăperea se referă la primul nivel antiincendiar, deoarece construcția sub acțiunea focului nu arde și nu fumegă.

Posibilitatea de lichidare rapidă a incendiului este în mare măsură determinată de informarea la timp despre incendiu. O metodă răspândită de informare este legătura telefonică. Dar, una dintre cele mai certe sisteme de informare este totuși semnalizarea electrică incendiară (SEI).

Pentru informarea despre incendiu se folosesc stații radio cu unde scurte, care funcționează într-o rază de 45km.Ele sunt înregistrate în automobilile pompierilor.

Caracteristicile condițiilor sanitar-igienice și ale factorilor de producție dăunători și periculoși.

CONCLUZIE

Optimizarea – este de o importanță mare așa în științele ca de exemplu: Fizica, Chimia și Biologia, dar și în științele care folosesc intiligența artificiаlă, ca de exemplu, cercetările și elaborările din domeniul infoematicii. Natura în general tot caută soluții optimale. De exemplu, structura cristalină reprezintă o stare energetică minimală pentru adunarea atomilor. Comportamentul naturii poate des fi lămurit pe baza principiilor de variații. Legile naturii pur și simplu devin condiții de optimalitate. De unde, matematica nelinira că întodeuna joaca rolul princupal la descrierea acestor condiții de optimalitate, si în analiza structurii al soluțiilor. Pe de altă parte, în stiințele artificiale, problemele puse folosesc pentru determinarea solutiilor optime, limbajul matematicii discrete sau al logicii.

Odată cu apariția metodei punctului Interior, imaginea se schimbă, deoarece aceste metode nu limitează rezolvarea ei în soluțiile discrete, dar și obiectele de natură combinatorială înschimb au o formă de cazuri restricționate ale ecuațiilor neliniare și folosesc proprietăți topologice și geometrice ale spațiului infinit. De asemenea, metoda punctului interior a descoperit, importanța structurii matemetice în optimizare atît în științele exacte cît și cele abstracte au mult comun.

În general multe probleme de optimizare(cu restrictii limitate) pot fi introduse in metoda celor mai mici patrate, la rindul sau, pot fi reformulate ca probleme de programare semidefinită. Aceste probleme asigura originalitatea aproximarii polinomiale temporale acestei probleme. De obicei, aproximarea relaxărilor SDP este mai rentabilă decît programarea liniara. Noi ilustrăm punctul nostru de vedere cu o singură aplicație din teoria grafurilor: Metoda tăieturii Max-Cut, a fost instrumentară în cele din urma la calcularea problemelor care folosec programarea semidefinită. Aceasta metodă de asemenea arată, cum SDP apare ca o relaxare a problemei, care folosește aproximarea pătratică.

Problema determinării tăieturii maxime într-un graf este o problemă de optimizare discretă. Fiind dat un graf finit și neorientat, problema constă în împarțirea vîrfurilor grafului în două mulțimi de vîrfuri care se leaga între ele cu muchii și suma muchiilor este maximă. În general, rezolvarea problemelor de așa natură necesită o enumerare completă a soluțiilor admesibile. O tehnică actuală de rezolvare a problemelor de optimizare combinatorială constă in relaxarea convexă a domeniului de soluții admesibile. Un rol important în aceste probleme îl joacă relaxarea semidefinită care transformă problema originală, data în spațiul vectorial n , într-o problemă de programare liniară în spațiul matriciilor simetrice semidefinite nxn. Problema relaxată este o problemă de programare convexă și poate fi rezolvată într-un timp polinomial.

În lucare problema determinării tăieturii maxime se reformulează ca o problemă de programare patratică cu restricții pătratice. Se prezintă relaxările bazate pe programarea semidefinită. Se arată ca toate aceste relaxari sunt echivalente între ele și că sunt produse de dualitatea Lagrange.

În general multe probleme de optimizare(cu restricții limitate) pot fi întroduse în metoda celor mai mici pătrate, la rîndul său, pot fi reformulate ca SDP. Aceasta SDP asigură originalitatea aproximării polinomiale temporale acestei probleme. De obicei, aproximarea relaxărilor SDP este mai rentabilă decît programarea liniara. Noi ilustrăm punctul nostru de vedere cu o singura aplicație din teoria grafurilor: Metoda tăieturii Max-Cut, a fost instrumentară în cele din urma la calcularea SDP. Această metodă deasemenea arată, cum SDP apare ca o relaxare a problemei, care folosește aproximarea patratică.

Algoritmul lucrării date decurge conform punctelor de mai jos:

Fiind dat un graf finit și neorientat (G), împarțirea vîrfurilor grafului se face în două mulțimi de vîrfuri care se leaga între ele cu muchii și suma muchiilor este maximă.

Întroducem matricia de adiacență (A) asociată grafului respectiv (G). După aceasta am determinat matricia Laplace (L = Diag(Ae) – A) asociată grafului G cu matricea adiacentă (A). La inițializarea vectorului multiplicatorilor Lagrange cu valori din domeniul soluțiilor admesibile se efectuiază reducerea problemei de optimizare condiționată la un șir de probleme de optimizare necondiționată prin asocierea funcției scop f(u) și funcția de barieră logaritmică. După care stabilim valoarea pasului K = K/ 2, inițial K fiind egal cu 1.

Prin fixarea vectorului u în cadrul matriciei se calculează gradientul funcției de barieră B(u). Apoi realizăm factorizarea Cholesky pentru matricea C(u)

Determinăm vectorii riRn din sistemul de ecuații liniare: ri –soluțiile sistemului de ecuații liniare, unde i – indecele care indica unității pozițiadin vectorul ei. După aceasta noi determinăm valoarile componentelor gradientului funcției de barieră B(u).

Se calculează gradientului funcției scop: fK(u) = e – KB(u).

Apoi se determină valoarea funcției scop care nu este altceva ca elemenetele de pe diagonală principală a matriciei F(u).

La rezolvarea problemei de optimizare necondiționată și utilizînd metoda gradientului cu fracționare a pasului, construim vectorul “U” .

La trecerea valorilor gradientului au trecut de 0 în negativ se va optimiza funcția scop.

Continuînd mai departe conform algoritmului descris și utilizînd programul MAX-CUT obținem soluția optimă, unde soluția optimă este suma maximă a ponderilor muchiilor în problema MAX-CUT pentru graful respectiv.

bIBLIOGRAFIE

Literatură:

Goemans M., Williamson D.P. : “Improvisation aproximation algorithms for maximum

Cut definits satisfiability problems using semidefinite programing”.

J.Assoc. Comput. Match., pag. 1115 – 1145, 1995

Vandenberghe L., Boyd S.: “Semidefinite programing” SIAM Review, 38, 49 – 95, 1996

V. Moraru: “Calculul gradientului funcției de penalizare în problema MAX-CUT”

Meridian Ingineresc, nr.2, 2001, pag. 27-30.

“Metode Numerice în Algebra Liniară” – ciclu de prelegeri.

Edit. Cartea Unversitară.

“Determinarea tăieturii maxime într-un graf folosind programarea

semidefinită”. Analele ASEM, nr.1, 2001, pag. 498 – 504

Ștefan Buzurniuc, Vasile Moraru: “Metode numerice” . Edit. Chișinău 2001.

Radu Șerban, Tudor Dumitrescu: “Metode de optimizare” Edit. Matrix Rom,

București 1998.

I. M. Goian, V. G. Marin: “Matrice, Operații cu matrice” Edit. Chișinău 1996.

В. Емеличев, О. Мельников: “Лекции по Теории Графов” изд. Москва

“Наука” 1990.

Internet:

http://www.optimization-online.org/ARCHIVE_DIGEST/2001-02.html

http://citeseer.nj.nec.com/klein96efficient.html

http://www.math.elte.hu/papers/semidef_prog.ps

http://citeseer.nj.nec.com/vandenberghe94semidefinite.html

http://www.mcs.anl.gov:80/home/otc/InteriorPoint

http://www.zib.de/helmberg/semidef.html

ftp://orion.uwaterloo.ca/pub/henry/reports/psd.bib.gz

anexe

Anexa.1

Listingul Programului:

#include <vcl.h>

#include <fstream.h>

#pragma hdrstop

#include "san1.h"

#include "Ahelp.h"

#include "Chelp.h"

#include "Run.h"

//–––––––––––––––––––––––––

#pragma package(smart_init)

#pragma link "cspin"

#pragma resource "*.dfm"

TMform *Mform;

int indic;

//–––––––––––––––––––––––––

fastcall TMform::TMform(TComponent* Owner) : TForm(Owner)

{

}

//–––––––––––––––––––––––––

void __fastcall TMform::Exit1Click(TObject *Sender)

{

Close();

}

//–––––––––––––––––––––––––

void __fastcall TMform::New1Click(TObject *Sender)

{

int i,j;

Edit1->Enabled=true;

StringGrid1->Enabled=true;

StringGrid2->Enabled=true;

StringGrid3->Enabled=true;

Run2->Enabled=false;

Rezultat->Enabled=true;

n=StrToInt(Edit1->Text);

StringGrid1->RowCount=n+1;

StringGrid1->ColCount=n+1;

StringGrid1->Cells[0][0]="Nr.elemente";

StringGrid2->RowCount=n+1;

StringGrid2->ColCount=n+1;

StringGrid2->Cells[0][0]="Nr.elemente";

StringGrid3->ColCount=n+1;

StringGrid3->Cells[0][0]="Nr.elemente";

StringGrid3->Cells[0][1]="linia 1";

for(i=0;i<n;i++)

{

StringGrid1->Cells[i+1][0]="coloana "+IntToStr(i+1);

StringGrid1->Cells[0][i+1]="linia "+IntToStr(i+1);

StringGrid2->Cells[i+1][0]="coloana "+IntToStr(i+1);

StringGrid2->Cells[0][i+1]="linia "+IntToStr(i+1);

StringGrid3->Cells[i+1][0]="coloana "+IntToStr(i+1);

StringGrid3->Cells[i+1][1]="";

}

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{

StringGrid2->Cells[j+1][i+1]="";

StringGrid1->Cells[j+1][i+1]="";

}

for(i=0;i<20;i++)

A[i]=new float[20];

e=new float[20];

u=new float[20];

FName="";

Mform->Caption="noname.max";

}

//–––––––––––––––––––––––––

void __fastcall TMform::Open1Click(TObject *Sender)

{

int i,j,k,iFLength;

char *buffer;

Edit1->Enabled=true;

StringGrid1->Enabled=true;

StringGrid2->Enabled=true;

StringGrid3->Enabled=true;

Rezultat->Enabled=true;

for(i=0;i<20;i++)

A[i]=new float[20];

e=new float[20];

u=new float[20];

if(OpenDialog1->Execute())

{

FName=OpenDialog1->FileName;

Mform->Caption=FName;

indic = FileOpen(FName, fmOpenRead);

iFLength=FileSeek(indic,0,2);

FileSeek(indic,0,0);

buffer=new char[iFLength+1];

FileRead(indic,buffer,iFLength);

FileClose(indic);

Edit1->Text=IntToStr((int) buffer[0] -48);

n=StrToInt(Edit1->Text);

StringGrid1->RowCount=n+1;

StringGrid1->ColCount=n+1;

StringGrid1->Cells[0][0]="Nr.elemente";

StringGrid2->RowCount=n+1;

StringGrid2->ColCount=n+1;

StringGrid2->Cells[0][0]="Nr.elemente";

StringGrid3->ColCount=n+1;

StringGrid3->Cells[0][0]="Nr.elemente";

StringGrid3->Cells[0][1]="linia 1";

for(i=0;i<n;i++)

{

StringGrid1->Cells[i+1][0]="coloana "+IntToStr(i+1);

StringGrid1->Cells[0][i+1]="linia "+IntToStr(i+1);

StringGrid2->Cells[i+1][0]="coloana "+IntToStr(i+1);

StringGrid2->Cells[0][i+1]="linia "+IntToStr(i+1);

StringGrid3->Cells[i+1][0]="coloana "+IntToStr(i+1);

StringGrid3->Cells[i+1][1]="";

}

for(i=0;i<n;i++)

for(j=0;j<n;j++)

StringGrid2->Cells[j+1][i+1]="";

k=1;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

StringGrid1->Cells[i+1][j+1]=FloatToStr((float) buffer[k++]-48);

/* for(i=0;i<n;i++)

for(j=0;j<n;j++)

StringGrid2->Cells[i+1][j+1]=FloatToStr((float) buffer[k++]-48);*/

for(i=0;i<n;i++)

StringGrid3->Cells[i+1][1]=FloatToStr((float) buffer[k++]-48);

delete [] buffer;

}

//–––––––––––––––––––––––––

void __fastcall TMform::Save1Click(TObject *Sender)

{

int i,j,iLength;

if(FName=="") SaveAs1Click(Sender);

else

{

indic = FileCreate(FName);

FileWrite(indic,Edit1->Text.c_str(),Edit1->Text.Length());

for ( i=0;i<n;i++)

for (j=0;j<n;j++)

{

FileWrite(indic, StringGrid1->Cells[i+1][j+1].c_str(), StringGrid1->Cells[i+1][j+1].Length());

}

for ( i=0;i<n;i++)

{

//iLength = StringGrid3->Cells[i+1][1].Length();

// FileWrite(indic, (char*)&iLength, sizeof(iLength));

FileWrite(indic, StringGrid3->Cells[i+1][1].c_str(), StringGrid3-Cells[i+1][1].Length());

}

FileClose(indic);

} }

//–––––––––––––––––––––––––

void __fastcall TMform::SaveAs1Click(TObject *Sender)

{

int i,j;

SaveDialog1->FileName=FName;

if(SaveDialog1->Execute())

{

FName=SaveDialog1->FileName;

Mform->Caption=FName;

indic = FileCreate(FName);

FileWrite(indic,Edit1->Text.c_str(),Edit1->Text.Length());

for ( i=0;i<n;i++)

for (j=0;j<n;j++)

{

FileWrite(indic, StringGrid1->Cells[i+1][j+1].c_str(), StringGrid1-Cells[i+1][j+1].Length());

}

for ( i=0;i<n;i++)

FileWrite(indic, StringGrid3->Cells[i+1][1].c_str(), StringGrid3-Cells[i+1][1].Length());

FileClose(indic);

}

//–––––––––––––––––––––––––

void __fastcall TMform::Edit1Exit(TObject *Sender)

{

int i,j;

if(StrToInt(Edit1->Text)<3)

{

Edit1->Text="20";

n=StrToInt(Edit1->Text);

}

if(StrToInt(Edit1->Text)>20)

{

Edit1->Text="3";

n=StrToInt(Edit1->Text);

}

n=StrToInt(Edit1->Text);

StringGrid1->RowCount=n+1;

StringGrid1->ColCount=n+1;

StringGrid1->Cells[0][0]="Nr.elemente";

StringGrid2->RowCount=n+1;

StringGrid2->ColCount=n+1;

StringGrid2->Cells[0][0]="Nr.elemente";

StringGrid3->ColCount=n+1;

StringGrid3->Cells[0][0]="Nr.elemente";

StringGrid3->Cells[0][1]="linia 1";

for(i=0;i<n;i++)

{

StringGrid1->Cells[i+1][0]="coloana "+IntToStr(i+1);

StringGrid1->Cells[0][i+1]="linia "+IntToStr(i+1);

StringGrid2->Cells[i+1][0]="coloana "+IntToStr(i+1);

StringGrid2->Cells[0][i+1]="linia "+IntToStr(i+1);

StringGrid3->Cells[i+1][0]="coloana "+IntToStr(i+1);

}

//StringGrid1->SetFocus();

}

//–––––––––––––––––––––––––

void __fastcall TMform::DmouseClick(TObject *Sender, TUDBtnType Button)

{

int i,j;

n=StrToInt(Edit1->Text);

StringGrid1->RowCount=n+1;

StringGrid1->ColCount=n+1;

StringGrid1->Cells[0][0]="Nr.elemente";

StringGrid2->RowCount=n+1;

StringGrid2->ColCount=n+1;

StringGrid2->Cells[0][0]="Nr.elemente";

StringGrid3->ColCount=n+1;

StringGrid3->Cells[0][0]="Nr.elemente";

StringGrid3->Cells[0][1]="linia 1";

for(i=0;i<n;i++)

{

StringGrid1->Cells[i+1][0]="coloana "+IntToStr(i+1);

StringGrid1->Cells[0][i+1]="linia "+IntToStr(i+1);

StringGrid2->Cells[i+1][0]="coloana "+IntToStr(i+1);

StringGrid2->Cells[0][i+1]="linia "+IntToStr(i+1);

StringGrid3->Cells[i+1][0]="coloana "+IntToStr(i+1);

}

//–––––––––––––––––––––––––

void __fastcall TMform::RezultatClick(TObject *Sender)

{

int i,j;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

A[i][j]=StrToFloat(StringGrid1->Cells[j+1][i+1]);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(A[i][j]!=A[j][i] || A[i][j]<0)

{

ShowMessage("Date ne valide. Detalii consultati Help-ul");

return;

}

//produs matrice vector

for(i=0;i<n;i++)

{

e[i]=0;

for(j=0;j<n;j++)

e[i]+=A[i][j];

}

//obtinerea matricei C(u)

for(i=0;i<n;i++)

for(j=0;j<n;j++)

A[i][j]=A[i][j]/4;

for(i=0;i<n;i++)

A[i][i]=e[i]/4;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

StringGrid2->Cells[j+1][i+1]=FloatToStr(A[i][j]);

Button1->Enabled=true;

}

//–––––––––––––––––––––––––

void __fastcall TMform::Button1Click(TObject *Sender)

{

int i,j;

for(i=0;i<n;i++)

u[i]=StrToFloat(StringGrid3->Cells[i+1][1]);

for(i=0;i<n;i++)

if(u[i]<A[i][i])

{

ShowMessage("Date ne valide. Detalii consultati Help-ul");

return;

}

Run2->Enabled=true;

}

//–––––––––––––––––––––––––

void __fastcall TMform::About1Click(TObject *Sender)

{

HAform->Show();

}

//–––––––––––––––––––––––––

void __fastcall TMform::fact_chol(float *a[],float *l[],int n){

int i,j,k;

float s;

l[0][0]=sqrt(a[0][0]);

for(i=0;i<n;i++)

l[0][i]=a[0][i]/l[0][0];

for(i=1;i<n;i++)

for(j=1;j<n;j++)

{

if(i==j)

{ s=0;

for(k=0;k<i;k++)

s+=pow(l[k][i],2);

l[i][j]=sqrt(a[i][j]-s);

}

if(i<j)

{

s=0;

for(k=0;k<i;k++)

s+=l[k][i]*l[k][j];

l[i][j]=(a[i][j]-s)/l[i][i];

} } }

void __fastcall TMform::sist_chol(float *l[],float r[],float e[],int n){

int i,k;

float s;

r[0]=e[0]/l[0][0];

for(i=1;i<n;i++)

{

s=0;

for(k=0;k<i;k++)

s+=l[k][i]*r[k];

r[i]=(e[i]-s)/l[i][i];

}

void __fastcall TMform::Run2Click(TObject *Sender)

{

int i,j,t,l;

float *A1[30],*I,*z,*F[30],*r[30],*gradf;

double alfa,s,s1,miu=1,fu,fz,norma,eps=0.001;

for(i=0;i<n;i++)

{

A1[i]=new float[n];

F[i]=new float[n];

r[i]=new float[n];

}

I=new float[n];

gradf=new float[n];

z=new float[n];

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{

F[i][j]=0;

A1[i][j]=A[i][j];

I[i]=u[i];

}

Rform->ListBox1->Items->Clear();

Rform->ListBox3->Items->Clear();

Rform->ListBox2->Items->Clear();

Rform->ListBox4->Items->Clear();

do{

// fixarea vectorului multiplicatorilor Lagrange

for(i=0;i<n;i++)

{

A[i][i]=u[i]-A[i][i];

e[i]=0;

}

fact_chol(A,F,n);

//calculul valorii functiei scop: f(u[0])

s=0;s1=0;

for(i=0;i<n;i++)

{

s+=u[i];

s1+=log(F[i][i]);

}

fu=s-2*miu*s1;

Rform->ListBox1->Items->Add(FloatToStr(fu));

Rform->ListBox1->Items->Add(" ");

do{

alfa=1;

//calculul vectorilor r[i]:

for(i=0;i<n;i++)

{

e[i]=1;

sist_chol(F,r[i],e,n);

e[i]=0;

}

//calculul gradientului functiei-scop: gradf(u[0])

for(i=0;i<n;i++)

{

s=0;e[i]=1;

for(j=0;j<n;j++)

s+= pow(r[i][j],2);

gradf[i]=e[i]-miu*s;

Rform->ListBox2->Items->Add(FloatToStr(gradf[i]));

}

Rform->ListBox2->Items->Add(" ");

// cout<<endl<<"Gradientul:";

// afis_vect(gradf,n);

// calculul normei gradienului functiei-scop

s=0;

for(j=0;j<n;j++)

s+= pow(gradf[j],2);

norma=sqrt(s);

Rform->ListBox3->Items->Add(FloatToStr(norma));

Rform->ListBox3->Items->Add(" ");

t=1;

for(i=0;i<n;i++)

if(gradf[i]<0)

{

t=0;break;

}

if(!t) break;

t=1;

while(t)

{

// calculul vectorului u[1]=u[0]-alfa*gradf(u[0])

for(i=0;i<n;i++)

{

z[i]=u[i]-alfa*gradf[i];

Rform->ListBox4->Items->Add(FloatToStr(z[i]));

}

Rform->ListBox4->Items->Add(" ");

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{

A[i][j]=A1[i][j];

F[i][j]=0;

}

// fixarea vectorului z si factorizarea Cholesky:

for(i=0;i<n;i++)

A[i][i]=z[i]-A[i][i];

l=1;

if(A[0][0]<0){l=0; break; }

F[0][0]=sqrt(A[0][0]);

for(i=0;i<n;i++)

F[0][i]=A[0][i]/F[0][0];

for(i=1;i<n;i++)

for(j=1;j<n;j++)

{

if(i==j)

{ s=0;

for(int k=0;k<i;k++)

s+=pow(F[k][i],2);

if(A[i][j]-s <0){l=0;break;}

F[i][j]=sqrt(A[i][j]-s);

}

if(i<j)

{

s=0;

for(int k=0;k<i;k++)

s+=F[k][i]*F[k][j];

F[i][j]=(A[i][j]-s)/F[i][i];

}

if(!l) break;

//calculul valorii functiei scop: f(z)

s=0;s1=0;

for(i=0;i<n;i++)

{

s+=z[i];

s1+=log(F[i][i]);

}

fz=s-2*miu*s1;

Rform->ListBox1->Items->Add(FloatToStr(fz));

Rform->ListBox1->Items->Add(" ");

if( fz<=(fu-0.75*alfa*norma*norma))

t=0;

else alfa/=2;

}

if(!l) break;

for(i=0;i<n;i++)

u[i]=z[i];

fu=fz;

}while(1);

if(!l) break;

miu/=2;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{

A[i][j]=A1[i][j];

F[i][j]=0;

u[i]=I[i];

}

}while(norma>eps);

s=0;

for(i=0;i<n;i++)

if(fu=modf(z[i],&norma)>=0.5)

{

z[i]=ceil(z[i]);

s+=z[i];

} else

{

z[i]=norma;

s+=z[i];

}

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{

A[i][j]=A1[i][j];

u[i]=I[i];

}

Rform->Edit1->Text=FloatToStr(s);

Rform->Show();

}

//–––––––––––––––––––––––––

void __fastcall TMform::Contents1Click(TObject *Sender)

{

HCform->Show();

}

//–––––––––––––––––––––––––

Anexa 2

Algoritmul proiectului de diplomă:

Realizarea matriciei de adiacență (A) asociată grafului resoectiv (G).

Determinarea matriciei Laplace (L = Diag(Ae) – A) asociată grafului G cu matricea adiacentă (A).

Inițializarea vectorului multiplicatorilor Lagrange cu valori din domeniul soluțiilor admesibile:

T={unDiag(u)-Q0}

Reducerea problemei de optimizare condiționată la un șir de probleme de optimizare necondiționată pein asocierea funcției scop f(u), funcția de barieră logaritmică: B(u) = ln det(Diag(u)-Q), fK(u) = K ln (det(Diag(u)-Q))min, uRn.

Stabilirea valorii parametrului K = K/ 2, inițial K fiind egal cu 1.

6. Calculul gradientului funcției de barieră B(u); prin fixarea vectorului u în cadrul matriciei

C(u)=Diag(u)-Q.

6.1 Factorizarea Cholesky penrtu matricea C(u) (C(u) = FT(u) F(u)).

6.2 Determinarea vectorilor riRn din sistemul de ecuații liniare: FT(u) ri = ei, i=1,2,..n unde i – indecele care indica unității pozițiadin vectorul ei.

6.3 Determinarea valorilor componentelor gradientului funcției de barieră B(u):

7. Calculul gradientului funcției scop: fK(u) = e – KB(u).

8. Determinarea valorii funcției scop fK(u) = eTu – 2K (ln(f11) + ln(f22) +.. + ln(fnn)), unde fii – elemenetele de pe diagonală principală a matriciei F(u).

Rezolvarea problemei de optimizare necondiționată din punctul 4. Utilizînd metoda gradientului cu fracționare a pasului, construind următorul vector: u(n+1) = u(n) – n fK(u(n)).

Calculul funcției scop pentru u(n+1) .

Verificarea condiției: f(u(n+1)) – f(u(n)) -n ║fK(u(n))║22.

Obținînd vectorul u(n+1) se trece la pasul 6. Dacă pentru u(n+1) gradientul funcției scop: fK(u(n)) primește valori negative și ║fK(u(n))║ › se trece la pasul 5. Dacă fK(u(n)) și ║fK(u(n))║ atunci STOP.

Anexa 3.

Schema Tăierii Max-Cut într-un graf

Anexa 4.

Cheltuieli suportate pentru elaborarea programului

Toate cheltuielile suportate pentru elaborarea softului.

Cheltuieli pentru materiale .

Cheltuieli pentru salariul de bază.

Cheltuieli pentru salariul suplimentar.

Defalcări în fondul social.

Cheltuieli pentru arenda calculatorului.

Cheltuieli de regie.

Tab.a1

Cheltuieli suportate pentru elaborarea programului

Tab.a2

Estimarea prețului programului

Determinarea eficienței economice a proiectului

Aflăm rata profit – vînzări:

Din rezultatele obținute se vede că utilizarea proiectului este argumentată economic, iar beneficiul obținut este de 1454,3 lei (Republica Moldova). În cazul măririi numărului de cereri a acestui soft, la vânzarea lui va fi necesar de inclus numai cheltuielile de multiplicare care sunt foarte mici comparativ cu costul lui. În rezultat vom obține un supraprofit, ceea ce ar fi foarte rentabil pentru programator. Dar mai luând în considerație lansarea proiectului pe plan mondial profitul poate deveni imprevizibil, ceia ce ar duce la sporirea bunăstării cum a programatorului așa și a companiei de sprigin.

Determinarea eficacității Sociale de la implimentare a proiectului

Acest Proiect de Diploma are un caracter de cercetare, a metodelor de Optimizare in grafuri cu ajutorul Programării Semidefinite.

Proiectului de diplomă este destinat: pentru Universitati de Cercetare in domeniul Matematicii Superioare și mai ales pentru capitolul Optimizarea in Metode Numerice și Cercetări Operționale.

Tab.a3

Evaluarea eficacității sociale de la implimentare

Anexa 5.

Schema Bloc a programului:

Anexa 6.

Schema Funcțională a Programului

Anexa 7.

Exemplu de problemă rezolvată prin metoda MAX-CUT

Matricea de adiacență asociată grafului:

(a7.1)

de unde Q = 1/4 L, iar L = diag(A e) –A

1 = 1;

Obținerea matricei C(U) = Diag(U) – Q

3) Inițializarea vectorului U: U(0) = (4, 8, 9, 4, 6, 8)T fixarea vectorului multiplicatorului lagrange:

4) Factorizarea matriciei prin metoda lui Cholesky: C(U(0)) = FT(U(0)) F(U(0))

Calculul valorii funcției scop: f(U(0)):

f(U(0)) = eT U(0) -20(ln f11 + ln f22 + ln f33 + ln f44 + ln f55 + ln f66) =

= 4+8+9+4+6+8 – 2(ln 1,803 + ln 2,0431 + ln 2,088 + ln 1,563 + ln 1,574 + ln 1,725) = 32,02884

Determinarea vectorilor:

Calculul gradientului funcției de barieră: B(U(0))

Exemplu:

Calculul gradientului funcției scop:

Calculul normei gradientului funcției scop:

10) Determinarea următorului vector “U” prin metoda gradientuli cu fracționare a pasului: = 1;

U(1) = (3,3175 7,3125 8,3073 3,4452 5,4288 7,3359)T

Valoarea funcției f0(U(1)) = 29,7906.

Verificăm condiția: pentru aceste valori condiția se respectă, prin urmare la pasul respectiv = 1.

Următorul pas: ; = 1.

Gradientul funcției de barieră: B(U(1)) – ?

B(U(1)) = (1,3577 1,0032 1,1939 1,7388 1,6182 0,5087)T.

Gradientul funcției:

Deoarece valorile gradientului au trecut de 0 în negativ vom optimiza funcția: f1(U) cu 1=1/2 atunci:

Fixăm U(0) = (4, 8, 9, 4, 6, 8)T – valorile inițiale, 1 = 1/2 = 0,5

f(U(0)) = eT U(0) -20(ln f11 + ln f22 + ln f33 + ln f44 + ln f55 + ln f66) = 35,5144

Calculul gradientului funcției scop:

Norma va fi următoare:

Determinarea vectorului:

Valoarea funcției scop: f1(U(1)) = 31,7042.

Verificarea condiției:

Condiția se respectă, de aici rezultă ca = 1 rămîne neschimbat, adică nu se modifică.

Continuînd mai departe conform algoritmului descris și utilizînd programul MAX-CUT obținem soluția optimă pentru formula (a7.1).

f(U)min = 29, reprezintă soluția optimă, adică “29” este suma maximă a ponderilor muchiilor în problema MAX-CUT pentru graful respectiv.

Copyright Notice

© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.

Acest articol: Proiectarea Si Optimizarea Problemelor de Programare Semidefinita (ID: 148789)

Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.

Proiectarea Si Optimizarea Problemelor de Programare Semidefinita

Copyright Notice

Aplicatie de Gestiune a Serviciilor Oferite de Automotive Service

Structuri Algebrice Si Topologice pe Multimea Idealelor Unui Inel

Dezvoltarea Si Implementarea Unui Sistem Administrativ Pentru Un Camin de Studenti

Compresia de Date In Aplicatii Multimedia

Programarea Jocurilor cu Ajutorul Limbajului de Porgramare Java

Funcțiile de Compatibilitate și de Curba Beveridge

Copyright Notice

Similar Posts