Risolutore di Programmazione Lineare

Risolutore di Programmazione Lineare

Il Risolutore di Programmazione Lineare è un calcolatore online che trova il massimo o il minimo di una funzione obiettivo lineare soggetta a un sistema di disuguaglianze o uguaglianze lineari. Utilizza il metodo del simplesso (variante Big-M) in modo che i vincoli <=, >= e = possano essere mischiati liberamente e, per i problemi a 2 variabili, disegna un grafico interattivo della regione ammissibile con ogni vertice e l'ottimo evidenziati.

Cos'è la programmazione lineare?

Un problema di programmazione lineare (PL) chiede di:

L'insieme dei punti che soddisfano ogni vincolo è chiamato regione ammissibile, un poliedro convesso. Il Teorema Fondamentale della Programmazione Lineare afferma che se la PL ha un ottimo finito, esso viene raggiunto in un vertice (punto estremo) di questo poliedro. Questo è il motivo per cui il metodo del simplesso — che cammina da vertice a vertice — è così efficace.

Come funziona il metodo del simplesso

Partendo da un vertice ammissibile, il metodo del simplesso migliora ripetutamente l'obiettivo ruotando verso un vertice vicino con un valore migliore. La meccanica:

1. Forma standard: converte la PL in max c^Tx soggetta a Ax = b, x ≥ 0. Per i vincoli <=, aggiunge variabili slack (scarto); per >=, sottrae un surplus e aggiunge una variabile artificiale con una grande penalità −M; per le uguaglianze, aggiunge un'artificiale.
2. Tableau iniziale: la base consiste di slack e artificiali, il che fornisce un vertice di partenza ovvio.
3. Variabile entrante: sceglie la variabile non di base con il costo ridotto positivo più grande \( c_j - z_j \). Se non esiste tale variabile, la soluzione attuale è ottimale.
4. Variabile uscente: dalla colonna entrante, esegue il test del rapporto minimo — divide l'RHS di ogni riga per il suo coefficiente positivo nella colonna entrante e sceglie la riga con il rapporto più piccolo. Se non esiste alcun coefficiente positivo, la PL è illimitata.
5. Pivot: usa l'eliminazione gaussiana per rendere la colonna entrante un vettore unitario, con 1 nella riga uscente.
6. Ripete fino a quando il criterio di arresto non è soddisfatto.

Se al termine dell'algoritmo rimane in base una variabile artificiale con valore positivo, la PL originale è impossibile.

Metodo grafico (per 2 variabili)

Per i problemi a due variabili, la regione ammissibile è un poligono convesso 2D. Poiché l'ottimo è sempre in un vertice, enumerare ogni vertice e valutare l'obiettivo lì è sufficiente per risolvere il problema. Questo calcolatore esegue tale enumerazione intersecando ogni coppia di confini dei vincoli, mantenendo solo le intersezioni che soddisfano tutti gli altri vincoli e ordinandole in senso antiorario per la visualizzazione.

Sintassi di input

Scrivi l'obiettivo sulla prima riga, poi un vincolo per riga. I nomi delle variabili possono essere qualsiasi identificatore (x, y, x1, profitto…). Gli operatori sono <=, >= e =. La non-negatività può essere scritta come x, y >= 0 come scorciatoia.

Le righe vuote e i commenti che iniziano con # vengono ignorati. Il risolutore accetta fino a 8 variabili decisionali e 20 vincoli.

Esempio svolto

Considera un laboratorio di mobili che costruisce tavoli e sedie. Ogni tavolo produce 3 \$ di profitto e richiede 1 unità di legno e 2 unità di lavoro. Ogni sedia produce 5 \$ di profitto e richiede 1 unità di legno, 1 unità di lavoro e 3 unità di vernice. Disponibili: 10 legno, 16 lavoro, 18 vernice. Con x = tavoli e y = sedie, la PL è:

La regione ammissibile è un pentagono. Valutando Z in ogni vertice:

Quindi il laboratorio dovrebbe costruire 6 tavoli e 4 sedie per un profitto massimo di 38 \$. I vincoli di legno e lavoro sono attivi (equivalgono al loro RHS all'ottimo); la vernice ha uno slack di 0 (anch'essa attiva in questo caso), il che significa che tutte e tre le risorse sono esaurite.

