Leonid Vital'evič Kantorovič: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: numeri di pagina nei template citazione e modifiche minori |
m →Problema Duale del Trasporto: caso discreto: refuso nei segni della Lagrangiana |
||
Riga 137:
:<math>{\mathbf V} = (V_1,\ldots, V_n) </math>
la '''funzione Lagrangiana''' del problema del trasporto ottimale è la seguente
:<math>\mathcal{L}({\mathbf F}, {\mathbf U}, {\mathbf V}) = \sum_{i = 1}^m \sum_{j= 1}^n r_{i,j} \cdot \ F_{i,j}
dopo semplici passaggi algebrici si ottiene
:<math>\mathcal{L}({\mathbf F}, {\mathbf U}, {\mathbf V}) = [ \sum_{i = 1}^m \sum_{j= 1}^n F_{i,j} \cdot \ ( r_{i,j}
Il problema duale associato alla Lagrangiana è per definizione
: <math>\max_{U,V}\min_{F\ge 0}\mathcal{L}({\mathbf F}, {\mathbf U}, {\mathbf V})</math>
Al fine di ottenere una descrizione esplicita del problema duale si minimizza <math>\min_{F\ge 0}\mathcal{L}({\mathbf F}, {\mathbf U}, {\mathbf V})</math>
rispetto ad <math> F </math> tenendo fissi <math> {\mathbf U} </math> e <math> {\mathbf V} </math> e si ottiene così
: <math>\min_{F\ge 0}\mathcal{L}({\mathbf F}, {\mathbf U}, {\mathbf V}) = - \sum_{i=1}^m U_{i} \cdot a_{i} + \sum_{j=1}^n V_{j} \cdot b_{j} + \min_{F\ge 0} [ \sum_{i = 1}^m \sum_{j= 1}^n F_{i,j} \cdot \ ( r_{i,j}
pertanto risulta
: <math>\min_{F\ge 0}\mathcal{L}({\mathbf F}, {\mathbf U}, {\mathbf V}) =
\left\{
\begin{matrix}
- \sum_{i=1}^m U_{i} \cdot a_{i} + \sum_{j=1}^n V_{j} \cdot b_{j} & \mbox{ se } r_{i,j}
-\infty & \mbox{ se } r_{i,j}
\end{matrix}
\right.</math>
in conclusione si ottiene il seguente problema di massimizzazione vincolato
: <math>\max_{U,V} \{ \sum_{i=1}^m - U_{i} \cdot a_{i} + \sum_{j=1}^n V_{j} \cdot b_{j} \mbox{ tale che } r_{i,j}
Il '''problema duale del trasporto ottimale''' è il seguente problema di programmazione lineare avente funzione obiettivo in <math>n+m</math> incognite
| |||