09-10-2025 - Operations Research - 3-Variable Exercise [EN]-[IT]

image.png


~~~ 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.png

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

image.png

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

image.png

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

image.png

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.

image.png

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.

image.png

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.

image.png

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

image.png

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

image.png

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

image.png

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

image.png

Tableau after the first transformation

image.png

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:

image.png

first Constraint

image.png

Second Constraint

image.png

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)

image.png

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

image.png

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

image.png

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

image.png

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.

image.png

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

image.png

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

image.png

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

image.png

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à

image.png

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

image.png

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à

image.png

Tableau dopo la prima trasformazione

image.png

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

image.png

primo vincolo

image.png

secondo vincolo

image.png

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



0
0
0.000
5 comments
avatar

Two weeks, wow, I would have treated myself for a thousand years.

Due settimane, wow, mi sarei concesso un trattamento per mille anni.

untitled.gif

0
0
0.000
avatar

Actually at one point, the post wants to start giving me severe headaches 😂

0
0
0.000
avatar

haha mi è piacuta molto la premessa, comunque penso che questo problema sarebbe stato complicato da risolvere anche per i miei professori universitari 😂

!PIZZA

0
0
0.000
avatar

Si ripete la data del 1947. Un risultato fantastico, considerando l'epoca e la situazione bellica.
Continuerò a lavorare e ad ascoltare le notizie.
Ti auguro un felice giovedì.

0
0
0.000