~~~ La versione in italiano inizia subito dopo la versione in inglese ~~~
ENGLISH
29-11-2025 - Operations Research - The LP Problem [EN]-[IT]
With this post, I would like to provide a brief introduction to the topic in question.
(lesson/article code: MS_02)
Image created with artificial intelligence, the software used is Microsoft Copilot
Introduction
Let's start from the beginning. What is a linear programming problem?
A linear programming problem is a particular type of optimization problem. A linear programming problem minimizes or maximizes a linear function in the decision variables.
A linear function is defined as one that can be expressed as a linear combination of the decision variables.
In other words, a linear function is a mathematical function of the type
Where a and b are real numbers and their graph is a straight line in the Cartesian plane.
Recall that the real numbers are the set of natural, integer, rational, and irrational numbers.
Example of an exercise
I should point out that in this post, we will see how to perform a linear programming exercise without going into the details of each operation, but we will nevertheless show all the steps to reach the solution.
Let's consider the following maximization exercise.
Standard Form
The first thing we must do when performing a linear programming exercise is transform it into standard form. This transformation is necessary to be able to perform all subsequent operations. Transforming a linear programming problem into standard form means manipulating its original formulation into a specific form that is particularly useful for applying solution algorithms. Not performing this transformation means complicating our lives right from the start.
To perform the transformation of the proposed linear programming problem, we will first need to introduce the slack variables and recompose our problem into standard form, which will appear as follows (the slack variables are in red):
The objective function, on the other hand, will change as follows: follows:
Initial base and basic solutions
The initial base will be:
Initial basic solution will be:
The concept of an initial basis is as follows. In linear programming problem-solving methods, the initial basis is the first feasible basis from which the algorithm starts.
The initial basic solution, on the other hand, is the first feasible basic solution from which the Simplex algorithm can begin its iterations.
The Simplex Table
At this point comes what we can consider the third phase, which is when we enter the heart of the solution construction process.
We begin building the simplex table.
In the simplex table, the columns will be built on the variables and then finally on the known term (usually described as RHS).
So the columns will be x1, x2, s1, s2 ∣ RHS
Below is how the simplex table will appear.
The first iteration
Identifying the entering variable
At this point, the simplex algorithm begins.
In row z, we must identify the coefficients of the non-basic variables x1 and x2, which are -3 and -5.
To maximize, we take the most negative coefficient, which in this case is -5 and corresponds to x2.
Identifying the leaving variable
To identify the leaving variable, we must use the ratio test.
This test is performed between the terms in the RHS column and those of the entering variable identified in the previous step.
We'll have that in the first row the ratio will be 8/2=4, while in the second 12/2=6.
The row with the lowest ratio is (1), so S1 comes out.
We won't need it at this stage, but we now know that the Pivot element is in row 1, in column x2, and is 2
Normalization of row (1)
We divide the entire row (1) by the Pivot element, then by 2.
We will then have the new row 1.
Now Let's calculate the new Z row by considering the following operations, with the main goal of eliminating x2, which is -5 (so the value I'll need to calculate for the z transformation will be +5):
Below is the old z row
And below is the new Row 1
Below are all the calculations for the new row z.
Row (2) must also be transformed (normalized) by eliminating x2, where in this case we have the coefficient 2
Below is the old line 2
Below line 1 Transform
Below is an example of the mathematical iteration to reconstruct row 2.
Here's what the new table looks like after the first iteration. complete
Now the current bases are x2 (line 1) and s2 (line 2)
Second iteration
Let's start with the method we ran previously.
I'll go faster with the description.
Calculating the entering variable
Let's check the most negative coefficient in Z.
We find it on x1.
So x1 enters.
Outgoing variable
In line (1) we have 4/(1/2)=8
In row (2) we have 4/2=2
The minimum result is on row (2), so we get S2 (row 2)
Continuation
From here on, we perform the same procedure as before to:
-normalize row (2)
-eliminate x1 from row Z
-eliminate x1 from row (1)
We will therefore obtain the final table.
Optimal Solution
The basic variables are x2 (line 1) and x1 (line 2), setting the non-basic variables s1=s2=0
So x1=2 while x2=3
Now, let's take our objective function and calculate the value Excellent
We can try a million other ways or do other tests, but we won't find a better result than this one with this objective function and the constraints we were given
Conclusions
Solving linear programming problems can provide excellent support for solving complex decision-making problems. This type of calculation is excellent for solving problems in business environments (production or cost reduction problems) or in logistics.
Question
Did you know that companies perform calculations similar to those shown in this post to improve the production of certain products and specific production departments?
Did you know that the calculation method shown in this post was invented by American mathematician George Bernard Dantzig in 1947?
ITALIAN
29-11-2025 - Ricerca operativa - Il problema di PL [EN]-[IT]
Con questo post vorrei dare una breve istruzione a riguardo dell’argomento citato in oggetto
(codice lezione/articolo: MS_02)
immagine creata con l’intelligenza artificiale, il software usato è Microsoft Copilot
Introduzione
Partiamo dall'inizio. Che cosa è un problema di programmazione lineare?
Un problema di programmazione lineare è una particolare tipologia di problema di ottimizzazione. Quello che fa un problema di programmazione lineare è minimizzare o massimizzare una funzione lineare nelle variabili di decisione.
Una funzione lineare si definisce così quando può essere espressa come una combinazione lineare delle variabili di decisione.
Possiamo dire in altre parole che una funzione lineare è una funzione matematica del tipo
Dove a e b sono numeri reali ed il suo grafico è una retta nel piano cartesiano.
Ricordiamo che i numeri reali è l'insieme dei numeri naturali, interi, razionali e irrazionali.
Esempio di un esercizio
Preciso che in questo post vedremo come si svolge un esercizio di programmazione lineare senza entrare nei dettagli di ogni operazione, ma mostrando comunque tutti i passaggi per arrivare alla soluzione.
Consideriamo il seguente esercizio di massimizzazione.
Forma standard
La prima cosa che dobbiamo fare quando eseguiamo un esercizio di programmazione lineare è trasformarlo in forma standard. Questa trasformazione è necessaria per poter svolgere tutte le operazioni successive. Trasformare un problema di Programmazione Lineare in forma standard significa manipolare la sua formulazione originale in una forma specifica che è particolarmente utile per l'applicazione di algoritmi di soluzione. Il non eseguire questa trasformazione significa complicarsi la vita sin da subito.
Per eseguire la trasformazione del problema di programmazione lineare proposto prima dovremo introdurre le variabili di slack e ricomporre il nostro problema in forma standard, che apparirà come segue (in rosso le variabili di slack)
La funzione obiettivo invece cambierà come segue:
Base iniziale e soluzioni di base
La base iniziale sarà:
Soluzione di base iniziale sarà:
Il concetto di base iniziale è il seguente. Nei metodi di risoluzione di un problema di programmazione lineare la base iniziale è la prima base ammissibile dalla quale l'algoritmo prende avvio.
La soluzione di base iniziale invece è la prima soluzione di base ammissibile a partire dalla quale l'algoritmo del Simplesso può iniziare le sue iterazioni
La tabella del simplesso
A questo punto arriva quella che possiamo considerare la terza fase, cioè si entra nel vivo della costruzione delle soluzioni.
Si inizia a costruire la tabella del simplesso.
Nella tabella del simplesso si andranno a costruire le colonne sulle variabili e poi infine sul termine noto (solitamente descritto come RHS)
Quindi le colonne saranno x1,x2,s1,s2 ∣ RHS
Qui di seguito ecco come apparirà la tabella del simplesso
La prima iterazione
Identificazione della variabile entrante
A questo punto inizia la procedura algoritmica del simplesso.
Nella riga z dobbiamo individuare i coefficienti delle non di base x1,x2 che sono -3 e -5
Per massimizzare si prende il coefficiente più negativo, che in questo caso è -5 e corrisponde a x2
Identificazione della variabile uscente
Per identificare la variabile uscente dobbiamo usare il test dei rapporti
Questo test si effettua tra i termini della colonna RHS e quelli della variabile entrante individuata nel passaggio precedente.
Avremo che nella prima riga il rapporto sarà 8/2=4, mentre nella seconda 12/2=6.
La riga con il rapporto più basso è la (1), quindi S1 esce
In questa fase non ci servirà, ma sappiamo ora che l'elemento Pivot è in riga 1, nella colonna x2 e vale 2
Normalizzazione della riga (1)
Dividiamo tutta la riga (1) per l'elemento Pivot, quindi per 2
Avremo quindi la nuova riga 1
Ora calcoliamo la nuova riga Z considerando le seguente operazioni, con lo scopo principale di eliminare x2 che vale -5 (quindi il valore che dovrò calcolare per la trasformazione di z sarà +5):
qui sotto la vecchia riga z
e qui sotto la nuova riga 1
Qui di seguito tutti i calcoli per la nuova riga z
Anche la riga (2) dovrà essere trasformata (normalizzata) con l'eliminazione di x2, dove in questo caso abbiamo il coefficiente 2
Qui sotto la vecchia riga 2
Qui sotto la riga 1 trasformata
Qui di seguito un esempio dell'iterazione matematica per ricostruire la riga 2
Ecco come si presenta ora la nuova tabella dopo la prima iterazione completa
Ora le basi correnti sono x2 (riga 1) e s2 (riga 2)
Seconda iterazione
Ripartiamo con il metodo eseguito prima.
Andrò più veloce con la descrizione
Calcolo della variabile entrante
Andiamo a verificare il coefficiente più negativo in Z
lo troviamo su x1
quindi entra x1
variabile uscente
In riga (1) abbiamo 4/(1/2)=8
In riga (2) abbiamo 4/2=2
Il risultato minimo è sulla riga (2) quindi esce S2 (riga 2)
Proseguimento
Da qui in poi eseguiamo la stessa procedura eseguita prima per:
-normalizzare la riga (2)
-eliminare x1 dalla riga Z
-eliminare x1 dalla riga (1)
otterremo quindi la tabella finale
Soluzione ottima
Le variabili di base sono x2 (riga 1) e x1 (riga 2), impostando le non di base s1=s2=0
Quindi x1=2 mentre x2=3
Ora, andiamo a prendere la nostra funzione obiettivo e possiamo calcolare il valore ottimo
Possiamo provare in altri milioni di modi o fare altre prove, ma non troveremo un risultato migliore di questo con questa funzione obiettivo e con i vincoli che ci erano stati dati
Conclusioni
Risolvere problemi di programmazione lineare può servire a dare un ottimo supporto alla soluzione di problemi decisionali complesse. Questa tipologia di calcolo è eccellente per risolvere problemi in ambito aziendale (problemi di produzione o di riduzione costi) o in ambito logistico.
Domanda
Sapevate che nelle aziende per migliorare la produzione di determinati prodotti e di determinati reparti di produzione eseguono calcoli simili a quelli mostrati in questo post?
Sapevate che il metodo di calcolo mostrato in questo post fu inventato dal matematico statunitense George Bernard Dantzig nel 1947?
THE END