Algoritmi per la programmazione lineare e la loro complessità

La tesi si pone l’obbiettivo di studiare tre diversi algoritmi per la programmazione lineare facendo attenzione alla loro complessità, intesa come tempo di calcolo dell’algoritmo, ovvero il numero di operazioni elementari eseguite in funzione della grandezza dell’istanza. Il primo metodo analizzato é quello del simplesso, il quale, pur non essendo polinomiale, si distingue per la sua elevata efficienza pratica. Vengono a questo scopo illustrate alcune regole di pivot e il famoso controesempio di Klee e Minty. Successivamente si tratta il metodo dell’ellissoide che, al contrario, riveste un ruolo fondamentale nella teoria della complessità ma non risulta efficace da un punto di vista pratico. Si conclude con i metodi di punto interno, i quali offrono un nuovo approccio di risoluzione al problema e garantiscono un buon compromesso tra solidità teorica e buone prestazioni pratiche. Vengono trattati due metodi: il metodo affine scaling e il metodo a barriera.