~~~ La versione in italiano inizia subito dopo la versione in inglese ~~~
ENGLISH
13-12-2025 - Operations Research - The Maximum Number of Basic Solutions [EN]-[IT]
With this post, I would like to provide a brief introduction to the topic mentioned above.
(lesson/article code: QE_09)
Image created with artificial intelligence, the software used is Microsoft Copilot
Introduction
Operations research is a recently developed university subject. This subject teaches how to transform real-world problems into mathematical problems and find the best possible solutions.
Operations research includes the entire section on linear programming. This is a mathematical optimization technique that allows us to maximize or minimize the profits, costs, or time of a work process.
Basic Solutions
When we face a linear programming problem, we must understand that our starting point will be to identify basic solutions. A basic solution is a feasible solution to the linear programming problem obtained by setting some variables (non-basic ones) to zero and solving the system of equations formed by the constraints.
Example
Consider the following linear programming problem:
Analysis
We are in...
... this means we have 2 variables and 4 linear constraints.
We can already say that the maximum number of possible basic solutions given by the combination of four constraints taken in pairs is 6 according to the following relationship:
Result
We have therefore arrived at the result that the maximum number of possible basic solutions for the given linear programming problem is 6
Process Analysis
Basic Solutions
Let's try to explain what basic solutions mean in R^2.
This means that in the R2 plane, a basic solution is the point obtained by combining two constraints, taken as equals, among all those that define the polyhedron of solutions.
In our case, there are 4 constraints.
We can see them below, enclosed in the largest curly bracket:
Combinatorial Counting
To arrive at the result, that is, to understand the maximum number of basic solutions, it is necessary to use combinatorial calculations.
In this case, we have 4 objects taken 2 by 2, and the number of combinations will be a division with factorial calculations in the numerator and denominator. Exactly as follows:
We can therefore conclude that there are at most 6 linear systems in 2 unknowns from which basic solutions can arise.
This is why the answer is 6.
WARNING: There are six basic solutions, but some are not feasible; Therefore, their number should be understood in a purely algebraic sense.
The Factorial Calculation
For those who don't remember how to calculate the factorial, here's an example.
Conclusions
A linear programming problem with n variables and m constraints has a maximum number of basic solutions and They are:
Knowing the number of basic solutions to a problem is very important in industrial and decision-making contexts.
The key concept is that in a company, when you introduce many constraints (rules, limits, resources, proportions, shifts, capacities, etc.), the number of possible basic solutions increases combinatorially.
Knowing this means that, if the number of basic solutions is too high, you need to start thinking about simplifying the system.
Question
Did you know that knowing the maximum number of basic solutions helps assess the complexity of a problem?
Did you know that at IKEA they extensively use Linear Programming (LP) and other Operations Research techniques to manage and simplify logistics?
ITALIAN
13-12-2025 - Ricerca operativa - Il massimo numero di soluzioni di base [EN]-[IT]
Con questo post vorrei dare una breve istruzione a riguardo dell’argomento citato in oggetto
(codice lezione/articolo: QE_09)
immagine creata con l’intelligenza artificiale, il software usato è Microsoft Copilot
Introduzione
La ricerca operativa è una materia universitaria nata di recente. Questa materia insegna come trasformare problemi reali in problemi matematici e trovare le miglior soluzioni possibili.
All'interno della Ricerca Operativa, c'è tutta la sezione della programmazione lineare. Questa è una tecnica matematica di ottimizzazione che permette di massimizzare o minimizzare i profitti, i costi o i tempi di un processo di lavoro.
Soluzioni di base
Quando siamo di fronte ad un problema di programmazione lineare dobbiamo comprendere che la nostra partenza sarà identificare delle soluzioni di base. Una soluzione di base è una soluzione ammissibile del problema di programmazione lineare che si ottiene ponendo a zero alcune variabili (quelle non di base) e risolvendo il sistema di equazioni formato dai vincoli.
Esempio
Consideriamo il seguente problema di programmazione lineare:
Analisi
Siamo in ....
... questo significa che abbiamo 2 variabili e abbiamo 4 vincoli lineari.
Possiamo già dire che i il massimo numero di soluzioni di base possibili è dato dalla combinazione di 4 vincoli presi a 2 a 2 è 6 secondo la seguente relazione:
Risultato
Siamo quindi giunti al risultato che, il massimo numero di soluzioni di base possibili, per il problema di programmazione lineare dato sono 6
Analisi del processo
Soluzioni di base
Proviamo a spiegare cosa vuol dire soluzioni di base in R^2.
Significa che nel piano R2 una soluzione di base è il punto ottenuto mettendo a sistema 2 vincoli, presi come uguaglianze, tra tutti quelli che definiscono il poliedro delle soluzioni.
Nel nostro caso i vincoli sono 4.
Li possiamo vedere qui sotto, racchiusi nella parentesi graffa più grande:
Conteggio combinatorio
Per arrivare al risultato, cioè capire qual è il massimo numero di soluzioni di base è necessario usare il calcolo combinatorio.
In questo caso abbiamo 4 oggetti presi 2 a 2 ed il numero di combinazioni sarà una divisione con al numeratore e al denominatore calcoli fattoriali. Esattamente come segue:
Possiamo quindi giungere alla seguente considerazione che ci sono al massimo 6 sistemi lineari in 2 incognite da cui possono nascere soluzioni di base.
Ecco perché la risposta è 6.
ATTENZIONE: Le soluzioni di base sono sei, ma alcune non risultano ammissibili; pertanto, il loro numero va inteso in senso puramente algebrico
Il calcolo fattoriale
Per chi non ricordasse come si esegue il calcolo del fattoriale, di seguito un esempio
Conclusioni
Un problema di programmazione lineare con n variabili e m vincoli ha un numero massimo di soluzioni di base e sono:
Conoscere il numero di soluzioni di base di un problema è molto importante in contesti industriali e decisionali.
Il concetto chiave è che in un’azienda, quando introduci molti vincoli (regole, limiti, risorse, proporzioni, turni, capacità...), il numero di possibili soluzioni di base cresce combinatoriamente.
Conoscere questo significa che, se il numero di soluzioni di base è troppo alto, bisogna iniziare a pensare ad una semplificazione del sistema.
Domanda
Sapevate che sapere il massimo numero di soluzioni di base serve a valutare la complessità di un problema?
Sapevate che in IKEA usano in modo massiccio la Programmazione Lineare (PL) e altre tecniche di Ricerca Operativa per gestire la logistica e semplificarla?
THE END