Please enable JavaScript.
Coggle requires JavaScript to display documents.
Programmazione Lineare (Geometria della programmazione lineare (Poliedro…
Programmazione Lineare
Modelli di programmazione matematica
Elementi
Insiemi
Raggruppano gli elementi del sistema
Parametri
Rappresentano i dati del problema
solitamente delle quantità fissate
Variabili decisionali o di controllo
grandezze variabili di un sistema
Operiamo su queste per ottimizzare
Con queste cerchiamo la soluzione ottima
Vincoli
Condizioni matematiche
Rappresentano quando il problema ha soluzioni ammissibili
Limitano le soluzioni
Discriminano i valori delle variabili decisionali
Funzione obbiettivo
Quantità da minimizzare o massimizzare
Dipende dalla richiesta del problema
Descivono le caratteristiche di un problema di ottimizzazione attraverso relazioni matematiche
Dichiara le caratteristiche della soluzione
é un linguaggio dichiarativo( che forma ha la soluzione che voglio trovare? )
non è procedurale (non descrive quali sono i passi per raggiungere una soluzione ottima)
Le soluzioni vengono trovate attraverso appositi motori di ottimizzazione
Dominio variabili decisionali
Programmazione lineare PL
tutte le variabili possono assumere valori reali
Programmazione Lineare Intera PLI
Tutte le variabili possono assumere valori interi
Programmazione lineare intera mista PLIM
Se alcune variabili possono assumere valori interi altre valori reali
Problemi di programmazione Lineare
Soluzioni
Inammissibile
L'insieme ammissibile è vuoto
Illimitato
Possiamo trovare soluzioni ammissibili che fanno ottimizzano la funzione obbiettivo a piacere
Ammette soluzione Ottima
Se esiste almeno una soluzione ammissibile che ottimizza la funzione obbiettivo
L'insieme di tutte le soluzioni ammissibili si dice regione ammissibile
per soluzione ottima intendiamo una soluzione ammissibile che ottimizza il valore della funzione obbiettivo
Risolvere un problema PL significa identificare una soluzione e in caso di soluzione ammissibile ricercare una soluzione ottima in base alla funzione obbiettivo
è un problema di ottimizzazione in cui la funzione obbiettivo e tutti i vincoli sono funzioni lineari delle variabili decisionali
Geometria della programmazione lineare
Poliedro
Insieme ottenuto dall'intersezione dei semispazi chiusi e degli interpiani di Rn
è la rappresentazione della regione ammissibile
Regione ammissibile
Regione dello spazio di Rn che rappresenta le soluzioni ammissibili
Convessità
Una combinazione convessa permette di ottenere dati due vettori, un terzo vettore che appartiene al segmento che congiunge i due vettori
esiste quindi uno scalare b compreso tra 0 e 1 tale per cui
z= bx + (1-bx)y
Stretta
Sei i valori di b sono strettamente compresi tra 0 e 1 ( ]0,1[ )
In questa casistica non possiamo rappresentare i punti estremi della combinazione
Vertice di un poliedro
è un punto del poliedro che non può essere espresso come combinazione convessa stretta di nessuno degli altri punti
Combinazione convessa
dati i punti del poliedro posso ottenenere un terzo punto appartenente al poliedro come combinazione degli altri suoi punti moltiplicati per uno scalare
Rappresentazione dei poliedri
Posso per quello che abbiamo detto fino ad ora sula convessità rappresentare un poliedro come combinazione convessa tra tutti i suoi vertici
Verice Ottimo
Se un problema ammette soluzione ottima allora questa si trova in un suo vertice
Caratterizzazione algebrica
Forma Standard
La funzione Obbiettivo è di minimo senza costanti additive o moltiplicative
se la funzione è di massimizzazione allora si moltiplica per -1 tale funzione
tutte le variabili devono essere positve o nulle
tutti i vincoli sono equazioni
Si aggiunge una variabile di slack positiva per i vincoli <=
Si aggiunge una variabile positiva di surplus per i vincoli <=
i termini noti sono positivi o nulli
si moltiplicano per -1 i termini noti negativi