~~~ La versione in italiano inizia subito dopo la versione in inglese ~~~
ENGLISH
04-07-2025 - Operations Research - Simplex Method [EN]-[IT]
With this post I would like to give a brief instruction about the topic mentioned in the subject
(code notes: X_87-86-85)
Simplex Method
image created with artificial intelligence, the software used is Microsoft Copilot
What is the simplex method
The simplex method is a method that is used in the field of operations research studies.
This method is used in particular to solve linear programming problems. In linear programming problems, one wants to maximize or minimize a linear function subject to constraints. These problems are studied to improve the production of a company, reduce the costs of a project or make calculations on population growth.
Its function described in a technical way
Technically we can say the following. The Simplex method, applied to a linear programming problem, proceeds iteratively generating a sequence of basic admissible solutions with non-increasing value of the objective function.
Main idea of the simplex method
image created with artificial intelligence, the software used is Napkin.ai
The simplex method starts from some basic ideas listed below:
1-It represents the problem in matrix form
2-It starts from a basic feasible solution
3-It moves from one vertex to another and improves the value of the objective function at each step.
4-It stops when it is no longer possible to improve, so it stops when the global maximum or minimum has been reached.
The steps of the simplex method
The simplex method is carried out in 5 fundamental steps, the generic iteration of the Simplex method is described below
1-Calculation of the reduced cost vector
2-Verification of the optimality criterion
3-Verification of the unboundedness criterion
4-Identification of the new feasible basic solution
5-Determination of the new canonical form
Structure of the simplex method
image created with artificial intelligence, the software used is Napkin.ai
-1-
Before starting the process of using the simplex method simplex you need to:
Verify that the problem is admissible and determine a first admissible basic solution.
-2-
Second thing to do, once the admissible basic solution has been determined, is divided into two parts:
2a-Determine a sequence of admissible basic solutions starting from the first
2b-Stop when the optimality or unboundedness criterion is satisfied.
Example
Let's try to maximize a mathematical problem respecting some constraints.
Mathematical problem:
Below are the constraints to be respected
The first thing to do is convert the constraints to equations
The second thing to do is to reconstruct the objective function in standard form.
After creating the initial simplex table we can identify the iterations of the simplex and then graphically find the problem and the optimal solution through a graph.
Below is the graph of the linear programming problem solved with the simplex method
image created with artificial intelligence, the software used is Microsoft Copilot
The blue region is the admissible region, that is, the set of all points that satisfy the constraints. The black and red points are the vertices of the admissible region and are the points that we can consider as optimal, of which one of those will be the absolute optimal.
The red point is the optimal point where the objective function reaches the maximum value.
Below is the calculation of the maximum value.
Conclusions
The simplex method is a tool used in linear programming. Basically, if we can transform a problem into a mathematical equation, we can understand with the simplex method what its maximum or minimum value is. This method is used to solve problems in economics, logistics, finance and industrial production.
Question
Did you know that the simplex method was invented by the American mathematician George Dantzig in 1947 to optimize military resources while he was working for the U.S. Air Force?
ITALIAN
04-07-2025 - Ricerca operativa - Metodo del simplesso [EN]-[IT]
Con questo post vorrei dare una breve istruzione a riguardo dell’argomento citato in oggetto
(code notes: X_87-86-85)
Metodo del simplesso
immagine creata con l’intelligenza artificiale, il software usato è Microsoft Copilot
Cosa è il metodo del simplesso
Il metodo del simplesso è un metodo che viene usato nell’ambito degli studi di ricerca operativa.
Questo metodo viene usato in particolare per risolvere problemi di programmazione lineare. Nei problemi di programmazione lineare si vuole massimizzare o minimizzare una funzione lineare soggetta a vincoli. Questi problemi vengono studiati per migliorare la produzione di un'azienda, abbattere i costi di un progetto o fare dei calcoli sulla crescita della popolazione.
La sua funzione descritta in maniera tecnica
Tecnicamente possiamo dire quanto segue. Il metodo del Simplesso, applicato ad un problema di programmazione lineare, procede iterativamente generando una sequenza di soluzioni di base ammissibili con valore non crescente della funzione obiettivo.
Idea principale del metodo del simplesso
immagine creata con l’intelligenza artificiale, il software usato è Napkin.ai
Il metodo del simplesso parte da alcune idee di base elencate qui di seguito:
1-Rappresenta il problema in forma matriciale
2-Parte da una soluzione di base ammissibile
3-Si muove da un vertice all’altro e migliora il valore della funzione obiettivo a ogni passo.
4-Si ferma quando non è più possibile migliorare, quindi significa che si ferma quando si è raggiunto il massimo o il minimo globale.
I passi del metodo del simplesso
Il metodo del simplesso si svolge in 5 passi fondamentali, qui di seguito è descritta la generica iterazione del metodo del Simplesso
1-Calcolo del vettore dei costi ridotti
2-Verifica del criterio di ottimalità
3-Verifica del criterio di illimitatezza
4-Identificazione della nuova soluzione di base ammissibile
5-Determinazione della nuova forma canonica
Struttura del metodo del simplesso
immagine creata con l’intelligenza artificiale, il software usato è Napkin.ai
-1-
Prima di iniziare il processo di utilizzo del metodo del simplesso bisogna:
Verificare che il problema sia ammissibile e determinare una prima soluzione di base ammissibile.
-2-
Seconda cosa da fare, una volta determinata la soluzione di base ammissibile, si divide in due parti:
2a-Determinare una sequenza di soluzioni di basi ammissibili a partire dalla prima
2b-Arrestarsi quando il criterio di ottimalità o di illimitatezza sono soddisfatti.
Esempio
Proviamo a massimizzare un problema matematico rispettando dei vincoli.
Problema matematico:
Qui di seguito i vincoli da rispettare
La prima cosa da fare è convertire i vincoli in equazioni
La seconda cosa da fare è ricostruire la funzione obiettivo in forma standard.
Dopo aver creato la tabella iniziale del simplesso possiamo identificare le iterazioni del simplesso e poi trovare graficamente il problema e la soluzione ottima attraverso un grafico.
Qui di seguito il grafico del problema di programmazione lineare risolto con il metodo del simplesso
immagine creata con l’intelligenza artificiale, il software usato è Microsoft Copilot
La regione azzurra è la regione ammissibile, cioè l’insieme di tutti i punti che soddisfano i vincoli. I punti neri e rossi sono i vertici della regione ammissibile e sono i punti che possiamo considerare come ottimi di cui uno di quelli sarà proprio l’ottimo in assoluto.
Il punto rosso è il punto di ottimo dove la funzione obiettivo raggiunge il massimo valore.
Qui di seguito il calcolo del massimo valore.
Conclusioni
Il metodo del simplesso è uno strumento usato nell’ambito della programmazione lineare. Sostanzialmente, se riusciamo a trasformare un problema in un'equazione matematica, possiamo capire con il metodo del simplesso qual’è il suo valore massimo o minimo. Questo metodo viene usato per risolvere problemi di economia, logistica, finanza e produzione industriale.
Domanda
Lo sapevate che il metodo del simplesso fu inventato dal matematico statunitense George Dantzig nel 1947 per ottimizzare le risorse militari mentre lavorava per l’U.S. Air Force?
THE END