Metode de Optimizare – Curriculum

I. PRELIMINARII

În cursul de „Metode de Optimizare” studenţii studiază problemele de programare matematică (problemele finit dimensionale). Importnţa acestor probleme este subliniată de multitudinea problemelor reale formalizabile ca probleme de programare matematică, probleme reale ce apar în variatele domenii ale activităţii umane: ştiinţă, tehnică, economie etc.

Studenţii studiază în cadrul disciplinei date conceptele de bază ce ţin de optimizarea în spaţii vestoriale şi condiţiile de optimalitate corespunzătoare. Se studiază metode analitice şi numerice de rezolvare a problemelor de programare matematică.

II. OBIECTIVELE STANDARD ALE DISCIPLINEI

Susţinând cu succes examenul masteranzii vor fi capabili:

la nivel de cunoaştere şi înţelegere

  • să descrie obiectul de studiu al disciplinei;
  • să interpreteze problema de extrem ca model matematic al unei probleme reale de luare a deciziei (de alegere a variantei optime);
  • să definească noţiunea de soluţie a problemei de extrem (optim local sau global);
  • să clasifice problemele de extrem necondiţionat sau condiţionat conform proprietăţilor componentelor lor;
  • să formuleze şi sa interpreteze geometric condiţii, principii şi criterii de optimalitate pentru diverse clase de probleme de extrem;
  • să rezolve prin metode analitice probleme de extrem;
  • să concretizeze algoritmic ideile ce stau la baza metodelor numerice de rezolvare pentru clasele principale de probleme de extrem;
  • la nivel de aplicare

  • să explice esenţa, oportunitatea şi importanţa noţiunilor de bază studiate în cadrul disciplinei;
  • să translateze o problemă reală din limbajul uzual al domeniului concret (economie, tehnică, informatică etc.) în limbajul caracteristic problemelor de extrem (funcţie obiectiv, restricţii, soluţii admisibile, soluţii optime locale şi globale etc.);
  • să explice ideile ce stau la baza metodelor clasice de rezolvare a problemelor de extrem şi să le implementeze sub formă de algoritmi concreţi;
  • să utilizeze cunoştinţele teoretice la rezolvarea analitică a problemelor simple din compartimentele de bază ale teoriei optimizării matematice: programare liniară, programare neliniară;
  • să selecteze o metodă potrivită de rezolvare a unei probleme de extrem local sau global, să argumenteze oportunitatea selectării metodei, să concretizeze metoda numerică sub formă de algoritmi şi programe de calculator;
  • să interpreteze soluţia problemei reale din perspectivele: teoretică şi practică;
  • la nivel de integrare

  • să cerceteze probleme de extrem ce nu sunt studiate în cadrul cursului, să definească pentru ele noţiunile potrivite de soluţie, să construiască criterii şi principii de optimalitate şi să demonstreze justeţea lor;
  • să rezolve probleme de extrem din domenii concrete ale activităţii umane prin metode analitice şi numerice;
  • să interpreteze soluţia unei probleme reale de extrem în termenii domeniului practic şi să elaboreze recomandări persoanelor care iau decizii;
  • să adapteze, perfecţioneze şi să dezvolte cunoştinţele şi abilităţile dobândite în cadrul disciplinei date şi în cadrul altor discipline: calcul variaţional şi control optimal, cercetări operaţionale, modelare matematică, econometrică, programare de calculator etc.
  • să-şi perfecţioneze solitar calificarea atât din perspectiva teoretică, cât şi din cea practică.
  • III. ADMINISTRAREA MODULULUI / DISCIPLINEI

    Codul modulului / disciplinei în planul de învăţământ Anul de studii Semestrul

    Numărul de ore

    Evaluarea

    Responsabil de modul / disciplină

    C

    S

    L

    Nr. de credite

    Forma de evaluare

    F

    III

    V

    30

    0

    30

    4

    Examen

    V.Ungureanu

    IV. TEMATICA ŞI REPARTIZAREA ORIENTATIVĂ A ORELOR

    a) Tematica şi repartizarea orientativă a orelor de curs

    Nr. d/ord. Tema şi subtemele ei

    Nr ore

    I. Concepte de bază în teoria problemelor de extrem. Probleme reale formalizabile ca probleme de extrem. 2
    II. Programarea liniară (PL). 6
    II.1 Forme de scriere a problemelor de PL (PPL). Echivalenţa formelor.
    Interpretări geometrice ale PPL. Subspaţii liniare şi afine.

     

    Mulţimi convexe. Învelitoare convexă a unei mulţimi. Vârfuri.

    Combinaţii liniare convexe (conice, afine) ale unui sistem de vectori.

    Mulţimi poliedrale.

    2
    II.2 Soluţii admisibile de bază (s.a.b.).

     

    Teorema despre învelitoarea şi combinaţia convexă a vârfurilor unui poliedru convex.

    Teorema despre echivalenţa noţiunilor de varf şi s.a.b.

    Teorema despre existenţa s.a.b.

    2
    II.3 Rezolvarea PPL.

     

    Teorema despre realizarea soluţiei de extrem a PPL într-un punct de vârf.

    Teorema despre caracterul global al soluţiei PPL.

    Trierea vârfurilor. Metoda Jordan-Gauss în PL.

    2
    III. Metoda simplex. 4
    III.1 Ideea metodei.

     

    Trecerea de la o s.a.b. la alta (selectarea liniei pivot).

    Criteriul de selectare a coloanei pivot.

    Criteriul de optimalitate.

    Criteriul de nemărginire.

    2
    III.2 Ordonarea calculelor.

     

    Tabelul simplex.

    Metode de determinare a s.a.b. iniţiale: metoda bazei artificiale şi cea a coeficienţilor de penalizare.

    Algoritmul simplex.

    Fenomenul de ciclare. Metode de suprimare a ciclării. Regula lui Bland.

    2
    IV. Dualitatea în programarea liniară. 4
    IV.1 Reguli de construire a problemei duale.

     

    Cuplul de probleme reciproc duale. Lemele de bază.

    Teorema fundamentală a dualităţii.

    2
    IV.2 Teorema ecarturilor complementare.

     

    Soluţionarea cuplului de probleme reciproc duale.

    Algoritmul simplex dual.

    2
    V. Problema de transport (PT). 4
    V.1 Proprietăţi de bază.

     

    Teorema de existenţă a planului optim de transport.

    Rangul matricei sistemului de ecuaţii a PT. Panuri degenerate.

    Metode de determinare a planului iniţial de transport.

    2
    V.2 Trecerea de la un plan la altul îmbunătăţit.

     

    Metode de soluţionare a problemei de transport (metoda potenţialelor şi cea a repartiţiei).

    Degenerarea şi integritatea planelor de transport.

    2
    VI. Programarea neliniară. 10
    VI.1 Probleme de optimizare necondiţionată.

     

    Condiţii de optimalitate pentru funcţii diferenţiabile (necesare şi suficiente).

    Cercetarea signaturii formelor pătratice.

    2
    VI.2 Optimizarea condiţionată.

     

    Problema clasică de extrem condiţionat.

    Metoda substituţiei. Teorema despre funcţiile implicite.

    Metoda lui Lagrange. Principiul Lagrange. Condiţii de optimalitate (necesare şi suficiente).

    4
    VI.3 Problema de programare neliniară (PPN).

     

    Condiţii de optimalitate de tip John şi Kuhn-Tucker.

    2
    VI.4 Condiţii geometrice de optimalitate. Interpretarea geometrică a condiţiilor de tip John şi Kuhn-Tucker.

     

    Punctul şa – criteriu suficient de optimalitate globală în problema de programare neliniară.

    2

    Total

    30

    b) Tematica şi repartizarea orientativă a orelor de laborator

    Nr. d/ord. Tema şi subtemele ei Numărul de ore
    I. Optimizarea unidimensională pentru funcţii unimodale. 10
    I.1 Metoda dihotomiei. 2
    I.2 Metoda secţiunii de aur. 2
    I.3 Metoda Fibonacci. 2
    I.4 Metoda liniilor frânte. 4
    II. Minimul necondiţionat pentru funcţii de mai multe variabile. 10
    II.1 Metoda gradientului. 4
    II.2 Metoda lui Newton. 4
    II.3 Metoda modificată Newton. 2
    III. Metoda simplex. 10
    III.1 Metoda simplex pentru p
    roblema standard cu bază unitară.
    4
    III.2 Metoda bazei artificiale. 4
    III.3 Rezolvarea problemelor de programare liniară. 2

    Total

    30

    c) Tematica şi repartizarea orientativă a orelor de seminar

    Nr.
    d/ord.
    Tema şi subtemele ei Numărul de ore
    I. Rezolvarea grafică a PPL. 2
    II. Construirea formei standard a PPL. 2
    III. Soluţie generală a unui sistem de ecuaţii, soluţii (plane) de bază, soluţii admisibile de bază, vârfuri ale mulţimii de soluţii admisibile. 2
    IV. Mulţimi convexe. Mulţimi poliedrale. Construirea s.a.b. optimale. 2
    V. Metoda simplex. 2
    VI. Metoda bazei artificiale. 2
    VII. Dualitatea în programarea liniară. Rezolvarea cuplului de probleme reciproc duale. 4
    VII.1 Teorema fundamentală a dualităţii. 2
    VII.2 Teorema ecarturilor complementare. 2
    VIII. Problema de transport. 4
    VIII.1 Metode de construire a planului iniţial de transport. 2
    VIII.2 Rezolvarea problemei de transport. Metoda potenţialelor. 2
    IX. Programarea neliniară. 6
    IX.1 Rezolvarea problemelor de optimizare necondiţionată prin metoda clasică. 2
    IX.2 Problema clasică de extrem condiţionata. Metoda multiplicatorilor Lagrange. 2
    IX.3 Rezolvarea grafică a problemelor de minim condiţionat.

     

    Problem cu restricţii inegalităţi. Metoda factorilor Lagrange.

    2

    Total

    30

     

    VI. OBIECTIVE DE REFERINŢĂ ŞI CONŢINUT

    Obiectivele de referinţă cer însuşirea temelor enumarate infra, atît din perspectiva acumulării cunoştinţelor teoretice şi practice, de înţelegere profundă a lor, cît şi din perspectiva dexterităţilor practice-aplicative şi de generare a noi cunoştinţe.

    Teme

    Conţinuturi

    1. Concepte de bază în teoria problemelor de extrem. Probleme reale formalizabile ca probleme de extrem. Formularea problemelor de extrem. Clasificarea problemelor. Componentele problemei de extrem. Extreme locale şi globale. Exemple de probleme reale ce pot fi modelate prin probleme de extrem.
    2. Formularea problemelor de programare liniară. Forme de scriere a problemelor de programare liniară. Echivalenţa formelor.
    3. Interpretări geometrice ale problemelor de programare liniară. Subspaţii liniare şi afine. Mulţimi convexe. Învelitoare convexă a unei mulţimi. Vârfuri. Combinaţii liniare convexe (conice, afine) ale unui sistem de vectori. Mulţimi poliedrale
    4. Soluţii admisibile de bază (s.a.b.). Teorema despre învelitoarea şi combinaţia convexă a vârfurilor unui poliedru convex. Teorema despre echivalenţa noţiunilor de varf şi s.a.b. Teorema despre existenţa s.a.b.
    5. Soluţiile problemelor de programare liniară. Teorema despre realizarea soluţiei de extrem a PPL într-un punct de vârf. Teorema despre caracterul global al soluţiei PPL. Trierea vârfurilor. Metoda Jordan-Gauss în PL.
    6. Metoda simplex. Teze teoretice. Ideea metodei. Trecerea de la o s.a.b. la alta (selectarea liniei pivot). Criteriul de selectare a coloanei pivot. Criteriul de optimalitate. Criteriul de nemărginire.
    7. Metoda simplex. Aplicaţii ale metodei. Ordonarea calculelor. Tabelul simplex. Metode de determinare a s.a.b. iniţiale: metoda bazei artificiale şi cea a coeficienţilor de penalizare. Algoritm
    ul simplex. Fenomenul de ciclare. Metode de suprimare a ciclării. Regula lui Bland.
    8. Dualitatea în programarea liniară. Teorema fundamentală a dualităţii. Reguli de construire a problemei duale. Cuplul de probleme reciproc duale. Lemele de bază. Teorema fundamentală a dualităţii.
    9. Dualitatea în programarea liniară. Teorema ecarturilor complementare. Teorema ecarturilor complementare. Aplicarea teoremei. Soluţionarea cuplului de probleme reciproc duale. Algoritmul simplex dual.
    10. Problema de transport. Proprietăţi. Teorema de existenţă a planului optim de transport. Rangul matricei sistemului de ecuaţii a PT. Panuri degenerate.
    11. Metode de rezolvare a problemei de trans-port. Metode de determinare a planului iniţial de transport. recerea de la un plan la altul îmbunătăţit Metode de soluţionare a problemei de transport (metoda potenţialelor şi cea a repartiţiei). Degenerarea şi integritatea planelor de transport.
    12. Probleme de optimizare necondiţionată. Condiţii de optimalitate pentru funcţii diferenţiabile (necesare şi suficiente). Metode de cercetare a signaturii formelor pătratice. Aplicarea lor în cazul folosirii condiţiilor de optimalitate de ordinul doi.
    13. Problema clasică de extreme condiţionat. Metoda substituţiei. Teorema despre funcţiile implicite. Metoda lui Lagrange. Principiul Lagrange. Condiţii de optimalitate (necesare şi suficiente).
    14. Problema de programare neliniară. Cazul funcţiilor componente diferenţiabile. Condiţii de optimalitate de tip John şi Kuhn-Tucker.
    15. Problema de programare neliniară. Cazul general. Condiţii geometrice de optimalitate. Interpretarea geometrică a condiţiilor de tip John şi Kuhn-Tucker. Proprietatea de a fi punct şa – criteriu suficient de optimalitate globală în problema de programare neliniară.

    VI. LUCRĂRI INDIVIDUALE

    Pe durata cursului fiecare student va efectua o lucrare individuală conform Indicaţiilor metodice anexate.

    VII. EVALUAREA

    1. Evaluări curente şi periodice

    Verificarea cunoştinţelor teoretice se va efectua prin două atestări cu notarea de la 1 la 10.

    Verificarea curentă a deprinderilor practice se va face pe parcursul semestrului la orele de laborator cu notarea de la 1 la 10.

    Utilizarea cunoştinţelor acumulate se va efectua prin lucrarea individuală cu notarea de la 1 la 10.

    2. Evaluarea sumativă finală

    Nota finală se constituie din media pentru laborator, două atestări, lucrarea individuală şi nota de examen. La evaluarea finală sunt admişi doar studenţii, care au îndeplinit toate lucrările de laborator şi lucrarea individuală şi au media pozitivă la evaluările curente.

    La stabilirea notei finale se iau în considerare

    Ponderea în notare, exprimată în % (Total=100%)

    Examinarea continuă pe parcursul semestrului

    – testarea continuă pe parcursul semestrului, rezultatele activităţii la seminare / lucrări practice / de laborator

    cel puţin 60%

    25

    – testarea periodică prin lucrări de control

    25

    – activităţi individuale (teme / referate / eseuri / traduceri / proiecte, studiu de caz, etc.)

    25

    – activităţi practice

     

    – alte activităţi (precizaţi)

     

    Examinarea finală

    Rezultatele de la examenul final

    cel mult 40%

    25


    IX. REFERINŢE BIBLIOGRAFICE

    1. Ungureanu V., Programarea matematică, Chişinău, USM, 2001.
    2. Neculai Andrei, Programarea matematică avansată, Bucureşti, Editura Tehnică, 1999.
    3. Пападимитриу Х., Стайглиц К., Комбинаторая оптимизация, М.: Мир, 1985.
    4. Шрайвер А., Теория линейного и целочисленного программирования, М.: Мир, 1991.
    5. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации, М.: Наука, 1986.
    6. Карманов В.Г., Математическое программирование, М.: Наука, 1986.
    7. Ашманов С.А. Линейное программирование, М.: Наука, 1981.
    8. Габасов Р., Кириллова Ф.М. Методы оптимизации, Минск, Издательство Белларусского университета, 1981.
    9. Васильев С.П. Численные методы решения экстремальных задач, М.: Наука, 1980.
    10. Базара М., Шетти К. Нелинейное программирование, М.: Мир, 1982.

    Lasă un răspuns

    Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

    Logo WordPress.com

    Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

    Poză Twitter

    Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

    Fotografie Facebook

    Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

    Fotografie Google+

    Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

    Conectare la %s