~~~ La versione in italiano inizia subito dopo la versione in inglese ~~~
ENGLISH
21-09-2025 - Operations Research - Simplex Exercise [EN]-[IT]
With this post, I would like to provide a brief instruction on the topic mentioned above.
(lesson/article code: MS_10)
Image created with artificial intelligence, the software used is Microsoft Copilot
Introduction
First of all, it's important to note that if you lack some basic knowledge of Operations Research, what follows may be difficult to understand, so I recommend moving straight to the conclusions and the final question/curiosity.
The table below represents a step in the simplex method procedure after Having completed the first steps.
The lines indicate the basic variables.
The -z line instead shows the reduced coefficients. These coefficients are useful for determining whether the solution is optimal or whether another step of the simplex method is necessary.
What you see from the tableau
From the tableau, you can see the current basis, which has:
the basic variables x1, x2, x4 (unit vector columns)
see image below for Clarification
The basic values are:
x1=1
x2=5
x4=2
See image below for clarification.
Non-basic variables are
x3=0
x5=0
Various considerations of the problem without considering the solution
If we were to maximize the input would be x5 where we would have the positive figure of 3/4
If we were to minimize the input would be x3 where we have the term -1/4
A summary of the considerations can be as follows.
-The current base is (x1,x2,x4)=(1,5,2)
-To maximize, x5 enters
-To minimize, x3 enters (x1 exits)
The variable that enters the base and the one that exits
Now what we need to do is determine which variable enters the base and which exits, trying to remember the simplex method.
Recall the following:
Result on the component
Interpreting the table as a minimization problem, we know that the negative --> enters.
So in this case, x3 enters; the only positive coefficient is on the row of x1, which would be 1/4. The ratio becomes 1/(1/4)=4, consequently, x1 exits.
So the final consideration is that:
x3 enters and x1 exits
Conclusions
A similar exercise is used to recognize a simplex tableau by recognizing the base and base values, choosing entering and exiting variables with a minimum ratio.
In practice, if this exercise had been created with variables related to product costs, it would indicate the best solution to reduce costs.
Question
Did you know that Russian mathematician Leonid Kantorovich used linear programming ideas like those discussed in this post to optimize wood cutting? Did you know that he created the root of the modern cutting, nesting, and planning problems we use in workshops today?
ITALIAN
21-09-2025 - Ricerca operativa - Esercizio relativo al simplesso [EN]-[IT]
Con questo post vorrei dare una breve istruzione a riguardo dell’argomento citato in oggetto
(codice lezione/articolo: MS_10)
immagine creata con l’intelligenza artificiale, il software usato è Microsoft Copilot
Introduzione
Innanzitutto è bene dire che se mancano alcune basi di Ricerca Operativa, ciò che è scritto qui di seguito potrebbe risultare poco comprensibile, quindi consiglio di passare subito alle conclusioni e alla domanda/curiosità finale.
La tabella qui sotto riportata rappresenta un punto della procedura del metodo del simplesso dopo aver eseguito i primi passaggi.
Le righe indicano le variabili di base
La riga -z mostra invece i coefficienti ridotti. Questi coefficienti sono utili per determinate se la soluzione è ottima oppure se è necessario fare un altro passaggio del metodo del simplesso.
Cosa si vede dal tableau
Dal tableau si vede la base corrente che ha:
le variabili di base x1,x2,x4 (colonne a vettore unitario)
vedi immagine sotto per chiarimento
I valori di base sono:
x1=1
x2=5
x4=2
Vedi immagine sotto per chiarimento
le variabili non di base sono
x3=0
x5=0
Considerazioni varie del problema senza considerare la soluzione
Se dovessimo massimizzare l'entrata sarebbe x5 dove avremmo la cifra positiva di 3/4
Se dovessimo minimizzare l'entrata sarebbe x3 dove abbiamo il termine -1/4
Un riassunto delle considerazioni può essere il seguente.
-La base attuale è (x1,x2,x4)=(1,5,2)
-Per massimizzare entra x5
-Per minimizzare entra x3 (esce x1)
La variabile che entra in base e quella che esce
Adesso quello che dobbiamo fare è determinare quale variabile entra in base e quale esce cercando di ricordare il metodo del simplesso.
Ricordiamo quanto segue:
Risultato sulla componente
Andando ad interpretare la tabella come un problema di minimizzazione sappiamo che il negativo --> entra
Quindi in questo caso entra x3, l'unico coefficiente positivo è sulla riga di x1, che sarebbe 1/4. Il rapporto diventa 1/(1/4)=4, di conseguenza esce x1
Quindi la considerazione finale è che:
entra x3 ed esce x1
Conclusioni
Un esercizio simile serve per riconoscere un tableau del simplesso riconoscendo base e valori di base, scegliere variabili entranti e uscenti con un rapporto minimo.
In pratica questo esercizio, se fosse stato creato con delle variabili relative ai costi di un prodotto, direbbe qual è la soluzione migliore per ridurre i costi.
Domanda
Sapevate che il matematico russo Leonid Kantorovich, usò idee di programmazione lineare come quelle trattate in questo post per ottimizzare il taglio del legno? Sapevate che egli creò la radice dei moderni problemi di taglio, nesting e pianificazione che usiamo oggi nelle officine?
THE END