programmazione matematica

programmazione matematica

programmazione matematica parte della ricerca operativa che studia problemi di determinazione degli estremanti (massimi o minimi) di una funzione (reale), detta funzione obiettivo, definita su insiemi finiti o infiniti. Senza perdita di generalità, si può sempre fare riferimento a problemi di minimo, poiché un problema di massimo si riconduce a uno di minimo sostituendo la funzione obiettivo con la sua opposta. Viceversa un problema di minimo si può sempre ricondurre a un equivalente problema di massimo. Si distingue tra → programmazione lineare in cui sia la funzione da ottimizzare sia i vincoli di segno sono espressi da funzioni o disequazioni lineari e → programmazione non lineare in cui funzioni e vincoli sono in tutto o in parte non lineari. Si parla poi di programmazione intera (o discreta) se intervengono variabili che assumono valori soltanto nell’insieme Z dei numeri interi, di programmazione mista se alcune variabili possono assumere solo valori interi, mentre le altre assumono valori reali e di programmazione bivalente (o zero-uno) se le variabili possono assumere soltanto i valori 0 e 1. Tra i metodi risolutivi si hanno:

• varianti del metodo del → simplesso: per tali metodi, l’idea generale è quella di risolvere una sequenza finita di problemi di programmazione lineare ordinaria, introducendo di volta in volta un vincolo ulteriore in modo che la regione ammissibile di ogni nuovo problema escluda la soluzione ottima del problema precedente, ma contenga tutte le soluzioni ammissibili (intere) del problema di partenza;

• metodi di tipo enumerativo (suscettibili di numerose versioni e applicazioni anche a problemi di programmazione non intera e a problemi non appartenenti all’ambito della programmazione) consistenti nel valutare la funzione obiettivo in un opportuno sottoinsieme dell’insieme delle soluzioni ammissibili: tra questi ultimi, i metodi di separazione progressiva (branch and bound) consistono nel suddividere opportunamente la regione ammissibile in sottoinsiemi in corrispondenza dei quali viene risolto un problema di programmazione lineare avente la medesima funzione obiettivo ed eliminando successivamente, mediante ulteriori indagini, alcuni di tali sottoinsiemi, fino ad arrivare, se necessario, a un sottoinsieme contenente soltanto la soluzione ottima.