PROGRAMMAZIONE LINEARE METODO

SIMPLEX

INVESTIGA

JEVA / PTI
1
PROGRAMMAZIONE LINEARE METODO
SIMPLEX

PROGRAMMAZIONE LINEARE: SOLUZIONE DEI PROBLEMI CON IL METODO SIMPLEX

El Método Simplex soluciona problemas de Programación Lineal de cualquier tamaño, desde dos hasta "n"
variabili decisionali. I problemi possono essere di massimizzazione o di minimizzazione a seconda del tipo di
Funzione obiettivo che hanno e per quanto riguarda il tipo di soluzione ottimale che danno, possono essere di soluzione unica di
soluzione multipla o alternata.

Il computer è un mezzo tecnologico che offre grande supporto nella soluzione di problemi di programmazione
Lineare, utilizzando la sua grande velocità di elaborazione dei dati. Il computer può utilizzare qualsiasi tipo di
software progettato per questo scopo, ma tutti utilizzeranno l'algoritmo matematico del Metodo
Simplex. Alcuni pacchetti software che possono essere utilizzati per risolvere questi problemi sono, il
WinQSB, Storm, Lindo, ecc. Si può anche programmare un foglio elettronico per questo scopo, con il Solver del
Excel.

Un requisito indispensabile per utilizzare il computer con questa orientamento è avere preventivamente il problema
modello per facilitare la cattura dei dati in ingresso, che dovranno essere secondo il formato del software
utilizzato e procedere alla sua esecuzione. La soluzione che dà il computer nel suo rapporto di uscita deve essere
interpretarpara apoyar la toma de decisiones.

L'approccio a questo tema è conoscere i fondamenti del Metodo Simplex come supporto per interpretare la
soluzione ottimale, che è la soluzione matematica che fornisce il computer. Per raggiungere questo, viene presentata la
metodologia che segue il Metodo Simplex nella soluzione manuale dei problemi di Programmazione Lineare siano
di massimizzazione o di minimizzazione:

1. Eguagliare le restrizioni del problema modellato.

2. Formare la 'Tabella Iniziale'.
3. Riconoscere se la soluzione fornita dalla Tabella è ottimale, controllando il rispetto del "Criterio di"
Ottimabilità (Cj-Zj≤0)". Se la soluzione non è ottimale, bisogna:
4. Calcolare il "Nuovo Tabella". fino a trovare la soluzione ottimale.
5. Ripetere il "Passo 3 e 4" fino a quando la tabella calcolata soddisfa il criterio di ottimalità.
6. Dare la 'Soluzione Ottimale' del problema.
7. Interpretare

Per presentare l'applicazione di questa metodologia, si procederà con tre problemi: uno di massimizzazione, un altro di
minimizzazione e l'ultima di soluzione ottimale alternata o multipla.

1. PROBLEMA DI 'MAXIMIZZAZIONE'.

Questa metodologia generale verrà spiegata con un problema di massimizzazione, di due variabili decisionali, che è
un problema piccolo solo per illustrare il Metodo Simplex.

Con l'intento di confrontare il Metodo Grafico e il Simplex, si riprende il problema della 'fabbricazione di
fertilizzanti" che in precedenza era stato risolto con il Metodo Grafico e ora sarà fatto con il Simplex.
In primo luogo viene presentata la soluzione del problema e poi verrà effettuato il confronto tra i due metodi:

1.1. Soluzione del problema con il Metodo Simplex.

Di seguito viene fornito il modello del problema dei fertilizzanti (problema presentato nelle note del Metodo
Grafico) da risolvere con il Metodo Simplex:

Máx. Z = 185X1+ 200X2

s. a. Nitrato 0.05X1+ 0.05X2≤1.100
Fosfato 0.05X1+ 0.10X2≤1.800
Potasio 0.10X1+ 0.05X2≤2.000

JEVA / PTI
2
PROGRAMMAZIONE LINEARE METODO
SIMPLEX

Passo 1. Eguagliare le restrizioni.

Si eguagliano le restrizioni per avere la matrice identità del problema. Questa matrice identità è il punto
di partenza che utilizza il Metodo Simplex per risolvere il problema.

Esistono le seguenti regole per effettuare l'uguagliamento delle restrizioni:

Se si ha una restrizione minore o uguale si aggiungerà una variabile di slack (H). Se la restrizione
se è maggiore o uguale si sottrarrà una variabile di eccedenza (E) e si aggiungerà una variabile artificiale (A). Se
la restrizione è un'uguaglianza si aggiungerà una variabile artificiale (A).

Un piccolo esempio per mostrare l'applicazione di queste regole è uguagliando i seguenti

restrizioni:

Restrizioni Eguagliando le restrizioni

2X1+ 4X2≤80 2X1+ 4X2+ H1+ 0 + 0 = 80

8X1+ 6X2≥12 8X1+ 6X2+ 0 - E2+ A1= 12
X1+ 3X2= 15 X1+ 3X2+ 0 + 0 + A2= 15
matrice identità

Ora, applicando queste regole per uguagliare le restrizioni del problema dei fertilizzanti, si ha:

Nitrato 0.05X1+ 0.05X2≤1.100 0,05X1+ 0,05X2+ H1= 1.100

Fosfato 0,05X1+ 0.10X2≤1.800 0,05X1+ 0.10X2+ H21.800
Potasio 0.10X1+ 0,05X2≤2.000 0,10X1+ 0.05X2+ H32.000

Passo 2. Formare la Tabella Iniziale.

Esistono diversi formati di tabelle che possono essere utilizzati per il Metodo Simplex. I formati sono
differiscono solo nella collocazione dei dati ma l'essenza è la stessa.

Una volta definito il formato della tabella, rimarrà lo stesso per tutto lo sviluppo del problema,
indipendentemente dalla fase che si sta facendo. Noi utilizzeremo il seguente formato per
fare le tabelle:

Tabella Iniziale o Tabella 1.

Función Objetivo:
Base Cj X1 X2 H1 H2 H3 Bio Variabili
185 200 0 0 0 Coefficienti di Contribuzione
H1 0 0,05 0,05 1 0 0 1100Restrizioni:
H2 0 0,05 0,10 0 1 0 1800 Coefficienti e Termini
H3 0 0,10 0,05 0 0 1 2000 Indipendenti

