~~~ La versione in italiano inizia subito dopo la versione in inglese ~~~
ENGLISH
01-10-2025 - Operations Research - Analytical Calculation of Basic Solutions [EN]-[IT]
With this post, I would like to provide a brief instruction on the topic mentioned above.
(lesson/article code: EX_LZ_11)
Image created with artificial intelligence, the software used is Microsoft Copilot
Introduction
IMPORTANT NOTICE! This post was written to get your brains in gear... don't try to understand anything; I will not be held responsible for any brain damage. (Joke)
Let's get serious...
Linear programming is a mathematical method for optimizing an objective function subject to a set of constraints expressed as linear equations or inequalities. Writing a linear programming problem involves an objective function and constraints that must be met.
Below is a maximization exercise.
Exercise
First, let's put our linear programming problem into standard form. The slack variables s1 and s2 will be introduced.
The Coefficient Matrix
Below is A, the coefficient matrix of the linear programming problem.
The vector of known terms
Below is b, the vector of known terms.
Calculating the number of basic solutions
To calculate the number of basic solutions, we can use the binomial coefficient formula, shown below.
Where
n = the variables (which are 4 in our case)
k = the constraints (which are 2 in our case)
In our case, by developing the formula we will have: follows:
So we now know that the number of basic solutions is 6.
Admissibility check, general principle
To check whether a solution is admissible, we use the following procedure:
1- Choose a subset of columns of A (for example, a basis B).
2- If the chosen columns are linearly independent, it means that B is invertible. If B is not invertible, it is not a basis.
3- Calculate
Where:
xB = basic variables
xN = non-basic variables
4-Final verdict: if xB ≥ 0, then the basic solution is feasible; otherwise, it is infeasible.
Feasibility check, basis 1
Basis (x1,x2)
In this case, it is not invertible, so it is not a basis.
Admissibility check, basis 2
Basis (x1,s1)
Memory, here Here's how to calculate an inverse matrix.
Now we perform the calculation as described in point 3 of the section "Admissibility Check, General Principle."
So (x1,s1)=(0,3) while the other variables are zero.
All values are ≥ 0, so we can deduce that basis 2 is admissible
Admissibility check, basis 3
Basis (x1,s2)
All values are ≥ 0, so we can deduce that base 3 is admissible.
Admissibility Check, Base 4
Base (x2,s1)
All values are ≥ 0, so we can deduce that base 4 is admissible
(equal to the second)
Admissibility Check, Base 5
Base (x2,s2)
All values are not ≥ 0, so we can deduce that base 5 is inadmissible.
Admissibility check, base 6
Base (s1,s2)
All values are ≥ 0, so we can deduce that basis 6 is feasible
Summary
Bases 2, 4, and 6 are feasible (0, 0, 3, 0)
Base 3 is feasible (3, 0, 0, 6)
Base 5 is infeasible (0, -3, 0, 6)
Base 1 (x1, x2) is a non-basis
Conclusions
When a basic solution is feasible, it means that it satisfies all the constraints of the problem. including non-negativity.
So a basic solution is the point of intersection of m constraints considered as equations, and it is feasible when that point actually lies within the feasible region of the problem, that is, it has no negative variables and satisfies all the constraints.
Question
Linear programming was formally developed as a mathematical discipline in the 1940s. Among the most brilliant minds in this discipline is Leonid Khachiyan. Did you know that the Soviet-American mathematician introduced the elliptic method in the 1970s and demonstrated for the first time that linear programming problems could be solved in polynomial time? (Polynomial time is a concept in theoretical computer science that indicates the speed of an algorithm.)
ITALIAN
01-10-2025 - Ricerca operativa - Calcolo analitico delle soluzioni di base [EN]-[IT]
Con questo post vorrei dare una breve istruzione a riguardo dell’argomento citato in oggetto
(codice lezione/articolo: EX_LZ_11)
immagine creata con l’intelligenza artificiale, il software usato è Microsoft Copilot
Introduzione
AVVISO IMPORTANTE! Questo post è stato fatto per far fumare il cervello... non cercate di capire qualsiasi cosa, non mi riterrò responsabile di eventuali danni al cervello (momento scherzoso)
Torniamo seri...
La programmazione lineare è un metodo matematico per ottimizzare una funzione obiettivo soggetta a un insieme di vincoli espressi come equazioni o disequazioni lineari. La scrittura di un problema di programmazione lineare è caratterizzata da una funzione obiettivo e da vincoli da rispettare.
Qui di seguito un esercizio di massimizzazione.
Esercizio
Per prima cosa portiamo in forma standard il nostro problema di programmazione lineare. Verranno introdotte le variabili di slack s1 e s2
La matrice dei coefficienti
Qui di seguito è riportata A, ovvero la matrice dei coefficienti del problema di programmazione lineare.
Il vettore dei termini noti
Qui di seguito è riportato b, ovvero il vettore dei termini noti.
Calcolo del numero delle soluzioni di base
Per calcolare il numero delle soluzioni di base possiamo usare la formula del coefficiente binomiale, qui di seguito riportata.
Dove
n=sono le variabili (che sono 4 nel nostro caso)
k=sono i vincoli (che sono 2 nel nostro caso)
Nel nostro caso andando a sviluppare la formula avremo quanto segue:
Quindi sappiamo ora che il numero di soluzioni di base è 6
Verifica di ammissibilità, principio generale
Per verificare se una soluzione è ammissibile usiamo il seguente procedimento:
1-Si sceglie un sottoinsieme di colonne di A (ad esempio una base B)
2-Se le colonne scelte sono linearmente indipendenti significa che B è invertibile, se B non è invertibile, non è una base.
3-Si calcola
Dove:
xB=variabili di base
xN=variabili fuori base
4-Verdetto finale, se xB≥0, allora la soluzione di base è ammissibile, altrimenti è non ammissibile.
Verifica di ammissibilità, base 1
Base (x1,x2)
In questo caso non è invertibile, quindi non è una base
Verifica di ammissibilità, base 2
Base (x1,s1)
Memo, qui di seguito come si calcola una matrice inversa
Ora eseguiamo il calcolo come descritto nel punto 3 del paragrafo “Verifica di ammissibilità, principio generale”
Quindi (x1,s1)=(0,3) mentre le altre variabili sono a zero.
Tutti i valori sono ≥ 0, quindi possiamo dedurre che la base 2 è ammissibile
Verifica di ammissibilità, base 3
Base (x1,s2)
Tutti i valori sono ≥ 0, quindi possiamo dedurre che la base 3 è ammissibile
Verifica di ammissibilità, base 4
Base (x2,s1)
Tutti i valori sono ≥ 0, quindi possiamo dedurre che la base 4 è ammissibile
(uguale alla seconda)
Verifica di ammissibilità, base 5
Base (x2,s2)
Tutti i valori non sono ≥ 0, quindi possiamo dedurre che la base 5 è non ammissibile
Verifica di ammissibilità, base 6
Base (s1,s2)
Tutti i valori sono ≥ 0, quindi possiamo dedurre che la base 6 è ammissibile
Riassunto
Le basi 2,4,6 sono ammissibili (0,0,3,0)
La base 3 è ammissibile (3,0,0,6)
La base 5 non è ammissibile (0,-3,0,6)
La 1 (x1,x2) è una non base
Conclusioni
Quando una soluzione di base è ammissibile significa che è una soluzione che rispetta tutti i vincoli del problema, compresa la non negatività.
Quindi una soluzione di base è punto di intersezione di m vincoli considerati come equazioni, ed è ammissibile quando quel punto sta effettivamente dentro la regione ammissibile del problema e cioè non ha variabili negative e soddisfa tutti i vincoli.
Domanda
La programmazione lineare è stata formalmente sviluppata come disciplina matematica negli anni 1940. Tra le menti più geniali di questa disciplina c'è Leonid Khachiyan. Sapevate che il matematico sovietico - americano, negli anni ’70 introdusse il metodo ellittico, egli dimostrò per la prima volta che i problemi di programmazione lineare si potevano risolvere in tempo polinomiale? (Il tempo polinomiale è un concetto dell’informatica teorica che indica la velocità di un algoritmo)
THE END