Teorema di Bellman

uni

Dato un albero di copertura $T$, che genera un flusso di base ($x_T$) ammissibile, se sono rispettate le Condizioni di Bellman allora siamo all’ottimo.

Condizioni di Bellman per Reti non Capacitate

Problema di Programmazione Matematica a Reti non Capacitate (PLRnC)

• $C_{ij}^{\pi }=0:(i,j)\in T$
  ovvero costi ridotti di archi di base $=0$
• $C_{ij}^{\pi }\ge 0:(i,j)\in L$
  ovvero costi ridotti di archi $\in L$ (non di base) $\ge 0$

Condizioni di Bellman per Reti Capacitate

Problema di Programmazione Matematica a Reti Capacitate (PLRC)

• $C_{ij}^{\pi }=0:(i,j)\in T$
  ovvero costi ridotti di archi di base $=0$
• $C_{ij}^{\pi }\ge 0:(i,j)\in L$
  ovvero costi ridotti di archi $\in L$ (non di base) $\ge 0$
• $C_{ij}^{\pi }\le 0:(i,j)\in U$
  ovvero costi ridotti di archi $\in U$ (non di base) $\le 0$

Costo Ridotto

Definito il costo ridotto relativo ad un arco:

$$C_{ij}^{\pi }=c_{ij}+{\pi }_i-{\pi }_j$$