Perdita Unitaria della Funzione Obiettivo

Zj 0 0 0 0 0 0
(Prezzo Ombra)
∆j 185 200 0 0 0
Incremento Marginale del valore della
Funzione Obiettivo

Per calcolare Zjy∆jsi faranno con le seguenti relazioni:

Zj= Σ Ai,jCj
∆j= Cj- Zj

JEVA / PTI
3
PROGRAMMAZIONE LINEARE METODO
SEMPLICE

Passo 3. Riconoscere se la soluzione fornita dalla tabella è ottimale. Verificare il rispetto del Criterio di
Ottimabilità (∆j≤0)

Il Metodo Simplex utilizza il Criterio di Ottimalità per sapere se ha già raggiunto la soluzione ottimale.
problema. Si la tabla que se tiene no cumple con este criterio, se tendrá que seguir adelante con otras
iterazioni, cioè, calcolando più tabelle fino a soddisfarlo. Il criterio di ottimalità è enunciato nella
forma seguente:
La soluzione sarà ottimale se e solo se ∆j≤0. Vale a dire, i valori della riga del∆jdevono essere
ceri o negativi. Un valore positivo indica che la soluzione della tabella non è ottimale.

Come il Metodo Simplex lavora per iterazioni (passare da una tabella all'altra fino a raggiungere la soluzione
ottimale), è possibile leggere la soluzione che si ha in qualsiasi tabella di quelle calcolate.

Per leggere la soluzione di una tabella che è stata calcolata, è necessario vedere due colonne, la colonna
Basenos darà le Variabili Fondamentali che formano la soluzione e la colonna "Bi" ci darà il valore di queste
variabili. Qualsiasi variabile non inclusa nel database è una Variabile non Base con valore zero.

Leggendo la soluzione della tabella precedente, si ha che:

Variabili di base Variabili non di base

(Soluzione della Tabella)
H1= 1100 X 1= 0
H2= 1800 X 2= 0
H3= 2000
Z = 0

Questa soluzione non è ottimale poiché, osservando la riga ∆jha valori positivi che non soddisfano
con il criterio di ottimalità. Pertanto è necessario creare una nuova tabella per trovare la
seguente soluzione fattibile e verificare se è ottimale.

Passo 4. Calcolare la "Nuova Tabella".

Per calcolare la nuova tabella è necessario definire la "Variabile di Ingresso (VE), la "Variabile di Uscita (VS)".
el"Pivote"y los"Criterios de Ajuste"para los nuevos renglones.

Il "Criterio per definire la Variabile di Ingresso" è selezionare la variabile con il valore massimo della riga
∆j. In questo caso la variabile di input è X2che ha un valore di 200 che è il valore maggiore. Questo
significa che per ogni tonnellata di fertilizzante 5-10-5 prodotta 2) si guadagnerà $200 per tonnellata
ma se fosse stato selezionato come variabile di input il 5-5-10 (X 1) si guadagnerebbe solo $185. La variabile
X2entrerà nella "Base" della nuova tabella.

Bio
Il "Criterio per definire la Variabile di Uscita" è selezionare il valore minimo positivo del quoziente .
Ah o
Prima si deve calcolare il quoziente e poi selezionare la variabile di uscita. In questo problema la
la variabile di uscita è H2.

Il 'Pivote' è l'intersezione della colonna della Variabile di Ingresso con la riga della Variabile di
Uscita e si deve "segnare" questo pivot poiché verrà utilizzato per fare i criteri di aggiustamento.

I "Criteri di aggiustamento" consistono nel fare le equazioni necessarie per calcolare le righe del
nueva tabla sin utilizar el cálculo matricial; obviamente estos cálculos se pueden hacer también con
matrici.

JEVA / PTI
4
PROGRAMMAZIONE LINEARE MÉTODO
SIMPLEX

Si raccomanda di fare i calcoli per "righe" per evitare errori invece di farli cella per cella.
In generale, i “criteri di aggiustamento” per calcolare le righe della nuova tabella possono essere definiti
nella forma seguente:

Vp
Riga Pivot Np =
p
Np= Righe pivot per la nuova tabella
Vp= Righe della vecchia tabella dove è contrassegnato il pivot
pValore del pivot segnato nella vecchia tabella

N iVioA Nho
p

Ni= Rigo "i" calcolato per la nuova tabella

