Duale problema cammino minimo

[anonymous_f3d38a]

Ciao a tutti! Ho un dubbio su una domanda che mi sembra a trabocchetto.

La domanda è la seguente:

"Si consideri un insieme di nodi $N$ ed un insieme di archi $A$.
Si consideri il problema $P$ del cammino di costo minimo da un nodo sorgente $s$ ad un nodo destinazione $t$ su
un grafo orientato $G = (N, A)$ , con $s, t in N$.

Si indichi sotto quali condizioni può essere definito il duale $D$ di $P$ e lo si formuli matematicamente."

Ebbene, io non so cosa intenda dire con "Sotto quali condizioni". Che io sappia, tale duale può essere definito sotto qualsiasi condizione!
Mi sbaglio forse???

----------------------------------------------------------------------------------------------------------

Il problema $P$ di cammino minimo è, considerando ogni arco $(i,j) in A$:

$P:$

$min sum_((i,j) in A) c_(ij)x_(ij) $

$ sum_((j,i) in A) x_(ji) - sum_((i,j) in A) x_(ij)= b= { ( -1 ...text(se i=s) ),( 1 ...text(se i=t) ),( 0 ...text(altrimenti) ):} $

$x_(ij)>=0 forall (i, j) in A$


Mentre il suo duale è:

$D:$

$max -lambda_s + lambda_t$

$-lambda_i + lambda_j <= c_(ij) forall (i,j) in A$

----------------------------------------------------------------------------------------------------------

Quali sono queste condizioni a cui si riferisce? Vi è qualcosa di cui sono all'oscuro?