~~~ La versione in italiano inizia subito dopo la versione in inglese ~~~
ENGLISH
26-09-2025 - Operations Research - The Simplex and the Tabular Form [EN]-[IT]
With this post, I would like to provide a brief introduction to the topic in question.
(lesson/article code: MS_13)
image created with artificial intelligence, the software used is Microsoft Copilot
Introduction
The simplex method is an algorithm designed to solve rather complex linear programming problems. In yesterday's article, I gave a general overview of what it was. Today, however, I would like to focus more on what a tableau is, which is the starting point for developing the simplex method.
I will skip the entire tableau construction phase, but as I promised yesterday, today I will try to go into more detail about the operations required to execute the tableau to arrive at a solution.
Initial tableau
So let's skip the part where we transform the problem into a linear programming problem and pretend we've already done all this (see yesterday's article).
Below is the initial tableau.
The objective is to maximize Z = 40x + 30y
while respecting the following constraints:
2x + y ≤ 100
x + 2y ≤ 80
x, y ≥ 0
1
The first thing to do is choose the entering variable for row Z.
The most negative coefficient is -40 below x --> enters x
What does "enters x" mean in the simplex method
In the initial tableau, the base variables are s1 and s2, while x and y have values of 0.
Row Z essentially gives us some starting points. Remember that in this problem we want to maximize; I've reported the objective function below.
The objective is to maximize Z = 40x + 30y
When we look at row Z, the negative coefficients indicate that by increasing that variable, we can increase the objective function.
So let's select the most negative value, which is -40, and it's right in the x column.
Saying that x enters means that the variable becomes a new base variable, meaning it will change from 0 to a positive value. We can also say that from this moment on, x will participate in finding the solution, and for this reason, in mathematical jargon, we say that "x enters the base."
However, one of the variables already in base s1 or s2 will be forced to exit, meaning it will be set to zero.
2
After choosing the variable that enters, we must choose the one that exits.
Let's now analyze the column of the incoming variable, which we said is x.
For each row, which represents the constraints, the following ratio is calculated:
The ratio test is used to decide which constraint becomes active and therefore which base variable is removed.
The smallest ratio will identify the pivot row, i.e., the row in which the base variable will be removed and replaced.
Below is an image to clarify the terms used for the ratio test.
The ratio test gives the following result.
The ratio indicates how much I can increase 𝑥 before constraint (1) is saturated.
3
Now let's move on to the pivot normalization step.
We're working on the pivot row (1), and the pivot is equal to 2, that is, the coefficient of the input variable x.
The pivot is the table element found in this specific position:
- in the input variable column (in this case, the x column)
- in the pivot row, the one chosen with the ratio test, in this example, row (1).
So now we normalize by dividing by 2. That is, we take row 1 and divide it by 2. It will become like this: follows:
So now the tableau will have a different first row than it was at the beginning, and it will look like this:
4
Now we need to zero the x column in (2) and Z.
For (2), we will perform the following transformation.
For Z, we will perform the following transformation.
So, the tableau after the The first pivot becomes as follows:
5
Second pivot
In Z, there is the negative term, which is -10 and is below y --> enters y
The ratio test on the Y column becomes following
So the operations are:
6
Now let's identify the pivot of row (2)
The pivot row is (2) and pivot = 1.5
Remember that
The pivot is the element of the table located in this specific position:
- in the column of the input variable (in this case, the y column)
- in the pivot row, the one chosen with the ratio test, in this example row (2)
So now we normalize row 2 by dividing by 1.5, and we get the following transformation of row (2)
The tableau now looks like this:
7
Now we reset the y column in (1) and Z.
For row (1), we need to make y=0, so We will apply the following transformation:
For row (z), we will have the following transformation:
The final tableau will be as follows:
There are no negative coefficients in row Z, which means that The optimum is reached.
Conclusions
The basic variables at the optimum are X=40 and y=20, meaning the simplex, with two pivots, yields x=40, y=20 with Z=2200. Note that both constraints are saturated and there is no unused capacity.
Question
As I wrote in yesterday's article, it was George Bernard Dantzig, shortly before 1950, who invented the simplex method for solving linear programming problems. Did you know that this calculation method is used today in the transportation and logistics sector? Did you know that the most advanced transport companies plan the transport of goods from warehouses to customers using the simplex method?
ITALIAN
26-09-2025 - Ricerca operativa - Il Simplesso e la forma tabellare [EN]-[IT]
Con questo post vorrei dare una breve istruzione a riguardo dell’argomento citato in oggetto
(codice lezione/articolo: MS_13)
immagine creata con l’intelligenza artificiale, il software usato è Microsoft Copilot
Introduzione
Il metodo del simplesso è un algoritmo creato per risolvere problemi di programmazione lineare piuttosto complessi. Nell'articolo di ieri avevo spiegato in linea generale di cosa di trattasse. Oggi invece mi vorrei dedicare di più a quello che è il tableau, che è la tabella iniziale per sviluppare il metodo del simplesso.
Tutta la fase di costruzione del tableau la salterò, ma come avevo promesso ieri, oggi cercherò di entrare più nel dettaglio delle operazioni da eseguire nel tableau per arrivare ad una soluzione.
tableau iniziale
Saltiamo quindi la parte in cui trasformiamo il problema in un problema di programmazione lineare e facciamo finta di aver già fatto tutto questo (vedi articolo di ieri).
Qui di seguito il tableau iniziale
L'obiettivo è massimizzare Z = 40x+30y
rispettando i seguenti vincoli:
2x+y≤100
x+2y≤80
x,y≥0
1
La prima cosa da fare è scegliere la variabile entrante della riga Z.
Il coefficiente più negativo è -40 sotto x --> entra x
Cosa significa "entra x" nel metodo del simplesso
Nel tableau iniziale, in base ci sono le variabili di scarto s1 e s2, mentre x e y hanno valore 0
La riga Z sostanzialmente ci da delle indicazioni di partenza. Ricordiamo che in questo problema vogliamo massimizzare, riporto qui sotto la funzione obiettivo.
L'obiettivo è massimizzare Z = 40x+30y
Quando guardiamo la riga Z, i coefficienti negativi indicano che aumentando quella variabile, possiamo far crescere la funzione obiettivo.
Andiamo quindi a selezionare il valore più negativo che è -40 ed è proprio nella colonna della x.
Dire che entra x significa che la variabile diventa una nuova variabile di base, ossia passerà da 0 ad un valore positivo. Possiamo anche dire che da questo momento in poi x parteciperà a trovare la soluzione e per questo motivo in gergo matematico si dice che "x entra in base".
Però una delle variabili già in base s1 o s2 saranno costrette ad uscire, cioè ad azzerarsi.
2
Dopo la scelta della variabile che entra, dobbiamo scegliere quella che esce.
Andiamo ora ad analizzare la colonna della variabile entrante che abbiamo detto che è la x
Per ogni riga, che rappresentano i vincoli, si fa il seguente rapporto:
Il test dei rapporti serve a decidere quale vincolo diventa attivo e quindi quale variabile di base esce.
Il rapporto più piccolo identificherà la riga pivot, cioè la riga in cui la variabile base uscirà e verrà sostituita.
Qui di seguito un immagine per chiarire quali sono i termini che si usano per il test dei rapporti
Il test dei rapporti da il seguente risultato.
Il rapporto indica quanto posso aumentare 𝑥 prima che il vincolo (1) venga saturato.
3
Ora passiamo al passo della normalizzazione del pivot
Stiamo lavorando sulla riga pivot (1) e il pivot è uguale a 2, cioè il coefficiente della variabile entrante x,
Il pivot è l'elemento della tabella che si trova in questa determinata posizione:
-nella colonna della variabile entrante (in questo caso nella colonna di x)
-nella riga pivot, quella scelta col test dei rapporti, in questo esempio la riga (1)
Quindi ora normalizziamo dividendo per 2, cioè prendiamo la riga 1 e la dividiamo per 2, diventerà come segue:
Quindi ora il tableau avrà la prima riga diversa da come era all'inizio e sarà così
4
Ora dobbiamo azzerare la colonna x in (2) e Z
per (2) eseguiremo la seguente trasformazione
per Z eseguiremo la seguente trasformazione
Quindi il tableau dopo il 1° pivot diventa come segue
5
Secondo pivot
In Z c'è il termine negativo che è -10 ed è sotto y --> entra y
Il test dei rapporti sulla colonna Y diventa il seguente
Quindi le operazioni sono
6
Ora individuiamo il pivot della riga (2)
La riga pivot è la (2) e pivot = 1.5
Ricordiamo che
Il pivot è l'elemento della tabella che si trova in questa determinata posizione:
-nella colonna della variabile entrante (in questo caso nella colonna di y)
-nella riga pivot, quella scelta col test dei rapporti, in questo esempio la riga (2)
quindi ora normalizziamo la riga 2 dividendo per 1,5 e avremo la seguente trasformazione della riga (2)
Il tableau ora è così
7
Ora azzeriamo la colonna y in (1) e Z
Per quanto riguarda la riga (1) dobbiamo far diventare y=0, quindi applicheremo la seguente trasformazione
Per quanto riguarda la riga (z) avremo la seguente trasformazione
Il tableau finale sarà il seguente
Nella riga Z non ci sono coefficienti negativi, questo significa che l'ottimo è raggiunto
Conclusioni
Le variabili di base nel punto di ottimo valgono X=40 e y=20, cioè il simplesso, in due pivot, fornisce x=40, y=20 con Z=2200. Da notare che entrambi i vincoli sono saturi e non resta capacità inutilizzata
Domanda
Come avevo scritto nell'articolo di ieri è stato George Bernard Dantzig, poco prima del 1950, ad inventare il metodo del simplesso per risolvere problemi di programmazione lineare. Sapevate che oggi questo metodo di calcolo viene usato nel settore dei trasporti e della logistica? Sapevate che le aziende di trasporti più avanzate pianificano i trasporti di merci da magazzini a clienti con il metodo del simplesso?
THE END