Problema di programmazione lineare

• Soluzione ottima
• Punto di massimo globale
• Forma canonica

Problema di programmazione lineare

Dato un poliedro $F\subseteq {\mathbb{R}}^n$ e una funzione scalare lineare $f:F\to \mathbb{R}$, il problema di programmazione lineare (LP) associato è: $z(LP)=maxf(x):x\in F$ Il poliedro F è chiamato feasible region del problema LP. La funzione scalare lineare $f$ è chiamata funzione obiettivo del problema LP.

Per risolvere un problema LP si deve determinare il massimo globale $z(LP)$ della funzione obiettivo nella feasible region.

Soluzione ottima

Soluzione ottima

Massimo globale $z(LP)$ del problema LP.

Punto di massimo globale

Si può dover ricorrere al calcolo del punto di massimo globale $\tilde{x}(LP)=\max f(x):x\in F$ che è chiamato soluzione ottima del problema LP.

Forma canonica

$m\times n$ valori di $a_{ij}\in \mathbb{R}$ dove $i\in \{1,2,...,m\}$ e $j\in \{1,2,...,n\}$. $m$ valori di $b_i\in \mathbb{R}$ con $i\in \{1,2,...,m\}$

La feasible region di un problema LP in forma canonica è il poliedro $F$ definito come:

Questo poliedro è definito come l’intersezione di m semispazi anche definiti come “vincoli di disuguaglianza di minore-o-uguale”.