08-10-2025 - Operations Research - Simplex Exercise [EN]-[IT]

---

~~~ La versione in italiano inizia subito dopo la versione in inglese ~~~

---

ENGLISH

08-10-2025 - Operations Research - Simplex Exercise [EN]-[IT]
With this post, I'd like to provide a brief instruction on the topic in question.
(lesson/article code: EX_LZ_12)

image created with artificial intelligence, the software used is Microsoft Copilot

Introduction
WARNING: This post might make you dizzy.
hihihihi!
I'm trying to write this post to demonstrate the simplex method. In linear programming, the simplex method is an algorithm used to solve linear optimization problems, that is, problems in which one seeks to maximize or minimize a linear objective function subject to linear constraints. We could almost say it's magic. Those who master it can find the optimal solution in a very short time, a bit like magic. In just a few minutes, you'll find the best solution... then you're tempted to explore the other 1,000 solutions, but none will be better than the one you find by applying the simplex method.

Let's look at an exercise below. My intention is to demonstrate some little-known aspects of mathematics.

Exercise
Below is a linear programming exercise solved using the simplex method.
Objective Function

Constraints

Solution
Below is the exercise solved using the simplex method.
Transformation to Standard Form
First, we perform the usual transformation of the linear programming problem into standard form. We then also introduce the slack variables s1 and s2.

Initial Tableau
Now let's build the initial tableau where we have s1, s2, and Z as rows, and x1, x2, s1, and s2 as columns. The known coefficients will become negative since it is a maximization problem.

First iteration
In this phase, we need to understand which variable will enter and which will exit.
Now we need to determine which is the most negative known coefficient, and based on that, we will know which variable will enter the base. In this case, the most negative coefficient on the Z row is that of x2. Therefore, x2 enters the base.
Now, let's calculate the minimum ratio to understand which variable will exit.
The minimum ratio is calculated by dividing the term in the "solution" column by the coefficient of x2.

The two ratios will therefore be
row 1 (s1) = 4/1=4
row 2 (s2) = 3/0=(undefined, therefore not eligible)
The minimum ratio is 4, so the pivot row will be the first, that of s1, so the output variable will be s1.
Pivot Element
The pivot element is found by intersecting column x2 (the one containing the input variable) and row s1, i.e., the Pivot Row (the one we just identified). In our case, the pivot element is 1.

First tableau transformation
Data summary:
The most negative Z-row coefficient is -3, which is found on the x2 column, and therefore x2 enters the base.
The minimum ratio is 4, so the pivot row is s1.
The pivot element is the intersection between column x2 and row s1, so it is 1.
New row x2
We must now update the new row x2 by dividing by 1.
The new row x2 will be as follows:
[1,1,1,0,4]
We have normalized the pivot column x2.
Update row Z.
We eliminate x1 (coefficient 1).
In this case, we must apply the pivot rule, which is as follows:

Where ai,p is the coefficient of the pivot column p in row i.
In this case, the pivot column = x2 (because it enters x2)
the pivot row = s1 already normalized [1 1 1 0 ∣ 4]
coefficient in row Z on column x2: az,p=-3
So it would be

So let's transform row Z with the goal of zeroing x2

x1 will become: -2 + 3(1) = 1
x2 will become: -3 + 3(1) = 0
s1 will become: 0 + 3(1) = 3
s2 will become: 0 + 3(0) = 0
RHS will become: 0 + 3(4) = 12
The new row Z will become [1 0 3 0 ∣ 12]

The tableau after the first Iteration

Now the basis is x2,s2
In row Z, there are no longer negative coefficients in the decision variable columns, which means we've reached the optimum.
The optimal solution
The basic variables are x2 and s2. Now I set the non-basic variables to zero, so x1=0 and s1=0.
Let's report the objective function and the constraints.

Let's verify the value of x2 by performing the first equality, knowing that x1=0 and s1=0

Let's verify the value of S2 by solving the second equality, knowing that x1=0 and s1=0.

Let's now verify Z

The optimal solution is with x1=0 and x2=4

Constraint Verification
Verify the first constraint

Verify the second constraint Constraint

Conclusions
The first iteration chooses x2 because it maximizes the improvement, identifies s1 as the outgoing solution with ratio tests, and a pivot already achieves optimality: x1=0, x2=4, Z=12

Question
The genius who invented this method was the American mathematician George Dantzig, in 1947.
Did you know that this mathematical method can identify, without error, the best possible solution among all 1,000 solutions that could be generated by a linear programming problem?

---

---

ITALIAN

08-10-2025 - Ricerca operativa - Esercizio svolto con il simplesso [EN]-[IT]
Con questo post vorrei dare una breve istruzione a riguardo dell’argomento citato in oggetto
(codice lezione/articolo: EX_LZ_12)

immagine creata con l’intelligenza artificiale, il software usato è Microsoft Copilot

