09/12/2020, 12:57
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?