30-07-2025 - Operations Research - Duality Theory [EN]-[IT]

---

~~~ La versione in italiano inizia subito dopo la versione in inglese ~~~

---

ENGLISH

30-07-2025 - Operations Research - Duality Theory [EN]-[IT]
With this post, I would like to provide a brief introduction to the topic in question.
(code notes: X_84)

Duality Theory

Image created with artificial intelligence, the software used is Microsoft Copilot
Introduction
We can discuss duality problems by offering two explanations.
First explanation
In Linear Programming, duality arises from the possibility of associating a generic LP problem with another LP problem, called a dual problem, which allows us to identify a series of interesting properties of the given problem, called a primal problem.
Second explanation
When we are in the field of operations research, duality establishes that every linear programming problem, called a primal problem, can be associated with a dual problem. When we tackle such a case, we already know that the two problems will be closely related and that they share some properties.

What does a primal problem look like in Operations Research?
In Operations Research, a primal problem has a standard form, which I have mentioned in previous articles. Essentially, a primal problem optimizes a linear function; that is, it solves an optimization or minimization problem, while still being subject to linear constraints.

Below is an example of a primal problem.

This linear programming problem aims to maximize profit while taking into account constraints on the use of available resources.
The decision variables could be the quantities to be produced.

*Primal and dual problem
Now we enter an even more complicated area than what was previously discussed.
The primal problem and the dual problem have some properties in common.
Let's start with the primal problem.
Here's an example:

Now we know that we can associate a dual problem with every primal problem.

Below is an example that might fit with the primal problem above.

Why we call it a dual problem
We call it a dual problem because by solving the dual problem, it is possible to both solve the primal problem and deduce some properties of the feasible solutions of the primal problem.
NOTE: The dual problem of a minimization problem is a maximization problem. Furthermore, the known terms of one problem are the coefficients of the objective function of the other.

Strong duality and Weak

Image created with artificial intelligence, the software used is Napkin.ai

In a dual problem, we can have a weak duality or a strong duality.
Below, we explain what a weak and strong duality is.
Weak Duality
For Feasible Solutions
Dual objective ≤ primal objective
Strong Duality
If there is a feasible and optimal solution for the primal (or dual), then
-The other problem also has an optimal solution
-The optimal values coincide

Conclusions
Every primal problem has a corresponding dual. The dual problem is a problem constructed from the primal. The dual problem has a symmetric relationship. Duality can be weak or strong. Duality theory is a way to view the same problem from two complementary perspectives. These studies are conducted to fully understand that every choice involves an opportunity cost. Understanding opportunity cost is essential for making efficient decisions.

Question
Did you know that John von Neumann introduced the idea of duality? Did you know that John von Neumann is considered the father of modern computer architecture? (I also discussed this in one of my previous articles on the fundamentals of computer science)

---

---

ITALIAN

30-07-2025 - Ricerca operativa - Teoria della dualità [EN]-[IT]
Con questo post vorrei dare una breve istruzione a riguardo dell’argomento citato in oggetto
(code notes: X_84)

Teoria della dualità

immagine creata con l’intelligenza artificiale, il software usato è Microsoft Copilot
Introduzione
Possiamo parlare dei problemi duali dando due spiegazioni.
Prima spiegazione
In Programmazione Lineare la dualità nasce dalla possibilità di associare a un generico problema di PL un altro problema di PL, detto problema duale, che permette di identificare una serie di proprietà interessanti sul problema dato, detto problema primale
Seconda spiegazione
Quando siamo nell'ambito della ricerca operativa la dualità stabilisce che ad ogni problema di programmazione lineare, che viene chiamato problema primale, è possibile associare un problema duale. Quando affrontiamo un caso simile sappiamo già che i due problemi saranno strettamente collegati e che condividono alcune proprietà tra di loro.

Come appare un problema primale in Ricerca Operativa?
In Ricerca Operativa un problema primale ha una forma standard, ho fatto qualche cenno in qualche articolo precedente. Sostanzialmente un problema primale ottimizza una funzione lineare, cioè risolve un problema di ottimizzazione o minimizzazione, essendo comunque soggetta a vincoli lineari.
Qui di seguito un esempio di problema primale.

Questo problema di programmazione lineare ha come obiettivo di massimizzare il profitto tenendo conto di vincoli che sono l'uso delle risorse disponibili.
Le variabili decisionali potrebbero essere le quantità da produrre.

*Problema primale e duale
Ora entriamo in un ambito ancora più complicato di ciò che è stato detto in precedenza.
Il problema primale ed il problema duale hanno delle proprietà in comune.
Partiamo dal problema primale.
qui di seguito un esempio:

Ora sappiamo che possiamo associare ad ogni problema primale uno duale.
QUi di seguito un esempio che potrebbe calzare con il problema primale scritto prima.

Perché si parla di problema duale
Si parla di problema duale perché risolvendo il problema duale è possibile sia risolvere il problema primale che dedurre alcune proprietà delle soluzioni ammissibile del problema primale
NOTA: Il problema duale di un problema di minimizzazione è un problema di massimizzazione, inoltre i termini noti di un problema sono e i coefficienti della funzione obiettivo dell’altro

Dualità forte e debole

immagine creata con l’intelligenza artificiale, il software usato è Napkin.ai

In un problema duale possiamo avere una dualità debole o una dualità forte.
Qui di seguito è spiegato cosa è una dualità debole e forte.
Dualità debole
Per le soluzioni ammissibili
Obiettivo duale ≤ obiettivo primale
Dualità forte
Se esiste una soluzione ammissibile e ottima per il primale (o il duale), allora
-Anche l'altro problema ha soluzione ottima
-I valori ottimali coincidono

Conclusioni
Ogni problema primale ha un duale corrispondente. Il problema duale è un problema costruito a partire dal primale. Il problema duale ha una relazione simmetrica. La dualità può essere debole oppure forte. La teoria della dualità è un modo per vedere lo stesso problema da due prospettive complementari. Questi studi vengono effettuati per comprendere bene che ogni scelta comporta un costo opportunità. La comprensione del costo opportunità è fondamentale per prendere decisioni efficienti.

Domanda
Lo sapevate che fu John von Neumann ad introdurre l’idea di dualità? Sapevate che John von Neumann è considerato il padre dell’architettura dei computer moderni? (ne parlai anche in uno dei miei articoli precedenti dedicati ai fondamenti di informatica)

THE END