LA PROGRAMMAZIONE LINEARE

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 (X^a ).

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 <= si somma una var di scarto.

Dopodichè si completa la tabella e per giungere alla soluzione ammissibile di base.

Xk = variabili dei vincoli con coeff +1

a_k = i coeff che le var della colonna Xk hanno nella f. obiettivo

Ak = termini noti corrispondenti a Xk che si trovano nell'espressione del vincolo con quella Xk

Ci = i coeff che le var della prima riga hanno nella f. obiettivo.

Z = 6X₁ + 5X₂ +X₃   (funzione obiettivo)

Yi = ak*xi + ak*xi +

Una volta completata, se nell'ultima riga ci sono valori negativi, bisogna continuare costruendo un'altra tabella, considerando, sempre nell'ultima riga, il valore assoluto più grande (6), quindi considerate i valori positivi di quella colonna (in questo caso solo 2). Ora fate i rapporti Ak/Xi (12/2)  e prendete quello che dà il quoziente maggiore (quello è il pivot) che si troverà all'intersezione fra una delle X (X1) - cioè la variabile entrante nella nuova tabella - e X4 cioè la variabile uscente al cui posto metteremo l'entrante. Detto questo la tabella si completa con lo stesso procedimento della prima, finché nell'ultima riga sono presenti solo valori positivi e/o uguali a 0.

P.S. Nonostante qualche omissione, con questi appunti ci ho fatto un buon compito in classe, spero che possa esservi utile!!