~~~ La versione in italiano inizia subito dopo la versione in inglese ~~~
ENGLISH
10-10-2025 - Operations Research - Feasible Basic Solutions [EN]-[IT]
With this post, I would like to provide a brief introduction to the topic in question.
(lesson/article code: MS_13_LZ-21)
Image created with artificial intelligence, the software used is Microsoft Copilot
Introduction
Linear programming, given a set of constraints, is used to solve optimal decision problems. Given the following linear programming problem, we will try to calculate how many basic solutions there are and whether they are feasible or not.
Exercise
The first thing to do is transform the problem into standard form by introducing the slack variables.
This way, we can express the constraints as equalities.
Constraint matrix A
Now we can proceed with constructing the constraint matrix. In this matrix, each row represents a constraint, and each column corresponds to a variable x1, x2, x3, and x4.
Below is a diagram to understand the coefficients we need to compose the matrix.
The constraint matrix will have the following characteristics:
Therefore, A is a matrix with real elements, belonging to the set of real numbers, and has dimensions 2 x 4, that is, 2 rows and 4 columns.
Matrix A looks like this:
In this matrix, we find the coefficients that relate the variables to the constraints.
The number of basic solutions
To find the number of basic solutions, we start from the resources, or rather, the known terms. We will therefore have the vector of known terms b
To calculate the number of basic solutions, we start from the concept of combination expressed below.
Where:
n = total number of elements (the our variables)
k = how many elements we choose.
!=factorial (i.e., the product of the integers from 1 to that number)
In our case, the calculation will be as follows:
Continuing with the calculations, we will obtain the result:
The basic solutions are 6
Admissible or inadmissible
To understand whether a basic solution is admissible, let's consider the 6 submatrices of matrix A.
Basic Solution 1 of 6
Let's consider the column submatrix B1 = {a1,a2}. Matrix N1 is formed by the remaining columns B1 = {a3,a4}
The rank of B1 is 2, which means that B1 is a basis and the inverse matrix exists.
The solution It is admissible if x1≥0.
We can calculate x1 as follows:
Therefore, the basic solution is admissible because:
Basic Solution 2 to 6
To verify the other basic solutions: Whether they are admissible or not, we proceed with the same method.
Conclusions
Linear programming is a mathematical technique used to optimize resources, plan production, and even choose the most efficient routes or means of transport to reduce transportation costs. Essentially, we can say that linear programming is used to solve optimal decision problems in the presence of constraints.
Question
George Dantzig was the father of linear programming, but did you know that John von Neumann (the inventor of the basic architectural model of modern computers) was instrumental in linear programming with his studies on game theory and duality? Did you know that his ideas laid the theoretical foundation for Dantzig's work?
ITALIAN
10-10-2025 - Ricerca operativa - Soluzioni di base ammissibili [EN]-[IT]
Con questo post vorrei dare una breve istruzione a riguardo dell’argomento citato in oggetto
(codice lezione/articolo: MS_13_LZ-21)
immagine creata con l’intelligenza artificiale, il software usato è Microsoft Copilot
Introduzione
La programmazione lineare, dato un insieme di vincoli, serve per risolvere problemi di decisione ottimale. Dato il seguente problema di programmazione lineare proveremo a calcolare quante sono le soluzioni di base e se sono ammissibili oppure no.
Esercizio
La prima cosa da fare è trasformare il problema in forma standard introducendo le variabili di slack
In questa maniera possiamo esprimere i vincoli come uguaglianze
Matrice dei vincoli A
Ora possiamo procedere con il costruire la matrice dei vincoli. In questa matrice ogni riga rappresenta un vincolo e ogni colonna corrisponde a una variabile x1, x2, x3, x4.
Qui di seguito uno schema per comprendere i coefficienti che ci servono per comporre la matrice
La matrice dei vincoli avrà la seguente caratteristica
Quindi A è una matrice con elementi reali, appartenenti all’insieme dei numeri reali e ha dimensioni 2 x 4, cioè 2 righe e 4 colonne.
La matrice A si presenta come segue:
In questa matrice troviamo i coefficienti che legano le variabili ai vincoli.
Il numero delle soluzioni di base
Per trovare il numero delle soluzioni di base partiamo dalle risorse o meglio dai termini noti. Avremo quindi il vettore dei termini noti b
Per calcolare il numero delle soluzioni di base partiamo dal concetto di combinazione espresso qui di seguito
Dove:
n=numero totale degli elementi (le nostre variabili)
k=quanti elementi scegliamo.
!=fattoriale (cioè prodotto dei numeri interi da 1 fino a quel numero)
Nel nostro caso il calcolo sarà il seguente:
Proseguendo con i calcoli otterremo il risultato
Le soluzioni di base sono 6
Ammissibile o inammissibile
Per comprendere se una soluzione base è ammissibile andiamo a considerare le 6 sottomatrici della matrice A
Soluzione di base 1 di 6
Consideriamo la sottomatrice di colonne B1 = {a1,a2}. La matrice N1 è formata dalle colonne rimanenti B1 = {a3,a4}
Il rango di B1 è 2, questo vuol dire che B1 è una base ed esiste la matrice inversa
La soluzione è ammissibile se x1≥0
x1 possiamo calcolarlo come segue
Quindi la soluzione di base è ammissibile in quanto
Soluzione di base da 2 a 6
Per verificare le altre soluzioni di base se sono ammissibili oppure no si procede con lo stesso metodo.
Conclusioni
La programmazione lineare è una tecnica matematica usata per ottimizzare le risorse, pianificare la produzione e anche scegliere le rotte o i mezzi più efficienti per ridurre i costi di trasporto. Sostanzialmente possiamo dire che la programmazione lineare serve per risolvere problemi di decisione ottimale in presenza di vincoli.
Domanda
George Dantzig è stato il padre della programmazione lineare, ma sapevate che John von Neumann (l'inventore del modello architettonico base dei computer moderni), fu fondamentale per la programmazione lineare con i suoi studi sulla teoria dei giochi e sulla dualità? Sapevate che le sue idee crearono le basi teoriche del lavoro di Dantzig?
THE END