~~~ La versione in italiano inizia subito dopo la versione in inglese ~~~
ENGLISH
09-10-2025 - Operations Research - 3-Variable Exercise [EN]-[IT]
With this post, I would 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
Below is a linear programming exercise in which:
-Transform the problem into standard form.
-Write the tabular form of the basic feasible solution derived from the standard form.
-Check whether the basic feasible solution is optimal and, if necessary, perform an appropriate pivot operation.
WARNING: You decide whether or not to read this post. The content may give you a severe headache. I will not assume any responsibility.
Exercise
Transformation of the problem into standard form
Introduce the slack variables s1 and s2, which will both be ≥ 0.
Below is the transformation of the problem into standard form with the two constraints, the objective function and the positivity constraint. variables
BFS (Basis of Rejections) Table
The initial basis B = { s1,s2}
non-basic x1=x2=x3=0
To construct the initial basic feasible solution (BFS), set the non-basic variables
x1=x2=x3=0
to zero and solve the constraints for the variables Base
So:
x1=x2=x3=0, s1=3, s2=0
It is said to be degenerate because at least one base variable is zero.
Therefore, the BFS (basis of the wastes) is degenerate.
Initial tableau
Below is the construction of the initial tableau after the transformation into standard form.
The basic feasible solution is not optimal because the z row of the initial table contains a negative coefficient (-2).
For a maximization problem, if any reduced cost is negative, the basis is not optimal.
Optimality and Pivot
Entering Variable
The first thing to identify is the entering variable, which corresponds to the column in which z has the most negative coefficient. In this case, we're on the x1 column, so x1 enters.
Outgoing variable
To identify the outgoing variable, the ratio test is performed.
The ratios are calculated for each of the rows representing the constraints and are the value in column b divided by the corresponding value in the input variable column.
So in this case we have
row 1, s1: 3/1 = 3
row 2, s2: coefficient 0 (no constraints)
So the minimum ratio at the end is s1 because x = 0 -> it is not considered.
The output variable is s1 (the only valid ratio).
The pivot element
The pivot element will be the coefficient that comes out of the intersection between the input variable column x1 and the output variable column. s1
In this exercise, the pivot element is 1.
New row 1
To obtain the new row, we divide by the pivot element, which we know is 1.
So, the new row 1 will be equal to the previous one, and It will be
We normalized the pivot row
Reset column x1 in the other rows
Row (2) the coefficient on x1 is 0 so it doesn't change
The row will remain the same
New row z
Row (z) the coefficient on x1 is -2
To calculate the new row Z we must perform the following normalization: New Row Z = Row z - (the coefficient of the pivot column p in row Z) * (row 1)
So the values will be as follows:
x1 = -2 - (-2) * (1) = 0
x2 = 0 - (-2) * (1) = 2
x3 = 1 - (-2) * (0) = 1
s1 = 0 - (-2) * (1) = 2
s2 = 0 - (-2) * (0) = 0
b = 0 - (-2) * (3) = 6
So the new row z will be equal to the previous one and will be
Tableau after the first transformation
We can conclude that x1 = 3, s2 = 0, non-basic x2 = x3 = s1 = 0, and z = 6.
In the z row, all coefficients are ≥ 0, meaning the optimum has been reached.
Optimal Solution
x1=3
x2=0
x3=0
z = 6
Conclusions
The optimal solution is x1=3, x2=0, x3=0, z = 6, which, when applied to the objective function and the constraints, is verified as follows:
first Constraint
Second Constraint
Question
The simplex method is one of the masterpieces of operations research and linear optimization, developed by George Dantzig in 1947.
Did you know he devised it during World War II to optimize the allocation of military and logistical resources?
Did you know that Dantzig devised this mathematical magic in two weeks?
ITALIAN
09-10-2025 - Ricerca operativa - Esercizio a 3 variabili [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
Qui di seguito un esercizio di programmazione lineare in cui:
-Si trasforma il problema in forma standard
-Si scrive la forma tabellare della soluzione di base ammissibile ricavabile dalla forma standard
-Verificare se la soluzione di base ammissibile è ottima e, eventualmente, effettuare un’opportuna operazione pivot
AVVISO: Siete voi a scegliere se leggere o meno questo post. Il contenuto potrebbe causarvi un forte mal di testa; io non mi assumerò alcuna responsabilità.
Esercizio
trasformazione del problema in forma standard
Si introducono le variabili di slack s1 e s2 che saranno entrambe ≥ 0
Qui di seguito la trasformazione del problema in forma standard con i due vincoli, la funzione obiettivo e il vincolo di positività delle variabili
Tabella della BFS (base degli scarti)
La base iniziale B = { s1,s2}
non di base x1=x2=x3=0
Per costruire la soluzione di base ammissibile iniziale (BFS) si pongono a zero le non di base
x1=x2=x3=0
e si risolvono i vincoli per le variabili di base
Quindi:
x1=x2=x3=0, s1=3, s2=0
Si dice degenere perché almeno una variabile di base vale zero
Quindi la BFS (base degli scarti) è degenere
Tableau iniziale
Qui di seguito la costruzione del tableau iniziale dopo la trasformazione in forma standard.
La soluzione di base ammissibile non è ottima perché nella riga di z della tabella iniziale c’è un coefficiente negativo (-2)
Per un problema di massimizzazione se qualche costo ridotto è negativo la base non è ottima.
Ottimalità e pivot
Variabile entrante
La prima cosa da individuare è la variabile entrante e questa corrisponde alla colonna in cui Z presenta il coefficiente più negativo. In questo caso siamo sulla colonna di x1, quindi entra x1
Variabile uscente
Per identificare la variabile uscente si esegue il test dei rapporti.
I rapporti si eseguono per ognuna delle righe che rappresentano i vincoli ed è il conto della colonna b diviso il valore corrispondente nella colonna della variabile entrante
Quindi in questo caso avremo
riga 1, s1: 3/1 = 3
riga 2, s2: coefficiente 0 (nessun vincolo)
Quindi il rapporto minimo alla fine è s1 perché x=0 -> non si considera
La variabile uscente è s1 (unico rapporto valido)
L’elemento pivot
L’elemento pivot sarà il coefficiente che esce fuori dall’incrocio tra la colonna della variabile entrante x1 e quella uscente s1
Nel caso di questo esercizio l’elemento pivot è 1
Nuova riga 1
Per ottenere la nuova riga uno dividiamo per l’elemento pivot, che sappiamo che è 1
Quindi la nuova riga 1 sarà uguale alla precedente e sarà
Abbiamo normalizzato la riga pivot
Azzeramento della colonna x1 nelle altre righe
Riga (2) il coefficiente su x1 è 0 quindi non cambia
La riga rimarrà la stessa
Nuova riga z
Riga (z) il coefficiente su x1 è -2
Per calcolare la nuova riga Z dobbiamo eseguire la seguente normalizzazione Nuova Riga Z = Riga z - (il coefficiente della colonna pivot p nella riga Z)* (riga 1)
Quindi i valori saranno i seguenti
x1= -2 - (-2) * (1) = 0
x2= 0 - (-2) * (1) = 2
x3= 1 - (-2) * (0) = 1
s1= 0 - (-2) * (1) = 2
s2= 0 - (-2) * (0) = 0
b= 0 - (-2) * (3) = 6
Quindi la nuova riga z sarà uguale alla precedente e sarà
Tableau dopo la prima trasformazione
Possiamo concludere che x1=3, s2=0, non base x2=x3=s1=0 e z =6.
Nella riga z tutti i coefficienti sono ≥ 0, questo significa che si è raggiunto l’ottimo
Soluzione ottima
x1=3
x2=0
x3=0
z = 6
Conclusioni
La soluzione ottima è x1=3, x2=0, x3=0, z = 6 che applicata alla funzione obiettivo e ai vincoli è verificata come segue
primo vincolo
secondo vincolo
Domanda
Il metodo del simplesso è uno dei capolavori della ricerca operativa e dell’ottimizzazione lineare ideato da George Dantzig nel 1947.
Sapevate che lo ideò durante la Seconda Guerra Mondiale per ottimizzare l’allocazione delle risorse militari e logistiche?
Sapevate che questa magia matematica, Dantzig la ideò in due settimane?
THE END