Problema di Ottimizzazione

Data una funzione $f: \R^n \to \R$ e $X \subseteq R^n$ un Problema di Ottimizzazione (PO) può essere formulato come:

$min \space f(\underline{x}) \\ s.t. \\ \underline{x} \in X$

Quindi un Problema di Ottimizzazione consiste nel determinare, se esiste, un punto di minimo della funzione $f$ tra i punti dell’insieme $X$

Problemi di Programmazione Matematica

Quando l’insieme delle soluzioni ammissibili di un Problema di Ottimizzazione viene espresso attraverso un sistema di equazioni e disequazioni, tale problema prende il nome di problema di Programmazione Matematica (PM)

$min \space f(\underline{x}) \\ s.t. \\ g_i(\underline{x}) \geq b_i \space\space\space\space i = 1,..,m$

Problemi di Programmazione Lineare

Un problema di Programmazione Matematica è lineare quando:

• la funzione obiettivo è lineare: $f(\underline{x}) = \underline{c}^T \underline{x}$
• l’insieme $X$ è espresso in termini di relazioni (uguaglianze e disuguaglianze) lineari

N.B. $f(x)$ è lineare $\iff$

1. $f(\underline{x}+\underline{y}) = f(\underline{x}) + f(\underline{y})$
2. $f(\lambda \underline{x}) = \lambda f(\underline{x})$

Forma esplicita

$min \space f(\underline{x}) \\ s.t. \\ c_1x_1 +..+c_nx_n \\ a_{11}x_1 +..+a_{1n}x_n \geq b_1 \\ .. \\ a_{m1}x_1 +..+a_{mn}x_n \geq b_m$

Forma compatta

$min \space f(\underline{x}) \\ s.t. \\ \underline{c}^T \underline{x} \\ A\underline{x} \geq \underline{b}$

• $\underline{x}$ è il vettore $n\times 1$ delle variabili decisionali
• $\underline{c}$ è il vettore $n \times 1$ dei coefficienti di costo della funzione obiettivo