Regione ammissibile
La regione delle soluzioni ammissibili (RSA) (anche insieme delle soluzioni ammissibili, ingl. Feasible region, feasible set) — nella ricerca operativa, nell'ottimizzazione e nella modellazione matematica è l'insieme di tutte le possibili soluzioni (insiemi di valori delle variabili) che soddisfano tutti i vincoli imposti al problema.
La RSA rappresenta il sottospazio in cui viene condotta la ricerca della soluzione ottimale. Qualsiasi soluzione che si trova al di fuori di questa regione è considerata inammissibile.
Definizione e formazione
La regione delle soluzioni ammissibili si forma come intersezione degli insiemi definiti da ciascun singolo vincolo del problema. I vincoli possono essere rappresentati sotto forma di:
- Disuguaglianze: Stabiliscono limiti superiori o inferiori per i valori delle variabili o delle loro combinazioni (ad esempio, "il consumo della risorsa A non deve superare 100 unità", "la quantità di prodotti fabbricati deve essere di almeno 50 pezzi").
- Uguaglianze: Richiedono il soddisfacimento esatto di una condizione (ad esempio, "il volume totale dei trasporti deve essere uguale a 1000 tonnellate", "il bilancio dei flussi entranti e uscenti è uguale a zero").
- Condizioni sul segno delle variabili: Spesso le variabili devono essere non negative, intere o appartenere a un determinato insieme discreto.
Un punto (o vettore di valori delle variabili) appartiene alla RSA se e solo se soddisfa simultaneamente tutti questi vincoli.
Interpretazione geometrica
La RSA ha spesso un'interpretazione geometrica intuitiva, in particolare nei problemi con un numero ridotto di variabili:
- Nello spazio bidimensionale (2 variabili): Ogni vincolo lineare di disuguaglianza definisce un semipiano. La RSA è l'intersezione di questi semipiani — un poligono convesso (eventualmente illimitato o vuoto).
- Nello spazio tridimensionale (3 variabili): Ogni vincolo lineare di disuguaglianza definisce un semispazio. La RSA è l'intersezione di questi semispazi — un poliedro convesso.
- Nello spazio multidimensionale: La RSA, definita da vincoli lineari, è un poliedro convesso (politopo).
Nel caso di vincoli non lineari, la RSA può avere una forma più complessa e non essere convessa.
Ruolo nell'ottimizzazione
La regione delle soluzioni ammissibili svolge un ruolo fondamentale nell'ottimizzazione:
1. Definizione dello spazio di ricerca: La soluzione ottimale del problema (se esiste) si trova sempre all'interno della RSA o sul suo confine. Gli algoritmi di ottimizzazione cercano l'estremo della funzione obiettivo proprio in questa regione. 2. Verifica dell'esistenza delle soluzioni: Se la RSA è un insieme vuoto (ovvero i vincoli si contraddicono a vicenda), il problema non ha soluzioni ammissibili e, di conseguenza, nemmeno una soluzione ottimale. 3. Influenza sulla soluzione ottimale: La forma e le dimensioni della RSA influiscono direttamente sulla possibilità di raggiungere l'estremo della funzione obiettivo e sul valore di tale estremo.
Proprietà della RSA (nei problemi di programmazione lineare)
Nei problemi di programmazione lineare (PL), dove tutti i vincoli e la funzione obiettivo sono lineari, la RSA possiede proprietà importanti:
- Convessità: Se due punti appartengono alla RSA, anche l'intero segmento che li unisce appartiene alla RSA. Questa proprietà garantisce che la soluzione ottimale (se esiste ed è unica) si trovi in uno dei vertici del poliedro della RSA.
- Chiusura: La RSA include i propri confini (a causa delle disuguaglianze non strette ≤, ≥ e delle uguaglianze).
La RSA può essere:
- Limitata: Ha dimensioni finite.
- Illimitata: Si estende all'infinito in una o più direzioni.
- Vuota: Non contiene alcun punto.
Vedi anche
- Ricerca operativa
- Ottimizzazione
- Modello matematico
- Vincoli
- Soluzione ammissibile
- Soluzione ottimale
- Funzione obiettivo
- Programmazione lineare
- Insieme convesso
Letteratura
- Ventcel' E. S. Ricerca operativa: problemi, principi, metodologia. — Mosca: Nauka, 1988.
- Ackoff R., Sasieni M. Fondamenti di ricerca operativa. — Mosca: Mir, 1971.
- Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
- Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)