VioRiga "i" selezionata dalla vecchia tabella
Aio, ho= Coefficienti della colonna della variabile di input nella riga "i" (tabella
vecchia
Np= Rigo di intestazione per la nuova tabella
Di seguito sono riportati i calcoli per il problema in fase di sviluppo:

Tabella 1

Base Cj X1 X2 H1 H2 H3 Bio Bi
185 200 0 0 0
Ah o
V1 H1 0 0,05 0,05 1 0 0 ["1100","22.000"]
V2 H2 0 0,05 0,10 0 1 0 1800 18.000 →VS = H2
V3 H3 0 0,10 0,05 0 0 1 2000 40,000
Zj 0 0 0 0 0 0
∆j 185 200 0 0 0

VE = X2

I criteri di adeguamento per calcolare le righe del nuovo tavolo sono:

V2
Riga Pivot N2 =
0.10
N1 =V1 − 0,05N2
N 3V30,05N2

Si presentano i calcoli delle righe per la nuova tabella:

Si deve sempre iniziare calcolando il "rigo pivot" per la nuova tabella che in questo caso è N2:

Riga N2:
V2 0,05 0,10 0 1 0 1.800
V 0,5 1 0 10 0 18.000
N2 = 2
0,10
Questo "renglón pivote" della nuova tabella è molto importante poiché sarà usato come riferimento per
calcolare le altre righe della tabella, come mostrato di seguito:

JEVA / PTI
5
PROGRAMMAZIONE LINEARE METODO
SIMPLEX

Riga N1:
V2 0,05 0,05 1 0 0 1.100
- 0,05 N2 - 0,025 - 0.05 0 - 0,5 0 900
N1 0,025 0 1 - 0.5 0 200

Riga N3:
V3 0,10 0,05 0 0 1 2.000
- 0,05N2 - 0,025 - 0,05 0 - 0,5 0 900
N3 0,075 0 0 - 0.5 1 1,100

Sistema i righi calcolati nella nuova tabella risulta nella seguente forma:

Tabella 2

Base Cj X1 X2 H1 H2 H3 Bio Bio

185 200 0 0 0
Ai , v e
N1 H1 0 0,025 0 1 - 0,5 0 200 8.000→VS = H1
N2 X2 200 0,5 1 0 10 0 18.000 36.000
N3 H3 0 0,075 0 0 - 0,5 1 1.100 14.666,7
Zj 100 200 0 2,000 0 3.600.000
∆j 85 0 0 2.000 0

VE = X1

Passo 5. Ripetere il 'Passo 3 e 4' fino a quando la tabella calcolata soddisfa il criterio di ottimalità.

Se il criterio di ottimalità è soddisfatto, allora la soluzione di quella tabella è ottimale; altrimenti, si

continua "iterando" cioè facendo nuove tabelle fino a trovare la soluzione ottimale del problema per
ciò che si ripete nuovamente il passo 4.

La soluzione della tabella precedente è: H1= 200

X2= 18.000
H3= 1.100
Máx. Z = 3.600.000

Questa soluzione non è ottimale, poi si calcola il seguente "nuovo tavolo" definendo la Variabile di Ingresso,
la Variabile di Uscita, Pivote e i Criteri di Regolazione.

Per calcolare la Tabella 3, si ha che la Variabile di Entrata è X1, la Variabile di Uscita è H1, il Pivot è
0,025 e i criteri di adeguamento sono:

V1
Riga Pivot N1 =
0,025
N 2 = V 2 − 0,5N1
N 3 =V3 −0,075N1
Tabella 3
Base Cj X1 X2 H1 H2 H3 BIo
185 200 0 0 0
X1 185 1 0 40 - 20 0 8.000
X2 200 0 1 - 20 20 0 14.000
H3 0 0 0 -3 1 1 500

JEVA / PTI
6
PROGRAMMAZIONE LINEARE MÉTODO
SIMPLEX

Zj 185 200 3.400 300 0 4.280.000

∆j 0 0 - 3.400 - 300 0

En esta tabla se cumple con el criterio de optimabilidad ∆j≤0 per cui si è arrivati alla soluzione
ottimale del problema.

Passo 6. Dare la 'Soluzione Ottimale' del problema.

La soluzione ottimale del problema che si trova nella Tabella 3 è:

X1= 8.000
X2= 14.000
H3= 500
Máx. Z = 4.280.000

Questa soluzione ottimale è una "soluzione matematica" che richiede di essere interpretata.

Passo 7. "Interpretare" la soluzione ottimale del problema.

Nell'interpretazione della soluzione ottimale, si deve vedere se il problema ha "variabili discrete" o

"variabili continue". Se si hanno variabili discrete, nel fare l'interpretazione della soluzione ottimale del
problema, dovrà essere fornito in valori "interi" apportando le modifiche necessarie alla soluzione
matematica ottenuta. Se sono variabili continue, l'interpretazione sarà fatta direttamente con i valori
ottenuti senza apportare alcuna modifica.

Nel nostro problema ci sono variabili continue quindi non è necessario fare aggiustamenti. Quindi, la
interpretación de la solución óptima será la siguiente:

Il programma di produzione per il mese prossimo sarà di 8.000 tonnellate di fertilizzante 5-5-10 (X 1=8,000) y
14.000 tonnellate del 5-10-5 (X 2=14.000) per avere il massimo utile di $4.280.000 (Max.Z=4.280.000).
Dopo aver realizzato questo programma di produzione rimarranno 500 tonnellate di potassio in eccesso.
Le restrizioni dominanti o "collo di bottiglia" sono il Nitrato e il Fosfato.

1.2. Comparazione tra il Metodo Simplex e il Metodo Grafico.

Riprendendo il problema dei "fertilizzanti", che è stato appena risolto con il Metodo Simplex, si farà un
analisi comparativa tra il Metodo Simplex e il Metodo Grafico.

Il Metodo Simplex è "iterativo", cioè continua a ripetere il calcolo delle tabelle, passando da una all'altra, fino a
trovare la soluzione ottimale mentre il Metodo Grafico valuta la Funzione Obiettivo in ogni vertice di
regione fattibile per scegliere la soluzione ottimale. La grande differenza che esiste tra i due metodi è che
La soluzione fornita dal Metodo Grafico può essere visualizzata graficamente, mentre quella del Simplex no.

Per analizzare la logica dei calcoli del Metodo Simplex e confrontarli con il Metodo Grafico, si presenta la
grafico seguente:

JEVA / PTI
7
PROGRAMMAZIONE LINEARE MÉTODO
SIMPLEX

H1= 200 X1= 0

X2= 18.000 H2 = X1= 8.000 H1=
0 0
H3= 1.100 X2= 14.000 H2=
Z = 3.600.000 0
VERTICE H3= 500
A Máx. Z =
4.280.000
VERTICE “B”

H1= 1.100 X1= 0

H2= 1.800 X2= 0
H3= 2,000
VERTICE “E”

Il Metodo Simplex nel calcolare la "Tabella Iniziale (Tabella 1)" con la matrice identità del problema, si posiziona nel
Il vertice "E" si trova nel punto d'origine (0,0). In questo modo il Simplex è pronto per iniziare la soluzione
del problema. In questa tabella iniziale si ha la seguente soluzione:

Variabili "Básicas" Variabili "non basilari"

H1= 1100 X 1= 0
H2= 1800 X 2= 0
H3= 2000
Z=0

Questa soluzione della "Tabella Iniziale" è uguale alla soluzione che si ha nel vertice "E" nel Metodo Grafico.
Essendo nel vertice "E", il Metodo Simplex valuta le alternative di movimento che ha, in questo caso due,
una direzione ti porta al vertice "A" e l'altra al "D". La riga dell "Incremento Marginale del valore della Funzione
Obiettivo (∆jen la Tabella Iniziale, indica che l'utilità per tonnellata che si può ottenere producendo X2es di
200$/tonnellata mentre con la X1è di $185. La migliore alternativa è produrre X2, è per questa ragione che si
scelse come "Variabile di Ingresso" (VE = X2) alla Base della "Nuova Tabella" (Tabella 2). Questo equivale a muoversi
nella direzione dell'asse X2come si può notare nel grafico.

Una volta selezionato l'indirizzo, il Simplex deve conoscere fino a dove può muoversi, questo lo ottiene definendo
la "Variabile di Uscita" della Base della Tabella Iniziale che è H2(VS = H2) che è collegata alla restrizione di
Fosfato. Questa restrizione dà il limite massimo fino a dove si può arrivare secondo il grafico, cioè fino a
il vertice "A".

La soluzione che si ha nel vertice "A" (vedi la soluzione della Tabella 2 del Metodo Simplex) è:

Variabili "Básicas" Variabili 'non basilari'

H1= 200 X 1= 0
X2= 18.000 H2= 0
H3= 1.100
Z = 3.600.000

Già nel vertice "A", si ripetono i passi precedentemente spiegati; secondo il grafico si valutano le
direzioni di movimento (passare al vertice “B” o al vertice “E”) e fino a dove può arrivare al massimo nella
direzione selezionata in modo tale da incrementare il valore della Funzione Obiettivo. Secondo il grafico,
si seleziona passare al vertice "B" (vincolo di Nitrato). Analizzando cosa fa il Simplex per passare al
il vertice "B" è selezionare la direzione di movimento attraverso la variabile di ingresso della Tabella 2 che è X1

JEVA / PTI
8
PROGRAMMAZIONE LINEARE MÉTODO
SIMPLEX

(VE = X1). Nel vertice "B" si trova la soluzione ottimale del problema che può essere vista nella Tabella 3 del Metodo
Semplice, cioè, in questa tabella si soddisfa il criterio di ottimalità.

La soluzione ottimale è:

Variabili "Básicas" Variabili "non di base"

X1= 8.000 H1= 0

X2= 14.000 H2= 0
H3= 500
Máx.Z = 4’280.000

Se si volesse passare a un altro vertice, ad esempio al "C", come si può vedere nel grafico, questo darebbe un valore della
Funzione obiettivo minore rispetto a quella che si aveva al vertice “B”, pertanto si riafferma che questo vertice è la soluzione.
ottimale. La soluzione che si trova nel vertice “C” è:

Variabili "Básicas" Variabili "non basilari"

X1= 18.000 H1= 0

X2= 4.000 H3= 0
H2= 500
Z = 4.130.000

2. PROBLEMA DI "MINIMIZZAZIONE".
Quando si vuole risolvere un problema di Programmazione Lineare, è necessario sviluppare un
ciclo di tre fasi: modellare il problema, risolvere il modello per trovare la soluzione ottimale e interpretare la
soluzione ottimale trovata. Di seguito viene presentato un problema di "minimizzazione" che presenta i tre
passi menzionati:

Alimenti per culturisti.

Un'azienda produttrice di alimenti per culturisti ha ricevuto un ordine di 1000 chilogrammi di
un prodotto ad alto contenuto proteico. L'azienda sa che la formulazione di questo ordine viene effettuata
con tre alimenti base. Attualmente si dispone nei magazzini di 800 chilogrammi del
alimento "A", 100 de "B" y 400 de "C". El producto final tiene como requerimiento cuando menos 600
chilogrammi del alimento "A" e non più di 500 degli alimenti "B" e "C" combinati. Il costo del
Il chilogrammo costa $15 per "A", $12 per "B" e $10 per "C". L'azienda vuole sviluppare un
modello per minimizzare il costo di questo ordine.

Modellazione.
Variabili di Decisione.
XioKilogrammi del Cibo "i" che saranno utilizzati nella produzione dell'ordine
(Kg)

Funzione Obiettivo.
mín. Z = 15X1+ 12X2+ 10X3
$ ($/Kg)(Kg) = $

Restrizioni.
1. Condizione di Bilanciamento.
X1+ X2+ X3= 1000
Kg Kg

JEVA / PTI
9
PROGRAMMAZIONE LINEARE METODO
SIMPLEX

2. Specifiche dell'Ordine.
Alimento "A" X1≥600
Alimento "B" X2+ X3≤500
Kg Kg

3. Disponibilità dei Materiali.

Alimento "A" X1≤800
Alimento 'B' X2≤100
Alimento "C" X3≤400
Kg Kg

4. Nessuna negatività Xi≥0

Analisi Dimensionale: Approvato.

Soluzione tramite il Metodo Simplex.

Per risolvere un problema di 'minimizzazione' con il Metodo Simplex, si può utilizzare la stessa metodologia
che si è applicato ai problemi di Massimizzazione. Per fare ciò, è necessario trasformare il problema di
minimizzazione a uno di massimizzazione applicando il seguente principio:
mín.Z = Máx.(-Z)

Funzione Obiettivo originale Funzione Obiettivo trasformata

mín. Z = 15X1 + 12X2+ 10X3 Max. Z = - 15X112X2- 10X3

Una volta trasformato il problema, si risolve come se fosse un problema di massimizzazione. Di seguito sono riportati i passi.
per la soluzione del problema:

• Eguagliare le restrizioni.
Si presenta l'equalizzazione delle restrizioni per formare la 'matrice identità' di questo problema:

Restrizioni Eguaglianza delle Restrizioni

Condizione di Bilancio X1+ X2+ X3= 1000 X1+ X2+ X3+ A1= 1000
Specificazione Alimento "A" X1≥600 X1- E1+ A2= 600
Specificazione Alimento "B" X2+ X3≤500 X2+ X3+ H2= 500
Disponibilidad Alimento "A" X1≤800 X1+ H3= 800
Disponibilità Alimento "B" X2≤100 X2+ H4= 100
Disponibilidad Alimento "C X3≤400 X3+ H5= 400

• Tabella iniziale del problema.

Considerando, la trasformazione del problema come se fosse di massimizzazione, si ha la seguente
"Tabla Inicial":

Tabella Iniziale (Tabella 1)

Base Cj X1 X2 X3 A1 E1 A2 H2 H3 H4 H5 Bio Bio
-15 -12 -10 -150 0 -150 0 0 0 0
Ah o
A1 -150 1 1 1 1 0 0 0 0 0 0 1.000 1.000
A2 -150 1 0 0 0 -1 1 0 0 0 0 600 600→VS
H2 0 0 1 1 0 0 0 1 0 0 0 500 Infinito
H3 0 1 0 0 0 0 0 0 1 0 0 800 800
H4 0 0 1 0 0 0 0 0 0 1 0 100 Infinito
H5 0 0 0 1 0 0 0 0 0 0 1 400 Infinito
Zj -300 -150 -150 -150 150 -150 0 0 0 0 -240.000
∆j 285 138 140 -1500 0 0 0 0 0

JEVA / PTI
10
PROGRAMMAZIONE LINEARE METODO
SIMPLEX

VE

• Riconoscere se la soluzione della tabella è ottimale.

Analizzando la riga ∆jci troviamo numeri positivi, che indicano che la soluzione che si ha in
questa tabella non è ottimale poiché non soddisfa il criterio di ottimalità. Quindi, deve essere calcolato
la seguente iterazione o tabella 2 (“Nuova Tabella”)

• Calcolare la 'Nuova Tabella'.

Sulla base della Tabella Iniziale (Tabella 1), vengono stabiliti i "Criteri di Regolazione" per passare al successivo
tabella, rimanendo nella seguente forma:

Riga Pivot N2= V2

N1= V1-N2
N3= V3
N4= V4-N2
N5= V5
N6= V6

Con questi criteri sono stati calcolati i righi della seguente tabella:

Tabella 2
Base Cj X1 X2 X3 A1 E1 A2 H2 H3 H4 H5 Bio Bio
-15 -12 -10 -150 0 -150 0 0 0 0
Ai o , h o
A1 -150 0 1 1 1 1 -1 0 0 0 0 400 400→VS
X1 -15 1 0 0 0 -1 1 0 0 0 0 600 Infinito
H2 0 0 1 1 0 0 0 1 0 0 0 500 500
H3 0 0 0 0 0 1 -1 0 1 0 0 200 Infinito
H4 0 0 1 0 0 0 0 0 0 1 0 100 Infinito
H5 0 0 0 1 0 0 0 0 0 0 1 400 400
Zj -15 -150 -150 -150 -135 135 0 0 0 0 -69.000
∆j 0 138 140 135 0 -285 0 0 0 0

VE

• Se la Tabella calcolata non soddisfa il "Criterio di Ottimabilità", è necessario continuare a fare "Nuove
Tabella" fino a raggiungere la soluzione ottimale del problema.
La Tabella 2 non è la soluzione ottimale per il problema, quindi bisogna continuare a iterare.
nuove tabelle) fino a raggiungere la soluzione ottimale della stessa. Di seguito vengono presentati i calcoli di
le tabelle calcolate:

Criteri di Adeguamento per passare alla Tabella 3:

Riga Pivot N1= V1

N2= V2
N3= V3-N1
N4= V4
N5= V5
N6= V6-N1

Tabella 3
Base Cj X1 X2 X3 A1 E1 A2 H2 H3 H4 H5 Bio
-15 -12 -10 -150 0 -150 0 0 0 0

JEVA / PTI
11
PROGRAMMAZIONE LINEARE MÉTODO
SIMPLEX

X3-10 0 1 1 1 1 -1 0 0 0 0 400
X1-15 1 0 0 0 -1 1 0 0 0 0 600
H2 0 0 0 0 -1 -1 1 1 0 0 0 100
H3 0 0 0 0 0 1 -1 0 1 0 0 200
H4 0 0 1 0 0 0 0 0 0 1 0 100
H5 0 0 -1 0 -1 -1 1 0 0 0 1 0
Zj -15 -10 -10 -10 5 -5 0 0 0 0 -13.000
∆j 0 -2 0 -140 -5 -145 0 0 0 0

In questa Tabella 3 si soddisfa il criterio di ottimabilità, ossia tutti i numeri della riga ∆jfiglio
negativi o zero. Quindi, la soluzione di questa tabella è ottimale.

• Soluzione Ottimale del problema.

La soluzione ottimale che si può leggere nella tabella è la seguente:

X3= 400
X1= 600
H2= 100
H3= 200 (¿¿)
H4= 100
H5= 0
Máx. Z = -13.000 che è uguale mín. Z = 13.000

• Interpretare
Il problema ha variabili continue, quindi segue la seguente interpretazione:
Per realizzare l'ordine che soddisfi i requisiti, sarà necessario utilizzare 600 chilogrammi del
alimento "A" (X1=600) e 400 chilogrammi del alimento "C" (X3=400) per avere il costo minimo di
$13.000 (mín.Z=13.000). Nel fare questo piano di produzione per l'ordine, si avrà la seguente analisi
dei risorsi: nella richiesta della combinazione degli alimenti 'B' e 'C' ci sarà un avanzo di
100 chilogrammi (H2=100), cioè, sono stati utilizzati 400 chilogrammi invece di 500; si ha un avanzo di
200 chilogrammi del cibo "A" (H3=200) e 100 chilogrammi del alimento "B" (H4=100) che non è stato utilizzato.
Il Cibo "C" (H 5=0) è terminato. La restrizione dominante è la specificazione del Cibo “A”, la
disponibilità del Cibo "C" e rispettare la condizione di equilibrio.

3. PROBLEMA DI "SOLUZIONE OTTIMA ALTERNATIVA" E "SOLUZIONI OTTIME"

MULTIPLI

Per sapere se un problema ha una o più “soluzioni ottimali alternative”, è necessario cercare nella “Tabella
Final" (la tabella con la soluzione ottimale del problema) le variabili che soddisfano le seguenti condizioni:

• Variabile “no base”

• Con valore zero nella riga∆j
• E almeno un coefficiente positivo nella sua colonna

Per ogni variabile presente nella Tabella Finale che soddisfa queste condizioni, si avrà una nuova soluzione
alternativa ottimale.

Per calcolare una "nuova soluzione ottimale" si forzerà come Variabile di Ingresso, la variabile che soddisfa le
condizioni. Si seguirà la procedura per calcolare la seguente tabella ('nuova tabella'), dove si troverà la
nuova soluzione ottimale (soluzione ottimale alternativa).

Se nella Tabella Finale ci sono varie variabili che soddisfano le condizioni, allora si avranno
Soluzioni Ottimali Multiple. A seconda del numero di queste variabili, si avrà almeno questo
numero o più soluzioni ottimali diverse per il problema.

JEVA / PTI
12
PROGRAMMAZIONE LINEARE METODO
SIMPLEX

Per calcolare queste soluzioni multiple, prima si costringerà una di esse a essere la Variabile di Ingresso nella
Tabella finale e seguendo la procedura per calcolare la tabella seguente, si troverà la prima soluzione
alternativa ottimale del problema. Se vengono inserite come Variabili di Input, le diverse variabili che
soddisfano le condizioni, saranno calcolate le diverse soluzioni ottimali alternative che il problema presenta.

Di seguito sono presentati due problemi per presentare le situazioni in cui si ha una 'Soluzione'
Óptima Alterna" e dove si hanno diverse "Soluzioni Ottimali Multiple":

3.1. Soluzione Ottimale Alternativa.

Per analizzare un problema con "soluzione ottimale alternativa", si tratterà nuovamente il problema dei fertilizzanti.
ma modificata leggermente la Funzione Obiettivo. Sono state mantenute le stesse restrizioni ma è stata cambiata la
Funzione Obiettivo a una nuova, rimanendo il modello nella seguente forma:

Funzione Obiettivo Max. Z = 100X1+ 200X2

Restricciones: Nitrato 0,05X1+ 0,05X2≤1.100

Fosfato 0,05X1+ 0.10X2≤1.800
Potasio 0.10X1+ 0.05X2≤2.000

Soluzione mediante il Metodo Simplex.

Di seguito sono presentate tutte le tabelle (iterazioni) del problema:

Tabella Iniziale (Tabella 1)

Base Cj X1 X2 H1 H2 H3 Bi Bio
100 200 0 0 0
Ai o h o
V1 H1 0 0,05 0,05 1 0 0 1100 22.000
V2 H2 0 0,05 0,10 0 1 0 1800 18.000 →VS
V3 H3 0 0,10 0,05 0 0 1 2000 40.000
Zj 0 0 0 0 0 0
∆j 100 200 0 0 0

VE

"Criterios de Ajuste" para pasar a la Tabla 2:

V2
Riga di Pivot N2=
0.10
N1= V1- 0,05N2
N3= V3- 0,05N2

Tabella 2 (Tabella Finale).

Base Cj X1 X2 H1 H2 H3 Bi Bio
100 200 0 0 0
Ai o , h o
N1 H1 0 0,025 0 1 -0,5 0 200 8.000→VS
N2 X2 200 0,5 1 0 10 0 18,000 36,000
N3 H3 0 0,075 0 0 -0.5 1 1.100 14.666,7

JEVA / PTI
13
PROGRAMMAZIONE LINEARE MÉTODO
SIMPLEX

Zj 100 200 0 2.000 0 3.600.000

∆j 0 0 0 -2.000 0

VE

La soluzione ottimale di questo problema è:

H1= 200
X2= 18,000
H3= 1,100
Máx. Z = 3.600.000

Analizzando la "Tabella Finale" del problema, si trovano due variabili non di base, la X1e la H2. La H2non cumple
con tutte le condizioni tranne la X1sì. Quindi il problema ha una soluzione ottimale alternativa. Per calcolare
questa soluzione ottimale alterna, si impone come Variabile di Ingresso la X1e si calcola la seguente Tabella.

"Criteri di Adeguamento" per passare alla tabella successiva:

V1
Riga Pivot N1=
0,025
N2= V2-0,5N1
N3= V3-0,075N1

Tabella della Soluzione Ottimale Alternativa.

Base Cj X1 X2 H1 H2 H3 Bi
100 200 0 0 0
X1 100 1 0 40 -20 0 8.000
X2 200 0 1 -20 20 0 14.000
H3 0 0 0 -3 1 1 500
Zj 100 200 0 2000 0 3.600.000
∆j 0 0 0 -2000 0

È stata calcolata una soluzione ottimale alternativa per il problema che è:

X1= 8.000
X2= 14.000
H3= 500
Máx. Z = 3’600,000

Una caratteristica della soluzione ottimale alterna è che deve fornire una soluzione diversa ma lo stesso valore di
la Funzione Obiettivo che la soluzione ottimale normale, in questo caso 3.600.000.

Se si analizza nuovamente la "Tabella Finale", si vedrà che la variabile H1rispetta tutte le condizioni. Al
risolvere, seguendo lo stesso procedimento, si troverà la soluzione ottimale precedente. Vengono presentate le due
soluzioni ottimali del problema:

Soluzione Ottimale Soluzione Ottimale Alternativa

H1= 200 X1= 8.000
X2= 18.000 X2= 14.000
H3= 1.100 H3= 500
Máx. Z = 3’600,000 Máx. Z = 3'600.000

Interpretazione delle 'Soluzioni Ottimali' del problema.

JEVA / PTI
14
PROGRAMMAZIONE LINEARE METODO
SIMPLEX

Il programma di produzione per il mese prossimo può essere realizzato in due modi possibili. Un modo
si produrranno 18.000 tonnellate del fertilizzante 5-10-5 (X 2=18.000) per avere il massimo utile di
$3’600,000 (Max.Z=3600,000). Realizzando questo programma di produzione avanzeranno 200 tonnellate di
Nitrato (H1200) e 1.100 tonnellate di Potassio (H3=0).
Un'altra soluzione alternativa è produrre 8.000 tonnellate del fertilizzante 5-5-10 (X 1=8.000) e 14.000
tonnellate del 5-10-5 (X 2=14.000) per avere l'utile massimo di $3.600.000 (Max.Z=3.600.000). Al
fare questo programma avanzeranno 500 tonnellate di Potassio (H3=500).

Rango Ottimale.
Nella maggior parte dei problemi, la pendenza della Funzione Obiettivo passa per un vertice nella regione fattibile
generando una soluzione unica o puntuale. Quando un problema ha una soluzione ottimale alternativa è che la
pendente della Funzione Obiettivo passa per tutto un lato della regione fattibile generando diverse soluzioni
ottimali. Questo è il risultato del fatto che la pendenza della Funzione Obiettivo è parallela a uno di quei lati della
regione fattibile. Questo serve come base per stabilire il “Campo Ottimale” del problema, stabilendo l'intervallo di
variazione per ciascuna delle variabili.

Para calcular el Rango Óptimo se debe recordar que las variables que no forman parte de la solución óptima
inicial del problema, tienen un valor de "cero". Con esta consideración y comparando las dos soluciones
ottimali trovate per questo problema che ha solo due variabili decisionali, si può stabilire il
Rango Ottimale che rimane nella seguente forma:
Rango Óptimo: 8.000≥X1≥0
18.000≥X2≥14.000
200≥H1≥0
1.100≥H3≥500
Máx. Z = 3’600.000

Conoscere l'Intervallo Ottimale per questo problema con due variabili decisionali ci consente di pianificare diverse
soluzioni ottimali che rispondano a esigenze specifiche. Ad esempio, se si vuole produrre 5.000
tonnellate del fertilizzante 5-5-10 (X 1=5.000) si può calcolare quante tonnellate del fertilizzante 5-10-5 si hanno
cosa fabbricare per avere il massimo utilità di $3.600.000. Questo si calcola nel modo seguente:

3.600.000 = 100(5.000) + 200 X2

X2= 15.000

Secondo questo calcolo, devono essere prodotti 15.500 tonnellate del fertilizzante 5-10-5 (X2=15.500).

Se all'interno dei valori dell'intervallo ottimale, si fissano simultaneamente i valori di X1y X2, si può generare
una soluzione non ottimale perciò è necessario verificarla. È necessario controllare che il valore della Funzione
L'obiettivo rimanga lo stesso in qualsiasi caso.

3.2. Soluzioni Ottimali Multiple.

Un problema che ha diverse soluzioni ottimali è anche detto avere "soluzioni ottimali multiple". Il
Il problema seguente è un esempio di questo tipo:

Cadena de tiendas.
Una grande catena di negozi di generi alimentari ha diversi punti vendita che operano 24 ore su 24.
Dalle esperienze passate avute nei negozi, si è osservato che si può fornire un servizio migliore al
il cliente assegna turni di 8 ore ai suoi dipendenti ma scaglionati in periodi di 4 ore, è
dire, inizia un turno ogni 4 ore.
La direzione dell'azienda ha determinato le esigenze di personale per il mese successivo,
presentato nella tabella che segue:

Turno Periodo Personale

Richiesto
1 8 a 12 ore 35
2 12 a 16 30
3 16 a 20 40

JEVA / PTI
15
PROGRAMMAZIONE LINEARE METODO
SIMPLEX

4 20 a 24 20
5 24 a 4 10
6 da 4 a 8 25

All'amministrazione piacerebbe avere un modello che consenta di determinare quanti dipendenti devono
lavorare in ogni turno in modo che il numero totale di dipendenti sia minimo.

Modellazione.
Variabili di Decisione.
Xi = Dipendenti da lavorare nel Turno "i"
(e)

Funzione Obiettivo.
mín. Z = X1+ X2+ X3+ X4+ X5+ X6
e e

Restrizioni.
1. Periodi.
8 a 12 ore X1+ X6≥35
12 a 16 X1+ X2≥30
16 a 20 X2+ X3≥40
20 a 24 X3+ X4>=20
24 a 4 X4+ X5≥10
da 4 a 8 X5+ X6≥25
e e
2. Nessuna negatività Xi => 0

Analisi Dimensional: Provato.

Soluzione del problema modellato al computer.

Risolvendo questo problema al computer, è stata ottenuta la seguente "Tabella Finale" dalla quale si può leggere la
soluzione ottimale:

Tabella Finale (Prima Soluzione Ottimale)

* * *
Base Cj X1 X2 X3 X4 X5 X6 E1 E2 E3 E4 E5 E6 Bio Bio
-1 -1 -1 -1 -1 -1 0 0 0 0 0 0
Ah o
X1 -1 1 0 0 1 0 0 -1 0 0 0 -1 1 20 20
X2 -1 0 1 0 -1 0 0 1 -1 0 0 1 -1 10 -10
X3 -1 0 0 1 1 0 0 -1 1 -1 0 -1 1 30 30
E4 0 0 0 0 0 0 0 -1 1 -1 1 -1 1 10 Infinito
X5 -1 0 0 0 1 1 0 0 0 0 0 -1 0 10 10→VS
X6 -1 0 0 0 -1 0 1 0 0 0 0 1 -1 15 -15
Zj -1 -1 -1 -1 -1 -1 1 0 1 0 1 0 -85
∆j 0 0 0 0 0 0 -1 0 -1 0 -1 0

VE

Analizzando la "Tabella Finale" del problema, si è scoperto che X4, E2y E6sono le variabili "non basi" che
soddisfano le condizioni per avere soluzioni ottimali alternative. In questo caso, si presenta un problema con
soluzioni ottimali multiple, con almeno quattro soluzioni diverse.

Nella "Tabella Finale" si può leggere la prima soluzione ottimale del problema, che è la seguente:
X1 = 20
X2= 10

JEVA / PTI
16
PROGRAMMAZIONE LINEARE METODO
SIMPLEX

X3= 30
E4= 10
X5= 10
X6= 15
mín. Z = 85

Per calcolare la seconda soluzione ottimale del problema, si è imposta come Variabile di Ingresso X4e si applicarono
i Criteri di Regolazione per calcolare la seguente tabella:

Criteri di adeguamento per calcolare la "seconda soluzione ottimale" del problema:

Riga Pivote N5= V5

N1= V1 - N5
N2= V2+ N5
N3= V3- N5
N4= V4
N6= V6+ N5

Tabella Finale (Seconda Soluzione Ottimale)

* * *
Base Cj X1 X2 X3 X4 X5 X6 E1 E2 E3 E4 E5 E6 Bio Bio
-1 -1 -1 -1 -1 -1 0 0 0 0 0 0
Ah o
X1 -1 1 0 0 0 -1 0 -1 0 0 0 0 1 10 Infinito
X2 -1 0 1 0 0 1 0 1 -1 0 0 0 -1 20 -20
X3 -1 0 0 1 0 -1 0 -1 1 -1 0 0 1 20 20
E4 0 0 0 0 0 0 0 -1 1 -1 1 -1 1 10 10→VS
X4 -1 0 0 0 1 1 0 0 0 0 0 -1 0 10 Infinito
X6 -1 0 0 0 0 1 1 0 0 0 0 0 -1 25 Infinito
Zj -1 -1 -1 -1 -1 -1 1 0 1 0 1 0 -85
∆j 0 0 0 0 0 0 -1 0 -1 0 -1 0

VE

In questa "Tabella Finale" si può leggere la “seconda soluzione ottimale” del problema che è:
X1= 10
X2= 20
X3= 20
E4= 10
X4 = 10
X6= 25
mín. Z = 85

JEVA / PTI
17
PROGRAMMAZIONE LINEARE METODO
SIMPLEX

Dopo aver calcolato la seconda soluzione ottimale, si torna alla Tabella Finale della prima soluzione e si prosegue
calcolando le altre soluzioni ottimali. Ora si seleziona come Variabile di Ingresso E2per calcolare la
"terza soluzione ottimale" del problema. Si segue la stessa procedura descritta in precedenza. Si presenta
i calcoli per trovare le altre soluzioni ottimali del problema:

Criteri di aggiustamento per calcolare la “terza soluzione ottimale” del problema:

Riga Pivot N4= V4

N1= V1
N2= V2+ N4
N3= V3- N4
N5= V5
N6= V6

Tabella Finale (Terza Soluzione Ottimale)

Base Cj X1 X2 X3 X4 X5 X6 E1 E2 E3 E4 E5 E6 Bio Bio
-1 -1 -1 -1 -1 -1 0 0 0 0 0 0
Ai o , h o
X1 -1 1 0 0 0 -1 0 -1 0 0 0 0 1 10 10→VS
X2 -1 0 1 0 0 1 0 0 0 -1 1 -1 0 30 Infinito
X3 -1 0 0 1 0 -1 0 0 0 0 -1 1 0 10 Infinito
E2 0 0 0 0 0 0 0 -1 1 -1 1 -1 1 10 10
X4 -1 0 0 0 1 1 0 0 0 0 0 -1 0 10 Infinito
X6 -1 0 0 0 0 1 1 0 0 0 0 0 -1 25 - 25
Zj -1 -1 -1 -1 -1 -1 1 0 1 0 1 0 -85
∆j 0 0 0 0 0 0 -1 0 -1 0 -1 0

VE

Terza soluzione ottimale:

X1= 10
X2= 30
X3= 10
S2= 10
X4= 10
X6= 25
mín. Z = 85

Criteri di aggiustamento per calcolare la 'quarta soluzione ottimale' del problema:

Riga Pivot N1= V1

N2= V2
N3= V3
N4= V4- N1
N5= V5
N6= V6+ N1

Tabella Finale (Quarta Soluzione Ottimale)

Base Cj X1 X2 X3 X4 X5 X6 E1 E2 E3 E4 E5 E6 Bio
-1 -1 -1 -1 -1 -1 0 0 0 0 0 0
E6 0 1 0 0 0 -1 0 -1 0 0
X2 -1 0 1 0 0 1 0 0 0 1

JEVA / PTI
18
PROGRAMMAZIONE LINEARE METODO
SIMPLEX

X3 -1 0 0 1 0 -1 0 0 0 -1
E2 0 -1 0 0 0 1 0 0 1 1
X4 -1 0 0 0 1 1 0 0 0 0
X6 -1 1 0 0 0 0 1 -1 0 0
Zj -1 -1 -1 -1 -1 -1 1 0 1 0 1 0 -85
∆j 0 0 0 0 0 0 -1 0 -1 0 -1 0

Quarta soluzione ottimale:

E6= 10
X2= 30
X3 = 10
E 2= 0
X4= 10
X6= 35
mín. Z = 85

Nella Tabella della "terza soluzione ottimale", se si inserisce come Variabile di Entrata X5si otterrà una "quinta
soluzione ottimale" che sarà:
X1= 20
X2= 20
X3= 20
E2= 10
X5= 10
X6= 10
mín. Z = 85

Si presenta un riassunto delle "soluzioni ottimali multiple" del problema:

Variabili Soluzioni Ottimali Multiple

Basilari 1 2 3 4 5
X1 20 10 10 20
X2 10 20 30 30 20
X3 30 20 10 10 20
X4 10 10 10
X5 10 10
X6 15 25 25 35 15
E2 10 0 10
E4 10 10
E6 10
mín. Z 85 85 85 85 85

Interpretazione della soluzione del problema.

Questo problema ha cinque diverse soluzioni ottimali che si caratterizzano per avere lo stesso valore di.
Funzione Obiettivo (min.Z=85). Si presenta l'interpretazione della prima soluzione ottimale del problema a
maniera di esempio:

JEVA / PTI
19
PROGRAMMAZIONE LINEARE MÉTODO
SIMPLEX

Programmare 20 dipendenti per lavorare il turno 1 (X1=20), 10 al turno 2 (X2=10), 30 nel turno 3
(X3=30), 10 nel turno 5 (X5=10) y 15 nel turno 6 (X6=15). In questo modo si avrà un totale di 85
dipendenti essendo la quantità minima per coprire tutti i requisiti (min.Z=85). Con questa
l'assegnazione si avrà nel turno 4, 10 dipendenti in più rispetto al minimo richiesto che è di 20.

Per problemi con molteplici soluzioni ottimali, come in questo caso, non è pratico fare un intervallo.
ottimo di soluzioni non tanto calcolare tutte le possibili soluzioni ottimali del problema. Si
si consiglia di utilizzare il computer con un software adeguato per calcolare tutte le soluzioni ottimali.
questo è la fine.

JEVA / PTI
20