L'ottimizzazione ti aiuta a trovare il miglior risultato che porta profitto, riduce i costi o imposta un parametro che causa errori nei processi aziendali.
Questo processo è anche chiamato programmazione matematica. Risolve il problema di determinare la distribuzione delle risorse limitate necessarie per raggiungere l'obiettivo fissato dal responsabile del problema di ottimizzazione. Tra tutte le opzioni possibili, è auspicabile trovare quella che massimizza (o riduce) il parametro di controllo, ad esempio profitto o costo. I modelli di ottimizzazione sono anche chiamati prescrittivi o normativi perché cercano di trovare una strategia fattibile per l'azienda.
Cronologia dello sviluppo
La programmazione lineare (LP) funziona con una classe di problemi di ottimizzazione in cui tutti i vincoli sono lineari.
Presentando una breve storia dello sviluppo di LP:
- Nel 1762, Lagrange risolse semplici problemi di ottimizzazione con vincoli di uguaglianza.
- Nel 1820, decise Gausssistema lineare di equazioni che utilizza l'eliminazione.
- Nel 1866, Wilhelm Jordan perfezionò il metodo per trovare gli errori dei minimi quadrati come criterio di adattamento. Questo è ora chiamato il metodo Gauss-Jordan.
- Il computer digitale apparve nel 1945.
- Danzig ha inventato i metodi simplex nel 1947.
- Nel 1968, Fiacco e McCormick introdussero il metodo Inside Point.
- Nel 1984, Karmarkar ha applicato il metodo interiore per risolvere i programmi lineari, aggiungendo la sua analisi innovativa.
LP ha dimostrato di essere uno strumento estremamente potente sia per la modellazione di problemi del mondo reale che come teoria matematica ampiamente applicata. Tuttavia, molti problemi di ottimizzazione interessanti non sono lineari.
Cosa fare in questo caso? Lo studio di tali problemi coinvolge una variegata miscela di algebra lineare, calcolo multivariato, analisi numerica e metodi computazionali. Gli scienziati stanno sviluppando algoritmi computazionali, inclusi metodi di punti interni per la programmazione lineare, la geometria, l'analisi di insiemi e funzioni convessi e lo studio di problemi strutturati in modo speciale come la programmazione quadratica.
L'ottimizzazione non lineare fornisce una comprensione fondamentale dell'analisi matematica ed è ampiamente utilizzata in vari campi come l'ingegneria, l'analisi di regressione, la gestione delle risorse, l'esplorazione geofisica e l'economia.
Classificazione dei problemi di ottimizzazione
Un importante passo avantiIl processo di ottimizzazione è la classificazione dei modelli, poiché i loro algoritmi di soluzione sono adattati a un tipo particolare.
1. Problemi di ottimizzazione discreta e continua. Alcuni modelli hanno senso solo se le variabili prendono valori da un sottoinsieme discreto di interi. Altri contengono dati che possono assumere qualsiasi valore reale. Di solito sono più facili da risolvere. I miglioramenti negli algoritmi, combinati con i progressi nella tecnologia informatica, hanno aumentato notevolmente le dimensioni e la complessità di un problema di ottimizzazione della programmazione lineare.
2. Ottimizzazione illimitata e limitata. Un' altra importante differenza sono le attività in cui non vi è alcun vincolo sulle variabili. Può variare ampiamente da semplici stimatori a sistemi di uguaglianze e disuguaglianze che modellano relazioni complesse tra i dati. Tali problemi di ottimizzazione possono essere ulteriormente classificati in base alla natura delle funzioni (lineari e non lineari, convessi e lisci, differenziabili e non differenziabili).
3. Compiti di fattibilità. Il loro obiettivo è trovare valori variabili che soddisfino i vincoli del modello senza alcun obiettivo di ottimizzazione specifico.
4. Compiti di complementarità. Sono ampiamente utilizzati in tecnologia ed economia. L'obiettivo è trovare una soluzione che soddisfi le condizioni di complementarità. In pratica, i compiti con più obiettivi sono spesso riformulati in obiettivi singoli.
5. Ottimizzazione deterministica vs ottimizzazione stocastica. L'ottimizzazione deterministica presuppone che i dati peri compiti sono completamente esatti. Tuttavia, su molti argomenti di attualità non possono essere conosciuti per una serie di motivi.
Il primo ha a che fare con un semplice errore di misurazione. Il secondo motivo è più fondamentale. Sta nel fatto che alcuni dati rappresentano informazioni sul futuro, ad esempio la domanda di un prodotto o il prezzo per un periodo di tempo futuro. Quando si esegue l'ottimizzazione in condizioni di ottimizzazione stocastica, l'incertezza è inclusa nel modello.
Componenti principali
La funzione obiettivo è quella da minimizzare o massimizzare. La maggior parte dei problemi di ottimizzazione ha una funzione obiettivo. In caso contrario, possono essere spesso riformulati per funzionare.
Due eccezioni a questa regola:
1. Attività di ricerca di destinazione. Nella maggior parte delle applicazioni aziendali, il manager desidera raggiungere un obiettivo specifico soddisfacendo i vincoli del modello. L'utente non desidera particolarmente ottimizzare qualcosa, quindi non ha senso definire una funzione obiettivo. Questo tipo è comunemente indicato come un problema di soddisfacibilità.
2. Molte caratteristiche oggettive. Spesso un utente vorrebbe ottimizzare diversi obiettivi contemporaneamente. Di solito sono incompatibili. Le variabili che ottimizzano per un obiettivo potrebbero non essere le migliori per gli altri.
Tipi di componenti:
- Un input controllato è un insieme di variabili decisionali che influenzano il valore di una funzione obiettivo. In un'attività di produzione, le variabili possono includere la distribuzione delle varie risorse disponibili o il lavoro richiestoogni azione.
- I vincoli sono relazioni tra variabili e parametri decisionali. Per un problema di produzione, non ha senso dedicare molto tempo a qualsiasi attività, quindi limita tutte le variabili "temporanee".
- Soluzioni possibili e ottimali. Il valore della decisione per le variabili, in base alla quale tutti i vincoli sono soddisfatti, è detto soddisfacibile. La maggior parte degli algoritmi prima lo trova, quindi cerca di migliorarlo. Infine, cambiano le variabili per passare da una soluzione fattibile all' altra. Questo processo viene ripetuto fino a quando la funzione obiettivo raggiunge il suo massimo o minimo. Questo risultato è chiamato la soluzione ottima.
Gli algoritmi dei problemi di ottimizzazione sviluppati per i seguenti programmi matematici sono ampiamente utilizzati:
- Convesso.
- Separabile.
- Quadrati.
- Geometrico.
Solutori lineari di Google
L'ottimizzazione lineare o programmazione è il nome dato al processo computazionale per la risoluzione ottimale di un problema. È modellato come un insieme di relazioni lineari che sorgono in molte discipline scientifiche e ingegneristiche.
Google offre tre modi per risolvere i problemi di ottimizzazione lineare:
- Libreria open source Glop.
- Componente aggiuntivo per l'ottimizzazione lineare per Fogli Google.
- Servizio di ottimizzazione lineare nello script di Google Apps.
Glop è integrato in Googlerisolutore lineare. È disponibile in open source. Puoi accedere a Glop tramite il wrapper del risolutore lineare OR-Tools, che è un wrapper per Glop.
Il modulo di ottimizzazione lineare per Fogli Google ti consente di eseguire una dichiarazione lineare del problema di ottimizzazione inserendo i dati in un foglio di lavoro.
Programmazione quadratica
La piattaforma Premium Solver utilizza una versione estesa LP/Quadratic del metodo Simplex con limiti di elaborazione dei problemi LP e QP fino a 2000 variabili decisionali.
SQP Risolutore per problemi su larga scala utilizza un'implementazione moderna del metodo degli insiemi attivi con scarsità per risolvere problemi di programmazione quadratica (QP). Il motore XPRESS Solver utilizza un'estensione naturale del metodo "Interior Point" o Newton Barrier per risolvere i problemi QP.
MOSEK Risolutore applica "Inside Point" incorporati e metodi auto-dual. Ciò è particolarmente efficace per problemi QP ad accoppiamento lento. Può anche risolvere i problemi relativi al vincolo quadratico di scala (QCP) e alla programmazione del cono del secondo ordine (SOCP).
Calcoli multi-operazione
Sono utilizzati con successo con l'uso delle funzionalità di Microsoft Office, ad esempio per risolvere problemi di ottimizzazione in Excel.
Nella tabella sopra, i simboli sono:
- K1 - K6 - clienti che devono fornire beni.
- S1 - S6 sono potenziali siti di produzione che potrebbero essere costruiti per questo. Può essere creato1, 2, 3, 4, 5 o tutte e 6 le posizioni.
Ci sono costi fissi per ogni struttura elencata nella colonna I (Correzione).
Se la posizione non cambia nulla, non conta. Quindi non ci saranno costi fissi.
Identifica potenziali posizioni per ottenere il costo più basso.
In queste condizioni, la posizione è stabilita o meno. Questi due stati sono: "TRUE - FALSE" o "1 - 0". Ci sono sei stati per sei posizioni, ad esempio, 000001 è impostato solo sul sesto, 111111 è impostato su tutti.
Nel sistema dei numeri binari, ci sono esattamente 63 diverse opzioni da 000001 (1) a 111111 (63).
L2-L64 dovrebbe ora leggere {=OPERAZIONI MULTIPLE (K1)}, questi sono i risultati di tutte le soluzioni alternative. Allora il valore minimo è=Min (L) e l' alternativa corrispondente è INDEX (K).
Programmazione di numeri interi CPLEX
A volte una relazione lineare non è sufficiente per arrivare al cuore di un problema aziendale. Ciò è particolarmente vero quando le decisioni implicano scelte discrete, ad esempio se aprire o meno un magazzino in una determinata posizione. In queste situazioni, è necessario utilizzare la programmazione intera.
Se il problema riguarda scelte sia discrete che continue, è un programma intero misto. Può avere problemi quadratici lineari, convessi e gli stessi vincoli del secondo ordine.
I programmi interi sono molto più complessi dei programmi lineari, ma hanno importanti applicazioni aziendali. SoftwareIl software CPLEX utilizza metodi matematici complessi per risolvere problemi con numeri interi. I suoi metodi implicano la ricerca sistematica di possibili combinazioni di variabili discrete utilizzando rilassamenti software lineari o quadratici per calcolare i limiti sul valore della soluzione ottima.
Usano anche LP e altri metodi di risoluzione dei problemi di ottimizzazione per calcolare i vincoli.
Solutore Microsoft Excel standard
Questa tecnologia utilizza l'implementazione di base del metodo Simplex principale per risolvere i problemi di LP. È limitato a 200 variabili. "Premium Solver" utilizza un metodo simplex primario migliorato con limiti a doppia faccia per le variabili. La piattaforma Premium Solver utilizza una versione estesa di LP/Quadratic Simplex Solver per risolvere un problema di ottimizzazione con un massimo di 2000 variabili decisionali.
L'LP su larga scala per la piattaforma Premium Solver applica un'implementazione all'avanguardia del metodo simplex e double simplex, che utilizza la scarsità nel modello LP per risparmiare tempo e memoria, strategie avanzate per l'aggiornamento e matrici di refactoring, pricing e rotazioni multiple e parziali e per il superamento della degenerazione. Questo motore è disponibile in tre versioni (capace di gestire fino a 8.000, 32.000 o variabili e limiti illimitati).
MOSEK Solver include primary e dual simplex, un metodo che sfrutta anche la scarsità e utilizza strategie avanzate per l'aggiornamento e la "rifattorizzazione" delle matrici. Risolve problemi di dimensioni illimitate, eratestato su problemi di programmazione lineare con milioni di variabili decisionali.
Esempio passo dopo passo in EXCEL
Per definire il modello del problema di ottimizzazione in Excel, attenersi alla seguente procedura:
- Organizza i dati per il problema in un foglio di calcolo in una forma logica.
- Seleziona una cella in cui memorizzare ogni variabile.
- Crea nella cella una formula per calcolare il modello matematico target del problema di ottimizzazione.
- Crea formule per calcolare il lato sinistro di ogni vincolo.
- Utilizzare le finestre di dialogo in Excel per informare il Risolutore di variabili decisionali, obiettivi, vincoli e limiti desiderati su tali parametri.
- Esegui "Risolutore" per trovare la soluzione ottimale.
- Crea un foglio Excel.
- Organizzare i dati per il problema in Excel dove viene calcolata la formula per la funzione obiettivo e il vincolo.
Nella tabella sopra, le celle B4, C4, D4 ed E4 sono state riservate per rappresentare le variabili decisionali X 1, X 2, X 3 e X 4. Esempi di decisione:
- Il modello del mix di prodotti ($ 450, $ 1150, $ 800 e $ 400 di profitto per prodotto) è stato inserito rispettivamente nelle celle B5, C5, D5 ed E5. Ciò consente di calcolare il target in F5=B5B4 + C5C4 + D5D4 + E5E4 o F5:=SUMPRODUCT (B5: E5, B4: E4).
- In B8 inserisci la quantità di risorse necessarie per fabbricare ogni tipo di prodotto.
- Formula per F8:=SOMMAPRODOTTO(B8:E8, $B$4:$E$4).
- Copia questoformula in F9. I segni del dollaro in $B$4:$E$4 indicano che questo intervallo di celle rimane costante.
- In G8 inserisci la quantità disponibile di risorse di ogni tipo, corrispondente ai valori delle restrizioni a destra. Questo ti permette di esprimerli in questo modo: F11<=G8: G11.
- Questo equivale a quattro limiti F8<=G8, F9 <=G9, F10 <=G10 e F11=0
Campi di applicazione pratica del metodo
L'ottimizzazione lineare ha molte applicazioni pratiche come esempio di un problema di ottimizzazione:
Un'azienda può realizzare diversi prodotti con un margine di contribuzione noto. La produzione di un'unità di ogni articolo richiede una quantità nota di risorse limitate. Il compito è creare un programma di produzione per determinare la quantità di ciascun prodotto da produrre in modo da massimizzare il profitto dell'azienda senza violare i vincoli di risorse.
I problemi di miscelazione sono la soluzione ai problemi di ottimizzazione relativi alla combinazione degli ingredienti nel prodotto finale. Un esempio di ciò è il problema della dieta studiato da George Danzica nel 1947. Vengono fornite numerose materie prime, come avena, carne di maiale e olio di girasole, insieme al loro contenuto nutrizionale, come proteine, grassi, vitamina A e il loro prezzo per chilogrammo. La sfida è miscelare uno o più prodotti finali di materie prime al minor costo possibile rispettando i limiti minimo e massimo del loro valore nutritivo.
Un'applicazione classica di un problema di ottimizzazione lineare consiste nel determinare l'instradamento in base alle esigenzetraffico nelle reti di telecomunicazioni o di trasporto. Allo stesso tempo, i flussi devono essere instradati attraverso la rete in modo tale da soddisfare tutti i requisiti di traffico senza violare le condizioni di larghezza di banda.
Nella teoria matematica, l'ottimizzazione lineare può essere utilizzata per calcolare strategie ottimali in giochi a somma zero per due persone. In questo caso viene calcolata la distribuzione di probabilità per ogni partecipante, che è il coefficiente di mescolamento casuale delle sue strategie.
Nessun processo aziendale di successo al mondo è possibile senza l'ottimizzazione. Sono disponibili molti algoritmi di ottimizzazione. Alcuni metodi sono adatti solo per determinati tipi di problemi. È importante essere in grado di riconoscere le loro caratteristiche e selezionare il metodo di soluzione appropriato.
