Programmazione lineare

La programmazione lineare è una branca della programmazione matematica e un metodo ampiamente utilizzato nella ricerca operativa, dedicato allo sviluppo della teoria e dei metodi per la risoluzione di problemi di ricerca dell'estremo (massimo o minimo) di una funzione lineare in presenza di vincoli lineari.

La programmazione lineare (PL) è uno degli strumenti più potenti e frequentemente applicati per la risoluzione di problemi di ottimizzazione in economia, gestione, pianificazione, logistica e altri settori.

Oggetto e finalità

Il problema fondamentale della programmazione lineare consiste nel trovare il modo migliore (ottimale) di allocare risorse limitate per raggiungere un determinato obiettivo, quando sia l'obiettivo sia i vincoli sull'utilizzo delle risorse possono essere espressi mediante relazioni lineari.

• La programmazione lineare consente di risolvere problemi pratici quali:
• Pianificazione ottimale della produzione.
• Ottimizzazione dei flussi di trasporto (problema del trasporto).
• Allocazione ottimale degli investimenti.
• Taglio ottimale dei materiali. Problema delle assegnazioni.

Formulazione matematica del problema di PL

Il problema standard di programmazione lineare è formulato come segue:

Si devono trovare i valori delle variabili decisionali che massimizzino o minimizzino una funzione obiettivo lineare. Le variabili decisionali sono soggette a vincoli espressi sotto forma di sistema di uguaglianze e/o disuguaglianze lineari. Di norma viene aggiunta la condizione di non negatività delle variabili decisionali (i loro valori devono essere maggiori o uguali a zero), il che è spesso dettato dal significato fisico o economico del problema.

Matematicamente ciò implica il lavoro con funzioni lineari e sistemi di equazioni/disuguaglianze lineari.

Concetti fondamentali della PL

• Variabili decisionali (variabili controllabili): grandezze i cui valori devono essere determinati nel processo di risoluzione del problema (ad esempio, i volumi di produzione di diversi prodotti, la quantità di risorse destinate a diversi obiettivi).
• Funzione obiettivo: funzione lineare delle variabili decisionali il cui valore deve essere massimizzato o minimizzato. Essa esprime quantitativamente l'obiettivo del problema (ad esempio, il profitto totale, i costi complessivi).
• Vincoli: sistema di uguaglianze e/o disuguaglianze lineari che le variabili decisionali devono soddisfare. I vincoli riflettono i limiti delle risorse, i requisiti tecnologici, gli obiettivi di piano e altre condizioni del problema.
• Regione ammissibile (RA): insieme di tutte le combinazioni di valori delle variabili decisionali che soddisfano tutti i vincoli del problema. Geometricamente, nello spazio multidimensionale, la RA rappresenta un poliedro convesso, eventualmente illimitato o vuoto.
• Soluzione ammissibile: qualsiasi combinazione di valori delle variabili appartenente alla RA.
• Soluzione ottimale: soluzione ammissibile in corrispondenza della quale la funzione obiettivo raggiunge il proprio valore estremo (massimo o minimo). Se la soluzione ottimale esiste, essa si trova sempre sulla frontiera della RA, almeno in uno dei vertici del poliedro convesso della RA (teorema fondamentale della PL).

Metodi di risoluzione dei problemi di PL

Esistono diversi metodi principali per la risoluzione di problemi di programmazione lineare:

• Metodo grafico: si applica ai problemi con due variabili decisionali. Consente di rappresentare visivamente la RA e la funzione obiettivo sul piano e di trovare la soluzione ottimale analizzando i vertici della RA o traslando la retta di livello della funzione obiettivo.
• Metodo del simplesso: algoritmo iterativo universale sviluppato da George Dantzig. Il metodo passa in sequenza da un vertice della RA al vertice adiacente, migliorando il valore della funzione obiettivo a ogni passo, finché non viene trovata la soluzione ottimale. È il metodo classico e più noto per la risoluzione di problemi di PL.
• Metodi del punto interno: classe alternativa di algoritmi, sviluppati successivamente al metodo del simplesso. Essi si avvicinano alla soluzione ottimale muovendosi all'interno della RA anziché lungo i suoi bordi. Questi metodi sono particolarmente efficaci per la risoluzione di problemi di PL di dimensioni molto grandi.

Dualità nella programmazione lineare

A ogni problema di programmazione lineare (detto problema primale) si può associare un altro problema di PL, detto problema duale. Il problema primale e il problema duale sono strettamente correlati:

La soluzione di un problema fornisce informazioni sulla soluzione dell'altro. I valori ottimali delle funzioni obiettivo in entrambi i problemi coincidono (se esistono). Le variabili del problema duale hanno un'importante interpretazione economica: esse corrispondono ai prezzi ombra (o valutazioni duali) delle risorse, indicando di quanto varia il valore ottimale della funzione obiettivo del problema primale a fronte di una piccola variazione del vincolo sulla risorsa corrispondente.

Applicazioni della PL

La programmazione lineare trova ampia applicazione in:

• Economia e business (pianificazione della produzione, logistica, finanza, marketing).
• Industria (ottimizzazione dei processi tecnologici, gestione delle scorte, taglio dei materiali).
• Trasporti (ottimizzazione dei percorsi, degli orari). Agricoltura (ottimizzazione delle superfici coltivate, delle razioni alimentari).
• Energia (ottimizzazione del carico delle capacità di generazione).

Vedi anche

• Ricerca operativa
• Ottimizzazione
• Funzione obiettivo
• Vincoli
• Regione ammissibile
• Soluzione ottimale

Bibliografia

• Dantzig G. Programmazione lineare, sue applicazioni e generalizzazioni. — Mosca: Progress, 1966.
• Judin D. B., Gol'štejn E. G. Programmazione lineare (teoria, metodi e applicazioni). — Mosca: Nauka, 1969.
• 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)