La programmazione lineare e il metodo del simplesso

Materie:Appunti
Categoria:Matematica
Download:630
Data:05.06.2007
Numero di pagine:2
Formato di file:.doc (Microsoft Word)
Download   Anteprima
programmazione-lineare-metodo-simplesso_1.zip (Dimensione: 6.11 Kb)
readme.txt     59 Bytes
trucheck.it_la-programmazione-lineare-e-il-metodo-del-simplesso.doc     37 Kb


Testo

LA PROGRAMMAZIONE LINEARE
La P.L. è una parte della ricerca operativa (una disciplina scientifica che cerca di risolvere problemi economici). Si ha un programma lineare quando il modello matematico (descrizione della realtà attraverso strumenti grafici, matematici, informatici, geometrici…) da studiare ha le seguenti caratteristiche:
• Una funzione lineare (con tutte le variabili di 1°) di n variabili da rendere max o min (funzione economica);
• Un sistema di vincoli espressi da equazioni o disequazioni lineari;
• Un sistema di vincoli di segno (le variabili devono essere positive o = 0, essendo grandezze economiche).

Oggetto della P.L. è l’ottimizzazione di variabili (spesa, impiego di risorse umane, guadagno, trasporto…) in funzione di altre grandezze, dette variabili d’azione, soggette a determinati vincoli.
La dipendenza delle variabili da ottimizzare dalle variabili d’azione è descritta dalla funzione obiettivo, della quale bisogna determinare il max o il min assoluto e i valori delle variabili d’azione per cui tale max o min viene raggiunto).
I problemi di P.L. in due variabili si risolvono col metodo grafico, visualizzando i vincoli sul piano cartesiano. Il metodo generale di risoluzione di un problema di P.L. è il metodo del simplesso, che partendo da una soluzione del sistema dei vincoli, con diversi passaggi iterativi permette di arrivare alla soluzione ottima.

L’ALGORITMO DEL SIMPLESSO
È un metodo per risolvere i problemi di P.L. Si vuole massimizzare o minimizzare una funzione lineare con dei vincoli, anch’essi lineari, che possono assumere valori positivi.
L’algoritmo viene formulato su problemi posti nella forma standard (cioè dove si deve massimizzare una funzione lineare soggetta a vincoli di uguaglianza); se sono presenti disuguaglianze, per >= si sottrae una var di scarto e viceversa.
Per trasformare il sistema in forma canonica (in ogni uguaglianza ci deve essere un coefficiente +1 che non è presente nelle altre uguaglianze), si aggiungono le var artificiali (Xa ).
Per passare direttamente alla forma canonica:
se = si aggiunge una var artificiale,
se >= si sottrae una var di scarto e si aggiunce una var artificiale,
se

Esempio