CRITICA RATIUNII ALGORITMILOR DE PROGRAMARE LINIARA
Neculai Andrei
Criticism of the Linear Programming Algorithms Reasoning
(Critica ratiunii algoritmilor de programare liniara)
(in Romanian)
Editura Academiei Romane - Bucharest, 2011
ISBN 978-973-27-2076-9
908 + XXVII pages
NECULAI ANDREI CRITICA RATIUNII ALGORITMILOR DE PROGRAMARE LINIARA
Cuprins
Lista prototipurilor de modele de programare liniara
Prefata
Simboluri si notatii
Cap. 1. Fundamente 1.1. Introducere in programarea liniara 1.2. Metode pentru programarea liniara si critica lor 1.3. Importanta programarii liniare 1.4. Contributia romaneasca in domeniul programarii liniare 1.5. Elemente de algebra liniara 1.6. Elemente de analiza convexa
Cap. 2. Poliedre. Inegalitati liniare si programarea liniara 2.1. Concepte fundamentale şi rezultate asupra poliedrelor şi inegalităţilor liniare
2.1.1. Teorema fundamentală a inegalităţilor liniare
2.1.2. Mulţimi şi conuri poliedrale
2.1.3. Lema lui Farkas-Minkowski şi variantele ei
2.1.4. Inegalităţi stricte
2.1.5. Puncte extreme. Feţe. Direcţii şi direcţii extreme ale mulţimilor poliedrale
2.1.6. Reprezentarea mulţimilor poliedrale
2.2. Introducere în programarea liniară.
2.2.1. Problema programării liniare
2.2.2. Forma standard şi canonică. Transformări echivalente
2.2.3. Interpretarea geometrică a programării liniare în spaţiul activităţilor
2.2.4. Interpretarea geometrică a programării liniare în spaţiul resurselor
Cap.3. Metoda simplex
3.1. Puncte extreme şi optimalitate
3.2. Soluţii admisibile de bază
3.3. Reducerea problemei în spaţiul variabilelor nebazice
3.4. Expresia geometrică a algoritmului simplex
3.5. Algoritmul simplex
3.6. Algoritmul simplex în format tablou
3.7. Determinarea unei soluţii admisibile de bază iniţiale
3.8. Metoda simplex a celor două faze
Cap.4.
Extensii ale algoritmului simplex. Convergenţă. Condiţii de optimalitate
4.1. Degenerare. Ciclare. Stagnare
4.1.1. Metoda lexicografică de protecţie la ciclare
4.1.2. Regula lui Bland
4.1.3. Metoda Wolfe
4.1.4. Stagnare
4.2. Metode de evaluare
4.2.1. Evaluări parţiale
4.2.2. Evaluări multiple
4.2.3. Metoda Devex
4.2.4. Selectarea celei mai abrupte direcţii
4.3. Algoritmul simplex cu variabile mărginite
4.3.1. Soluţii admisibile de bază
4.3.2. Îmbunătăţirea unei soluţii admisibile de bază
4.3.3. Algoritmul simplex cu variabile mărginite
4.3.4. Convergenţă. Degenerare. Ciclare
4.4. Condiţiile Karush-Kuhn-Tucker în programarea liniară
4.4.1. Teoreme de alternativă
4.4.2. Lema Farkas-Minkowski şi programarea liniară
4.4.3. Condiţiile KKT pentru programarea liniară cu restricţii inegalităţi
4.4.4. Condiţiile KKT pentru programarea liniară cu restricţii egalităţi
4.4.5. Condiţiile KKT şi algoritmul simplex
4.4.6. Dualitate Lagrangeană în programarea liniară
Cap.5.
Dualitate în programarea liniară
5.1. Formularea problemei duale
5.2. Proprietăţi de dualitate în programarea liniară
5.3. Interpretarea economică a dualităţii
5.4. Rezolvarea simultană a unui cuplu de probleme duale
5.5. Algoritmul simplex dual
5.6. Algoritmul simplex primal-dual
Cap.6.
Reoptimizare. Analiza sensibilităţii. Programarea liniară parametrică şi robustă
6.1. Reoptimizare în programarea liniară
6.1.1. Modificarea termenului liber
6.1.2. Modificarea coeficienţilor funcţiei obiectiv
6.1.3. Modificarea unei coloane a matricei restricţiilor
6.1.4. Adăugarea unei noi activităţi (coloane)
6.1.5. Adăugarea unei noi restricţii (linii)
6.2. Analiza sensibilităţii în programarea liniară
6.2.1. Sensibilitatea la variaţia componentelor termenului liber
6.2.2. Sensibilitatea la variaţia coeficienţilor funcţiei obiectiv
6.2.3. Sensibilitatea la variaţia elementelor matricei restricţiilor
6.2.4. Toleranţe asupra modificării simultane şi independente în coeficienţii funcţiei obiectiv sau a termenului liber
6.3. Programarea liniară parametrică
6.3.1. Parametrizarea funcţiei obiectiv
6.3.2. Parametrizarea termenului liber
6.4. Soluţii neadmisibile
6.5. Programarea liniară interval
6.6. Programarea liniară robustă
Cap.7. Forma produs a inversei şi algoritmul simplex
7.1. Forma produs a inversei
7.2. Strategii de alegere a pivoţilor în calculul FPI
7.2.1. Preasignarea pivoţilor cu selectarea coloanelor spic
7.2.2. Preasignarea pivoţilor utilizând partiţionarea ierarhizată
7.3. Algoritmi de calcul a FPI
7.4. Algoritmul simplex cu FPI
7.5. Reinversarea bazei
Cap.8. Forma de eliminare a inversei şi algoritmul simplex
8.1. Forma de eliminare a inversei
8.2. Strategii de alegere a pivoţilor în calculul FEI
8.3. Comparaţie între FPI şi FEI
8.4. Algoritmi de calcul a FEI
8.5. Actualizarea FEI
8.6. Algoritmul simplex cu FEI
8.7. Studiu numeric (MINOS)
Cap.9. Factorizarea dinamică partiţionată a bazei şi algoritmul simplex
9.1. Inversa bazei partiţionate
9.2. Triunghiularizarea cucuielor
9.3. Repartiţionarea bazei
9.4. Algoritmul simplex cu FDP a bazei
Cap.10. Complexitatea algoritmului simplex. Algoritmi polinomiali de programare liniară
10.1. Aspecte ale complexităţii computaţionale
10.2. Complexitatea problemei de programare liniară
10.3. Aspecte asupra complexităţii algoritmului simplex
10.4. Metoda elipsoidului
10.5. Algoritmi de punct interior
10.5.1. Algoritm de scalare afină (Ye)
10.5.2. Algoritm de scalare proiectivă (Karmarkar)
Cap. 11. Metode de punct interior de scalare afină pentru programarea liniară
11.1. Interpretare geometrică
11.2. Aspecte matematice
11.3. Algoritmul de scalare afină primal
11.4. Algoritmul de scalare afină primal cu partiţionarea restricţiilor
11.5. Algoritmul de scalare afină dual
11.6. Metode de scalare afină în spaţiul nul
Cap. 12. Metode de punct interior de urmărire a traiectoriei în programarea liniară
12.1. Problema barieră
12.2. Multiplicatori Lagrange
12.3. Traiectoria centrală
12.4. Metoda primal-duală de urmărire a traiectoriei pentru programarea liniară
12.5.Metoda predictor-corector de urmărire a traiectoriei pentru programarea liniară
12.6. Metoda predictor-corector de ordin superior de urmărire a traiectoriei pentru programarea liniară
12.7. Aspecte algebrice ale metodelor de punct interior
12.8. Studiu numeric (HOPDM)
Cap. 13. Metode omogene auto-duale în programarea liniară
13.1. Forma auto-duală a unei probleme de programare liniară
13.2. Probleme omogene autoduale
13.3. Metoda omogenă auto-duală pentru programarea liniară
Cap. 14. Programe liniare cu structuri speciale. Metode de descompunere
14.1. Programe liniare cu structură unghiulară
14.1.1. Principiul şi algoritmul de descompunere Dantzig-Wolfe
14.1.2. Metode de partiţionare şi relaxare. Algoritmul Rosen
14.2. Programe liniare cu structură scară
14.2.1. Metoda simplex pentru programarea liniară cu structură scară
14.2.2. Metoda descompunerii în cuib
14.2.3. O metodă de descompunere ([Andrei, 1981a,b, 1983])
Cap. 15. Simplificarea modelelor de programare liniară
15.1. Teste de simplificare a modelelor de programare liniară
15.2. Eliminarea restricţiilor de balanţă
15.3. Splitarea coloanelor dense
Cap.16. Modelare matematică în programarea liniară
16.1. Aspecte generale asupra modelării matematice
16.2. Modelarea fenomenelor ca programe liniare
16.3. Schema de modelare pentru programarea liniară
16.4. Formatul standard MPS
16.5. Descrierea externă într-un limbaj de programare matematică
Cap. 17. Modele de programe liniare în limbajul ALLO
17.1. Sistemul SAMO –Sistem Avansat de Modelare şi Optimizare
17.2. Modele de alocare
17.3. Modele de asamblare
17.4. Modele de dezasamblare
17.5. Modele de dezasamblare-asamblare
17.6. Modele de transport
17.7. Modele de repartiţie (asignare)
17.8. Modele de curgere în reţele
17.9. Modele de amestec
17.10. Modele de producţie cu selectarea optimă a tehnologiilor
17.11. Modele de sisteme cu stocuri
17.12. Modele de producţie liniar dinamice
17.13. Modele cu structură scară. Optimizarea „mersului” unei centrale termoelectrice
17.14. Dezvoltarea modelelor
Cap. 18. Pachete de programe pentru programarea liniară
18.1. Pachete bazate pe algoritmul simplex
18.2. Pachete bazate pe metode de punct interior
Anexa A1. Complemente asupra poliedrelor, inegalităţilor liniare şi programării liniare
Anexa A2. Lista algoritmilor
Anexa A3. Lista modelelor de programare liniară în limbajul ALLO. Prototipuri
Anexa A4. Lista programelor şi a prototipurilor în limbajul ALLO
Anexa A5. O colecţie de probleme de programare liniară pentru care algoritmul simplex ciclează