Introduzione
ATTENZIONE: Post che potrebbe far venire le vertigini.
hihihihi!
Provo a fare questo post per mostrare il metodo del simplesso. In programmazione lineare il metodo del simplesso è un algoritmo utilizzato per risolvere problemi di ottimizzazione lineare, cioè problemi in cui si cerca di massimizzare o minimizzare una funzione obiettivo lineare soggetta a vincoli lineari. Possiamo quasi dire che è magia. Chi lo sa padroneggiare, riesce ad individuare la soluzione ottima in pochissimo tempo, un po' come una magia. In pochi minuti si trova qual è la soluzione migliore da prendere... poi uno è tentato ad esplorare le altre 1000 soluzioni, ma nessuna sarà meglio di quella che verrà fuori applicando il metodo del simplesso.
Vediamo qui di seguito un esercizio. La mia intenzione è quella di mostrare alcuni aspetti della matematica poco conosciuti.

Esercizio
Qui di seguito un esercizio di programmazione lineare risolto con il metodo del simplesso.
Funzione obiettivo

Vincoli

Svolgimento
Qui di seguito l’esercizio svolto con il metodo del simplesso.
Trasformazione in forma standard
Per prima cosa facciamo la solita trasformazione del problema di programmazione lineare in forma standard. Introduciamo quindi anche le variabili di slack s1 e s2.

Tableau iniziale
Costruiamo ora il tableau iniziale dove avremo come righe s1,s2 e Z, mentre come colonne avremo x1,x2,s1,s2. I coefficienti noti diventeranno negativi in quanto è un problema di massimizzazione

Prima iterazione
In questa fase dobbiamo comprendere quale variabile entrerà e quale uscirà.
Ora dobbiamo vedere qual è il coefficiente noto più negativo e in base a quello sapremo quale sarà la variabile che entra in base. In questo caso il coefficiente della riga Z più negativo è quello di x2. Quindi x2 entra nella base.
Eseguiamo ora il calcolo del rapporto minimo per comprendere quale sarà la variabile uscente.
Il rapporto minimo si calcola facendo il rapporto tra il termine che c’è nella colonna “soluzione” e il coefficiente di x2

I due rapporti saranno quindi
riga 1 (s1) = 4/1=4
riga 2 (s2)= 3/0=(non definito, quindi non candidabile)
Il rapporto minimo è 4, quindi la riga pivot sarà la prima, quella di s1, quindi la variabile uscente sarà s1.
Elemento Pivot
L’elemento pivot si trova facendo l’intersezione tra la colonna x2 (quella della variabile entrante) e la riga s1, cioè la riga Pivot (quella che abbiamo appena individuato). Nel nostro caso l’elemento pivot è 1

Prima trasformazione del tableau
Riassunto dei dati:
Il coefficiente della riga Z più negativo è -3, si trova sulla colonna di x2 e quindi x2 entra in base
Il rapporto minimo è 4, quindi la riga pivot è s1.
L’elemento pivot è l’intersezione tra la colonna x2 e la riga s1, quindi è 1
Nuova riga x2
Dobbiamo ora aggiornare la nuova riga x2 dividendo per 1
La nuova riga x2 sarà la seguente
[1,1,1,0,4]
Abbiamo normalizzato la tiga pivot x2
Aggiornamento riga Z
Eliminiamo x1 (coefficiente 1)
In questo caso dobbiamo applicare la regola del pivot che è la seguente

Dove ai,p è il coefficiente della colonna pivot p nella riga i
In questo caso la colonna pivot = x2 (perché entra x2)
la riga pivot = s1 già normalizzata [1 1 1 0 ∣ 4]
coefficiente in riga Z sulla colonna x2:az,p=-3
Quindi sarebbe

Quindi andiamo a trasformare la riga Z con l’obiettivo di azzerare x2

x1 diventerà: -2 + 3(1) = 1
x2 diventerà: -3 + 3(1) = 0
s1 diventerà: 0 + 3(1) = 3
s2 diventerà: 0 + 3(0) = 0
RHS diventerà: 0 + 3(4) = 12
La nuova riga Z diventerà [1 0 3 0 ∣ 12]

Il tableau dopo la prima iterazione

Ora la base è x2,s2
Nella riga Z non ci sono più coefficienti negativi nelle colonne delle variabili decisionali, questo significa che abbiamo raggiunto l’ottimo.
La soluzione ottima
Le variabili di base sono x2 e s2, Ora metto a zero le non-base, quindi x1=0 e s1=0
Riportiamo la funzione obiettivo ed i vincoli

Verifichiamo il valore di x2 svolgendo la prima uguaglianza sapendo che x1=0 e s1=0

Verifichiamo il valore di S2 svolgendo la seconda uguaglianza sapendo che x1=0 e s1=0

Verifichiamo ora Z

La soluzione ottima è con x1=0 e x2=4

Verifica dei vincoli
verifica del primo vincolo

verifica del secondo vincolo

Conclusioni
La prima iterazione sceglie x2 perché massimizza il miglioramento, individua s1 come uscente con test dei rapporti e con un pivot si arriva già all’ottimalità: x1=0, x2=4, Z=12

Domanda
Il genio che si inventò questo metodo fu il matematico statunitense George Dantzig, nel 1947.
Sapevate che questo metodo matematico riesce ad individuare, senza errori, la miglior soluzione possibile tra tutte le 1000 soluzioni che potrebbe generare un problema di programmazione lineare?

THE END