Errori comuni e cosa rileva il risolutore

Applicazioni

• Mix di prodotti e pianificazione della produzione — quanti prodotti fabbricare per il massimo profitto sotto limiti di risorse.
• Problemi di dieta e miscelazione — minimizzare il costo di una dieta o di un mangime che soddisfi comunque i minimi nutrizionali.
• Trasporto e assegnazione — minimizzare i costi di spedizione quando offerta e domanda devono equilibrarsi.
• Ottimizzazione del portafoglio — massimizzare il rendimento atteso sotto vincoli di rischio o esposizione (linearizzati).
• Flusso di rete — il flusso massimo e il flusso di costo minimo si riducono a PL con matrici dei coefficienti totalmente unimodulari.
• Pianificazione dei turni — turnistica della forza lavoro con requisiti di turno e limiti di ore totali.

Come usare questo calcolatore

1. Digita la tua PL nella casella di testo. La prima riga deve iniziare con Massimizza o Minimizza. Ogni riga successiva è un vincolo, uno per riga.
2. Usa la scorciatoia x, y >= 0 per dichiarare la non-negatività per tutte le variabili elencate contemporaneamente.
3. Clicca su Risolvi problema di PL. Il risolutore riporta il valore ottimale Z, i valori ottimali di ogni variabile decisionale, un elenco di vincoli attivi e, per le PL a 2 variabili, un grafico interattivo della regione ammissibile.
4. Passa il mouse su un vertice nel grafico per vedere le sue coordinate e il valore Z. L'ottimo è evidenziato con una stella.
5. Rivedi i tableau del simplesso per vedere ogni pivot e tracciare come il metodo migliora Z. La colonna entrante è evidenziata in ambra; la riga uscente in rosso.

Domande frequenti

Cos'è un problema di programmazione lineare?

Un problema di programmazione lineare (PL) richiede il massimo o il minimo di una funzione obiettivo lineare su un insieme di variabili decisionali che soddisfano un sistema di disuguaglianze o uguaglianze lineari. Il set ammissibile è un poliedro convesso e l'ottimo è sempre raggiunto in uno dei suoi vertici — il fatto chiave sfruttato dal metodo del simplesso.

Come funziona il metodo del simplesso?

Il metodo del simplesso si sposta lungo i vertici del poliedro ammissibile. Ogni passaggio (un "pivot") scambia una variabile nella base con un'altra, spostandosi verso un vertice vicino con un obiettivo strettamente migliore. L'algoritmo si ferma quando nessun pivot può migliorare Z — il vertice corrente è quindi ottimale. Questo strumento utilizza la variante Big-M in modo che i vincoli <=, >= e = possano essere mischiati.

Cos'è la regione ammissibile?

La regione ammissibile è l'insieme di tutti i valori delle variabili che soddisfano contemporaneamente ogni vincolo. Per 2 variabili è un poligono convesso 2D; per n variabili è un poliedro n-dimensionale. Un poliedro vuoto significa che la PL è impossibile; un poliedro che si estende all'infinito nella direzione del miglioramento significa che la PL è illimitata.

Cosa significa "illimitato" nella programmazione lineare?

Una PL è illimitata quando la regione ammissibile si allunga all'infinito in una direzione in cui l'obiettivo continua a migliorare. Ad esempio, Massimizza x soggetto solo a x ≥ 0 non ha un massimo finito. Le PL del mondo reale che risultano illimitate di solito rivelano un vincolo mancante — spesso un limite superiore su una risorsa o variabile.

Cosa significa "ottimi alternativi"?

Gli ottimi alternativi si verificano quando più di un punto raggiunge lo stesso miglior valore obiettivo. Geometricamente, l'obiettivo è parallelo a un lato attivo del poligono, quindi ogni punto lungo quel lato — e ogni combinazione convessa dei suoi estremi — è ottimale. Il risolutore lo segnala quando una variabile decisionale non di base ha un costo ridotto pari a zero al termine.

Quante variabili e vincoli accetta il risolutore?

