Tableaux duali a coefficienti interi per problemi di programmazione lineare

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