Presentazione del Corso in Programmazione Lineare

aims of the course (in order of priority):

• 1. Introduce and motivate the Linear Programming Problem (LP);
• 2. Describe and analyze the Simplex Method to solve LP;
• 3. Introduce and study Duality Theory in LP;
• 4. Develop the geometric point of view;
• 5. Moving the first steps from LP to Combinatorial Optimization;
• 6. See the complementary slackness conditions put in action.

obiettivi del corso (in ordine di priorità:

• 1. Introdurre e motivare il problema della programmazione lineare (PL);
• 2. Descrivere ed analizzare il metodo del simplesso per la PL;
• 3. Introdurre e studiare la teoria della dualit\`a per la PL;
• 4. Sviluppare la visione geometrica della PL;
• 5. Muovere i primi passi dalla PL all'ottimizzazione cominatoria;
• 6. Venire a conoscere le condizioni degli scarti complementari ed il loro utilizzo.

program:

• 1. Introduction: Polly's diet problem;
• 2. Equivalent Formulations;
• 3. How the Simplex Method Works;
• 4. Pitfalls and How to Avoid Them;
• 5. Duality: motivations and theory;
• 6. The Geometric Interpretation;
• 7. Sensitivity Analysis and Economics Interpretation; (optional)
• 8. Applications;
• 9. Efficiency: how fast is the simplex method? (optional)
• 10. An Account to Other Methods and Their Peculiarities.

programma:

• 1. Introduzione: Polly deve mettersi a dieta;
• 2. Formulazioni Equivalenti;
• 3. Come funziona il Metodo del Simplesso;
• 4. Problemi con il Metodo: come evitarli;
• 5. Dualità: motivazioni e teoria;
• 6. Interpretazione Geometrica;
• 7. Analisi di Sensitivit\`a ed Interpretazione Economica; (opzionale);
• 8. Applicazioni;
• 9. Efficienza: tempi di calcolo per il metodo del simplesso; (opzionale);
• 10. Accenni ad altri metodi e rispettive peculiarità.

Reference Books:

• V. Chvátal, Linear Programming, Freeman, New-York (1983)

• Robert J. Vanderbei, Linear Programming: Foundations and Extensions, Kluwer Academic Publishers (2001)

  The www site of the book is full of useful material and also offers an online consultable updated version of the book.

Testi di Riferimento (Reference Books):

• V. Chvátal, Linear Programming, Freeman, New-York (1983)

• Robert J. Vanderbei, Linear Programming: Foundations and Extensions, Kluwer Academic Publishers (2001)

  Il sito www del libro è ricco di materiale utile ed offre una versione aggiornata e consultabile online.

Period:

• 6 weeks with the following weekly timetable:
  • theory: 1 meeting [2 hours each]
  • practice: 1 meeting [2 hours each]
• otherwise we can compress to 4 weeks with the following weekly timetable:
  • theory: 2 meetings [1:30 hours each]
  • practice: 1 meeting [3:00 hours each]

Periodo:

• 6 settimane secondo il seguente orario:
  • teoria: 1 incontro [2 ore ciascuno]
  • pratica: 1 incontro [2 ore ciascuno]
• altrimenti possiamo comprimere a 4 settimane con il seguente orario:
  • teoria: 2 incontri [1:30 ciascuno]
  • pratica: 1 incontro [3 ore ciascuno]

Language: I will first speak in English, then repeat in Italian. Then pupils can either correct my mistakes or translate into a further language. This is to say that everybody is welcome.

Lingua: Farò ogni sforzo affinch\`e quello della lingua non risulti essere un problema per nessuno.

Prerequisites: Curiosity.

Exam: The course gives 3 credits. If you are interested in these credits, then you must do the proposed homeworks and pass a final written exam.

Esame: Il corso dà 3 crediti. Se sei interessato in questi crediti allora devi svolgere i compiti suggeriti per casa e superare un esame scritto finale.

The Course Program is available also as .ps file or you can ask for it in the secretary offices.

Il Programma del Corso é disponibile anche in forma di .ps file o in segreteria.

created:   30 Ottobre 2001 updated:   26 Novembre 2001

© Dipartimento di Matematica University of Verona