Modellazione e Ottimizzazione: Comprendere i Vincoli nella Programmazione Lineare

Modellazione di Problemi di Programmazione Lineare

Il processo di modellazione di un problema di programmazione lineare si articola nelle seguenti fasi:

• Determinare e definire l'obiettivo (sia massimizzare o minimizzare).
• Sviluppare l'elenco delle scelte.
• Definire le variabili di decisione (X1, X2, ..., Xn).
• Sviluppare un elenco di restrizioni pertinenti.
• Definire la funzione obiettivo, ad esempio: Max Z = 40X1 + 50X2.

Vincoli e Restrizioni

I vincoli possono essere di tipo limitazione (≤) o requisito (≥).

Le restrizioni dovrebbero stabilire limitazioni relative alla disponibilità delle risorse e alla necessità di rispettare gli impegni per il periodo.

Tipologie di Vincoli

• Vincoli di capacità e/o disponibilità delle risorse: Si tratta di limiti dovuti a restrizioni del sistema in termini di quantità di attrezzature, spazi, finanziamenti, materie prime e manodopera a disposizione. Un esempio potrebbe essere il vincolo relativo alla terra disponibile per le colture. Questi vincoli sono espressi come limitazioni o disuguaglianze di tipo (≤). Ciò che possiamo fare con una risorsa non può essere maggiore di quanto ne abbiamo a disposizione.
• Vincoli di mercato: Ci sono dei limiti (inferiore, superiore o entrambi) sulla quantità di prodotto che può essere venduto o utilizzato. Ad esempio, il massimo delle vendite e il minimo storico per un prodotto. Quest'ultimo (il minimo storico) rappresenta un requisito o una disuguaglianza di tipo (≥), poiché se è stato concordato un certo fatturato per un prodotto, non si può decidere di produrne meno di tale importo, altrimenti non si potrebbero rispettare gli impegni di consegna. Il primo (il massimo delle vendite) è un vincolo o una disuguaglianza di tipo (≤), poiché non si dovrebbe produrre più di quanto storicamente si è stati in grado di vendere in ogni stagione.
• Vincoli di qualità o di composizione di una miscela: Queste restrizioni limitano la miscela di ingredienti che normalmente definiscono la qualità dei prodotti risultante. Queste restrizioni possono essere limitazioni (≤), requisiti (≥) o condizioni più restrittive di tipo (=).
• Vincoli di tecnologia di produzione o di bilancio dei materiali: Sono vincoli che definiscono l'output di un processo in funzione degli ingressi, spesso includendo sprechi o perdite di resa. Queste restrizioni, come quelle sopra menzionate, possono anche essere limitazioni (≤), requisiti (≥) o condizioni più restrittive di tipo (=), a seconda del processo da modellare.
• Vincoli di definizione: Queste restrizioni definiscono una variabile in funzione di altre. Spesso queste restrizioni derivano da definizioni contabili o bilanciamenti dei materiali, come il rapporto tra la quantità prodotta di un bene, che deve essere uguale a quanto venduto più quanto rimasto in magazzino. Queste restrizioni di solito sono requisiti di tipo (=).

Caratterizzazione della Soluzione Ottimale

Tipi di Vincoli

• Vincoli attivi: Questi definiscono direttamente la posizione ottimale.
• Vincoli non attivi: Questi non sono direttamente coinvolti nel determinare la posizione ottimale.
• Vincoli ridondanti: Questi sono vincoli non attivi che non partecipano direttamente o non determinano i confini dell'area delle soluzioni ammissibili.

Prezzo Ombra del Vincolo

Il prezzo ombra di un vincolo è una misura quantitativa di come ciascun vincolo influenzi il valore ottimale della funzione obiettivo in un sistema, indicando se tale valore migliora o peggiora.

Esistono due definizioni equivalenti per il prezzo ombra:

• Definizione n. 1: Il tasso di miglioramento del valore ottimale della funzione obiettivo per ogni unità di aumento del termine noto di un vincolo.
• Definizione n. 2: Il tasso di peggioramento del valore ottimale della funzione obiettivo per ogni unità di diminuzione del termine noto di un vincolo.

Queste due definizioni si basano sul presupposto che il prezzo ombra sia positivo.

Normalmente, il prezzo ombra di una restrizione di tipo limitazione (≤), se attiva, è sempre positivo.

Quando il prezzo ombra di un vincolo è negativo, cosa che accade normalmente con le restrizioni di tipo requisito (≥), l'effetto sulla funzione obiettivo è in contrasto con la definizione: quando si aumenta il termine noto, la FO peggiora; quando lo si diminuisce, migliora.

Intervalli di Valori per il Prezzo Ombra del Vincolo

• Il prezzo ombra di un vincolo attivo sarà non negativo (≥ 0) se la restrizione è una limitazione (≤).
• Il prezzo ombra di un vincolo attivo sarà non positivo (≤ 0) se la restrizione è un requisito di tipo (≥).
• Il prezzo ombra di un vincolo attivo sarà positivo, negativo o uguale a 0 se la restrizione è un requisito di tipo (=); ciò dipenderà da ogni modello specifico.
• Il prezzo ombra di un vincolo non attivo è sempre zero.

Fascia di Validità del Prezzo Ombra del Vincolo

• Il valore del prezzo ombra di un vincolo è valido solo per aumenti o diminuzioni del suo termine noto a valori tali da non causare che alcuno dei vincoli attivi della soluzione ottimale originale smetta di essere attivo.

Impatto del Prezzo Ombra sulla Funzione Obiettivo (FO)

• La Funzione Obiettivo (FO) migliorerà il suo valore (aumenterà se si sta massimizzando e diminuirà se si sta minimizzando) quando si aumenta il valore del termine noto di un vincolo attivo di tipo limitazione (≤).
• La FO peggiorerà il suo valore (diminuirà se si sta massimizzando e aumenterà se si sta minimizzando) quando il termine noto di un vincolo attivo di tipo limitazione (≤) diminuisce.
• La FO migliorerà il suo valore (aumenterà se si sta massimizzando e diminuirà se si sta minimizzando) quando il termine noto di un vincolo attivo di tipo requisito (≥) diminuisce.
• La FO peggiorerà il suo valore (diminuirà se si sta massimizzando e aumenterà se si sta minimizzando) quando si aumenta il valore del termine noto di un vincolo attivo di tipo requisito (≥).
• La FO manterrà il suo valore (non cambierà) quando si aumenta o diminuisce il valore del termine noto di un vincolo non attivo di qualsiasi tipo.