~~~ La versione in italiano inizia subito dopo la versione in inglese ~~~
ENGLISH
21-08-2025 - Operations Research - Optimization on Graph Networks [EN]-[IT]
With this post, I would like to provide a brief introduction to the topic mentioned above.
(code notes: X_73)
Image created with artificial intelligence, the software used is Microsoft Copilot
Introduction
Operations research is a relatively young discipline, introduced around 1950. Its goal is to solve complex organizational and optimization problems. For example, this discipline is used to calculate the maximum profit of a product line, the best efficiency in saving company costs, or the best route for a fleet of trucks transporting goods.
Today we're talking about something very important and directly related to operations research: network optimization.
What is network optimization?
First of all, let's start by saying that network optimization studies problems in which variables and constraints can be represented by a network, that is, a set of nodes connected by arcs or branches.
This representation is also called a graph.
Graph Theory
Image created with artificial intelligence, the software used is Napkin.ai
Graph theory studies the main properties of graphs, which, as we will see, are a very useful abstract data structure for representing a wide range of physical structures. These will help us make better decisions.
Some consider graph theory one of the most prolific and interesting fields of applied mathematics and discrete optimization.
Graph theory can be applied in the following areas:
─ Communication network design and optimization
─ Transportation network design and optimization
─ Production and storage facility location
─ Data clustering
─ Production and distribution planning
─ Transportation problems
Example of a graph
Below is an example of a graph.
Image created with artificial intelligence, the software used is ChatGPT
In the image above, we see a weighted undirected graph where:
The circles
The circles are the network nodes, and in this example we see 8 of them. They can represent cities, stations, servers, or warehouses.
The connections
The connections between the circles, or rows, are the connections between the various nodes; that is, they represent the connections that a given node can have.
The numbers written on the rows*
The number we see written on the row (also called an arc) is the cost associated with that connection. I mentioned cost to better understand the importance of the row, but it can be a mass or a time; in essence, they are the weights of the graph.
How to read it
In the image above, there is information. This information is as follows. There is a connection with weight 1 between node 1 and node 2 (for example: distance = 1 km).
Here's another example.
Between node 3 and node 8, the weight is 5.
Shortest path
Now imagine connecting node 1 to node 7
If we wanted to calculate the shortest path between node 1 and node 7, we would consider all possible paths and choose the one with the lowest total weight.
From node 1, we would go to node 3 passing through the arc with weight 1... and then we would continue the path traversing the arcs with the lowest weights.
The solution is below.
Conclusions
Network optimization is of fundamental importance in operations research. Network optimization seeks to determine the best solution, which may be the cheapest, fastest, or most efficient, while respecting capacity, cost, or flow constraints. We can confidently conclude that this part of optimization is widely used in solving problems of practical interest.
Question
I believe Operations Research and Graph Theory isn't yet widely taught in Italian schools. So I'm asking you: Have you ever heard of graphs? Have you ever solved even one in school?
ITALIAN
21-08-2025 - Ricerca operativa - Ottimizzazione su reti Grafi [EN]-[IT]
Con questo post vorrei dare una breve istruzione a riguardo dell’argomento citato in oggetto
(code notes: X_73)
immagine creata con l’intelligenza artificiale, il software usato è Microsoft Copilot
Introduzione
La ricerca operativa è una disciplina abbastanza giovane che è stata introdotta intorno al 1950. Questa disciplina ha l'obiettivo di risolvere problemi complessi di organizzazione e di ottimizzazione. Ad esempio, si applica questa disciplina per calcolare il profitto massimo di una linea di prodotti, la miglior efficienza nel risparmio dei costi aziendali o il miglior tragitto che possono compiere una flotta di camion che trasportano merci.
Oggi parliamo di una cosa molto importante e che riguarda proprio la ricerca operativa, ovvero, l'ottimizzazione su reti.
Cosa è l'ottimizzazione su reti
Innanzi tutto partiamo con il dire che l'ottimizzazione su reti è studia problemi in cui le variabili e i vincoli sono rappresentabili tramite una reta, ovvero un insieme di nodi collegati da archi o rami.
Questa rappresentazione viene chiamata anche grafo.
Teoria dei grafi
immagine creata con l’intelligenza artificiale, il software usato è Napkin.ai
La Teoria dei grafi si occupa di studiare le principali proprietà dei grafi, che come vedremo sono una struttura dati astratta molto utile a rappresentare una vasta gamma di strutture fisiche. Questi aiuteranno a prendere le decisioni migliori.
Qualcuno considera la teoria dei grafi come uno dei settori più prolifici e interessanti della matematica applicata e dell’ottimizzazione discreta.
La teoria dei grafi può essere applicata nei seguenti ambiti:
─ progetto e ottimizzazione di reti di comunicazione
─ progetto e ottimizzazione di reti trasporto
─ localizzazione degli impianti di produzione e di stoccaggio
- clustering dei dati
─ pianificazione della produzione e della distribuzione
─ problema del trasporto
Esempio di un grafo
Qui di seguito l'esempio di un grafo.
immagine creata con l’intelligenza artificiale, il software usato è ChatGPT
Nell'immagine qui sopra riportata vediamo precisamente un grafo pesato non orientato dove:
I cerchi
I cerchi sono i nodi della rete ed in questo esempio ne vediamo 8. Essi possono raffigurare delle città, delle stazioni, dei server oppure dei magazzini.
I collegamenti
I collegamenti tra i cerchi, ovvero le righe, sono i collegamenti tra i vari nodi, cioè rappresentano le connessioni che quel determinato nodo può avere.
I numeri scritti sulle righe*
Il numero che vediamo scritto sulla riga (detta anche arco) è il costo associato a quel collegamento. Ho parlato di costo per far capire meglio l'importanza della riga, ma può essere una massa o un tempo, comunque, in sostanza, sono i pesi del grafo.
Come si legge
Nell'immagine sopra riportata c'è un informazione. Questa informazione è la seguente. Tra il nodo 1 e il nodo 2 c’è un collegamento con peso 1 (ad esempio: distanza = 1 km)
Qui di seguito un altro esempio
Tra il nodo 3 e il nodo 8 il peso è 5.
Percorso minimo
Immaginiamo ora di pensare di collegare il nodo 1 al nodo 7
Se volessimo calcolare il percorso minimo tra nodo 1 e nodo 7, prenderemmo in considerazione tutti i cammini possibili e sceglieremmo quello con il peso totale più basso.
Dal nodo 1 andremo al 3 passando per l'arco con peso 1...e poi andremo a proseguire il percorso attraversando gli archi con minor peso.
Qui di seguito la soluzione
Conclusioni
In ricerca operativa l’ottimizzazione su reti ha un'importanza fondamentale. L'ottimizzazione su reti cerca di determinare la soluzione migliore, che può essere la più economica, la più veloce, oppure la più efficiente, rispettando vincoli di capacità, costi o flussi. Possiamo concludere affermando con sicurezza che questa parte dell’ottimizzazione è largamente impiegata nella soluzione di problemi di pratico interesse.
Domanda
Io credo che Ricerca operativa e la teoria dei grafi non sia ancora molto diffusa nelle scuole italiane. Per questo vi chiedo se avete mai sentito parlare dei grafi? Ne avete mai risolto anche solo uno a scuola?
THE END