~~~ La versione in italiano inizia subito dopo la versione in inglese ~~~
ENGLISH
30-11-2025 - Operations Research - The Unbounded Problem [EN]-[IT]
With this post, I would like to provide a brief introduction to the topic in question.
(lesson/article code: MS_03)
Image created with artificial intelligence, the software used is Microsoft Copilot
Introduction
Below, we'll look at something very specific: a linear programming problem with the characteristic of unboundedness. The conclusions provide some brief information about it.
Linear programming is a mathematical method for finding optimal solutions and is used in industrial production and logistics.
Example
Let's consider the following table derived from a linear programming problem and then analyze it.
Table Analysis
The first numerical row of the table is the reduced costs row, and since there are negative reduced costs, x1 and x4, the optimality criterion is not satisfied.
I've reproduced the row considered below for clarity.
Let's move on to the other two rows, which I reproduce below.
Note that there is a 2x2 identity matrix in these two rows, in the columns x2 and x3.
Below is a screenshot.
From this, we deduce that x2 and x3 are the base variables and both have values greater than 0 since x2=8 and x3=2.
Therefore, the base solution is feasible; we can rule out the possibility that the problem is infeasible.
Basis and non-basis variables
Therefore, it is the identity matrix that tells us which variables are the base and which are not.
In this case, we have the following:
base variables: x2, x3
non-base variables: x1, x4
This simply means that the basic solution is
The Unboundedness Criterion
Let's use the technical definition of the unboundedness criterion, which we can summarize as follows:
For the unboundedness criterion: if there is a variable with negative reduced cost and the corresponding column of 𝐵^−1𝑁 has all non-positive components, the problem is unbounded.
Checking for Unboundedness
Let's check X1 and X4
If we check x1, we get the following:
x1 = -2, which is less than 0, and the column is (-3,0), so all components are less than or equal to zero, so the unboundedness criterion is satisfied.
If we check x4, we see that it has a value of -3, but the column is (-1,1), thus having a positive element.
However, one of the two variables between x1 and x4 satisfies both points of the criterion, so we can conclude that the problem is unbounded.
Real-World Example
Let's imagine we own a small artisanal business that produces wooden frames.
Our variables will be:
x = number of frames
z = total profit
Each frame generates a profit of €20.
The linear programming model is
The objective function is
Since there are no other constraints, profit grows infinitely, because we have no limits on raw materials or machine hours.
The company can produce infinite frames and earn infinite profits, so this result immediately suggests that the initial conditions are probably incorrect.
Conclusions
When we tackle a linear programming problem that attempts to study a company's production and the problem has an unbounded solution, technically we say the problem is unbounded, but in practice we have overlooked one or more capacity constraints on the production plant; that is, we have poorly analyzed the problem and forgotten to consider some variables. In this case, we don't need to revise the calculations, but rather how we set up the problem, before doing the calculations.
Question
Did you know that linear programming is widely used by airlines to optimize crew rosters and aircraft utilization?
ITALIAN
30-11-2025 - Ricerca operativa - Il problema illimitato [EN]-[IT]
Con questo post vorrei dare una breve istruzione a riguardo dell’argomento citato in oggetto
(codice lezione/articolo: MS_03)
immagine creata con l’intelligenza artificiale, il software usato è Microsoft Copilot
Introduzione
Qui di seguito vedremo una cosa molto particolare, un problema di programmazione lineare con la caratteristica di illimitatezza. Nelle conclusioni alcune informazioni a riguardo riportate in maniera sintetica.
La programmazione lineare è un metodo matematico per trovare soluzioni ottime e viene usato nell'ambito della produzione industriale e della logistica.
Esempio
Prendiamo in considerazione la seguente tabella derivata da un problema di programmazione lineare e poi andremo ad analizzarla.
Analisi della tabella
La prima riga numerica della tabella è la riga dei costi ridotti e siccome ci sono dei costi ridotti negativi, x1 e x4, il criterio di ottimalità non è soddisfatto.
Riposto qui di seguito la riga prese in considerazione per essere più chiari.
Passiamo alle altre due righe, che riporto qui di seguito
Notiamo che c'è una matrice identità 2x2 in questa due righe, nelle colonne di x2 e x3.
Qui di seguito uno screenshot
Da questo deduciamo che x2 e x3 sono le variabili in base ed hanno entrambe valori maggiori di 0 in quanto x2=8 e x3=2.
Quindi la soluzione di base è ammissibile, possiamo escludere che il problema sia inammissibile
Variabili in base e non basi
Quindi è la matrice identità che ci indica quali sono le variabili in base e quelle non base.
In questo caso abbiamo quanto segue:
variabili in base: x2,x3
variabili non basi: x1,x4
Questo significa semplicemente che la soluzione di base è
Il criterio di illimitatezza
Usiamo la definizione tecnica del criterio di illimitatezza che potremmo riassumere come segue:
Per il criterio di illimitatezza: se esiste una variabile con costo ridotto negativo e la relativa colonna di 𝐵^−1𝑁 ha tutte le componenti non positive, il problema è illimitato.
Verifica dell'illimitatezza
Controlliamo X1 e X4
Se andiamo a controllare x1 avremo quanto segue:
x1 = -2 che quindi è minore di 0 e la colonna è (-3,0), quindi tutte le componenti sono minori o uguali a zero, quindi il criterio di illimitatezza è soddisfatto.
Andando invece a controllare x4 vediamo che ha un valore di -3 ma la colonna è (-1,1) ed ha così un elemento positivo.
Però una delle due variabili tra x1 e x4 soddisfa entrambi i punti del criterio, quindi possiamo concludere che il problema è illimitato.
Esempio calato nella realtà
Immaginiamo di possedere una piccola azienda artigianale che produce cornici di legno.
Le nostre variabili saranno:
x=numero di cornici
z=profitto totale
Ogni cornice dà un profitto di 20 €.
Il modello di programmazione lineare è
la funzione obiettivo è
Siccome non ci sono altri vincoli il profitto cresce all'infinito, perché non abbiamo limiti di materia prima e di ore di utilizzo delle macchine.
L’azienda può produrre infinite cornici e guadagnare all’infinito, quindi questo risultato fa subito intendere che probabilmente le condizioni iniziali non sono corrette.
Conclusioni
Quando affrontiamo un problema di programmazione lineare che cerca di studiare la produzione di un'azienda ed il problema ha una soluzione illimitata, tecnicamente si dice che il problema è illimitato, ma in pratica abbiamo dimenticato uno o più vincoli di capacità dell’impianto produttivo, cioè abbiamo analizzato male il problema ed abbiamo dimenticato di considerare delle variabili. In questo caso non dobbiamo rivedere i conti, ma come abbiamo impostato il problema, prima di fare i conti.
Domanda
Lo sapevate che la programmazione lineare è molto usata dalle compagnie aeree per ottimizzare i turni degli equipaggi e l'uso degli aerei?
THE END