Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

Tableaux duali a coefficienti interi per problemi di programmazione lineare

In questo elaborato mi sono concentrato sullo studio della trasformazione lineare che è alla base del più conosciuto algoritmo per la risoluzione dei problemi di programmazione lineare: l'algoritmo del simplesso. Ho cercato di rappresentare dettagliatamente il più vasto numero di casi possibili, pervenendo ad una rappresentazione congiunta dei diversi problemi che fosse il più generale possibile e che esibisca, in ogni fase dell'algoritmo, le corrispondenti matrici tableaux dei due problemi.
Durante la stesura della tesi ho anche proposto una procedura alternativa per l'esecuzione di tali trasformazioni che consente di rappresentare congiuntamente e con coefficienti interi i due problemi. I tableaux interi consentono di facilitare i calcoli quando questi vengono fatti a mano, inoltre, in tali circostanze, facilitano l'individuazione di eventuali errori commessi.

Mostra/Nascondi contenuto.
Introduzione Durante il mio percorso accademico, la mia immaginazione Ł stata positivamente stimolata dal concetto di dualit , associato ai problemi di programmazione lineare, introdotto durante il corso di ricerca operativa. In generale, un problema di pro- grammazione lineare Ł composto da una funzione lineare, da ottimizzare, e da un numero nito di vincoli, disequazioni ed equazioni, sui quali ricercare una soluzione ottima, quandoesiste. Perlarisoluzione, ogniproblemavienetrasformatoinunpro- blema equivalente la cui regione ammisibile Ł formata esclusivamente da equazioni e da vincoli di non negativit su tutte le variabili. In questo modo Ł possibile rap- presentare ciascun problema mediante apposite matrici, dette matrici tableaux, che esibiscono, ciascuna, una distinta soluzione ed il relativo valore assunto dalla cor- rispondente funzione obiettivo; Ł possibile inoltre trasformare ogni matrice tableau, in altre che esibiscono problemi equivalenti e che esplicitano delle soluzioni distinte, per il problema di partenza. Ad ogni problema di programmazione lineare si associa un altro problema, detto duale, che sebbene non sembri avere molto in comune con il primo, Ł in realt in strettarelazioneconesso. Incuriositodalfattochelasoluzioneottimadiunproblema di programmazione lineare Ł strettamente legata alla soluzione ottima del corrispon- dente problema duale ho iniziato a vericare se tale relazione potesse essere estesa ai punti che, ad ogni stadio dell algoritmo utilizzato per la risoluzione di un problema, 3

Tesi di Laurea

Facoltà: Economia

Autore: Enrico Rossi Contatta »

Composta da 154 pagine.

 

Questa tesi ha raggiunto 14 click dal 21/11/2017.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.