Modelli di ottimizzazione e richiami su ℝ

Dal problema al modello

Un problema espresso a parole non si risolve direttamente. Lo si traduce in un modello matematico, che dice che cosa si chiede, e a quel modello si applica un algoritmo numerico, che calcola la soluzione. La traduzione è spesso la parte più difficile.

Problema in linguaggio naturaleModello matematicovariabili, vincoli, obiettivoAlgoritmo numericoSoluzione

Un modello ha quattro ingredienti:

• parametri: i dati assegnati, che non si possono modificare;
• variabili di decisione: i parametri liberi, ciò su cui si può agire;
• vincoli: le condizioni che le variabili devono rispettare;
• funzione obiettivo: la quantità da minimizzare o massimizzare.

Provare a costruire a mano una soluzione intuitiva non serve: prima si scrive il modello. Quattro problemi classici mostrano come.

Assegnamento di ingegneri a progetti

Ci sono 30 ingegneri e 30 progetti. Ogni ingegnere va a un solo progetto e ogni progetto a un solo ingegnere. Il tempo di addestramento $t_{ij}$ dell'ingegnere $i$ sul progetto $j$ è un parametro assegnato: non si decide. Si decide chi va dove, con variabili che valgono $0$ o $1$ (variabili binarie):

$$x_{ij}=\begin{cases}1&\text{ingegnere }i\to\text{progetto }j\\0&\text{altrimenti}\end{cases}$$

Ogni ingegnere ha esattamente un progetto, e ogni progetto esattamente un ingegnere:

$$\begin{gathered} \sum_{j=1}^{30}x_{ij}=1\qquad i=1,\dots,30\\ \sum_{i=1}^{30}x_{ij}=1\qquad j=1,\dots,30 \end{gathered}$$

L'obiettivo è il tempo complessivo di addestramento. Nel prodotto $t_{ij}x_{ij}$ contano solo le coppie scelte, quelle con $x_{ij}=1$:

$$\min\sum_{i=1}^{30}\sum_{j=1}^{30}t_{ij}\,x_{ij}$$

Calendario sportivo

Per un campionato di $N=16$ squadre il girone di andata ha 15 giornate; il ritorno è speculare. Le variabili hanno tre indici:

$$x_{ijk}=\begin{cases}1&\text{la squadra }i\text{ gioca in casa}\\&\text{contro la squadra }j\text{ alla giornata }k\\0&\text{altrimenti}\end{cases}$$

Su queste variabili si scrivono tutti i vincoli del calendario e uno o più obiettivi. Se la squadra $S_1$ non può giocare in casa alla giornata 3, la somma delle sue partite in casa alla giornata 3 deve essere nulla. La somma corre su tutte le squadre $j$:

$$\sum_{j=1}^{N}x_{1j3}=0$$

Un calendario ha un centinaio di vincoli. Se sono incompatibili nessuna scelta delle $x$ li soddisfa tutti: il problema è inammissibile, e l'algoritmo lo segnala. Allora bisogna indebolire qualche richiesta.

Problema dello zaino

