NECULAI ANDREI Home Page


Advanced Mathematical Programming

Theory, Computational Methods, Applications

NECULAI ANDREI
PROGRAMAREA MATEMATICA AVANSATA
Teorie, Metode Computationale, Aplicatii
  • Prefata

  • Cuprins

  • Lista de simboluri si notatii

  • Partea I-a: GENERALITATI

    • Cap.1 Notiuni Fundamentale
    1.1. Programare matematica. Definitii
    1.2. Elemante de algebra liniara
    1.3. Elemante de topologie
    1.4. Elemente de calcul calcul diferential
    1.5. Elemente de analiza convexa
    1.6. Studiul convergentei. Convergenta locala si convergenta asimptotica
    1.7. Elemente de complexitate computationala
  • Partea a II-a: CONDITII DE OPTIMALITATE

    • Cap.2. Optimizare Clasica
    2.1. Optimizare fara restrictii
    2.1.1. Conditii necesare de optim local
    2.1.2. Conditii suficiente de optim local
    2.2. Optimizare cu restrictii egalitati
    2.2.1. Conditii necesare de optimalitate
    2.2.2. Conditii suficiente de optimalitate
    2.2.3. Interpretarea multiplicatorilor Lagrange
    2.2.4. Functia Lagrange. Dualitate
    2.3. Functii convexe si concave
    Exercitii
    Cap. 3. Optimizare cu Restructii Inegalitati
    3.1. Restrictii active
    3.2. Directii admisibile
    3.3. Conditiile de optimalitate Kuhn-Tucker
    3.4. Proprietatea de punct sa a functiei Lagrange
    3.4.1. Conditii necesare de punct sa ale functiei Lagrange
    3.4.2. Conditii suficiente de punct sa ale functiei Lagrange
    3.4.3. O conditie necesara si suficienta de punct sa. Functii de perturbare
    3.5. Conditii de existenta a multiplicatorilor Lagrange
    3.6. Dualitate in sens Lagrange
    Exercitii
    Note asupra conditiilor de optimalitate
  • Partea a III-a: PROGRAMAREA LINIARA AVANSATA

    • Cap. 4. Poliedre. Inegalitati Liniare si Programarea Liniara
    4.1. Concepte fundamentale si rezultate asupra poliedrelor si inegalitatilor liniare
    4.1.1. Teorema fundamentala a inegalitatilor liniare
    4.1.2. Multimi si conuri poliedrale
    4.1.3. Teorema lui Farkas-Minkowski si variantele ei
    4.1.4. Puncte extreme, fete, directii si directii extreme ale multimilor poliedrale
    4.1.5. Reprezentarea multimilor poliedrale
    4.2. Introducere in programarea liniara
    4.2.1. Problema programarii liniare
    4.2.2. Ipoteze de modelare in programarea liniara
    4.2.3. Forma standard si canonica. Transformari echivalente
    4.2.4. Interpretarea geometrica a programarii liniare in spatiul activitatilor
    4.2.5. Interpretarea geometrica a programarii liniare in spatiul resurselor
    Exercitii
    Cap. 5. Metoda Simplex
    5.1. Puncte extreme si optimalitate
    5.2. Solutii admisibile de baza
    5.3. Reducerea problemei in spatiul variabilelor nebazice
    5.4. Expresia geometrica a algoritmului simplex
    5.5. Algoritmul simplex
    5.6. Algoritmul simplex in format tablou
    5.7. Determinarea unei solutii admisibile de baza initiale
    5.8. Metoda simplex a celor doua faze
    Exercitii
    Cap. 6. Extensii ale Algoritmului Simplex. Convergenta. Conditii de Optimalitate
    6.1. Degenerare. Ciclare. Stagnare
    6.1.1. Metoda lexicografica de protectie la ciclare
    6.1.2. Regula lui Bland
    6.1.3. Metoda Wolfe
    6.1.4. Stagnare
    6.2. Metode de evaluare
    6.2.1. Evaluari partiale
    6.2.2. Evaluari multiple
    6.2.3. Metoda Devex
    6.2.4. Selectarea celei mai abrupte directii
    6.3. Algoritmul simplex cu variabile marginite
    6.3.1. Solutii admisibile de baza
    6.3.2. Imbunatatirea unei solutii admisibile de baza
    6.3.3. Algoritmul simplex cu variabile marginite
    6.3.4. Convergenta. Degenerare. Ciclare
    6.4. Conditiile Kuhn-Tucker in programarea liniara
    6.4.1. Teorema Farkas-Minkowski si programarea liniara
    6.4.2. Conditiile Kuhn-Tucker pentru programarea liniara cu restrictii inegalitati
    6.4.3. Conditiile Kuhn-Tucker pentru programarea liniara cu restrictii egalitati
    6.4.4. Conditiile Kuhn-Tucker si algoritmul simplex
    Exercitii
    Cap.7. Dualitate si Analiza Sensibilitatii in Programarea Liniara
    7.1. Formularea problemei duale
    7.2. Proprietati de dualitate in programarea liniara
    7.3. Interpretarea economica a dualitatii
    7.4. Rezolvarea simultana a unui cuplu de probleme duale
    7.5. Algoritmul simplex dual
    7.6. Algoritmul Primal-Dual
    7.7. Reoptimizare in programarea liniara
    7.7.1. Modificarea termenului liber
    7.7.2. Modificarea coeficientilor functiei obiectiv
    7.7.3. Modificarea unei coloane a matricei restrictiilor
    7.7.4. Adaugarea unei noi activitati
    7.7.5. Adaugarea unei restrictii
    7.8. Analiza sensibilitatii in programarea liniara
    7.8.1. Sensibilitatea la variatia componentelor termenului liber
    7.8.2. Sensibilitatea la variatia coeficientilor functiei obiectiv
    7.8.3. Sensibilitatea la variatia elementelor matricei restrictiilor
    7.8.4. Tolerante asupra modificarii simultane si independente in coeficientii functiei obiectiv sau a termenului liber
    7.9. Programarea liniara parametrica
    7.9.1. Parametrizarea functiei obiectiv
    7.9.2. Parametrizarea termenului liber
    7.10 Solutii neadmisibile
    Exercitii
    Cap. 8. Modelare in Programarea Liniara. Simplificarea Modelelor de Programare Liniara
    8.1. Modelarea problemelor ca programe liniare
    8.1.1. Scheme de reprezentare in modelare
    8.1.2. Formatul standard MPS
    8.1.3. Limbaje de modelare
    8.2. Tehnici de simplificare a modelelor de programare liniara
    8.2.1. Teste de simplificare a modelelor de programare liniara
    8.2.2. Eliminarea restrictiilor de balanta
    8.2.3. Splitarea coloanelor dense
    Exercitii
    Cap.9. Forma Produs a Inversei si Algoritmul Simplex
    9.1. Forma produs a inversei
    9.2. Strategii de alegere a pivotilor in calculul FPI
    9.3. Algoritmi de calcul a FPI
    9.4. Algoritmul simplex cu FPI
    9.5. Reinversarea bazei
    Exercitii
    Cap. 10. Forma de Eliminare a Inversei si Algoritmul Simplex
    10.1. Forma de eliminare a inversei
    10.2. Strategii de alegere a pivotilor in calculul FEI
    10.3. Comparatie intre FPI si FEI
    10.4. Algoritmi de calcul a FEI
    10.5. Actualizarea FEI
    10.6. Algoritmul simplex cu FEI
    Exercitii
    Cap. 11. Factorizarea Dinamica Partitionata a Bazei si Algoritmul Simplex
    11.1. Inversa bazei partitionata
    11.2. Triunghiularizarea cucuielor
    11.3. Repartitionarea bazei
    11.4. Algoritmul simplex cu factorizarea dinamica partitionata a bazei
    Exercitii
    Cap. 12. Complexitatea Algoritmului Simplex. Algoritmi Polinomiali de Programare Liniara
    12.1. Aspecte ale complexitatii polinomiale
    12.2. Complexitatea computationala a algoritmului simplex
    12.3. Metoda elipsoidului, a lui Khachian
    12.4. Metoda proiectiva a lui Karmarkar
    12.4.1. Algoritmul Karmarkar
    12.4.2. Conversia unei probleme generale de PL la forma Karmarkar
    12.4.3. Analiza algoritmului Karmarkar. Convergenta. Complexitate
    12.4.4. Metoda glisarii functiei obiectiv. Solutii optime de baza
    12.5. Metode de Scalare Afina
    Exercitii
    Cap. 13. Programarea Liniara de Mari Dimensiuni
    13.1. Programe liniare cu structura unghiulara
    13.1.1. Principiul de descompunere Dantzig-Wolfe
    13.1.2. Metode de partitionare si relaxare. Algoritmul Rosen
    13.2. Programe liniare cu structura scara
    13.2.1. Metoda simplex pentru programarea liniara cu structura scara
    13.2.2. Aplicatie. Conducerea optima a unei centrale termoelectrice
    care utilizeaza mai multe surse de combustibil
    13.2.3. Metoda descompunerii in cuib
    13.2.4. Aplicatie. Conducerea proceselor industriale discrete
    Exercitii
    Note asupra programarii liniare
  • Partea a IV-a: OPTIMIZARE FARA RESTRICTII

    • Cap. 14. Optimizare Unidimensionala
    14.1. Metode de cautare
    14.1.1. Metoda Fibonacci
    14.1.2. Metoda sectiunii de aur
    14.1.3. Metoda de interpolare patratica Powell
    14.2. Metode utilizind derivate
    14.2.1. Metoda Newton
    14.2.2. Metoda secantei
    14.2.3. Metoda de interpolare cubica Davidon
    14.3. Algoritmi de optimizare unidimensionala si aplicatii multivoce inchise
    14.3.1. Optimizare unidimensionala exacta
    14.3.2. Optimizare unidimensionala aproximativa
    Exercitii
    Cap. 15. Metode Clasice de Optimizare Fara Restrictii
    15.1. Metoda pasului descendent
    15.2. Metoda Newton
    15.2.1. Metoda Newton pentru rezolvarea sistemelor algebrice neliniare
    15.2.2. Metoda Newton pentru minimizarea functiilor
    15.2.3. Metoda Newton discreta
    15.2.4. Metoda Newton discreta cu matrice Jacobian sau Hessian rare
    15.2.5. Metoda Newton inexacta
    15.2.6. Metoda Newton compusa
    15.3. Metoda Goldstein-Price
    15.4. O metoda practica de optimizare fara restrictii
    Exercitii
    Cap. 16. Metode Quasi-Newton pentru Optimizare Fara Restrictii
    16.1 Metoda Broyden
    16.2. Metoda de actualizare simetrica Powell-Broyden
    16.3. Metode de actualizare simetrice si pozitiv definite: BFGS si DFP
    16.4. Metode de actualizare quasi-Newton cu memorie limitata
    16.4.1. Metoda BFGS cu memorie limitata
    16.4.2 Metoda Newton trunchiata cu actualizarea BFGS cu memorie limitata
    16.5. Alte actualizari de tip secanta pentru minimizarea functiilor
    Exercitii
    Cap. 17. Metode de Directii Conjugate
    17.1 Directii conjugate. Proprietati
    17.2. Metoda gradientilor conjugati
    17.3. Metoda gradientilor conjugati ca un proces optimal
    17.4. Metoda gradientilor conjugati aplicata problemelor nepatratice
    17.4.1. Metoda aproximarii patratice
    17.4.2. Metodele Fletcher-Reeves si Polak-Ribiere
    17.4.3. Metodele gradientilor conjugati ca metode quasi-Newton fara memorie
    17.4.4. Metoda Shanno-Phua
    Exercitii
    Cap. 18. Metode de Cautare
    18.1. Cautare paralela cu axele
    18.2. Metoda Hooke-Jeeves, de cautare a formei
    18.3. Metoda Powell, a directiilor conjugate
    18.4. Metoda Rosenbrock, a rotirii coordonatelor
    18.5. Metoda Nelder-Mead, a deplasarii simplexului
    18.6. Metoda Chazan-Miranker, a optimizarii paralele
    Exercitii
    Cap. 19. Complemente Privind Optimizarea Fara Restrictii
    19.1. Formularea problemelor de optimizare fara restrictii
    19.2. Scalare
    19.3. Criterii de oprire a iteratiilor
    19.4. Diferentiere automata
    19.5. Alegerea metodei de optimizare
    19.6. Functii de test
    19.7. Rezultate ale diferitilor algoritmi de optimizare fara restrictii.
    Exercitii
    Note asupra optimizarii fara restrictii
  • Partea a V-a: OPTIMIZARE CU RESTRICTII

    • Cap. 20. Optimizare cu Restrictii. Caracteristici. Moduri de Rezolvare
    20.1. Caracteristicile problemelor de optimizare cu restrictii
    20.2. O procedura generala de modelare si rezolvare a problemelor de optimizare
    20.3. Metode de rezolvare a problemelor de optimizare
    Cap. 21. Metode de liniarizare
    21.1. Metoda Frank-Wolfe
    21.2. Metoda programarii liniare succesive
    21.3. Metoda programarii liniare succesive penalizate
    21.4. Metoda planelor secante a lui Kelley
    21.5. Metoda de generare a coloanelor
    Exercitii
    Cap. 22. Metoda Simplex Convexa
    Cap. 23. Metode de Directii Admisibile
    Cap. 24. Metode de Gradient
    24.1. Metoda gradientului proiectat
    24.2. Metoda gradientului redus
    24.3. Metoda gradientului redus generalizat (GRG)
    Exercitii
    Cap. 25. Metoda MINOS
    25.1. Probleme cu restrictii liniare
    25.2. Probleme cu restrictii neliniare
    Exercitii
    Cap. 26. Metode de Programare Patratica Succesiva
    26.1. Programarea Patratica
    26.1.1. Metode pentru programarea patratica cu restrictii egalitati
    26.1.2. Metode pentru programarea patratica cu restrictii inegalitati
    26.2. Programarea Patratica Succesiva
    26.2.1. Programarea Patratica Succesiva pentru probleme cu restrictii liniare
    26.2.2. Programarea Patratica Succesiva pentru probleme cu restrictii neliniare
    Exercitii
    Cap. 27. Metoda Elipsoidului
    Cap. 28. Metode bazate pe conditiile de optimalitate Kuhn - Tucker
    28.1. Metode pentru restrictii egalitati
    28.2. Metode pentru restrictii inegalitati
    Exercitii
    Cap. 29. Metode de Penalizare
    29.1. Metode de penalizare
    29.1.1. Metode de penalizare exterioara
    29.1.2. Metode de penalizare interioara (bariera)
    29.1.3. Aproximarea multiplicatorilor Kuhn-Tucker in punctul de optim
    29.1.4. Hessianul Problemei Penalizate
    29.1.5. Penalizare exacta
    29.2. Metode bazate pe functia Lagrange clasica
    29.3. Functia Lagrange generalizata. Puncte sa in programarea neconvexa
    29.3.1. Functii Lagrange augmentate
    29.3.2. Reprezentarea Lagrangeana a unei probleme de optimizare cu restrictii
    29.3.3. Reprezentarea perturbationala a unei probleme de optimizare cu restrictii
    29.3.4. Puncte sa in programarea neconvexa
    29.4. Interpretarea geometrica si compararea metodelor de penalizare
    si de Lagrangean clasic sau augmentat
    29.5. Analiza convergentei metodelor de Lagrangean clasic si augmentat
    29.6. Metode combinate de Lagrangean augmentat si penalizare modificate
    Exercitii
    Cap.30. Metode de Punct Interior de Urmarire a Traiectoriei Centrale
    30.1. Traiectoria centrala
    30.2. Metoda primal-duala de urmarire a traiectoriei centrale pentru programarea liniara
    30.3. Metoda predictor-corector de urmarire a traiectoriei centrale pentru programarea liniara
    30.4. Metoda predictor-corector de ordin superior de urmarire a traiectoriei centrale pentru programarea liniara
    30.5. Metode de punct interior de urmarire a traiectoriei centrale pentru optimizare cu restrictii liniare
    30.6. Metode de punct interior de urmarire a traiectoriei centrale pentru
    optimizare cu restrictii neliniare
    Exercitii
    Cap. 31. Complemente Privind Optimizarea cu Restrictii
    31.1. Formularea problemelor de optimizare cu restrictii
    31.2. Transformarea modelelor neliniare
    31.3. Degenerare in optimizarea cu restrictii
    31.4. Zigzaging, Jamming
    31.5. Dificultati in optimizarea cu restrictii
    31.6. Probleme de test. Aplicatii
    31.7. Rezolvarea problemelor de test si a aplicatiilor. Comparatii
    Exercitii
    Note asupra optimizarii cu restrictii
    Bibliografie
    Index de notiuni
    Index de autori
    Neculai Andrei,  August 1999