--- title: "Programmazione lineare" source: "https://systems-analysis.info/int/Programmazione_lineare" wiki: "systems-analysis.info/int" article: "Programmazione_lineare" language: "it" categories: - "Category:Italian" - "Category:Mathematical modeling" - "Category:Operations research" revision_id: 5896 wiki_created_at: 2026-09-06T23:55:33Z wiki_modified_at: 2026-09-06T23:55:33Z downloaded_at: 2026-09-07T23:10:55Z --- # 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)