Fino a 8 variabili decisionali e 20 vincoli. Il grafico interattivo della regione ammissibile viene disegnato solo per problemi a 2 variabili; con 3 o più variabili ottieni comunque la soluzione numerica completa del simplesso, i tableau passo dopo passo e il rapporto sui vincoli attivi.

Ulteriori letture

• Programmazione lineare — Wikipedia
• Algoritmo del simplesso — Wikipedia
• Metodo Big M (Inglese) — Wikipedia
• Dualità nell'ottimizzazione — Wikipedia

Operazioni matematiche avanzate:

• Calcolatore di Matrice di Adiacenza Nuovo
• Calcolatore di Antilogaritmo
• Calcolatore di funzione Beta
• Calcolatore del Coefficiente Binomiale
• Calcolatrice di distribuzione binomiale
• Calcolatore Bitwise
• Semplificatore di Algebra Booleana Nuovo
• Calcolatore del Teorema Centrale del Limite
• Calcolatore del Teorema Cinese del Resto
• Calcolatore di combinazione
• Calcolatore di Funzione di Errore Complementare
• Calcolatrice di Numeri Complessi
• Calcolatore di Frazioni Continue Popolare
• Calcolatore di Derangement (Sottofattoriale)
• Calcolatore del Percorso più Breve di Dijkstra
• Calcolatore di Entropia
• Calcolatore della funzione di errore
• Calcolatore della Funzione Toziente di Eulero
• Calcolatore di decadimento esponenziale
• Calcolatore della crescita esponenziale
• Calcolatore dell'Integrale Esponenziale
• Calcolatore di Esponenti (Alta Precisione) Popolare
• Calcolatore dell'Algoritmo Euclideo Esteso
• Calcolatrice del Fattoriale Popolare
• Calcolatore della Funzione Gamma
• Calcolatore del Rapporto Aureo
• Calcolatore di Colorazione di Grafi Nuovo
• Validatore di Sequenza di Gradi di Grafo
• Calcolatore Ordine Teoria dei Gruppi Nuovo
• Calcolatore del tempo di dimezzamento
• Verificatore di Cammino Hamiltoniano Nuovo
• Calcolatore Inclusione-Esclusione Nuovo
• Risolutore di Mappa di Karnaugh (K-Map) Nuovo
• Risolutore di Programmazione Lineare Nuovo
• Calcolatore Distribuzione Stazionaria Catena di Markov
• Calcolatore dell'Albero Ricoprente Minimo
• Calcolatore Esponenziazione Modulare Nuovo
• Calcolatore dell'Inverso Moltiplicativo Modulare
• Calcolatore Distribuzione Binomiale Negativa Nuovo
• Calcolatore di Flusso in Rete (Flusso Massimo) Nuovo
• Calcolatore del Tasso di Crescita Percentuale
• Calcolatore di Permutazione
• Calcolatore Permutazioni con Ripetizione Nuovo
• Calcolatore del Principio dei Cassetti
• Verificatore di Grafo Planare Nuovo
• Calcolatrice della Distribuzione di Poisson
• Calcolatrice delle Radici dei Polinomi con Passaggi Dettagliati
• Calcolatore Radice Primitiva
• Calcolatrice delle probabilità
• Calcolatrice di Distribuzione di Probabilità
• Calcolatore di Proporzioni
• Calcolatore di formula quadratica
• Calcolatore di Anelli e Campi Nuovo
• Calcolatore di Arrotondamento Nuovo
• Calcolatrice Scientifica
• Calcolatore di notazioni scientifiche Popolare
• Calcolatore di Teoria degli Insiemi
• Calcolatore di Cifre Significative Nuovo
• Risolutore del Problema del Matrimonio Stabile Nuovo
• Calcolatore di Numeri di Stirling
• Calcolatore di Somme di Cubi
• Calcolatore di somme di numeri interi positivi
• Calcolatore di Somme di Quadrati
• Calcolatore di Ordinamento Topologico Nuovo
• Risolutore del Commesso Viaggiatore (TSP) Nuovo
• Generatore di Tabella di Verità
• Generatore di Diagramma di Venn (3 Insiemi)