Ricerca operativa

Modelli di programmazione lineare: modelli di allocazione ottima di risorse, modelli di miscelazione e di trasporto. Programmazione lineare intera con vincoli logici (uso di variabili binarie). Problemi di PL, caratterizzazione di un poliedro e calcolo dei vertici come soluzione/i ottime/i del problema di PL. Teoria della dualità: teorema della dualità debole e teorema della dualità forte, condizioni di complementarietà. Soluzioni di base ammissibile (SBA) e metodo del simplesso. Condizione di ottimalità, condizione di illimitatezza; regola anticiclaggio di Bland e operazione di Pivot.

Esame Ricerca operativa

Facoltà Ingegneria

Dal corso del Prof. De Santis Marianna

Università Università degli Studi di Roma La Sapienza

Publisher simonebelli04

A.A. 2023-2024

51 pagine

Appunti esame

Vota 4,5 / 5 (2)

Scarica

Estratto del documento

Ricerca operativa Simone Belli 1 Indice 1 Introduzione 1.1 Problemi di ottimizzazione . . . . . . . . . . . . . . . . . . . . . . 1.2 Primo esempio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Prodotto scalare . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Problemi di programmazione lineare 2.1 Poliedri . . . . . . . . . . . . . . . . 2.2 Esempio: calcolo dei vertici . . . . . 2.3 Ultime considerazioni . . . . . . . . 2.4 Teorema fondamentale della PL . . . 4 6 6 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 10 13 14 15 3 Teoria della dualità 3.1 Teorema della dualità debole . . . . . . . . . 3.2 Conseguenze del teorema della dualità debole 3.3 Teorema della dualità forte . . . . . . . . . . 3.4 Scrittura dei problemi duali . . . . . . . . . . 3.5 Condizioni di complementarietà . . . . . . . . 3.5.1 Caso generale . . . . . . . . . . . . . . 3.5.2 Esempio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 17 18 18 19 19 20 21 4 Metodo del simplesso 4.1 Forma standard . . . . . . . . . . . . 4.2 Esempio . . . . . . . . . . . . . . . . 4.3 Matrici di base e fuori base . . . . . 4.4 Procedura per calcolare SBA . . . . 4.4.1 Schema riepilogativo . . . . . 4.5 Criterio sufficiente di ottimalità . . . 4.6 Criterio di illimitatezza . . . . . . . 4.7 Costruzione di una nuova SBA . . . 4.7.1 Regola anticiclaggio di Bland 4.8 Algoritmo metodo del simplesso . . . 4.9 Operazione di Pivot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 22 24 24 26 26 27 30 32 33 34 35 5 Modelli di programmazione lineare 5.1 Modelli di allocazione ottima di risorse . . 5.1.1 Schema generale . . . . . . . . . . 5.1.2 Risorse concorrenti . . . . . . . . . 5.1.3 Risorse alternative . . . . . . . . . 5.2 Modelli di miscelazione . . . . . . . . . . . 5.2.1 Schema generale . . . . . . . . . . 5.3 Modelli di pianificazione dei trasporti . . 5.4 Modelli di programmazione lineare intera 5.4.1 Problema dello zaino . . . . . . . . 5.4.2 Problema dell’assegnamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 38 38 39 40 40 41 41 44 44 45 2 . . . . . . . . . . . . . . . . . . . . . . 5.5 5.6 5.7 Vincoli logici . . . . . . . . . . . . . . . . . . Variabili binarie

Anteprima

Vedrai una selezione di 12 pagine su 51