Un convegno ha un budget $b$ fissato (100 000 euro nell'esempio) e $N$ relatori tra cui scegliere. Per il relatore $i$ si stima il numero $c_i$ di partecipanti che attrae e il costo di ingaggio $a_i$ (viaggio e alloggio compresi). Si decide solo se invitarlo:

$$x_i=\begin{cases}1&\text{ingaggio il relatore }i\\0&\text{altrimenti}\end{cases}$$

Il vincolo è il budget, l'obiettivo sono le presenze:

$$\begin{gathered} \sum_{i=1}^{N}a_i\,x_i\le b\\ \max\sum_{i=1}^{N}c_i\,x_i \end{gathered}$$

Se $x_i=0$ il relatore non pesa né sul costo né sulle presenze.

Problema del trasporto

Ci sono $M$ magazzini e $N$ punti vendita. Sono assegnati il costo unitario $c_{ij}$ di trasporto dal magazzino $i$ al punto vendita $j$, la capacità $a_i$ del magazzino $i$ e la domanda $d_j$ del punto vendita $j$. Qui $x_{ij}$ non è $0$ o $1$: è la quantità trasportata da $i$ a $j$, quindi $x_{ij}\ge 0$.

Da un magazzino non esce più della sua capacità; a un punto vendita arriva esattamente la sua domanda:

$$\begin{gathered} \sum_{j=1}^{N}x_{ij}\le a_i\qquad i=1,\dots,M\\ \sum_{i=1}^{M}x_{ij}=d_j\qquad j=1,\dots,N \end{gathered}$$

Si minimizza il costo complessivo:

$$\min\sum_{i=1}^{M}\sum_{j=1}^{N}c_{ij}\,x_{ij}$$

La natura del bene decide il tipo delle variabili. Per le automobili $x_{ij}$ è intera, perché non si trasporta $0{,}7$ di un'auto; per il grano può essere reale. Con variabili intere si usa una classe di algoritmi diversa, e il problema è computazionalmente molto più difficile.

Estremo inferiore e superiore

Il corso porta in $\mathbb R^n$ ciò che si conosce in $\mathbb R$. Si richiamano le definizioni in $\mathbb R$.

Sia $A\subseteq\mathbb R$. Un numero $\lambda$ è un minorante di $A$ se

$$\lambda\le x\qquad\forall x\in A$$

L'estremo inferiore è il più grande dei minoranti. Quindi $\lambda=\inf A$ se valgono due condizioni:

$$\begin{gathered} \text{(1) }\lambda\text{ è un minorante di }A\\ \text{(2) }\lambda\ge L\quad\forall\,L\text{ minorante di }A \end{gathered}$$

Per l'estremo superiore si inverte tutto: un maggiorante è un numero $\ge x$ per ogni $x\in A$, e $\lambda=\sup A$ è il più piccolo dei maggioranti, cioè $\lambda\le L$ per ogni maggiorante $L$.

Queste definizioni hanno senso perché $\mathbb R$ è totalmente ordinato: due numeri si confrontano sempre. In $\mathbb R^2$ non c'è un ordine totale, e di un insieme del piano non si definiscono estremo inferiore e superiore.

Condizioni necessarie e sufficienti

Siano $P$ una proprietà e $C$ una condizione. Il «solo se» esprime la condizione necessaria, il «se» la sufficiente:

$$\begin{gathered} C\text{ necessaria per }P:\quad P\Rightarrow C\\ C\text{ sufficiente per }P:\quad C\Rightarrow P\\ C\text{ necessaria e sufficiente:}\quad P\Longleftrightarrow C \end{gathered}$$

Avere almeno 18 anni è necessario per avere la patente, ma non sufficiente: manca l'esame. Vincere tutte le partite è sufficiente per vincere il campionato, ma non necessario.

In $\mathbb R$, per $A$ non vuoto, la limitatezza è necessaria e sufficiente perché esistano finiti sia $\inf A$ sia $\sup A$. Dimostrare il «se» significa partire da $A$ limitato e ricavare i due estremi; dimostrare il «solo se» significa partire dai due estremi e ricavare che $A$ è limitato. Prima di dimostrare, bisogna riconoscere quale implicazione si sta provando.

Intorni

Dati $x_0\in\mathbb R$ e un raggio $\rho>0$, l'intorno sferico è

$$B_\rho(x_0)=\{x\in\mathbb R:\ |x-x_0|<\rho\}$$

cioè l'intervallo aperto $(x_0-\rho,\,x_0+\rho)$. Un intorno di $x_0$ è un intervallo qualsiasi, non necessariamente sferico, che contiene un intorno sferico di $x_0$.

Intorno sferico di $x_0=0,5$

$x_0$$x$

• $|x-x_0|$
• $B_{\rho }(x_0)$
• altezza $\rho$ negli estremi

$\rho$

0,8

Punti di accumulazione e punti isolati

Un punto $x_0\in\mathbb R$ è di accumulazione per $A\subseteq\mathbb R$ se ogni intorno sferico di $x_0$ contiene almeno un punto di $A$ diverso da $x_0$:

$$\forall\rho>0\ \ \exists x\in A:\quad x\ne x_0,\ \ x\in B_\rho(x_0)$$

Un punto di accumulazione sta in $\mathbb R$ e può non appartenere ad $A$. L'insieme dei punti di accumulazione si indica con $DA$. Per $A=\{x\in\mathbb R:\ 0<x\le 1\}$ si ha

$$DA=\{x\in\mathbb R:\ 0\le x\le 1\}$$

Il punto $0$ non appartiene ad $A$, ma ogni suo intorno contiene punti di $A$.

Accumulazione per $A=(0,1]$

$0\notin A$$1\in A$$\rho /2\in A$$x_0$$x$

• $A$
• $B_{\rho }(x_0)$

$\rho$

0,4

Un punto di $A$ che non è di accumulazione per $A$ si dice isolato: appartiene ad $A$ e ha un intorno sferico in cui non cade nessun altro punto di $A$.

Da $\mathbb R$ a $\mathbb R^n$

In $\mathbb R$ la distanza fra due punti è il valore assoluto della differenza. In $\mathbb R^2$, $\mathbb R^3$, $\mathbb R^n$ il valore assoluto è sostituito da una norma $\|\cdot\|$ (la sua definizione formale si dà dopo). L'intorno sferico diventa

$$B_\rho(x_0)=\{x\in\mathbb R^n:\ \|x-x_0\|<\rho\}$$

Le definizioni di punto di accumulazione e di punto isolato poggiano sull'intorno: la differenza fra $\mathbb R$ e $\mathbb R^n$ sta tutta nella distanza.