Elaborato di Teoria dello
Sviluppo dei Processi Chimici
Algoritmo del simplesso
Studenti:
Amabile Roberto 564/18
Donatantonio Riccardo 564/19
Farace Antonio 564/28
Perfetto Alfonso 564/45
Docente:
Prof. Michele Miccio
Struttura del lavoro
Il lavoro si compone delle seguenti fasi:
1. Realizzazione di un software in ambiente
LabView 7.0™
2. Approfondimento di argomenti trattati
durante il corso inerenti la programmazione
lineare
3. Svolgimento di problemi di programmazione
lineare risolti mediante l’algoritmo del
simplesso al fine di verificare il corretto
funzionamento del SimpLab 1.0
Problema generale
La semplicità nel calcolo della soluzione di base per il
caso di tutti vincoli ≤ è legata alla presenza di un
minore unitario dei coefficienti delle variabili aggiunte.
Es.
2 x1  5 x2  6 x3  x4
x1  2 x2  x3
8
 x5  5
Minore unitario
Nel caso generale la presenza di questo minore
unitario dei coefficienti non è garantita e in verità
quasi mai verificata.
Variabili artificiali
Vista la facilità di calcolo della b.a. nel caso in cui vi sia
un minore unitario dei coefficienti si è arrivati all’idea di
costruire quest’ultimo, nel caso generale, mediante
l’aggiunta di altre variabili dette variabili artificiali.
Es.
Forma canonica
2 x1  5 x2  6 x3  8
2 x1  5 x2  6 x3
slack
 x4
8
x1  2 x2  x3  5
x1  2 x2  x3
5
3 x1  2 x2  4 x3  9
3x1  2 x2  4 x3  x6
9
surplus
2 x1  5 x2  6 x3
 x4
x1  2 x2  x3
3x1  2 x2  4 x3  x6
 x5
8
5
 x7  9
artificiali
Minore unitario
Problema artificiale
L’aggiunta delle variabili artificiali ovviamente non è
cosa “lecita”; questo infatti trasforma il nostro
problema in un nuovo problema che ha delle variabili
in più rispetto a quello di partenza.
Di contro però va detto che di questo nuovo problema
noi riusciamo a conoscere banalmente la prima
soluzione di base ammissibile, come fatto per il caso di
vincoli tutti di tipo ≤, e per questo definendo
opportunamente una nuova funzione obiettivo
potremmo riuscire ad arrivare alla soluzione b.a. del
problema originario ottimizzando questo nuovo
obiettivo.
La nuova funzione obiettivo che si definisce prende il
nome di Forma d’Inammissibilità.
Forma d’Inammissibilità
La Forma d’Inammissibilità è definita come:
a
w   X n j
j 1
n=numero di variabili del problema originario
a=numero di variabili artificiali
Xn+j=variabili artificiali
Questa funzione va minimizzata tenendo in conto che:
•Se min w=0: l’n-pla X0 in cui la w è minima è una soluzione
basica ammissibile per la funzione obiettivo del problema
originario. Questo perchè si possono escludere tutte le
variabili artificiali poiché la loro somma è nulla
•Se min w>0: non esiste una soluzione basica ammissibile
per il problema originario
Il Tableau
La procedura di calcolo che porta alla determinazione del
valore di ottimo della funzione obiettivo si basa su un
processo iterativo che parte con la costruzione di una
matrice detta Tableau e di volta in volta continua con
l’aggiornamento di quest’ultima fino al raggiungimento
della soluzione ottima.
La costruzione del Tableau parte dal problema in
forma canonica con l’aggiunta di variabili artificiali.
Riassumendo, quindi, in base al tipo di vincolo devo
aggiungere al problema delle variabili:
•Slack: per vincoli di tipo 
•Artificiali: per vincoli di tipo =
•Artificiali e Surplus: per vincoli di tipo 
Costruzione del Tableau
Il Tableau assume la forma:
Xa
Xb
Variabili surplus
Variabili decisionali
X1
X2
X3
Xn
a11
a21
a12
a22
a13
a23
a1n
a2n
Xn+1
1 0
0 1
Xn+j Xn+j+1
0
0
0 -1
0 0
1
0 0
0
1 0
b1
b2
Xq
am1
am2
am3
amn
0 0
(-z)
c1
c2
c3
cn
0 0
0
0
(-w) d1
d2
d3
dn
0 0
1
dj
Coefficienti di costo Matrice dei tassi di assorbimento
Minore unitario delle variabili slack
Coefficienti di costo modificati
più quelle artificiali
Variabili in base
bm
Risorse
Condizione di ottimalità
Resta ora da stabilire quando il ciclo del simplesso deve
arrestarsi, cioè come verificare il raggiungimento della
soluzione ottima.
A questo scopo notiamo che:
 ( z )
 cj
j  1;m 
X j
Con m = numero totale di variabili.
Da questo è evidente che, durante le iterazioni del
simplesso, nel caso in cui tutti i coefficienti di costo sono
positivi/negativi siamo in una condizione di
minimo/massimo della F.O.
La condizione di ottimo quindi sarà, per il problema a
minimizzare:
cj  0
j  1;m
Metodo delle due fasi
Rendere i termini noti
non negativi
Aggiungere variabili
slack

, =, 
Vincoli di
tipo
STOP:
soluzione
non limitata
Aggiungere
variabili slack e
artificiali
=
Scelta riga pivot r: br/ars=min bi/ais
Aggiungere variabili
artificiali
NO
SÌ
Tutti
gli
ais=0
Pivoting sul perno ars
Aggiungere forma di
inammissibilità
Scelta colonna
pivot s: cs=min cj
Scelta colonna pivot s: ds=min dj
START
fase 2
NO
START
fase 1
Tutti i
dj0
SÌ
NO
Tutti i
cj0
SÌ
SÌ
w=0
NO
STOP: nessuna soluzione
ammissibile
Eliminare colonne
con dj >0. Eliminare la
forma di
inammissibilità
cj>
0
NO
STOP: soluzione
basica
ammissibile
minima
STOP:
infinite
soluzioni
Metodo dei grossi pesi
Si procede aggiungendo le variabili slack, surplus o
artificiali in base al tipo di vincoli.
Si introducono dei coefficienti di costo per le variabili
artificiali detti penalità in modo da ottenere:
a
z  C  X  P  X n j
T
j 1
Con o.d.g.(P)>>o.d.g.(ci)
•-P se il problema è a massimizzare
•+P se il problema è a minimizzare
Se il problema è a minimizzare le variabili artificiali
saranno le prime ad uscire dalla base (per il “grosso
peso” di P) e non vi rientreranno più.