Duale di un problema LP in Forma Standard

Messaggioda ZombieBest » 23/01/2019, 09:45

Buongiorno, sto cercando di trovare il duale del problema LP in forma standard specificato sotto.
Ho però alcuni dubbi sulla soluzione proposta, e in generale non riesco ancora a trovare il duale di problemi in forma standard (quando sono presenti le sommatorie). Sono invece in grado di trovare il duale di un problema con un numero "piccolo" di variabili (senza sommatorie).

Problema - Duale di graph coloring:

Testo nascosto, fai click qui per vederlo
Sia G = (V, E) un grafo non orientato di n nodi, senza nodi isolati. Il problema della colorazione del grafo richiede di assegnare un colore (i.e., un’etichetta numerica) ad ogni nodo, in modo tale che gli estremi di ogni arco abbiano colore diverso, e che il numero complessivo di colori usati sia minimo possibile.
Un modello per questo problema utilizza variabili binarie $x_{vc}$ per ogni vertice v ∈ V e colore c ∈ {1,...,n} (si noti che non possono essere mai necessari più di n colori, per cui possiamo assumere che i colori usati saranno un sottoinsieme di {1,...,n}). Il senso della variabile $x{vc}$ è che essa è uguale a 1 se e solo se il nodo v è stato colorato con il colore c. Inoltre, per ogni colore c = 1, . . . , n, utilizziamo una variabile binaria $y_c$ che vale 1 se e solo se il colore c è usato da qualche nodo.
La funzione obiettivo e i vincoli del problema sono, rispettivamente:

$min \sum_{c=1}^n y_c$ s.t. (7)

$\sum_{c=1}^n x_{vc}=1 \forall v \in V$ (8)
$x_{vc} + x_{jc} \leq y_c \forall vj \in E, \forall c = 1..n$ (9)

I vincoli (8) impongono che ogni nodo abbia esattamente un colore. I vincoli (9) dicono fondamentalmente che se un colore non è usato (i.e., $y_c = 0$) allora nessun nodo può avere quel colore, mentre se un colore è usato (i.e., $y_c = 1$) allora per ogni arco del grafo al massimo uno dei due estremi può avere quel colore.
Sia P il problema di programmazione lineare definito da (7), (8) e (9) nelle variabili $x \geq 0$ e $y \geq 0$.
Scrivere il duale di P.


La soluzione fornita è la seguente:
Testo nascosto, fai click qui per vederlo
Introduciamo delle variabili duali $u_v$, per v ∈ V , associate ai vincoli (8), e $w_{ec}$, per e ∈ E e c = 1, . . . , n, associate ai vincoli (9). Le variabili $u$ sono libere, mentre le variabili $w$ sono non-negative.
La funzione obiettivo duale è:
$max \sum_{v\inV} u_v$ s.t
$\sum_{e\inE} w_{ec} \leq 1$ (corrispondenti alle variabili primali $y_c$), e
$u_v - \sum_{e\in\sigma(v)} w_{ec} \leq 0 \forall v\inV, c = 1..n$ (corrispondenti alle variabili primali $x_{vc}).


Io procederei nel seguente modo:

Testo nascosto, fai click qui per vederlo
  • Inverto le disequazioni nel primale in modo che siano tutte $\geq$ (essendo il primale un minimo)
  • Sposto tutte le variabili a sinistra delle disequazioni in modo da avere solo costanti a destra.
    Nel vincolo (9) del primale ottengo dunque: $-x_{vc}-x_{jc}+y_c\geq0$
  • Definisco delle variabili duali in base a quanti vincoli ho nel primale (in questo caso 2). La prima variabile sarà libera poiché il primo vincolo nel primale è un'uguaglianza, la seconda invece avrà vincolo $\geq0$.
    In questo passo non mi è esattamente chiaro come siano state scelte le due variabili, ci si è basati sul fatto che i vincoli abbiano $\forallv\inV$ e $\forallvj\inE$?
  • Nella funzione obiettivo del duale ho dunque $max 1 * \sum_{v\inV} u_v + 0 * \sum_{e\inE} \sum_{c\inC} w_{ec}$.
    Questo perché nel primale avevo assegnato al primo vincolo $u_v$ e al secondo vincolo $w_{ec}$.
  • Nei vincoli del duale, nella parte destra della disequazione, inserisco i valori della funzione obiettivo del primale. Dunque, in questo caso, nel primale avevo solo gli $y_c$, che ho associato al vincolo relativo alla variabile duale $u_v$. Perciò a destra della disequazione del primo vincolo duale ho 1.
    Similmente per i $w_{ec}$ non ho alcuna variabile presente nella funzione obiettivo del primale, perciò inserisco 0 nella parte destra della disequazione del secondo vincolo.
  • La parte sinistra dei vincoli del duale invece non mi è chiara. So che andrebbe presa la trasposta della matrice dei coefficienti (dunque andrebbero letti i vincoli "in verticale"), ma in questo caso non riesco a capire come questi vengano selezionati.
    Secondo la soluzione il primo vincolo dovrebbe essere $\sum_{e\inE} w_{ec} \leq 1$. Come mai si specifica $w_{ec}$? La variabile $-x_{vc}$ del secondo vincolo del primale non viene considerata? E $-x_{jc}$?
    Similmente per il secondo vincolo, $uv - \sum_{e\in\sigma(v)}w_{ec}\leq0$: il fatto che sia stata presa $u_v$ con segno positivo significa che ad $u_v$ è associata $y_c$, ma poi tra le due variabili $x_{vc}$ e $x_{jc}$ quale viene presa per $w_{ec}$?

Un'ultima domanda: a livello concettuale, il duale del problema proposto, quali soluzioni mi dovrebbe far trovare?
Grazie anticipatamente!
ZombieBest
Starting Member
Starting Member
 
Messaggio: 21 di 42
Iscritto il: 25/12/2016, 16:00

Torna a Analisi Numerica e Ricerca Operativa

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite