Se sei un ingegnere o uno studente di ingegneria, potresti sapere cosa significa ottimizzare.
Per ottenere il miglior risultato possibile, è importante trovare il modo migliore per fare le cose.
Nella programmazione lineare, puoi utilizzare una soluzione di base per trovare la soluzione migliore.
Ma cos'è una soluzione di base e perché è così importante che gli ingegneri ne siano a conoscenza? In questo articolo parlerò di cosa sono le soluzioni di base, perché sono importanti nell'ingegneria e come possono essere utilizzate per ottenere i migliori risultati in diverse situazioni.
Quindi allacciati le cinture e preparati a tuffarti nel mondo delle soluzioni di base, dove svelerò i misteri e ti mostrerò quanto può essere potente questa tecnica.
Soluzioni di base nella programmazione lineare
Definizione formale:
Una soluzione a un modello di programma lineare costituito da m equazioni in n variabili si ottiene risolvendo per m variabili in termini delle restanti (nm) variabili e ponendo le (nm) variabili uguali a zero.
Una soluzione di base nella programmazione lineare è un modo per risolvere un problema di programmazione lineare che soddisfa determinati requisiti tecnici.
In particolare, un vettore x è una soluzione base per un poliedro se i vettori {ai : xi = 0} sono linearmente indipendenti.
Ciò significa che le colonne di A che hanno variabili xi diverse da zero sono linearmente indipendenti.
Una soluzione di base con componenti non negative è chiamata soluzione di base ammissibile (BFS) (BFS).
Un BFS soddisfa tutte le regole che definiscono un poliedro.
Ogni BFS è un angolo del poliedro delle soluzioni ammissibili dal punto di vista geometrico.
Per trovare una soluzione di base, devi impostare nm variabili che non sono di base a zero e risolvere le m variabili che sono di base.
È possibile che basi diverse conducano alla stessa soluzione di base, il che significa che potrebbe esserci più di un modo per risolvere lo stesso problema.
Il metodo Simplex è un processo iterativo che si sposta da un BFS al successivo BFS finché non trova il miglior BFS.
Dopo aver utilizzato il metodo del simplesso per trovare un BFS, possiamo dire se la soluzione è la migliore vedendo se altri BFS nelle vicinanze danno un valore migliore per la funzione obiettivo.
Se non esiste un tale BFS, l'attuale BFS è il migliore.
Modello di programmazione lineare
Un modello di programmazione lineare coinvolge tre componenti principali: variabili decisionali, una funzione obiettivo e vincoli.
Sia la funzione obiettivo che i vincoli devono essere funzioni lineari e le variabili decisionali devono essere continue.
La funzione obiettivo viene utilizzata per aumentare o diminuire un numero che rappresenta il profitto, il costo, il numero di prodotti realizzati, ecc.
I vincoli sono limiti o restrizioni sulla quantità totale di una determinata risorsa necessaria per svolgere le attività che determineranno il livello di successo nelle variabili decisionali.
Inoltre, alcuni programmi lineari richiedono che tutte le variabili decisionali siano non negative.
Nei modelli di programmazione lineare è possibile utilizzare anche variabili intere e binarie.
Le variabili binarie possono avere solo un valore di 0 o 1, quindi possono avere solo un valore di 0 o 1.
Il metodo del simplesso
Uno dei modi più utilizzati per risolvere i problemi di programmazione lineare è il metodo Simplex.
Le soluzioni di base sono importanti nel metodo del simplesso perché corrispondono ai vertici della regione ammissibile e il metodo del simplesso si sposta da un angolo all'altro finché non viene trovata una soluzione ottima.
Il metodo del simplesso è un modo rapido per trovare la migliore risposta a un problema di programmazione lineare utilizzando le proprietà delle soluzioni di base.
Per utilizzare il metodo del simplesso per trovare il miglior BFS, dobbiamo trovare una base B per la matrice dei vincoli A e risolvere il sistema Ax = b con tutte le variabili diverse dalla base impostate a zero.
I valori risultanti per le variabili di base formano un BFS.
Se esiste una soluzione ottima, allora esiste un BFS ottimale.
Il metodo Simplex si sposta da un BFS a un BFS adiacente fino a raggiungere un BFS ottimale utilizzando le procedure pivot.
Confronto tra Soluzioni Base e Soluzioni Fattibili
La differenza tra una soluzione di base e una soluzione fattibile è che una soluzione di base non deve soddisfare alcuna condizione.
In particolare, deve avere vettori linearmente indipendenti e avere valori diversi da zero per xi, e x deve essere minore di 0.
D'altra parte, una soluzione ammissibile è qualsiasi punto che rientri nei limiti del problema.
Ma non tutte le soluzioni fattibili sono soluzioni fattibili di base.
Le soluzioni ammissibili di base (BFS) sono solo quelle che corrispondono agli angoli del poliedro delle soluzioni ammissibili.
Ritorno alle origini: sbloccare la potenza delle soluzioni di base nell'ingegneria
Ancora difficile da capire? Permettimi di cambiare un po' il punto di vista:
Sei stufo di usare metodi e algoritmi complicati per risolvere problemi difficili? Vorresti che ci fosse un modo più semplice e diretto per affrontare i problemi del tuo modello di programma lineare?
Bene, non preoccuparti, perché la risposta è qui: risolvi per m variabili in termini delle rimanenti (nm) variabili e imposta le (nm) variabili a zero.
Chi ha bisogno di algoritmi che suonino fantasiosi quando puoi tornare alle basi? Quindi metti via le calcolatrici e iniziamo a conoscere soluzioni semplici.
Ok, quello era solo uno scherzo fatto per sembrare uno spot televisivo.
Ora torniamo alla spiegazione.
Programmazione lineare della soluzione 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: | La soluzione di base può essere utilizzata nei problemi di allocazione delle risorse, in cui l'obiettivo è dividere risorse limitate tra esigenze concorrenti. Ad esempio, un'azienda potrebbe dover dividere il proprio budget tra diversi reparti o progetti. Utilizzando soluzioni di base, possono capire il modo migliore per utilizzare le proprie risorse per guadagnare di più o spendere il meno possibile. |
| Pianificazione per la produzione: | Nella pianificazione della produzione, la soluzione di base può essere utilizzata per capire il miglior mix di prodotti da realizzare per guadagnare di più. Le aziende possono trovare il miglior mix di produzione che porta più soldi e costa meno utilizzando la soluzione di base. |
| Programmazione: | La soluzione di base può essere utilizzata per capire come pianificare attività o lavori in modo che possano essere eseguiti nel modo più efficiente. Ad esempio, un'azienda potrebbe dover pianificare l'orario di lavoro dei propri dipendenti per assicurarsi che abbiano abbastanza lavoratori quando l'attività è occupata. Utilizzando una soluzione di base, possono trovare il modo migliore per programmare le cose in modo da ridurre al minimo i tempi di inattività e svolgere quanto più lavoro possibile. |
| Gestione della filiera: | Nella gestione della catena di approvvigionamento, l'obiettivo è assicurarsi che beni e servizi si muovano nel modo più agevole possibile dal fornitore al cliente. Ad esempio, un'azienda potrebbe aver bisogno di capire i percorsi migliori per il trasporto delle merci in modo che i costi siano ridotti al minimo e le merci vengano consegnate in tempo. Utilizzando soluzioni di base, possono trovare il miglior piano per la gestione della catena di approvvigionamento che mantenga bassi i costi e soddisfi i clienti. |
| Ottimizzazione del portafoglio: | Nell'ottimizzazione del portafoglio, dove l'obiettivo è trovare il miglior mix di investimenti per guadagnare di più correndo il minimo rischio, è possibile utilizzare soluzioni di base. Ad esempio, un'impresa di investimento potrebbe aver bisogno di trovare il miglior mix di azioni, obbligazioni e altri titoli per aiutare i propri clienti a raggiungere i propri obiettivi di investimento. Utilizzando una soluzione semplice, possono trovare il modo migliore per mescolare i loro portafogli in modo da ottenere i migliori rendimenti assumendosi il minimo rischio. |
Conclusione
In conclusione, l'idea di una soluzione di base è molto importante nel campo dell'ingegneria e può essere utilizzata in molti modi diversi.
Sapendo cos'è una soluzione di base e cosa fa nella programmazione lineare, possiamo migliorare le soluzioni, ridurre i costi e renderle più efficienti.
Ma è importante ricordare che la soluzione di base non è una soluzione valida per tutti, anche se è uno strumento potente.
Per ottenere i migliori risultati, ogni problema deve essere attentamente esaminato e pensato.
Come ingegneri, dobbiamo continuare a esaminare come le soluzioni di base e altre tecniche di ottimizzazione possono aiutarci a fare progressi e a trovare nuove idee.
Quindi, riconosciamo il potere delle soluzioni semplici e continuiamo a spingere i limiti di ciò che è possibile utilizzando nuove tecniche e strategie.
Link e riferimenti
Libri:
- Programmazione lineare di Vasek Chvatal
- Modellazione e risoluzione della programmazione lineare con R di Jose M. Sallan
Condividere su…
