Sai cosa significa ottimizzare un sistema per ottenere il miglior risultato possibile se sei uno studente di ingegneria o un ingegnere.
L'ottimizzazione di una soluzione è la chiave del successo in tutto, dalla costruzione di ponti alla realizzazione di software.
L'idea di una soluzione fattibile di base arriva a questo punto.
È un'idea di base nella programmazione lineare che ti consente di capire quale di un insieme di possibili soluzioni è la migliore.
Ma perché è così importante? In questo articolo parlerò delle soluzioni fattibili di base e di come possono essere utilizzate per risolvere problemi di ingegneria nel mondo reale.
Parlerò di come trovarli, di cosa sono fatti e perché sono importanti.
Quindi, che tu sia un ingegnere esperto o uno studente appena agli inizi, vieni con noi mentre mi tuffo nel mondo delle soluzioni fattibili di base e ti mostro come utilizzare la potenza della programmazione lineare.
Comprensione della soluzione fattibile di base
Definizione formale:
Una soluzione di base per un modello di programma lineare in cui tutte le variabili sono non negative.
Una soluzione fattibile di base (BFS) è un'idea chiave nella programmazione lineare che aiuta a trovare le soluzioni migliori.
Un BFS è una soluzione con il minor numero possibile di variabili diverse da zero.
È un angolo del poliedro delle soluzioni ammissibili.
In altre parole, un BFS è una soluzione di base che soddisfa i vincoli non negativi e si trova nella regione fattibile o nell'area problematica.
Trovare una soluzione ottimale di base fattibile
Per trovare il miglior BFS, dobbiamo fare quanto segue:
- Scrivi il programma in forma standard per una sequenza lineare.
- Trasforma il sistema di disuguaglianze in una matrice aumentata.
- Scopri quali variabili sono fondamentali e quali no.
- Scopri quali sono le variabili di base in termini di altre variabili.
- Metti queste espressioni nella funzione obiettivo per ottenere una funzione delle sole variabili che non sono di base.
- Trova una variabile non di base che può essere aumentata senza rompere alcun vincolo e che migliorerà la funzione obiettivo.
Questa variabile è ora una variabile di base e una delle altre variabili di base non è più una variabile di base.
Se esiste una soluzione ottima, deve trovarsi in una delle estremità, o vertici, della regione in cui sono possibili soluzioni.
Quindi, se un PL ha una soluzione ottima, ha una soluzione ottima in un punto estremo dell'insieme ammissibile.
Inoltre, esiste sempre un BFS ottimale se esiste una soluzione ottimale.
Utilizzo del metodo Simplex per trovare un BFS ottimale
Il Simplex Method è un algoritmo per la risoluzione di problemi nella programmazione lineare.
Si sposta da un BFS a un BFS "adiacente" utilizzando la procedura pivot.
Nella procedura pivot, una variabile non di base viene scelta per diventare una variabile di base, quindi l'attuale BFS viene utilizzato per risolvere le nuove variabili di base.
Quando nessuna variabile non di base può essere modificata per migliorare la funzione obiettivo, l'algoritmo è terminato.
Perché le soluzioni fattibili di base sono fondamentali per risolvere problemi di ingegneria complessi
Ancora difficile da capire? Permettimi di cambiare un po' il punto di vista:
Chi ha bisogno comunque di risposte semplici e praticabili? Basta mettere tutto insieme e sperare per il meglio.
Dopotutto, chi ha bisogno di ottimizzazione quando il caos è molto più divertente? Benvenuti nel mondo delle variabili non negative, dove tutto è solo un suggerimento e il fallimento è quasi certo.
O è?
Esploriamo perché il concetto apparentemente basilare di soluzioni fattibili di base è tutt'altro che basilare e perché potrebbero essere la chiave per risolvere anche i problemi ingegneristici più complessi.
Ok, quello era solo uno scherzo fatto per sembrare uno spot televisivo.
Ora torniamo alla spiegazione.
Trovare la soluzione ammissibile di base
Una soluzione ammissibile di base (BFS) è una soluzione a un problema di ottimizzazione lineare che soddisfa tutti i vincoli e ha il minor numero di variabili diverse da zero.
Ogni BFS è un angolo del poliedro delle soluzioni ammissibili dal punto di vista geometrico.
Se esiste una soluzione migliore, deve esserci anche un primo passo migliore.
In questo articolo parleremo di come trovare una soluzione ammissibile di base iniziale, come trovare tutte le soluzioni ammissibili di base e come trovare una soluzione ammissibile di base senza variabili di margine.
Trovare una soluzione fattibile di base iniziale
Possiamo utilizzare diversi metodi, a seconda di come è impostato il problema, per trovare una soluzione di base iniziale che funzioni per un problema di ottimizzazione lineare.
Un modo consiste nell'aggiungere variabili di scarto ai vincoli sulle disuguaglianze e impostare tutte le altre variabili su zero.
Le variabili slack diventano le variabili di base e il resto sono variabili non di base.
Il metodo Simplex a due fasi è un altro modo per risolvere il problema.
Questo metodo prevede la risoluzione di un problema di programmazione extra lineare per trovare una soluzione di base iniziale che sia fattibile.
Una volta trovata una soluzione ammissibile di base iniziale, il Metodo del Simplesso può essere utilizzato per passare da una soluzione ammissibile di base alla successiva e quindi alla soluzione migliore.
Trovare tutte le soluzioni fattibili di base
Ci può essere più di una soluzione di base che funziona per un programma lineare.
Possiamo cambiare il sistema aggiungendo variabili di slack e quindi utilizzare il nuovo sistema per trovare tutte le soluzioni ammissibili di base per un programma lineare.
Quindi, queste soluzioni ammissibili di base vengono utilizzate per trovare le soluzioni ammissibili di base per il problema originale.
Trovare una soluzione ammissibile di base senza variabili allentate
Abbiamo bisogno di utilizzare le variabili slack per eliminare i vincoli inferiori a in modo da poter trovare una soluzione di base che funzioni senza variabili slack.
Una variabile slack è solo la differenza tra il lato destro di un vincolo e il lato sinistro.
Ad esempio, per il primo vincolo, definiamo una variabile di slack x4 = 14 - 2x1 - x2 - x3. In termini di questa nuova variabile, il primo vincolo equivale semplicemente a x4 ≥ 0, che è un vincolo di positività per x4.
Quando aggiungiamo queste variabili slack, otteniamo un programma lineare uguale a quello originale, tranne per il fatto che tutti i vincoli sono o equazioni o vincoli che dicono che qualcosa è positivo.
L'insieme delle variabili di base, che hanno valori diversi da zero nella soluzione di base, è chiamato base.
Le variabili che hanno un valore pari a zero nella soluzione di base non sono variabili di base.
Per trovare la soluzione migliore, dobbiamo trovare un vettore x che soddisfi tutte le regole e ottenga il valore più grande o più piccolo per l'obiettivo.
Ma trovare la soluzione migliore richiede più passaggi rispetto alla semplice ricerca di una soluzione che funzioni e non abbia variabili allentate.
Non è sempre possibile trovare una soluzione di base senza variabili slack, specialmente per problemi con vincoli inferiori a.
Per trovare una soluzione ammissibile di base, è necessario utilizzare il metodo del simplesso o un altro algoritmo di programmazione lineare per cercare una soluzione che soddisfi tutti i vincoli e abbia il minor numero di variabili diverse da zero.
Proprietà e significato della soluzione ammissibile di base
Proprietà della soluzione ammissibile di base
Una soluzione ammissibile di base ha al massimo m variabili diverse da zero e almeno nm variabili pari a zero, dove n è il numero di variabili decisionali e m è il numero di vincoli.
Un BFS è un angolo del poliedro delle possibili soluzioni, e ogni BFS ha n vincoli attivi linearmente indipendenti.
Se esiste una soluzione migliore, deve esserci anche un primo passo migliore.
La cosa più importante delle soluzioni ammissibili di base è che sono le estremità dell'insieme delle soluzioni convesse per un problema di programmazione lineare.
Per trovare la risposta migliore, l'algoritmo del simplesso passa attraverso una serie di BFS.
L'algoritmo Simplex ricerca tutte le possibili soluzioni di base in modo organizzato per trovare la migliore.
Significato della soluzione ammissibile di base
Trovare una soluzione di base possibile è importante perché aiuta a trovare la migliore risposta ai problemi di programmazione lineare.
Fornisce inoltre ad algoritmi complessi un punto di partenza e può essere utilizzato per capire se un programma lineare è possibile o meno.
Per trovare tutte le soluzioni ammissibili di base per un programma lineare, è possibile modificare il sistema aggiungendo variabili di margine e quindi utilizzare il sistema modificato per trovare tutte le soluzioni ammissibili di base.
Quindi, queste soluzioni ammissibili di base vengono utilizzate per trovare le soluzioni ammissibili di base per il problema originale.
Video: soluzioni fattibili di base
Suggerimento: attiva il pulsante dei sottotitoli se ne hai bisogno. Scegli "traduzione automatica" nel pulsante delle impostazioni, se non hai familiarità con la lingua parlata. Potrebbe essere necessario fare clic sulla lingua del video prima che la tua lingua preferita diventi disponibile per la traduzione.
Casi d'uso
| Usato in: | Descrizione: |
|---|---|
| Allocazione di risorse: | BFS può essere utilizzato per dividere risorse limitate tra diversi progetti in modo da ottenere il massimo con il minimo. Questo metodo può essere utilizzato in molti campi diversi, come i trasporti, l'agricoltura e la finanza. |
| Ottimizzazione della rete: | BFS può essere utilizzato per far funzionare meglio le reti di comunicazione, trasporto e logistica. BFS può aiutare a trovare i percorsi migliori per beni e servizi, ridurre il tempo e il denaro spesi per il trasporto e velocizzare ed effettuare consegne più accurate. |
| Pianificazione per la produzione: | BFS può essere utilizzato per pianificare la produzione in modo che risorse come manodopera, materie prime e attrezzature vengano utilizzate nel miglior modo possibile per ottenere il massimo da esse. BFS può aiutare a ridurre i costi di produzione, ridurre gli sprechi e migliorare l'efficienza. |
| Progetto finanziario: | Nella pianificazione finanziaria, BFS può essere utilizzato per ottimizzare i portafogli di investimento, ridurre i rischi e recuperare la maggior parte dei soldi. BFS può aiutare a trovare il modo migliore per dividere le risorse, ridurre i costi di transazione e guadagnare di più. |
| Gestione della filiera: | BFS può essere utilizzato per migliorare il flusso di beni e servizi dai fornitori ai clienti come parte della gestione della supply chain. BFS può aiutare a capire la migliore quantità di stock da tenere a portata di mano, abbreviare i tempi di consegna e migliorare il servizio clienti. |
Conclusione
Mentre questo sguardo alle soluzioni fattibili di base volge al termine, è chiaro che sono uno strumento importante per qualsiasi ingegnere o studente di ingegneria.
Dall'individuare il modo migliore per costruire un sistema complicato allo sfruttare al massimo le risorse disponibili, le soluzioni fattibili di base forniscono un quadro per ottenere il miglior risultato possibile.
Ma più che essere utili, mostrano quanto possa essere elegante e bella la matematica.
È incredibile che tu possa ridurre problemi complicati a un semplice insieme di equazioni e quindi utilizzare quelle equazioni per risolvere problemi nel mondo reale.
È un buon promemoria del fatto che l'ingegneria consiste nel risolvere problemi e che, utilizzando il potere della matematica, possiamo trovare risposte che una volta erano ritenute impossibili.
Quindi, mentre impari di più sull'ingegneria, tieni a mente ciò che hai imparato sulle soluzioni semplici che funzionano e usale per rendere il mondo un posto migliore e più efficiente.
Link e riferimenti
Libri:
- Programmazione lineare: fondamenti ed estensioni
- Programmazione lineare: teoria e applicazioni
Condividere su…
